xBestIndex constraints: discern between JOIN and regular constraints
(1) By Gunter Hick (gunter_hick) on 2021-06-14 11:12:40 [link] [source]
with SQLite 3.24.0 (sorry, no newer version in production here yet) I have two virtual tables corresponding to the following table definitions:
CREATE TABLE privilege (
module_def_no INTEGER,
user_person_id INTEGER,
module_action_no INTEGER,
read_access_allowed INTEGER,
write_access_allowed INTEGER,
UNIQUE (module_def_no, user_person_id, module action no);
CREATE TABLE assmnt(
module_def_no INTEGER,
state_def_no INTEGER,
module_action_no INTEGER,
state_transition_no INTEGER,
entity_id INTEGER,
UNIQUE (module_def_no, module_action_no,state_def_no,state_transition_no));
When preparing the following statement
SELECT ... FROM privilege p, assmnt a
<C1> WHERE a.state_def_no=13
<C2> AND a.module_def_no=14076
<C3> AND p.module_def_no=a.module_def_no
<C4> AND p.user_person_id=1002
<C5> AND p.module_action_no=a.module_action_no
<C6> AND p.write_access_allowed = 1
<C7> AND a.module_action_no NOT IN (12);
the BestIndex function are called thus (with answers shown):
Note: Constraint information is formatted "C" for constraint, field name, operation : argvIndex, "O" if Omit flags is set
Note: Return information is formatted "R" for result, index name, (index number), cost, rows, "Unique" if Unique flag is set
Call #1
with all four fields of privilege table available, i.e. RHS of the JOIN,
Bestindex responds with the fields of the index in index order and result is unique
2021-06-14 11:19:19.215: B BestIndex for table privilege
2021-06-14 11:19:19.215: Constraints
2021-06-14 11:19:19.216: C module_def_no EQ : 1 O
2021-06-14 11:19:19.216: C user_person_id EQ : 2 O
2021-06-14 11:19:19.216: C module_action_no EQ : 3 O
2021-06-14 11:19:19.216: C write_access_allowed EQ : 0
2021-06-14 11:19:19.216: R privilege_idx (1) Cost 15.39 Rows 1 Unique
Call #2
with only the fields available to the LHS of the JOIN being usable,
BestIndex responds with a full table scan returning all rows
2021-06-14 11:19:19.216: B BestIndex for table privilege
2021-06-14 11:19:19.216: Constraints
2021-06-14 11:19:19.216: C (module_def_no EQ) : 0
2021-06-14 11:19:19.216: C user_person_id EQ : 0
2021-06-14 11:19:19.216: C (module_action_no EQ) : 0
2021-06-14 11:19:19.216: C write_access_allowed EQ : 0
2021-06-14 11:19:19.216: R privilege_idx (1) Cost 43061.39 Rows 43046
Call #3
with all 5 fields available, i.e. the RHS of the JOIN,
BestIndex responds with a partial key scan using the first three index fields
B BestIndex for table assmnt
Constraints
<C1> C state_def_no EQ : 3 O
<C2> C module_def_no EQ : 1 O
<C7> C module_action_no NE : 0
<C5> C module_action_no EQ : 2 O
<C3> C module_def_no EQ : 0
R assmnt_idx (1) Cost 14.34 Rows 5
Call #4
with only the fields available to the LHS of the JOIN being usable,
BestINdex responds with a partial key scan using the first field
2021-06-14 11:19:19.216: B BestIndex for table assmnt
2021-06-14 11:19:19.216: Constraints
2021-06-14 11:19:19.216: C state_def_no EQ : 0
2021-06-14 11:19:19.216: C module_def_no EQ : 1 O
2021-06-14 11:19:19.216: C module_action_no NE : 0
2021-06-14 11:19:19.216: C (module_action_no EQ) : 0
2021-06-14 11:19:19.216: C (module_def_no EQ) : 0
2021-06-14 11:19:19.216: R assmnt_idx (1) Cost 137.34 Rows 128
this resulta in the
QUERY PLAN
|--SCAN TABLE assmnt VIRTUAL TABLE INDEX 1:
`--SCAN TABLE privilege VIRTUAL TABLE INDEX 1:
How can the BestIndex function determine if a given constraint comes from a "result set limiting" constraint or from a "join constraint"?
In the case of module_action_no, looking at the operation (EQ vs. NE) is sufficient to ensure that the value passed to the Filter function comes from the JOIN.
In the case of module_def_no, the case is not so clear; indeed, if forced to use the "wrong" query plan, I can see that SQLite is checking p.module_def_no against the constant (addr 37,10,11) and passing a copy of the constant to the Filter function (addr 12..17) instead of a copy of the field value.
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 35 0 00 NULL
1 VOpen 0 0 0 vtab:DD205A0 00 NULL
2 VOpen 1 0 0 vtab:DD221F0 00 NULL
3 Integer 1 1 0 00 NULL
4 Integer 0 2 0 00 NULL
5 VFilter 0 34 1 00 NULL
6 VColumn 0 1 3 00 NULL
7 Ne 4 33 3 (BINARY) 53 NULL
8 VColumn 0 4 5 00 NULL
9 Ne 6 33 5 (BINARY) 54 NULL
10 VColumn 0 0 7 00 NULL
11 Ne 8 33 7 (BINARY) 53 NULL
12 Integer 14076 11 0 00 NULL
13 VColumn 0 2 12 00 NULL
14 Integer 13 13 0 00 NULL
15 Integer 1 9 0 00 NULL
16 Integer 3 10 0 00 NULL
17 VFilter 1 33 9 00 NULL
18 VColumn 1 0 14 00 NULL
19 Ne 14 32 7 (BINARY) 53 NULL
20 VColumn 1 2 15 00 NULL
21 Eq 16 32 15 (BINARY) 53 NULL
22 Concat 15 22 21 00 NULL
23 Concat 22 21 17 00 NULL
24 Copy 15 21 0 00 NULL
25 Function0 0 21 18 hex(1) 01 NULL
26 VColumn 0 2 23 00 NULL
27 Concat 23 22 21 00 NULL
28 Concat 22 21 19 00 NULL
29 Copy 23 21 0 00 NULL
30 Function0 0 21 20 hex(1) 01 NULL
31 ResultRow 17 4 0 00 NULL
32 VNext 1 18 0 00 NULL
33 VNext 0 6 0 00 NULL
34 Halt 0 0 0 00 NULL
35 Integer 1002 4 0 00 NULL
36 Integer 1 6 0 00 NULL
37 Integer 14076 8 0 00 NULL
38 Integer 12 16 0 00 NULL
39 String8 0 22 0 * 00 NULL
40 Goto 0 1 0 00 NULL
(2) By Richard Hipp (drh) on 2021-06-14 12:24:00 in reply to 1 [source]
How can the BestIndex function determine if a given constraint comes from a "result set limiting" constraint or from a "join constraint"?
I'm not sure what those two categories of constraint mean. SQLite certainly doesn't make any such distinctions anywhere internally, as far as I know.
(3) By Gunter Hick (gunter_hick) on 2021-06-14 14:17:27 in reply to 2 [link] [source]
A "result set limiting" constraint associates a field with a constant (or a variable), whereas a "join constraint" defines a relation between two fields of the tables being joined.
There are three (not including syntax variations) logically equivalent ways to express an equijoin between two tables limited to a certain value of the field used:
- T1.a == x AND T1.a == T2.a
- T2.a == x AND T1.a == T2.a
- T1.a == x AND T2.a == x
Form 1 favors T1 in the outer loop Form 2 favors T2 in the outer loop Form 3 is indifferent
Combining Form 1 with a cross join with T2 in the outer loop makes SQLite check T2.a == x inside the full table scan loop instead of asking for a partial key scan of the same condition.