SQL: Quando si tratta di NON IN e NON UGUALI, che è più efficiente e perché?

Question

Diciamo che ho una serie di elementi:

• Item1
• Item2
• Item3
• Item4
• item5

Una query può essere costruito in due modi. In primo luogo:

SELECT * 
FROM TABLE 
WHERE ITEM NOT IN ('item1', 'item2', 'item3', 'item4','item5') 

Oppure, può essere scritto come:

SELECT * 
FROM TABLE 
WHERE ITEM != 'item1' 
    AND ITEM != 'item2' 
    AND ITEM != 'item3' 
    AND ITEM != 'item4' 
    AND ITEM != 'item5' 

1. che è più efficiente e perché?
2. A che punto si diventa più efficienti rispetto agli altri? In altre parole, cosa succede se ci fossero 500 articoli?

La mia domanda riguarda specificamente PostgreSQL.

Answer 1

In PostgreSQL c'è di solito una differenza abbastanza piccola a lunghezze di lista ragionevoli, anche se IN è molto più pulito concettualmente. Gli elenchi molto lunghi AND ... <> ... e gli elenchi molto lunghi NOT IN eseguono entrambi in modo terribile, con AND molto peggio di NOT IN.

In entrambi i casi, se sono abbastanza lunghi da farvi persino porre la domanda, dovreste fare un test di esclusione anti-join o subquery su una lista valori.

WITH excluded(item) AS (
    VALUES('item1'), ('item2'), ('item3'), ('item4'),('item5') 
) 
SELECT * 
FROM thetable t 
WHERE NOT EXISTS(SELECT 1 FROM excluded e WHERE t.item = e.item); 

o:

WITH excluded(item) AS (
    VALUES('item1'), ('item2'), ('item3'), ('item4'),('item5') 
) 
SELECT * 
FROM thetable t 
LEFT OUTER JOIN excluded e ON (t.item = e.item) 
WHERE e.item IS NULL; 

(On moderne versioni Pg sia produrrà lo stesso piano di query in ogni caso).

Se l'elenco valori è sufficientemente lungo (molte decine di migliaia di elementi), l'analisi può iniziare a richiedere un costo significativo. A questo punto dovresti prendere in considerazione la creazione di una tabella , COPY i dati da escludere in essa, possibilmente creando un indice su di essa, quindi utilizzare uno degli approcci precedenti sulla tabella temporanea invece del CTE.

Demo:

CREATE UNLOGGED TABLE exclude_test(id integer primary key); 
INSERT INTO exclude_test(id) SELECT generate_series(1,50000); 
CREATE TABLE exclude AS SELECT x AS item FROM generate_series(1,40000,4) x; 

dove exclude è la lista di valori da omettere.

ho confronta i seguenti approcci sugli stessi dati con tutti i risultati in millisecondi:

• NOT IN lista: 3424,596
• AND ... lista: 80173,823
• VALUES basato JOIN esclusione: 20.727
• VALUES basato subquery esclusione: 20,495
• basato su tabella JOIN, nessun indice su ex-list: tavolo 25,183
• sottoquery basato, nessun indice su ex-list: 23,985

... rendendo l'approccio basato su CTE oltre tremila volte più veloce rispetto all'elenco AND e 130 volte più veloce rispetto all'elenco NOT IN.

Codice: https://gist.github.com/ringerc/5755247 (proteggiti gli occhi, voi che seguite questo link).

Per questa serie di dati, l'aggiunta di un indice nell'elenco di esclusioni non ha fatto alcuna differenza.

Note:

• IN lista generata con SELECT 'IN (' || string_agg(item::text, ',' ORDER BY item) || ')' from exclude;
• AND lista generata con SELECT string_agg(item::text, ' AND item <> ') from exclude;)
• sottoquery e unisciti ad esclusione tabella basata erano più o meno lo stesso attraverso i funzionamenti ripetuti.
• Esame del piano mostra che si traduce Pg NOT IN al <> ALL

Quindi ... si può vedere che non c'è un vero e enorme divario tra i due IN e AND liste vs facendo una corretta join. Ciò che mi ha sorpreso è stata la rapidità con cui un CTE utilizzava un elenco VALUES ... l'analisi dell'elenco VALUES non prendeva quasi più tempo, eseguendo lo stesso o leggermente più veloce di l'approccio tabella nella maggior parte dei test.

Sarebbe bello se PostgreSQL in grado di riconoscere automaticamente un assurdamente lungo IN clausola o la catena di simili AND condizioni e passare a un approccio più intelligente come fare un hash join o implicitamente trasformandolo in un nodo di CTE. In questo momento non sa come farlo.

Consulta anche:

• this handy blog post Magnus Hagander wrote on the topic

Answer 2

Non sono d'accordo un po 'con la risposta accettata originale di @Jayram.

Non ultimo, il collegamento è per SQL Server e contraddice molti altri articoli e risposte. Inoltre, non ci sono indici sulla tabella di esempio.

Normalmente, per subquery SQL costruisce

• <> (o !=) è un scalare comparatore
• NOT IN è un sinistra anti-semi-join operatore relazionale

In termini più semplici

• NOT IN diventa una forma di join che può utilizzare un indice
• != è spesso non SARGable e un indice non può essere utilizzato

Questo è stato discusso in dba.se (eccetto PostgreSQL!): "The use of NOT logic in relation to indexes" . Per PostgreSQL, quindi questo explainextended article spiega più interno (ma non per un elenco di costanti con NOT IN sfortunatamente).

In entrambi i casi, per un elenco di costanti, utilizzare NOT IN prima del <> in genere perché è più facile da leggere e grazie a ciò che @CraigRinger ha spiegato.

Per una sottoquery, NOT EXISTS è la strada da percorrere