Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment:  Corrections to the INoperator notes. 

Downloads:  Tarball  ZIP archive  SQL archive 
Timelines:  family  ancestors  descendants  both  rowvalue 
Files:  files  file ages  folders 
SHA1: 
25033ee94538289ba7e0147da30a1830 
User & Date:  drh 20160825 14:23:59 
Context
20160825
 
15:46  Improvements to IN operator code generator comments. Avoid unnecessary Copy operations on the LHS of the IN operator. (checkin: b6344298 user: drh tags: rowvalue)  
14:23  Corrections to the INoperator notes. (checkin: 25033ee9 user: drh tags: rowvalue)  
14:00  Add notes on the implementation of the IN operator. (checkin: d256b2ca user: drh tags: rowvalue)  
Changes
Changes to src/inoperator.md.
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
..
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

4. Return FALSE ## Optimized Algorithm The following procedure computes the same answer as the simple fullscan algorithm, though it does so with less work in the common case. This is the algorithm that is implemented in SQLite. The steps must occur in the order specified. Except for the INDEX_NOOP optimization of step 1, none of the steps can be skipped. 1. If the RHS is a constant list of length 1 or 2, then rewrite the IN operator as a simple expression. Implement x IN (y1,y2) as if it were ................................................................................ This is the INDEX_NOOP optimization and is only undertaken if the IN operator is used for membership testing. If the IN operator is driving a loop, then skip this step entirely. 2. If the RHS is empty, return FALSE. 3. If the LHS is a totalNULL or if the RHS contains a totalNULL, then return NULL. 4. If the LHS is nonNULL, then use the LHS as a probe in a binary search of the RHS <ol type='a'> <li> If the binary search finds an exact match, return TRUE <li> If the RHS is known to be notnull, return FALSE </ol> 5. At this point, it is known that the result cannot be TRUE. All that remains is to distinguish between NULL and FALSE. If a NOTTRUE result is acceptable, then return NOTTRUE now. 6. For each row in the RHS, compare that row against the LHS and if the result is NULL, immediately return NULL. This step is essentially the "Simple Fullscan Algorithm" above with the tests for TRUE removed, since we know that the result cannot be TRUE at this point. 7. Return FALSE. 



<
<


<

58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
..
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

4. Return FALSE ## Optimized Algorithm The following procedure computes the same answer as the simple fullscan algorithm, though it does so with less work in the common case. This is the algorithm that is implemented in SQLite. The steps must occur in the order specified. Steps 1 and 3 are optional. All other steps are required for correctness. 1. If the RHS is a constant list of length 1 or 2, then rewrite the IN operator as a simple expression. Implement x IN (y1,y2) as if it were ................................................................................ This is the INDEX_NOOP optimization and is only undertaken if the IN operator is used for membership testing. If the IN operator is driving a loop, then skip this step entirely. 2. If the RHS is empty, return FALSE. 3. If the LHS is a totalNULL, then return NULL. 4. If the LHS is nonNULL, then use the LHS as a probe in a binary search of the RHS 4A. If the binary search finds an exact match, return TRUE 4B. If the RHS is known to be notnull, return FALSE 5. At this point, it is known that the result cannot be TRUE. All that remains is to distinguish between NULL and FALSE. If a NOTTRUE result is acceptable, then return NOTTRUE now. 6. For each row in the RHS, compare that row against the LHS and if the result is NULL, immediately return NULL. This step is essentially the "Simple Fullscan Algorithm" above with the tests for TRUE removed, since we know that the result cannot be TRUE at this point. 7. Return FALSE. 