Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment:  Further refinement of the inoperator.md documentation. 

Downloads:  Tarball  ZIP archive  SQL archive 
Timelines:  family  ancestors  descendants  both  rowvalue 
Files:  files  file ages  folders 
SHA1:  df0648373a50006ca18d692e12552d1d 
User & Date:  drh 20160825 17:40:32 
Context
20160825
 
17:47  Another fix in the INoperator algorithm description. checkin: f474aeac user: drh tags: rowvalue  
17:40  Further refinement of the inoperator.md documentation. checkin: df064837 user: drh tags: rowvalue  
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  
Changes
Changes to src/inoperator.md.
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
..
74
75
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

3. If the nullflag is true, return NULL. 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 ................................................................................ x=y1 OR x=y2 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. 

<
<

>
<
<
>

<
>


<
<
<
<

<
<
<
>
>
>

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

3. If the nullflag is true, return NULL. 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. 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 ................................................................................ x=y1 OR x=y2 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. Check the LHS to see if it is a partialNULL and if it is, jump ahead to step 4. 3. Do a binary search for the RHS using the LHS as a probe. If an exact match is found, return TRUE. 4. If we do not need to distingish between FALSE and NULL, then return FALSE. 5. If the RHS is nonNULL then return FALSE. 6. For each row in the RHS, compare that row against the LHS and if the result is NULL, immediately return NULL. In the case of a scalar IN operator, we only need to look at the very first row the RHS because for a scalar RHS, all NULLs will always come first. If the RHS is empty, this step is a noop. 7. Return FALSE. 