Many hyperlinks are disabled.

Use anonymous login
to enable hyperlinks.

Overview

Comment: | Corrections to the IN-operator notes. |
---|---|

Downloads: | Tarball | ZIP archive | SQL archive |

Timelines: | family | ancestors | descendants | both | rowvalue |

Files: | files | file ages | folders |

SHA1: |
25033ee94538289ba7e0147da30a1830 |

User & Date: | drh 2016-08-25 14:23:59 |

Context

2016-08-25
| ||

15:46 | Improvements to IN operator code generator comments. Avoid unnecessary Copy operations on the LHS of the IN operator. check-in: b6344298 user: drh tags: rowvalue | |

14:23 | Corrections to the IN-operator notes. check-in: 25033ee9 user: drh tags: rowvalue | |

14:00 | Add notes on the implementation of the IN operator. check-in: d256b2ca user: drh tags: rowvalue | |

Changes

Changes to src/in-operator.md.

58 58 4. Return FALSE 59 59 60 60 ## Optimized Algorithm 61 61 62 62 The following procedure computes the same answer as the simple full-scan 63 63 algorithm, though it does so with less work in the common case. This 64 64 is the algorithm that is implemented in SQLite. The steps must occur 65 -in the order specified. Except for the INDEX_NOOP optimization of step 1, 66 -none of the steps can be skipped. 65 +in the order specified. Steps 1 and 3 are optional. All other steps 66 +are required for correctness. 67 67 68 68 1. If the RHS is a constant list of length 1 or 2, then rewrite the 69 69 IN operator as a simple expression. Implement 70 70 71 71 x IN (y1,y2) 72 72 73 73 as if it were ................................................................................ 76 76 77 77 This is the INDEX_NOOP optimization and is only undertaken if the 78 78 IN operator is used for membership testing. If the IN operator is 79 79 driving a loop, then skip this step entirely. 80 80 81 81 2. If the RHS is empty, return FALSE. 82 82 83 - 3. If the LHS is a total-NULL or if the RHS contains a total-NULL, 84 - then return NULL. 83 + 3. If the LHS is a total-NULL, then return NULL. 85 84 86 85 4. If the LHS is non-NULL, then use the LHS as a probe in a binary 87 86 search of the RHS 88 87 89 - <ol type='a'> 90 - <li> If the binary search finds an exact match, return TRUE 88 + 4-A. If the binary search finds an exact match, return TRUE 91 89 92 - <li> If the RHS is known to be not-null, return FALSE 93 - </ol> 90 + 4-B. If the RHS is known to be not-null, return FALSE 94 91 95 92 5. At this point, it is known that the result cannot be TRUE. All 96 93 that remains is to distinguish between NULL and FALSE. 97 94 If a NOT-TRUE result is acceptable, then return NOT-TRUE now. 98 95 99 96 6. For each row in the RHS, compare that row against the LHS and 100 97 if the result is NULL, immediately return NULL. This step is 101 98 essentially the "Simple Full-scan Algorithm" above with the 102 99 tests for TRUE removed, since we know that the result cannot be 103 100 TRUE at this point. 104 101 105 102 7. Return FALSE.