Yesterday I achieved a 500x performance boost after rewriting an
IN. I did some investigation to find out why and finally came to the following example. Basically, we draw 5 lucky numbers out of 0 - 999, and count how many lucky numbers are drawn.
CREATE TABLE IF NOT EXISTS natural_numbers AS WITH RECURSIVE natural_numbers(x) AS ( SELECT 0 UNION SELECT x + 1 FROM natural_numbers LIMIT 1000 ) SELECT x FROM natural_numbers; .eqp ON .timer ON WITH lucky_numbers(lucky_number) AS ( SELECT x FROM natural_numbers ORDER BY RANDOM() LIMIT 5 ) SELECT SUM(EXISTS( SELECT 1 FROM lucky_numbers WHERE x = lucky_number )) FROM natural_numbers; WITH lucky_numbers(lucky_number) AS ( SELECT x FROM natural_numbers ORDER BY RANDOM() LIMIT 5 ) SELECT SUM(x IN lucky_numbers) FROM natural_numbers;
The output is
QUERY PLAN |--SCAN TABLE natural_numbers `--CORRELATED SCALAR SUBQUERY 2 |--CO-ROUTINE 1 | |--SCAN TABLE natural_numbers | `--USE TEMP B-TREE FOR ORDER BY `--SCAN SUBQUERY 1 4 Run Time: real 0.095 user 0.094819 sys 0.000000 QUERY PLAN |--SCAN TABLE natural_numbers `--LIST SUBQUERY 2 |--SCAN TABLE natural_numbers `--USE TEMP B-TREE FOR ORDER BY 5 Run Time: real 0.001 user 0.000289 sys 0.000007
It seems that
EXISTS re-executes the common table expression
lucky_numbers for each
x (and is consequently much slower), whereas
IN only executes it once for the whole table (the result is always 5, no more, no less). This is kind of surprising because common table expressions are supposed to be a view instead of a temporary table, so I would expect the behavior of
To complicate things further, if you replace
LIMIT 5 with
LIMIT X where
X >= 8 in the
EXISTS clause, its execution plan would become
QUERY PLAN |--SCAN TABLE natural_numbers `--CORRELATED SCALAR SUBQUERY 2 |--CO-ROUTINE 1 | |--SCAN TABLE natural_numbers | `--USE TEMP B-TREE FOR ORDER BY `--SEARCH SUBQUERY 1 USING AUTOMATIC COVERING INDEX (lucky_number=?)
and the result will always be
X instead of a random variable for
X <= 7. I suspect this is because the common table expression
lucky_numbers is no longer re-run for each row, but instead cached in the
AUTOMATIC COVERING INDEX. In other words, the query planner is changing the result of our query here!
So, when are common table expressions run for each row / the whole table? Looks like with
IN it's guaranteed to run only once for the whole table (which is somehow inconsistent with the document's words that an ordinary common table expression is essentially a pre-packaged SELECT statement), but with
EXISTS things are more complicated and the decision is left to the query planner.