1

In SQLite's query planners is it generally faster to do this kind of thing?

SELECT foo.bar,foo.baz 
FROM foo 
WHERE NOT EXISTS (SELECT lol.haha FROM lol WHERE lol.haha = foo.haha)

... or ...

SELECT foo.bar,foo.baz 
FROM foo 
WHERE haha NOT IN (SELECT haha FROM lol)

They are functionally equivalent but I'm wondering whether the query planner handles them differently. I know in larger databases like PostgreSQL there are IN / NOT IN optimizations that make the latter as fast or faster than the former.

1
  • NOT IN/ NOT EXISTS are functionally equivalent only if there are no NULLs involved.
    – dnoeth
    Commented Jan 8, 2019 at 10:57

1 Answer 1

2

Let's assume that lol.haha is declared as NOT NULL, so that both queries give the same result.

When there is no index on lol.haha, the EXPLAIN QUERY PLAN outputs look similar:

> SELECT foo.bar,foo.baz FROM foo WHERE NOT EXISTS (SELECT lol.haha FROM lol WHERE lol.haha = foo.haha);
QUERY PLAN
|--SCAN TABLE foo
`--CORRELATED SCALAR SUBQUERY
   `--SCAN TABLE lol
> SELECT foo.bar,foo.baz FROM foo WHERE haha NOT IN (SELECT haha FROM lol);
QUERY PLAN
|--SCAN TABLE foo
`--LIST SUBQUERY
   `--SCAN TABLE lol

However, the correlated subquery scans the lol table once for every row in the foo table, while the NOT IN query puts all rows returned by the subquery into a temporary index, and then does all searches using that.
This can be seen in the output of the EXPLAIN command, if you really want to bother to decode it:

> EXPLAIN SELECT foo.bar,foo.baz FROM foo WHERE NOT EXISTS (SELECT lol.haha FROM lol WHERE lol.haha = foo.haha);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     19    0                    00  Start at 19
1     OpenRead       0     4     0     3              00  root=4 iDb=0; foo
2     Rewind         0     18    0                    00
3       Integer        0     2     0                    00  r[2]=0; Init EXISTS result
4       Integer        1     3     0                    00  r[3]=1; LIMIT counter
5       OpenRead       1     2     0     1              00  root=2 iDb=0; lol
6       Rewind         1     13    0                    00
7         Column         1     0     4                    00  r[4]=lol.haha
8         Column         0     2     5                    00  r[5]=foo.haha
9         Ne             5     12    4     (BINARY)       51  if r[4]!=r[5] goto 12
10        Integer        1     2     0                    00  r[2]=1
11        DecrJumpZero   3     13    0                    00  if (--r[3])==0 goto 13
12      Next           1     7     0                    01
13      If             2     17    1                    00
14      Column         0     0     7                    00  r[7]=foo.bar
15      Column         0     1     8                    00  r[8]=foo.baz
16      ResultRow      7     2     0                    00  output=r[7..8]
17    Next           0     3     0                    01
18    Halt           0     0     0                    00
19    Transaction    0     0     6     0              01  usesStmtJournal=0
20    Goto           0     1     0                    00
> EXPLAIN SELECT foo.bar,foo.baz FROM foo WHERE haha NOT IN (SELECT haha FROM lol);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     26    0                    00  Start at 26
1     OpenRead       0     4     0     3              00  root=4 iDb=0; foo
2     Rewind         0     25    0                    00
3       Noop           0     0     0                    00  begin IN expr
4       Once           0     12    0                    00
5       OpenEphemeral  3     1     0     k(1,B)         00  nColumn=1
6       OpenRead       1     2     0     1              00  root=2 iDb=0; lol
7       Rewind         1     12    0                    00
8         Column         1     0     1                    00  r[1]=lol.haha
9         MakeRecord     1     1     2     A              00  r[2]=mkrec(r[1])
10        IdxInsert      3     2     1     1              00  key=r[2]
11      Next           1     8     0                    01
12      Column         0     2     2                    00  r[2]=foo.haha
13      IsNull         2     16    0                    00  if r[2]==NULL goto 16
14      Affinity       2     1     0     A              00  affinity(r[2])
15      Found          3     20    2     1              00  key=r[2]
16      Rewind         3     21    0                    00
17      Column         3     0     3                    00  r[3]=
18      Ne             2     21    3     (BINARY)       00  if r[3]!=r[2] goto 21
19      Goto           0     24    0                    00  end IN expr
20      Goto           0     24    0                    00
21      Column         0     0     4                    00  r[4]=foo.bar
22      Column         0     1     5                    00  r[5]=foo.baz
23      ResultRow      4     2     0                    00  output=r[4..5]
24    Next           0     3     0                    01
25    Halt           0     0     0                    00
26    Transaction    0     0     6     0              01  usesStmtJournal=0
27    Goto           0     1     0                    00

With an index, both queries do an index search for every foo row, i.e., they execute in exactly the same way:

> create index i on lol(haha);
> SELECT foo.bar,foo.baz FROM foo WHERE NOT EXISTS (SELECT lol.haha FROM lol WHERE lol.haha = foo.haha);
QUERY PLAN
|--SCAN TABLE foo
`--CORRELATED SCALAR SUBQUERY
   `--SEARCH TABLE lol USING COVERING INDEX i (haha=?)
> SELECT foo.bar,foo.baz FROM foo WHERE haha NOT IN (SELECT haha FROM lol);
QUERY PLAN
|--SCAN TABLE foo
`--USING INDEX i FOR IN-OPERATOR
4
  • Seems those haha columns are NULLable, does the NOT IN plan change when you change it to NOT NULL?
    – dnoeth
    Commented Jan 8, 2019 at 11:04
  • The high-level plan does not change, but the program reads the first index entry (where a NULL would have to show up), and does additional checks.
    – CL.
    Commented Jan 8, 2019 at 11:55
  • So bottom line seems to be that with an index they're identical and without an index the NOT IN is possibly more efficient. Thanks! Also means SQLite's query planner is better than I expected. Commented Jan 8, 2019 at 13:53
  • @AdamIerymenko: But the NOT IN will return a different result than NOT EXISTS when there are NULLs, e.g. no result when the subquery returns a single NULL. You must at least add WHERE haha IS NOT NULL in the NOT IN.
    – dnoeth
    Commented Jan 8, 2019 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.