Começarei definindo o relacionamento de Muitos para Muitos MySQL (Experts podem pular para o próximo parágrafo).

O que é um relacionamento de Muitos para Muitos MySQL

Um relacionamento de Muitos para Muitos MySQL é um relacionamento que é multi-valorizado em ambas as direções.

Esse tipo de relacionamento é auxiliado pelo uso de uma tabela de ligação. Por exemplo, uma Pergunta (Question) pode ter mais de uma Categoria (Categorie), e uma Categoria pode ter mais de uma Pergunta. 

CREATE TABLE link (
   Question_id int unsigned NOT NULL,
   Category varchar(20),
   PRIMARY KEY  (`Question_id `,` Category`),
   KEY `category_question` (`Category`,`Question_id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1
 
+-------------+---------------+
| Question_id | Category      |
+-------------+---------------+
|  1          | Animals       |
|  1          | Business      |
|  1          | Vehicles      |
|  2          | Animals       |
|  3          | Business      |
|  3          | Vehicles      |
|  4          | Animals       |
|  4          | Vehicles      |
|  5          | Business      |
+-------------+---------------+

Essa é uma tabela de ligação chamada link, que nos ajuda a juntar relacionamentos entre as duas tabelas, Perguntas e Categorias.

Como podemos ver, essa tabela está refletindo um relacionamento de muitos para muitos (a pergunta 1 tem as categorias Animais, Negócios e Veículos – ‘Animals,  Business and Vehicles’. A categoria Animais tem as perguntas 1, 2 e 4).

O que é o problema de relação de exclusão?

Dada uma tabela de relacionamento de muitos para muitos, como você é capaz de selecionar linhas que não tenham um relacionamento específico? Em termos do exemplo pergunta-categoria, essa pergunta é traduzida no seguinte:

Como você consegue selecionar (digamos as primeiras mil) perguntas que não têm a categoria Negócios. No nosso exemplo, queremos somente que os Question_id 2 e 4 sejam retornados.

Uma solução ruim

Uma solução ruim seria:

 SELECT
    DISTINCT Question_id
FROM
    link
WHERE
    Category <> "Business"
ORDER BY
    Question_id DESC
LIMIT
    1000;

Essa consulta irá funcionar se uma pergunta somente for permitida uma categoria. No nosso caso, como uma pergunta tem pelo menos uma categoria, desde que uma pergunta esteja associada à outra categoria que não seja Business, ela retornará. Portanto, o resultado dessa consulta é Question_id: 1, 2, 3, e 4 , que não satisfaz a relação de exclusão.

Primeira solução

SELECT
    DISTINCT Question_id
FROM
    link
WHERE
    Question_id NOT IN (SELECT Question_id FROM link WHERE Category="Business")  
ORDER BY
    Question_id DESC
LIMIT
    1000;

A consulta dependente interna (SELECT Question_id FROM link WHERE Category<>”Business”) tem um problema de desempenho – ela será executada pela menos mil vezes e, se ela não for rápida, os atrasos são multiplicados por um número que é, no mínimo, 1.000. Quando o método de acesso (o type field no EXPLAIN statement output) é index_subquery, um index de pesquisa de otimização é usado e um monte de sobrecarga é evitada.

Quando é ampla, a sub query está sendo reexecutada, como é feita para cada linha. Você deve verificar seus . You must check your EXPLAIN details.

Segunda solução

CREATE TEMPORARY TABLE not_wanted_Question_id (
     UNIQUE KEY(Question_id)
) ENGINE=MEMORY
SELECT
    DISTINCT Question_id
FROM
    link
WHERE
    Category="Business";
 
SELECT
    DISTINCT link.Question_id
FROM
    link
LEFT JOIN
    not_wanted_Question_id nw ON (link.Question_id = nw.Question_id)
WHERE
    nw.Question_id is NULL
ORDER BY
    link.Question_id DESC
LIMIT
    1000;
 
DROP TABLE not_wanted_Question_id;

O problema de execução de consultas internas múltiplas é reduzido a uma pesquisa uma única chave dentro de uma tabela na memória, que é basicamente uma pesquisa hash e é muito rápida. No entanto, a construção de perguntas indesejadas pode sair caro para tabelas grandes. Note que criar a tabela, selecionar e então soltar devem ser todos feitos juntos, para toda vez que você precisar dos resultados.

Terceira solução (a melhor em desempenho)

Esta é minha melhor solução para esse problema e com melhor desempenho para tabelas pesadas:

SELECT
     Question_id ,
     SUM(IF (Category="Business", 1, 0)) AS exclude
FROM
     link
GROUP BY
     Question_id DESC
HAVING
     exclude=0
LIMIT
     10000;

Isso funciona muito bem no nosso caso, porque temos um index no Question_id e colunas de categorias. A função SUM está contando o número de ocorrências indesejadas de categoria para cada Question_id na ordem e o statement Having está filtrando-os.

O LIMIT termina os cálculos assim que chega no número limite.

Texto original em ingles de Hazan Ilan, disponível em http://www.mysqldiary.com/a-many-to-many-relationship-table-solving-the-exclude-relation-problem/