Sottoselezione Sqlite molto più veloce del distinto + ordine di

Question

Sono confuso dai tempi di esecuzione drasticamente diversi delle seguenti due query che producono output identico. Le query sono in esecuzione su Sqlite 3.7.9, su un tavolo con circa 4,5 milioni di righe e ciascuna produce ~ 50 righe di risultati.

Ecco le domande:

% echo "SELECT DISTINCT acolumn FROM atable ORDER BY acolumn;" | time sqlite3 mydb 
sqlite3 mydb 8.87s user 15.06s system 99% cpu 23.980 total 


% echo "SELECT acolumn FROM (SELECT DISTINCT acolumn FROM atable) ORDER BY acolumn;" | time sqlite3 options 
sqlite3 mydb 1.15s user 0.10s system 98% cpu 1.267 total 

Non dovrebbe la performance delle due interrogazioni essere più vicini? Capisco che potrebbe accadere che il pianificatore delle query esegua le operazioni "ordinamento" e "distinto" in ordini diversi, ma in tal caso, è necessario? O dovrebbe essere in grado di capire come farlo più veloce?

Modifica: come richiesto qui è l'output del comando "PIANO DI QUANTITÀ EXPLAIN" per ogni query.

Per la prima (monolitico) query:

0|0|0|SCAN TABLE atable (~1000000 rows) 
0|0|0|USE TEMP B-TREE FOR DISTINCT 

Per il secondo (subquery) query:

1|0|0|SCAN TABLE atable (~1000000 rows) 
1|0|0|USE TEMP B-TREE FOR DISTINCT 
0|0|0|SCAN SUBQUERY 1 (~1000000 rows) 
0|0|0|USE TEMP B-TREE FOR ORDER BY 

Answer 1

vostra prima query ordina i record prima inserendo tutte di loro in una tabella temporanea ordinato, e quindi implementa la DISTINCT passando attraverso di loro e restituendo solo quelli che non sono identici alla precedente. (Questo può essere visto nella EXPLAIN output mostrato sotto, il DISTINCT effettivamente preso convertito GROUP BY, che si comporta lo stesso.)

La seconda domanda è, in teoria, identica alla prima, ma Query Optimizer di SQLite è piuttosto semplice e non può dimostrare che questa conversione sia sicura (come spiegato nello subquery flattening documentation). Pertanto, viene implementato eseguendo prima lo DISTINCT, inserendo solo eventuali non duplicati in una tabella temporanea e quindi eseguendo ORDER BY con una seconda tabella temporanea. Questo secondo passaggio è completamente superfluo perché la prima tabella temporanea era già stata ordinata, ma ciò risulta essere più veloce per i dati comunque perché si dispone di così tanti duplicati che non vengono mai memorizzati in nessuna tabella temporanea.

In teoria, la vostra prima query potrebbe essere più veloce, perché SQLite ha già riconosciuto che le DISTINCT e ORDER BY clausole possono essere attuate con la stessa ordinato tabella temporanea. In pratica, tuttavia, SQLite non è abbastanza intelligente da ricordare che lo DISTINCT implica che i duplicati non debbano essere memorizzati nella tabella temporanea. (Questo particolare ottimizzazione potrebbe essere aggiunto a SQLite se chiedete bene sul mailing list.)

---

$ sqlite3 mydb 
sqlite> .explain 
sqlite> explain SELECT DISTINCT acolumn FROM atable ORDER BY acolumn; 
addr opcode   p1 p2 p3 p4    p5 comment  
---- ------------- ---- ---- ---- ------------- -- ------------- 
0  Trace   0  0  0     00    
1  SorterOpen  1  2  0  keyinfo(1,BINARY) 00    
2  Integer  0  3  0     00 clear abort flag 
3  Integer  0  2  0     00 indicate accumulator empty 
4  Null   0  6  6     00    
5  Gosub   5  37 0     00    
6  Goto   0  40 0     00    
7  OpenRead  0  2  0  1    00 atable  
8  Rewind   0  14 0     00    
9  Column   0  0  8     00 atable.acolumn 
10 Sequence  1  9  0     00    
11 MakeRecord  8  2  10     00    
12 SorterInsert 1  10 0     00    
13 Next   0  9  0     01    
14 Close   0  0  0     00    
15 OpenPseudo  2  10 2     00    
16 SorterSort  1  39 0     00 GROUP BY sort 
17 SorterData  1  10 0     00    
18 Column   2  0  7     20    
19 Compare  6  7  1  keyinfo(1,BINARY) 00    
20 Jump   21 25 21     00    
21 Move   7  6  0     00    
22 Gosub   4  32 0     00 output one row 
23 IfPos   3  39 0     00 check abort flag 
24 Gosub   5  37 0     00 reset accumulator 
25 Column   2  0  1     00    
26 Integer  1  2  0     00 indicate data in accumulator 
27 SorterNext  1  17 0     00    
28 Gosub   4  32 0     00 output final row 
29 Goto   0  39 0     00    
30 Integer  1  3  0     00 set abort flag 
31 Return   4  0  0     00    
32 IfPos   2  34 0     00 Groupby result generator entry point 
33 Return   4  0  0     00    
34 Copy   1  11 0     00    
35 ResultRow  11 1  0     00    
36 Return   4  0  0     00 end groupby result generator 
37 Null   0  1  0     00    
38 Return   5  0  0     00    
39 Halt   0  0  0     00    
40 Transaction 0  0  0     00    
41 VerifyCookie 0  2  0     00    
42 TableLock  0  2  0  atable   00    
43 Goto   0  7  0     00    

sqlite> explain SELECT acolumn FROM (SELECT DISTINCT acolumn FROM atable) ORDER BY acolumn; 
addr opcode   p1 p2 p3 p4    p5 comment  
---- ------------- ---- ---- ---- ------------- -- ------------- 
0  Trace   0  0  0     00    
1  Goto   0  39 0     00    
2  Goto   0  17 0     00    
3  OpenPseudo  0  3  1     01 coroutine for sqlite_subquery_DA7480_ 
4  Integer  0  2  0     01    
5  OpenEphemeral 2  0  0  keyinfo(1,BINARY) 08    
6  OpenRead  1  2  0  1    00 atable  
7  Rewind   1  14 0     00    
8  Column   1  0  3     00 atable.acolumn 
9  Found   2  13 3  1    00    
10 MakeRecord  3  1  4     00    
11 IdxInsert  2  4  0     00    
12 Yield   1  0  0     00    
13 Next   1  8  0     01    
14 Close   1  0  0     00    
15 Integer  1  2  0     00    
16 Yield   1  0  0     00 end sqlite_subquery_DA7480_ 
17 SorterOpen  3  3  0  keyinfo(1,BINARY) 00    
18 Integer  2  1  0     00    
19 Yield   1  0  0     00 next row of co-routine sqlite_subquery_DA7480_ 
20 If    2  29 0     00    
21 Column   0  0  5     00 sqlite_subquery_DA7480_.acolumn 
22 MakeRecord  5  1  6     00    
23 Column   0  0  7     00 sqlite_subquery_DA7480_.acolumn 
24 Sequence  3  8  0     00    
25 Move   6  9  0     00    
26 MakeRecord  7  3  10     00    
27 SorterInsert 3  10 0     00    
28 Goto   0  19 0     00    
29 OpenPseudo  4  6  1     00    
30 OpenPseudo  5  11 3     00    
31 SorterSort  3  37 0     00    
32 SorterData  3  11 0     00    
33 Column   5  2  6     20    
34 Column   4  0  5     20    
35 ResultRow  5  1  0     00    
36 SorterNext  3  32 0     00    
37 Close   4  0  0     00    
38 Halt   0  0  0     00    
39 Transaction 0  0  0     00    
40 VerifyCookie 0  2  0     00    
41 TableLock  0  2  0  atable   00    
42 Goto   0  2  0     00    

Answer 2

All'interno maggior DBMS, istruzioni SQL sono convertiti in relational algebra e poi strutturato in un'espressione albero. Il dbms utilizza quindi l'euristica per ottimizzare le query. Una delle principali euristiche è "Perform selection early" (p.46). Suppongo che il pianificatore di query sqlite faccia altrettanto, quindi le differenze nei tempi di esecuzione.

Poiché il risultato della sottoquery è molto più piccolo (~ 50 righe opposte a 4,5 milioni), l'ordinamento, alla fine dell'albero delle espressioni, avviene molto più velocemente. (Semplice) La selezione non è un processo molto costoso, le operazioni in esecuzione su una moltitudine di risultati sono davvero.

Answer 3

Credo che ciò sia dovuto al fatto che l'operazione di ordine e le operazioni distinte devono essere implementate in modo più efficiente se separate dalla sottoselezione - che è in effetti un modo più semplice per dire come dice alexdeloy.

Questo esperimento non è completo. Eseguire anche il seguente:

% echo "SELECT acolumn FROM (SELECT DISTINCT acolumn FROM atable ORDER BY acolumn) ;" | time sqlite3 mydb 

Dimmi se questo richiede più tempo rispetto agli altri due, in media, e grazie.