optimization - 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

score 4 · Accepted Answer

您的第一个查询首先通过将所有记录插入到已排序的临时表中来对记录进行排序，然后DISTINCT通过遍历它们并仅返回与前一个不同的记录来实现。（这可以在EXPLAIN下面显示的输出中看到；DISTINCT实际上已转换为 a GROUP BY，其行为相同。）

理论上，您的第二个查询与第一个查询相同，但 SQLite 的查询优化器相当简单，无法证明这种转换是安全的（如子查询展平文档中所述）。因此，它是通过执行第一个操作来实现的DISTINCT，即仅将任何非重复项插入到临时表中，然后ORDER BY使用第二个临时表执行操作。这第二步完全是多余的，因为第一个临时表已经排序，但是无论如何这对您的数据来说更快，因为您有太多的重复项从未存储在任何一个临时表中。

理论上，您的第一个查询可能会更快，因为 SQLite 已经认识到DISTINCTandORDER BY子句可以使用相同的排序临时表实现。然而，在实践中，SQLite 不够聪明地记住这DISTINCT意味着不需要将重复项存储在临时表中。（如果你在邮件列表中很好地询问，这个特殊的优化可能会被添加到 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

score 1 · Accepted Answer

在大多数 DBMS 中，SQL 语句被翻译成关系代数，然后在表达式树中结构化。然后 dbms 使用启发式方法来优化查询。主要启发式方法之一是“尽早执行选择”（第 46 页）。我想 sqlite 查询计划器也会这样做，因此执行时间会有所不同。

由于子查询的结果要小得多（约 50 行而不是 450 万行），因此在表达式树的末尾进行排序要快得多。（普通）选择不是一个非常昂贵的过程，对大量结果运行操作确实是。

score 0 · Accepted Answer

我相信这一定是因为当被子选择分开时，顺序操作和不同的操作必须更有效地实现——这实际上是一种更简单的方式来表达 alexdeloy 所说的方式。

这个实验是不完整的。请同时运行以下命令：

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

告诉我这是否比其他两个平均花费更长的时间，谢谢。

optimization - Sqlite 子选择比 distinct + order by 快得多

3 回答 3

Related

Reference