SQLite

Check-in [df0648373a]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Further refinement of the in-operator.md documentation.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | rowvalue
Files: files | file ages | folders
SHA1: df0648373a50006ca18d692e12552d1d53d549e3
User & Date: drh 2016-08-25 17:40:32.626
Context
2016-08-25
17:47
Another fix in the IN-operator algorithm description. (check-in: f474aeac4f user: drh tags: rowvalue)
17:40
Further refinement of the in-operator.md documentation. (check-in: df0648373a user: drh tags: rowvalue)
15:46
Improvements to IN operator code generator comments. Avoid unnecessary Copy operations on the LHS of the IN operator. (check-in: b634429878 user: drh tags: rowvalue)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/in-operator.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 null-flag is true, return NULL.
  4.  Return FALSE

## Optimized Algorithm

The following procedure computes the same answer as the simple full-scan
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 total-NULL, then return NULL.

  4.  If the LHS is non-NULL, then use the LHS as a probe in a binary
      search of the RHS 

      4-A.  If the binary search finds an exact match, return TRUE

      4-B.  If the RHS is known to be not-null, 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 NOT-TRUE result is acceptable, then return NOT-TRUE 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 Full-scan 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 null-flag is true, return NULL.
  4.  Return FALSE

## Optimized Algorithm

The following procedure computes the same answer as the simple full-scan
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 partial-NULL 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 non-NULL 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 no-op.

  7.  Return FALSE.