/ Check-in [25033ee9]
Login

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: 25033ee94538289ba7e0147da30a18300047123f
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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.