Почему EXISTS такой медленный по сравнению с IN с агрегацией? - PullRequest
Новая
       51

Почему EXISTS такой медленный по сравнению с IN с агрегацией?

0 голосов
/ 05 августа 2020

Предположим, у нас есть таблица эффективности кандидатов 

CREATE TABLE IF NOT EXISTS candidates AS
WITH RECURSIVE candidates(team, score) AS (
    SELECT RANDOM() % 1000, RANDOM() % 1000000
    UNION
    SELECT RANDOM() % 1000, RANDOM() % 1000000
    FROM candidates
    LIMIT 1000000
)
SELECT team, score
FROM candidates;

Наша цель - вывести список из 1000 команд и общий балл кандидатов в этой команде. Однако, если общий счет команды не в первом тайме, он будет заменен на ноль. Я придумал два способа сделать это:

  1. С EXISTS потребовалось Run Time: real 30.653 user 30.635649 sys 0.008798
WITH top_teams_verbose(top_team, total_score) AS (
    SELECT team, SUM(score)
    FROM candidates
    GROUP BY team
    ORDER BY 2 DESC
    LIMIT 500
)
SELECT team, SUM(score) * EXISTS(SELECT 1 FROM top_teams_verbose WHERE team = top_team)
FROM candidates
GROUP BY team;

план запроса 

QUERY PLAN
|--SCAN TABLE candidates
|--USE TEMP B-TREE FOR GROUP BY
`--CORRELATED SCALAR SUBQUERY 2
   |--CO-ROUTINE 1
   |  |--SCAN TABLE candidates
   |  |--USE TEMP B-TREE FOR GROUP BY
   |  `--USE TEMP B-TREE FOR ORDER BY
   `--SCAN SUBQUERY 1
С IN потребовалось Run Time: real 0.045 user 0.041872 sys 0.002999 
WITH top_teams_verbose(top_team, total_score) AS (
    SELECT team, SUM(score)
    FROM candidates
    GROUP BY team
    ORDER BY 2 DESC
    LIMIT 500
),
top_teams AS (
    SELECT top_team
    FROM top_teams_verbose
)
SELECT team, SUM(score) * (team IN top_teams)
FROM candidates
GROUP BY team;

План запроса 

QUERY PLAN
|--SCAN TABLE candidates
|--USE TEMP B-TREE FOR GROUP BY
`--LIST SUBQUERY 3
   |--CO-ROUTINE 1
   |  |--SCAN TABLE candidates
   |  |--USE TEMP B-TREE FOR GROUP BY
   |  `--USE TEMP B-TREE FOR ORDER BY
   `--SCAN SUBQUERY 1

Почему? Может быть, EXISTS выполняется для каждой строки, а IN используется как агрегатная функция? Я взглянул на план запроса, и единственная разница (CORRELATED SCALAR SUBQUERY против LIST SUBQUERY) слишком абстрактна, чтобы быть информативной.

Я использую версию SQLite3 3.31.1 2020-01-27 19:55:54 3bfa9cc97da10598521b342961df8f5f68c7388fa117345eeb516eaa837bb4d6 На RHEL 7.

1 Ответ

0 голосов
/ 05 августа 2020

У меня нет времени на углубленный анализ плана запроса, но оказывается, что EXISTS вызывает повторное выполнение общего табличного выражения для каждой строки. Согласно Википедии, это называется коррелированный запрос :

В запросе к базе данных SQL коррелированный подзапрос (также известный как синхронизированный подзапрос) является подзапросом ( запрос, вложенный в другой запрос), который использует значения из внешнего запроса. Поскольку подзапрос может оцениваться один раз для каждой строки, обрабатываемой внешним запросом, он может быть медленным.

Конкретно рассмотрим следующий пример, который случайным образом выбирает 5 "счастливых команд" из 10 

DROP TABLE IF EXISTS candidates;


CREATE TABLE candidates AS
WITH RECURSIVE candidates(team, score) AS (
    SELECT ABS(RANDOM()) % 10, 1
    UNION
    SELECT ABS(RANDOM()) % 10, score + 1
    FROM candidates
    LIMIT 100
)
SELECT team, score
FROM candidates;


WITH lucky_teams(lucky_team, total_score) AS (
    SELECT team, SUM(score)
    FROM candidates
    GROUP BY team
    ORDER BY RANDOM()
    LIMIT 5
)
SELECT team, SUM(score) * EXISTS(
    SELECT 1
    FROM lucky_teams
    WHERE team = lucky_team
)
FROM candidates
GROUP BY team
ORDER BY team;

Можно было бы ожидать, что всегда будет 5 команд с положительными оценками, а остальные с нулевым счетом, но время от времени вы будете получать 4 или 7 положительных оценок. Это потому, что каждая команда имеет независимых 50% шанс появиться в таблице lucky_teams, что предотвращает обнуление их очков. 

$ sqlite3 < quirky.sql
0|0
1|752
2|285
3|620
4|223
5|0
6|0
7|423
8|1035
9|370
...