Sqlite的子查詢速度遠快於distinct + order by

Question

我對以下兩個查詢產生相同輸出的截然不同的運行時間感到困惑。查詢在Sqlite 3.7.9上運行，在一個約450萬行的表上，每個查詢產生大約50行結果。

這裏有疑問：

% 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 

應該不是兩個查詢的性能更接近？我知道查詢計劃員可能會以不同的順序執行「排序」和「不同」操作，但如果是這樣，它是否需要？還是應該能夠弄清楚如何做到最快？

編輯：按照要求，這裏是每個查詢的「EXPLAIN QUERY PLAN」命令的輸出。

對於第（單片）的查詢：

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

對於第二（子查詢）的查詢：

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

你的第一個查詢訂單記錄首次通過插入所有的人都到一個排序的臨時表，然後通過他們去和返回只有那些不等同於前一個實現DISTINCT。 （這可以在如下所示的EXPLAIN輸出中看到;所述DISTINCT實際上得到轉化爲GROUP BY，其行爲是相同的。）

你的第二查詢是，在理論上，相同於第一，但SQLite的的查詢優化是相當簡單，並不能證明這種轉換是安全的（如subquery flattening documentation中所述）。 因此，通過首先執行DISTINCT來實現它，方法是隻將任何非重複項插入到臨時表中，然後使用第二個臨時表執行ORDER BY。 這第二步完全是多餘的，因爲第一個臨時表已經排序，但無論如何，這對您的數據來說會更快，因爲您有太多的副本永遠不會存儲在臨時表中。

從理論上講，你的第一個查詢可能會更快，因爲SQLite的已經認識到，DISTINCT和ORDER BY條款可與相同實施分類臨時表。 然而，在實踐中，SQLite並不足夠記住DISTINCT意味着重複項不需要存儲在臨時表中。 （這種特殊的優化可能會增加，如果你在mailing list很好問到的SQLite。）

---

$ 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

裏面最DBMS，SQL語句被轉換爲relational algebra，然後在表達結構化樹。 dbms然後使用啓發式來優化查詢。其中一個主要啓發是「Perform selection early」（第46頁）。我想sqlite查詢計劃者也這樣做，因此執行時間的差異。

由於子查詢的結果小得多（~50行與450萬行相反），因此在表達式樹的末尾進行排序的速度要快得多。 （普通）選擇不是一個非常昂貴的過程，確實會對多個結果運行操作。

Answer 3

我相信這一定是因爲訂單操作和獨特的操作必須在被子選擇分離時更有效地實現 - 這實際上是一種更簡單的方式，這正是alexdeloy所說的方式。

本實驗未完成。請同時運行以下命令：

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

告訴我這是否需要比其他兩個平均時間更長，謝謝。