Sqlite subselect намного быстрее, чем отдельный + порядок

Меня смущает резко отличающееся время работы следующих двух запросов, которые производят идентичный вывод. Запросы выполняются на Sqlite 3.7.9, на столе с примерно 4,5 миллионами строк, и каждый из них производит ~ 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

Ответ 1

Первый запрос заказывает записи сначала, вставив их все в отсортированную временную таблицу, а затем реализует DISTINCT, пройдя через них и возвращая только те, которые не идентичны предыдущему. (Это видно на выходе EXPLAIN, показанном ниже, DISTINCT фактически преобразован в GROUP BY, который ведет себя одинаково.)

Второй запрос теоретически идентичен первому, но оптимизатор запросов SQLite довольно прост и не может доказать, что это преобразование было бы безопасным (как описано в ). Поэтому он реализуется с помощью DISTINCT во-первых, вставляя только любые не дубликаты во временную таблицу, а затем делая ORDER BY со второй временной таблицей. Этот второй шаг совершенно лишний, потому что первая временная таблица уже была отсортирована, но в любом случае это будет быстрее для ваших данных, потому что у вас так много дубликатов, которые никогда не сохраняются ни в таблице temp.

Теоретически ваш первый запрос может быть быстрее, поскольку SQLite уже признал, что предложения DISTINCT и ORDER BY могут быть реализованы с помощью той же отсортированной временной таблицы. На практике, однако, SQLite недостаточно умен, чтобы помнить, что DISTINCT подразумевает, что дубликаты не должны храниться в таблице temp. (Эта конкретная оптимизация может быть добавлена в 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

Ответ 2

Внутри большинства СУБД операторы SQL переводятся в реляционную алгебру и затем структурируются в дереве выражений. Затем dbms использует эвристику для оптимизации запросов. Одной из основных эвристик является "" Выполнить предварительный отбор" (стр .46). Я полагаю, что планировщик запросов sqlite делает это также, следовательно, различия во времени выполнения.

Так как результат подзапроса намного меньше (~ 50 строк против 4,5 миллиона), сортировка в конце дерева выражений происходит намного быстрее. (Plain) Выбор не очень дорогой процесс, на самом деле выполняются операции с множеством результатов.

Ответ 3

Я считаю, что это должно быть потому, что операция заказа и различные операции должны быть реализованы более эффективно, если они разделены подзапросом, - это, по сути, более простой способ сказать, как говорит alexdeloy.

Этот эксперимент не завершен. Также выполните следующие действия:

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

Скажите, если это займет больше времени, чем два других в среднем и спасибо.