/ Hex Artifact Content
Login

Artifact 78b6b4de94db84aecbdc07fe3e38f648eb391e9a:


0000: 2f 2a 0a 2a 2a 20 32 30 31 33 2d 31 31 2d 31 32  /*.** 2013-11-12
0010: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 68 6f  .**.** The autho
0020: 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70 79  r disclaims copy
0030: 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73 6f  right to this so
0040: 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20 70  urce code.  In p
0050: 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c 65 67  lace of.** a leg
0060: 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65 20  al notice, here 
0070: 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a 2a  is a blessing:.*
0080: 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f 75 20  *.**    May you 
0090: 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74 20  do good and not 
00a0: 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 79 20  evil..**    May 
00b0: 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 76 65  you find forgive
00c0: 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 65 6c  ness for yoursel
00d0: 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 6f 74  f and forgive ot
00e0: 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 79 20  hers..**    May 
00f0: 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 6c 79  you share freely
0100: 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 20 6d  , never taking m
0110: 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 69 76  ore than you giv
0120: 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  e..**.**********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a  ***************.
0170: 2a 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20  **.** This file 
0180: 63 6f 6e 74 61 69 6e 73 20 73 74 72 75 63 74 75  contains structu
0190: 72 65 20 61 6e 64 20 6d 61 63 72 6f 20 64 65 66  re and macro def
01a0: 69 6e 69 74 69 6f 6e 73 20 66 6f 72 20 74 68 65  initions for the
01b0: 20 71 75 65 72 79 0a 2a 2a 20 70 6c 61 6e 6e 65   query.** planne
01c0: 72 20 6c 6f 67 69 63 20 69 6e 20 22 77 68 65 72  r logic in "wher
01d0: 65 2e 63 22 2e 20 20 54 68 65 73 65 20 64 65 66  e.c".  These def
01e0: 69 6e 69 74 69 6f 6e 73 20 61 72 65 20 62 72 6f  initions are bro
01f0: 6b 65 6e 20 6f 75 74 20 69 6e 74 6f 0a 2a 2a 20  ken out into.** 
0200: 61 20 73 65 70 61 72 61 74 65 20 73 6f 75 72 63  a separate sourc
0210: 65 20 66 69 6c 65 20 66 6f 72 20 65 61 73 69 65  e file for easie
0220: 72 20 65 64 69 74 69 6e 67 2e 0a 2a 2f 0a 0a 2f  r editing..*/../
0230: 2a 0a 2a 2a 20 54 72 61 63 65 20 6f 75 74 70 75  *.** Trace outpu
0240: 74 20 6d 61 63 72 6f 73 0a 2a 2f 0a 23 69 66 20  t macros.*/.#if 
0250: 64 65 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 54  defined(SQLITE_T
0260: 45 53 54 29 20 7c 7c 20 64 65 66 69 6e 65 64 28  EST) || defined(
0270: 53 51 4c 49 54 45 5f 44 45 42 55 47 29 0a 2f 2a  SQLITE_DEBUG)./*
0280: 2a 2a 2f 20 69 6e 74 20 73 71 6c 69 74 65 33 57  **/ int sqlite3W
0290: 68 65 72 65 54 72 61 63 65 3b 0a 23 65 6e 64 69  hereTrace;.#endi
02a0: 66 0a 23 69 66 20 64 65 66 69 6e 65 64 28 53 51  f.#if defined(SQ
02b0: 4c 49 54 45 5f 44 45 42 55 47 29 20 5c 0a 20 20  LITE_DEBUG) \.  
02c0: 20 20 26 26 20 28 64 65 66 69 6e 65 64 28 53 51    && (defined(SQ
02d0: 4c 49 54 45 5f 54 45 53 54 29 20 7c 7c 20 64 65  LITE_TEST) || de
02e0: 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 45 4e 41  fined(SQLITE_ENA
02f0: 42 4c 45 5f 57 48 45 52 45 54 52 41 43 45 29 29  BLE_WHERETRACE))
0300: 0a 23 20 64 65 66 69 6e 65 20 57 48 45 52 45 54  .# define WHERET
0310: 52 41 43 45 28 4b 2c 58 29 20 20 69 66 28 73 71  RACE(K,X)  if(sq
0320: 6c 69 74 65 33 57 68 65 72 65 54 72 61 63 65 26  lite3WhereTrace&
0330: 28 4b 29 29 20 73 71 6c 69 74 65 33 44 65 62 75  (K)) sqlite3Debu
0340: 67 50 72 69 6e 74 66 20 58 0a 23 20 64 65 66 69  gPrintf X.# defi
0350: 6e 65 20 57 48 45 52 45 54 52 41 43 45 5f 45 4e  ne WHERETRACE_EN
0360: 41 42 4c 45 44 20 31 0a 23 65 6c 73 65 0a 23 20  ABLED 1.#else.# 
0370: 64 65 66 69 6e 65 20 57 48 45 52 45 54 52 41 43  define WHERETRAC
0380: 45 28 4b 2c 58 29 0a 23 65 6e 64 69 66 0a 0a 2f  E(K,X).#endif../
0390: 2a 20 46 6f 72 77 61 72 64 20 72 65 66 65 72 65  * Forward refere
03a0: 6e 63 65 73 0a 2a 2f 0a 74 79 70 65 64 65 66 20  nces.*/.typedef 
03b0: 73 74 72 75 63 74 20 57 68 65 72 65 43 6c 61 75  struct WhereClau
03c0: 73 65 20 57 68 65 72 65 43 6c 61 75 73 65 3b 0a  se WhereClause;.
03d0: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 57  typedef struct W
03e0: 68 65 72 65 4d 61 73 6b 53 65 74 20 57 68 65 72  hereMaskSet Wher
03f0: 65 4d 61 73 6b 53 65 74 3b 0a 74 79 70 65 64 65  eMaskSet;.typede
0400: 66 20 73 74 72 75 63 74 20 57 68 65 72 65 4f 72  f struct WhereOr
0410: 49 6e 66 6f 20 57 68 65 72 65 4f 72 49 6e 66 6f  Info WhereOrInfo
0420: 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  ;.typedef struct
0430: 20 57 68 65 72 65 41 6e 64 49 6e 66 6f 20 57 68   WhereAndInfo Wh
0440: 65 72 65 41 6e 64 49 6e 66 6f 3b 0a 74 79 70 65  ereAndInfo;.type
0450: 64 65 66 20 73 74 72 75 63 74 20 57 68 65 72 65  def struct Where
0460: 4c 65 76 65 6c 20 57 68 65 72 65 4c 65 76 65 6c  Level WhereLevel
0470: 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  ;.typedef struct
0480: 20 57 68 65 72 65 4c 6f 6f 70 20 57 68 65 72 65   WhereLoop Where
0490: 4c 6f 6f 70 3b 0a 74 79 70 65 64 65 66 20 73 74  Loop;.typedef st
04a0: 72 75 63 74 20 57 68 65 72 65 50 61 74 68 20 57  ruct WherePath W
04b0: 68 65 72 65 50 61 74 68 3b 0a 74 79 70 65 64 65  herePath;.typede
04c0: 66 20 73 74 72 75 63 74 20 57 68 65 72 65 54 65  f struct WhereTe
04d0: 72 6d 20 57 68 65 72 65 54 65 72 6d 3b 0a 74 79  rm WhereTerm;.ty
04e0: 70 65 64 65 66 20 73 74 72 75 63 74 20 57 68 65  pedef struct Whe
04f0: 72 65 4c 6f 6f 70 42 75 69 6c 64 65 72 20 57 68  reLoopBuilder Wh
0500: 65 72 65 4c 6f 6f 70 42 75 69 6c 64 65 72 3b 0a  ereLoopBuilder;.
0510: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 57  typedef struct W
0520: 68 65 72 65 53 63 61 6e 20 57 68 65 72 65 53 63  hereScan WhereSc
0530: 61 6e 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75  an;.typedef stru
0540: 63 74 20 57 68 65 72 65 4f 72 43 6f 73 74 20 57  ct WhereOrCost W
0550: 68 65 72 65 4f 72 43 6f 73 74 3b 0a 74 79 70 65  hereOrCost;.type
0560: 64 65 66 20 73 74 72 75 63 74 20 57 68 65 72 65  def struct Where
0570: 4f 72 53 65 74 20 57 68 65 72 65 4f 72 53 65 74  OrSet WhereOrSet
0580: 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 6f 62  ;../*.** This ob
0590: 6a 65 63 74 20 63 6f 6e 74 61 69 6e 73 20 69 6e  ject contains in
05a0: 66 6f 72 6d 61 74 69 6f 6e 20 6e 65 65 64 65 64  formation needed
05b0: 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20 61 20   to implement a 
05c0: 73 69 6e 67 6c 65 20 6e 65 73 74 65 64 0a 2a 2a  single nested.**
05d0: 20 6c 6f 6f 70 20 69 6e 20 57 48 45 52 45 20 63   loop in WHERE c
05e0: 6c 61 75 73 65 2e 0a 2a 2a 0a 2a 2a 20 43 6f 6e  lause..**.** Con
05f0: 74 72 61 73 74 20 74 68 69 73 20 6f 62 6a 65 63  trast this objec
0600: 74 20 77 69 74 68 20 57 68 65 72 65 4c 6f 6f 70  t with WhereLoop
0610: 2e 20 20 54 68 69 73 20 6f 62 6a 65 63 74 20 64  .  This object d
0620: 65 73 63 72 69 62 65 73 20 74 68 65 0a 2a 2a 20  escribes the.** 
0630: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f  implementation o
0640: 66 20 74 68 65 20 6c 6f 6f 70 2e 20 20 57 68 65  f the loop.  Whe
0650: 72 65 4c 6f 6f 70 20 64 65 73 63 72 69 62 65 73  reLoop describes
0660: 20 74 68 65 20 61 6c 67 6f 72 69 74 68 6d 2e 0a   the algorithm..
0670: 2a 2a 20 54 68 69 73 20 6f 62 6a 65 63 74 20 63  ** This object c
0680: 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74 65  ontains a pointe
0690: 72 20 74 6f 20 74 68 65 20 57 68 65 72 65 4c 6f  r to the WhereLo
06a0: 6f 70 20 61 6c 67 6f 72 69 74 68 6d 20 61 73 20  op algorithm as 
06b0: 6f 6e 65 20 6f 66 0a 2a 2a 20 69 74 73 20 65 6c  one of.** its el
06c0: 65 6d 65 6e 74 73 2e 0a 2a 2a 0a 2a 2a 20 54 68  ements..**.** Th
06d0: 65 20 57 68 65 72 65 49 6e 66 6f 20 6f 62 6a 65  e WhereInfo obje
06e0: 63 74 20 63 6f 6e 74 61 69 6e 73 20 61 20 73 69  ct contains a si
06f0: 6e 67 6c 65 20 69 6e 73 74 61 6e 63 65 20 6f 66  ngle instance of
0700: 20 74 68 69 73 20 6f 62 6a 65 63 74 20 66 6f 72   this object for
0710: 0a 2a 2a 20 65 61 63 68 20 74 65 72 6d 20 69 6e  .** each term in
0720: 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73 65   the FROM clause
0730: 20 28 77 68 69 63 68 20 69 73 20 74 6f 20 73 61   (which is to sa
0740: 79 2c 20 66 6f 72 20 65 61 63 68 20 6f 66 20 74  y, for each of t
0750: 68 65 0a 2a 2a 20 6e 65 73 74 65 64 20 6c 6f 6f  he.** nested loo
0760: 70 73 20 61 73 20 69 6d 70 6c 65 6d 65 6e 74 65  ps as implemente
0770: 64 29 2e 20 20 54 68 65 20 6f 72 64 65 72 20 6f  d).  The order o
0780: 66 20 57 68 65 72 65 4c 65 76 65 6c 20 6f 62 6a  f WhereLevel obj
0790: 65 63 74 73 20 64 65 74 65 72 6d 69 6e 65 73 0a  ects determines.
07a0: 2a 2a 20 74 68 65 20 6c 6f 6f 70 20 6e 65 73 74  ** the loop nest
07b0: 65 64 20 6f 72 64 65 72 2c 20 77 69 74 68 20 57  ed order, with W
07c0: 68 65 72 65 49 6e 66 6f 2e 61 5b 30 5d 20 62 65  hereInfo.a[0] be
07d0: 69 6e 67 20 74 68 65 20 6f 75 74 65 72 20 6c 6f  ing the outer lo
07e0: 6f 70 20 61 6e 64 0a 2a 2a 20 57 68 65 72 65 49  op and.** WhereI
07f0: 6e 66 6f 2e 61 5b 57 68 65 72 65 49 6e 66 6f 2e  nfo.a[WhereInfo.
0800: 6e 4c 65 76 65 6c 2d 31 5d 20 62 65 69 6e 67 20  nLevel-1] being 
0810: 74 68 65 20 69 6e 6e 65 72 20 6c 6f 6f 70 2e 0a  the inner loop..
0820: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 4c  */.struct WhereL
0830: 65 76 65 6c 20 7b 0a 20 20 69 6e 74 20 69 4c 65  evel {.  int iLe
0840: 66 74 4a 6f 69 6e 3b 20 20 20 20 20 20 20 20 2f  ftJoin;        /
0850: 2a 20 4d 65 6d 6f 72 79 20 63 65 6c 6c 20 75 73  * Memory cell us
0860: 65 64 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20  ed to implement 
0870: 4c 45 46 54 20 4f 55 54 45 52 20 4a 4f 49 4e 20  LEFT OUTER JOIN 
0880: 2a 2f 0a 20 20 69 6e 74 20 69 54 61 62 43 75 72  */.  int iTabCur
0890: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68  ;          /* Th
08a0: 65 20 56 44 42 45 20 63 75 72 73 6f 72 20 75 73  e VDBE cursor us
08b0: 65 64 20 74 6f 20 61 63 63 65 73 73 20 74 68 65  ed to access the
08c0: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74 20   table */.  int 
08d0: 69 49 64 78 43 75 72 3b 20 20 20 20 20 20 20 20  iIdxCur;        
08e0: 20 20 2f 2a 20 54 68 65 20 56 44 42 45 20 63 75    /* The VDBE cu
08f0: 72 73 6f 72 20 75 73 65 64 20 74 6f 20 61 63 63  rsor used to acc
0900: 65 73 73 20 70 49 64 78 20 2a 2f 0a 20 20 69 6e  ess pIdx */.  in
0910: 74 20 61 64 64 72 42 72 6b 3b 20 20 20 20 20 20  t addrBrk;      
0920: 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65 72 65      /* Jump here
0930: 20 74 6f 20 62 72 65 61 6b 20 6f 75 74 20 6f 66   to break out of
0940: 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20 20 69   the loop */.  i
0950: 6e 74 20 61 64 64 72 4e 78 74 3b 20 20 20 20 20  nt addrNxt;     
0960: 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65 72       /* Jump her
0970: 65 20 74 6f 20 73 74 61 72 74 20 74 68 65 20 6e  e to start the n
0980: 65 78 74 20 49 4e 20 63 6f 6d 62 69 6e 61 74 69  ext IN combinati
0990: 6f 6e 20 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72  on */.  int addr
09a0: 53 6b 69 70 3b 20 20 20 20 20 20 20 20 20 2f 2a  Skip;         /*
09b0: 20 4a 75 6d 70 20 68 65 72 65 20 66 6f 72 20 6e   Jump here for n
09c0: 65 78 74 20 69 74 65 72 61 74 69 6f 6e 20 6f 66  ext iteration of
09d0: 20 73 6b 69 70 2d 73 63 61 6e 20 2a 2f 0a 20 20   skip-scan */.  
09e0: 69 6e 74 20 61 64 64 72 43 6f 6e 74 3b 20 20 20  int addrCont;   
09f0: 20 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65        /* Jump he
0a00: 72 65 20 74 6f 20 63 6f 6e 74 69 6e 75 65 20 77  re to continue w
0a10: 69 74 68 20 74 68 65 20 6e 65 78 74 20 6c 6f 6f  ith the next loo
0a20: 70 20 63 79 63 6c 65 20 2a 2f 0a 20 20 69 6e 74  p cycle */.  int
0a30: 20 61 64 64 72 46 69 72 73 74 3b 20 20 20 20 20   addrFirst;     
0a40: 20 20 20 2f 2a 20 46 69 72 73 74 20 69 6e 73 74     /* First inst
0a50: 72 75 63 74 69 6f 6e 20 6f 66 20 69 6e 74 65 72  ruction of inter
0a60: 69 6f 72 20 6f 66 20 74 68 65 20 6c 6f 6f 70 20  ior of the loop 
0a70: 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72 42 6f 64  */.  int addrBod
0a80: 79 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 42 65  y;         /* Be
0a90: 67 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 62  ginning of the b
0aa0: 6f 64 79 20 6f 66 20 74 68 69 73 20 6c 6f 6f 70  ody of this loop
0ab0: 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49   */.#ifndef SQLI
0ac0: 54 45 5f 4c 49 4b 45 5f 44 4f 45 53 4e 54 5f 4d  TE_LIKE_DOESNT_M
0ad0: 41 54 43 48 5f 42 4c 4f 42 53 0a 20 20 69 6e 74  ATCH_BLOBS.  int
0ae0: 20 69 4c 69 6b 65 52 65 70 43 6e 74 72 3b 20 20   iLikeRepCntr;  
0af0: 20 20 20 2f 2a 20 4c 49 4b 45 20 72 61 6e 67 65     /* LIKE range
0b00: 20 70 72 6f 63 65 73 73 69 6e 67 20 63 6f 75 6e   processing coun
0b10: 74 65 72 20 72 65 67 69 73 74 65 72 20 2a 2f 0a  ter register */.
0b20: 20 20 69 6e 74 20 61 64 64 72 4c 69 6b 65 52 65    int addrLikeRe
0b30: 70 3b 20 20 20 20 20 20 2f 2a 20 4c 49 4b 45 20  p;      /* LIKE 
0b40: 72 61 6e 67 65 20 70 72 6f 63 65 73 73 69 6e 67  range processing
0b50: 20 61 64 64 72 65 73 73 20 2a 2f 0a 23 65 6e 64   address */.#end
0b60: 69 66 0a 20 20 75 38 20 69 46 72 6f 6d 3b 20 20  if.  u8 iFrom;  
0b70: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57 68             /* Wh
0b80: 69 63 68 20 65 6e 74 72 79 20 69 6e 20 74 68 65  ich entry in the
0b90: 20 46 52 4f 4d 20 63 6c 61 75 73 65 20 2a 2f 0a   FROM clause */.
0ba0: 20 20 75 38 20 6f 70 2c 20 70 33 2c 20 70 35 3b    u8 op, p3, p5;
0bb0: 20 20 20 20 20 20 20 20 2f 2a 20 4f 70 63 6f 64          /* Opcod
0bc0: 65 2c 20 50 33 20 26 20 50 35 20 6f 66 20 74 68  e, P3 & P5 of th
0bd0: 65 20 6f 70 63 6f 64 65 20 74 68 61 74 20 65 6e  e opcode that en
0be0: 64 73 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20  ds the loop */. 
0bf0: 20 69 6e 74 20 70 31 2c 20 70 32 3b 20 20 20 20   int p1, p2;    
0c00: 20 20 20 20 20 20 20 2f 2a 20 4f 70 65 72 61 6e         /* Operan
0c10: 64 73 20 6f 66 20 74 68 65 20 6f 70 63 6f 64 65  ds of the opcode
0c20: 20 75 73 65 64 20 74 6f 20 65 6e 64 73 20 74 68   used to ends th
0c30: 65 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 6e 69 6f  e loop */.  unio
0c40: 6e 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 20  n {             
0c50: 20 20 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e    /* Information
0c60: 20 74 68 61 74 20 64 65 70 65 6e 64 73 20 6f 6e   that depends on
0c70: 20 70 57 4c 6f 6f 70 2d 3e 77 73 46 6c 61 67 73   pWLoop->wsFlags
0c80: 20 2a 2f 0a 20 20 20 20 73 74 72 75 63 74 20 7b   */.    struct {
0c90: 0a 20 20 20 20 20 20 69 6e 74 20 6e 49 6e 3b 20  .      int nIn; 
0ca0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0cb0: 4e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65  Number of entrie
0cc0: 73 20 69 6e 20 61 49 6e 4c 6f 6f 70 5b 5d 20 2a  s in aInLoop[] *
0cd0: 2f 0a 20 20 20 20 20 20 73 74 72 75 63 74 20 49  /.      struct I
0ce0: 6e 4c 6f 6f 70 20 7b 0a 20 20 20 20 20 20 20 20  nLoop {.        
0cf0: 69 6e 74 20 69 43 75 72 3b 20 20 20 20 20 20 20  int iCur;       
0d00: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 56 44         /* The VD
0d10: 42 45 20 63 75 72 73 6f 72 20 75 73 65 64 20 62  BE cursor used b
0d20: 79 20 74 68 69 73 20 49 4e 20 6f 70 65 72 61 74  y this IN operat
0d30: 6f 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 69 6e  or */.        in
0d40: 74 20 61 64 64 72 49 6e 54 6f 70 3b 20 20 20 20  t addrInTop;    
0d50: 20 20 20 20 20 2f 2a 20 54 6f 70 20 6f 66 20 74       /* Top of t
0d60: 68 65 20 49 4e 20 6c 6f 6f 70 20 2a 2f 0a 20 20  he IN loop */.  
0d70: 20 20 20 20 20 20 75 38 20 65 45 6e 64 4c 6f 6f        u8 eEndLoo
0d80: 70 4f 70 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  pOp;         /* 
0d90: 49 4e 20 4c 6f 6f 70 20 74 65 72 6d 69 6e 61 74  IN Loop terminat
0da0: 6f 72 2e 20 4f 50 5f 4e 65 78 74 20 6f 72 20 4f  or. OP_Next or O
0db0: 50 5f 50 72 65 76 20 2a 2f 0a 20 20 20 20 20 20  P_Prev */.      
0dc0: 7d 20 2a 61 49 6e 4c 6f 6f 70 3b 20 20 20 20 20  } *aInLoop;     
0dd0: 20 20 20 20 20 20 2f 2a 20 49 6e 66 6f 72 6d 61        /* Informa
0de0: 74 69 6f 6e 20 61 62 6f 75 74 20 65 61 63 68 20  tion about each 
0df0: 6e 65 73 74 65 64 20 49 4e 20 6f 70 65 72 61 74  nested IN operat
0e00: 6f 72 20 2a 2f 0a 20 20 20 20 7d 20 69 6e 3b 20  or */.    } in; 
0e10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0e20: 2f 2a 20 55 73 65 64 20 77 68 65 6e 20 70 57 4c  /* Used when pWL
0e30: 6f 6f 70 2d 3e 77 73 46 6c 61 67 73 26 57 48 45  oop->wsFlags&WHE
0e40: 52 45 5f 49 4e 5f 41 42 4c 45 20 2a 2f 0a 20 20  RE_IN_ABLE */.  
0e50: 20 20 49 6e 64 65 78 20 2a 70 43 6f 76 69 64 78    Index *pCovidx
0e60: 3b 20 20 20 20 20 20 20 2f 2a 20 50 6f 73 73 69  ;       /* Possi
0e70: 62 6c 65 20 63 6f 76 65 72 69 6e 67 20 69 6e 64  ble covering ind
0e80: 65 78 20 66 6f 72 20 57 48 45 52 45 5f 4d 55 4c  ex for WHERE_MUL
0e90: 54 49 5f 4f 52 20 2a 2f 0a 20 20 7d 20 75 3b 0a  TI_OR */.  } u;.
0ea0: 20 20 73 74 72 75 63 74 20 57 68 65 72 65 4c 6f    struct WhereLo
0eb0: 6f 70 20 2a 70 57 4c 6f 6f 70 3b 20 20 2f 2a 20  op *pWLoop;  /* 
0ec0: 54 68 65 20 73 65 6c 65 63 74 65 64 20 57 68 65  The selected Whe
0ed0: 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 20 2a 2f  reLoop object */
0ee0: 0a 20 20 42 69 74 6d 61 73 6b 20 6e 6f 74 52 65  .  Bitmask notRe
0ef0: 61 64 79 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  ady;          /*
0f00: 20 46 52 4f 4d 20 65 6e 74 72 69 65 73 20 6e 6f   FROM entries no
0f10: 74 20 75 73 61 62 6c 65 20 61 74 20 74 68 69 73  t usable at this
0f20: 20 6c 65 76 65 6c 20 2a 2f 0a 23 69 66 64 65 66   level */.#ifdef
0f30: 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 53   SQLITE_ENABLE_S
0f40: 54 4d 54 5f 53 43 41 4e 53 54 41 54 55 53 0a 20  TMT_SCANSTATUS. 
0f50: 20 69 6e 74 20 61 64 64 72 56 69 73 69 74 3b 20   int addrVisit; 
0f60: 20 20 20 20 20 20 20 2f 2a 20 41 64 64 72 65 73         /* Addres
0f70: 73 20 61 74 20 77 68 69 63 68 20 72 6f 77 20 69  s at which row i
0f80: 73 20 76 69 73 69 74 65 64 20 2a 2f 0a 23 65 6e  s visited */.#en
0f90: 64 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 45 61  dif.};../*.** Ea
0fa0: 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74  ch instance of t
0fb0: 68 69 73 20 6f 62 6a 65 63 74 20 72 65 70 72 65  his object repre
0fc0: 73 65 6e 74 73 20 61 6e 20 61 6c 67 6f 72 69 74  sents an algorit
0fd0: 68 6d 20 66 6f 72 20 65 76 61 6c 75 61 74 69 6e  hm for evaluatin
0fe0: 67 20 6f 6e 65 0a 2a 2a 20 74 65 72 6d 20 6f 66  g one.** term of
0ff0: 20 61 20 6a 6f 69 6e 2e 20 20 45 76 65 72 79 20   a join.  Every 
1000: 74 65 72 6d 20 6f 66 20 74 68 65 20 46 52 4f 4d  term of the FROM
1010: 20 63 6c 61 75 73 65 20 77 69 6c 6c 20 68 61 76   clause will hav
1020: 65 20 61 74 20 6c 65 61 73 74 0a 2a 2a 20 6f 6e  e at least.** on
1030: 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20  e corresponding 
1040: 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74  WhereLoop object
1050: 20 28 75 6e 6c 65 73 73 20 49 4e 44 45 58 45 44   (unless INDEXED
1060: 20 42 59 20 63 6f 6e 73 74 72 61 69 6e 74 73 0a   BY constraints.
1070: 2a 2a 20 70 72 65 76 65 6e 74 20 61 20 71 75 65  ** prevent a que
1080: 72 79 20 73 6f 6c 75 74 69 6f 6e 20 2d 20 77 68  ry solution - wh
1090: 69 63 68 20 69 73 20 61 6e 20 65 72 72 6f 72 29  ich is an error)
10a0: 20 61 6e 64 20 6d 61 6e 79 20 74 65 72 6d 73 20   and many terms 
10b0: 6f 66 20 74 68 65 0a 2a 2a 20 46 52 4f 4d 20 63  of the.** FROM c
10c0: 6c 61 75 73 65 20 77 69 6c 6c 20 68 61 76 65 20  lause will have 
10d0: 6d 75 6c 74 69 70 6c 65 20 57 68 65 72 65 4c 6f  multiple WhereLo
10e0: 6f 70 20 6f 62 6a 65 63 74 73 2c 20 65 61 63 68  op objects, each
10f0: 20 64 65 73 63 72 69 62 69 6e 67 20 61 0a 2a 2a   describing a.**
1100: 20 70 6f 74 65 6e 74 69 61 6c 20 77 61 79 20 6f   potential way o
1110: 66 20 69 6d 70 6c 65 6d 65 6e 74 69 6e 67 20 74  f implementing t
1120: 68 61 74 20 46 52 4f 4d 2d 63 6c 61 75 73 65 20  hat FROM-clause 
1130: 74 65 72 6d 2c 20 74 6f 67 65 74 68 65 72 20 77  term, together w
1140: 69 74 68 0a 2a 2a 20 64 65 70 65 6e 64 65 6e 63  ith.** dependenc
1150: 69 65 73 20 61 6e 64 20 63 6f 73 74 20 65 73 74  ies and cost est
1160: 69 6d 61 74 65 73 20 66 6f 72 20 75 73 69 6e 67  imates for using
1170: 20 74 68 65 20 63 68 6f 73 65 6e 20 61 6c 67 6f   the chosen algo
1180: 72 69 74 68 6d 2e 0a 2a 2a 0a 2a 2a 20 51 75 65  rithm..**.** Que
1190: 72 79 20 70 6c 61 6e 6e 69 6e 67 20 63 6f 6e 73  ry planning cons
11a0: 69 73 74 73 20 6f 66 20 62 75 69 6c 64 69 6e 67  ists of building
11b0: 20 75 70 20 61 20 63 6f 6c 6c 65 63 74 69 6f 6e   up a collection
11c0: 20 6f 66 20 74 68 65 73 65 20 57 68 65 72 65 4c   of these WhereL
11d0: 6f 6f 70 0a 2a 2a 20 6f 62 6a 65 63 74 73 2c 20  oop.** objects, 
11e0: 74 68 65 6e 20 63 6f 6d 70 75 74 69 6e 67 20 61  then computing a
11f0: 20 70 61 72 74 69 63 75 6c 61 72 20 73 65 71 75   particular sequ
1200: 65 6e 63 65 20 6f 66 20 57 68 65 72 65 4c 6f 6f  ence of WhereLoo
1210: 70 20 6f 62 6a 65 63 74 73 2c 20 77 69 74 68 0a  p objects, with.
1220: 2a 2a 20 6f 6e 65 20 57 68 65 72 65 4c 6f 6f 70  ** one WhereLoop
1230: 20 6f 62 6a 65 63 74 20 70 65 72 20 46 52 4f 4d   object per FROM
1240: 20 63 6c 61 75 73 65 20 74 65 72 6d 2c 20 74 68   clause term, th
1250: 61 74 20 73 61 74 69 73 66 79 20 61 6c 6c 20 64  at satisfy all d
1260: 65 70 65 6e 64 65 6e 63 69 65 73 0a 2a 2a 20 61  ependencies.** a
1270: 6e 64 20 74 68 61 74 20 6d 69 6e 69 6d 69 7a 65  nd that minimize
1280: 20 74 68 65 20 6f 76 65 72 61 6c 6c 20 63 6f 73   the overall cos
1290: 74 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68 65  t..*/.struct Whe
12a0: 72 65 4c 6f 6f 70 20 7b 0a 20 20 42 69 74 6d 61  reLoop {.  Bitma
12b0: 73 6b 20 70 72 65 72 65 71 3b 20 20 20 20 20 20  sk prereq;      
12c0: 20 2f 2a 20 42 69 74 6d 61 73 6b 20 6f 66 20 6f   /* Bitmask of o
12d0: 74 68 65 72 20 6c 6f 6f 70 73 20 74 68 61 74 20  ther loops that 
12e0: 6d 75 73 74 20 72 75 6e 20 66 69 72 73 74 20 2a  must run first *
12f0: 2f 0a 20 20 42 69 74 6d 61 73 6b 20 6d 61 73 6b  /.  Bitmask mask
1300: 53 65 6c 66 3b 20 20 20 20 20 2f 2a 20 42 69 74  Self;     /* Bit
1310: 6d 61 73 6b 20 69 64 65 6e 74 69 66 79 69 6e 67  mask identifying
1320: 20 74 61 62 6c 65 20 69 54 61 62 20 2a 2f 0a 23   table iTab */.#
1330: 69 66 64 65 66 20 53 51 4c 49 54 45 5f 44 45 42  ifdef SQLITE_DEB
1340: 55 47 0a 20 20 63 68 61 72 20 63 49 64 3b 20 20  UG.  char cId;  
1350: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 79             /* Sy
1360: 6d 62 6f 6c 69 63 20 49 44 20 6f 66 20 74 68 69  mbolic ID of thi
1370: 73 20 6c 6f 6f 70 20 66 6f 72 20 64 65 62 75 67  s loop for debug
1380: 67 69 6e 67 20 75 73 65 20 2a 2f 0a 23 65 6e 64  ging use */.#end
1390: 69 66 0a 20 20 75 38 20 69 54 61 62 3b 20 20 20  if.  u8 iTab;   
13a0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f             /* Po
13b0: 73 69 74 69 6f 6e 20 69 6e 20 46 52 4f 4d 20 63  sition in FROM c
13c0: 6c 61 75 73 65 20 6f 66 20 74 61 62 6c 65 20 66  lause of table f
13d0: 6f 72 20 74 68 69 73 20 6c 6f 6f 70 20 2a 2f 0a  or this loop */.
13e0: 20 20 75 38 20 69 53 6f 72 74 49 64 78 3b 20 20    u8 iSortIdx;  
13f0: 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74 69          /* Sorti
1400: 6e 67 20 69 6e 64 65 78 20 6e 75 6d 62 65 72 2e  ng index number.
1410: 20 20 30 3d 3d 4e 6f 6e 65 20 2a 2f 0a 20 20 4c    0==None */.  L
1420: 6f 67 45 73 74 20 72 53 65 74 75 70 3b 20 20 20  ogEst rSetup;   
1430: 20 20 20 20 20 2f 2a 20 4f 6e 65 2d 74 69 6d 65       /* One-time
1440: 20 73 65 74 75 70 20 63 6f 73 74 20 28 65 78 3a   setup cost (ex:
1450: 20 63 72 65 61 74 65 20 74 72 61 6e 73 69 65 6e   create transien
1460: 74 20 69 6e 64 65 78 29 20 2a 2f 0a 20 20 4c 6f  t index) */.  Lo
1470: 67 45 73 74 20 72 52 75 6e 3b 20 20 20 20 20 20  gEst rRun;      
1480: 20 20 20 20 2f 2a 20 43 6f 73 74 20 6f 66 20 72      /* Cost of r
1490: 75 6e 6e 69 6e 67 20 65 61 63 68 20 6c 6f 6f 70  unning each loop
14a0: 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 6e 4f 75   */.  LogEst nOu
14b0: 74 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 45  t;          /* E
14c0: 73 74 69 6d 61 74 65 64 20 6e 75 6d 62 65 72 20  stimated number 
14d0: 6f 66 20 6f 75 74 70 75 74 20 72 6f 77 73 20 2a  of output rows *
14e0: 2f 0a 20 20 75 6e 69 6f 6e 20 7b 0a 20 20 20 20  /.  union {.    
14f0: 73 74 72 75 63 74 20 7b 20 20 20 20 20 20 20 20  struct {        
1500: 20 20 20 20 20 20 20 2f 2a 20 49 6e 66 6f 72 6d         /* Inform
1510: 61 74 69 6f 6e 20 66 6f 72 20 69 6e 74 65 72 6e  ation for intern
1520: 61 6c 20 62 74 72 65 65 20 74 61 62 6c 65 73 20  al btree tables 
1530: 2a 2f 0a 20 20 20 20 20 20 75 31 36 20 6e 45 71  */.      u16 nEq
1540: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1550: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 71 75  /* Number of equ
1560: 61 6c 69 74 79 20 63 6f 6e 73 74 72 61 69 6e 74  ality constraint
1570: 73 20 2a 2f 0a 20 20 20 20 20 20 49 6e 64 65 78  s */.      Index
1580: 20 2a 70 49 6e 64 65 78 3b 20 20 20 20 20 20 20   *pIndex;       
1590: 20 20 2f 2a 20 49 6e 64 65 78 20 75 73 65 64 2c    /* Index used,
15a0: 20 6f 72 20 4e 55 4c 4c 20 2a 2f 0a 20 20 20 20   or NULL */.    
15b0: 7d 20 62 74 72 65 65 3b 0a 20 20 20 20 73 74 72  } btree;.    str
15c0: 75 63 74 20 7b 20 20 20 20 20 20 20 20 20 20 20  uct {           
15d0: 20 20 20 20 2f 2a 20 49 6e 66 6f 72 6d 61 74 69      /* Informati
15e0: 6f 6e 20 66 6f 72 20 76 69 72 74 75 61 6c 20 74  on for virtual t
15f0: 61 62 6c 65 73 20 2a 2f 0a 20 20 20 20 20 20 69  ables */.      i
1600: 6e 74 20 69 64 78 4e 75 6d 3b 20 20 20 20 20 20  nt idxNum;      
1610: 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 6e        /* Index n
1620: 75 6d 62 65 72 20 2a 2f 0a 20 20 20 20 20 20 75  umber */.      u
1630: 38 20 6e 65 65 64 46 72 65 65 3b 20 20 20 20 20  8 needFree;     
1640: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
1650: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 69 64   sqlite3_free(id
1660: 78 53 74 72 29 20 69 73 20 6e 65 65 64 65 64 20  xStr) is needed 
1670: 2a 2f 0a 20 20 20 20 20 20 69 38 20 69 73 4f 72  */.      i8 isOr
1680: 64 65 72 65 64 3b 20 20 20 20 20 20 20 20 20 20  dered;          
1690: 2f 2a 20 54 72 75 65 20 69 66 20 73 61 74 69 73  /* True if satis
16a0: 66 69 65 73 20 4f 52 44 45 52 20 42 59 20 2a 2f  fies ORDER BY */
16b0: 0a 20 20 20 20 20 20 75 31 36 20 6f 6d 69 74 4d  .      u16 omitM
16c0: 61 73 6b 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  ask;          /*
16d0: 20 54 65 72 6d 73 20 74 68 61 74 20 6d 61 79 20   Terms that may 
16e0: 62 65 20 6f 6d 69 74 74 65 64 20 2a 2f 0a 20 20  be omitted */.  
16f0: 20 20 20 20 63 68 61 72 20 2a 69 64 78 53 74 72      char *idxStr
1700: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e  ;          /* In
1710: 64 65 78 20 69 64 65 6e 74 69 66 69 65 72 20 73  dex identifier s
1720: 74 72 69 6e 67 20 2a 2f 0a 20 20 20 20 7d 20 76  tring */.    } v
1730: 74 61 62 3b 0a 20 20 7d 20 75 3b 0a 20 20 75 33  tab;.  } u;.  u3
1740: 32 20 77 73 46 6c 61 67 73 3b 20 20 20 20 20 20  2 wsFlags;      
1750: 20 20 20 20 2f 2a 20 57 48 45 52 45 5f 2a 20 66      /* WHERE_* f
1760: 6c 61 67 73 20 64 65 73 63 72 69 62 69 6e 67 20  lags describing 
1770: 74 68 65 20 70 6c 61 6e 20 2a 2f 0a 20 20 75 31  the plan */.  u1
1780: 36 20 6e 4c 54 65 72 6d 3b 20 20 20 20 20 20 20  6 nLTerm;       
1790: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
17a0: 20 65 6e 74 72 69 65 73 20 69 6e 20 61 4c 54 65   entries in aLTe
17b0: 72 6d 5b 5d 20 2a 2f 0a 20 20 75 31 36 20 6e 53  rm[] */.  u16 nS
17c0: 6b 69 70 3b 20 20 20 20 20 20 20 20 20 20 20 20  kip;            
17d0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 4e 55 4c  /* Number of NUL
17e0: 4c 20 61 4c 54 65 72 6d 5b 5d 20 65 6e 74 72 69  L aLTerm[] entri
17f0: 65 73 20 2a 2f 0a 20 20 2f 2a 2a 2a 2a 20 77 68  es */.  /**** wh
1800: 65 72 65 4c 6f 6f 70 58 66 65 72 28 29 20 63 6f  ereLoopXfer() co
1810: 70 69 65 73 20 66 69 65 6c 64 73 20 61 62 6f 76  pies fields abov
1820: 65 20 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  e **************
1830: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a 23 20 64 65 66  *********/.# def
1840: 69 6e 65 20 57 48 45 52 45 5f 4c 4f 4f 50 5f 58  ine WHERE_LOOP_X
1850: 46 45 52 5f 53 5a 20 6f 66 66 73 65 74 6f 66 28  FER_SZ offsetof(
1860: 57 68 65 72 65 4c 6f 6f 70 2c 6e 4c 53 6c 6f 74  WhereLoop,nLSlot
1870: 29 0a 20 20 75 31 36 20 6e 4c 53 6c 6f 74 3b 20  ).  u16 nLSlot; 
1880: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1890: 62 65 72 20 6f 66 20 73 6c 6f 74 73 20 61 6c 6c  ber of slots all
18a0: 6f 63 61 74 65 64 20 66 6f 72 20 61 4c 54 65 72  ocated for aLTer
18b0: 6d 5b 5d 20 2a 2f 0a 20 20 57 68 65 72 65 54 65  m[] */.  WhereTe
18c0: 72 6d 20 2a 2a 61 4c 54 65 72 6d 3b 20 20 20 2f  rm **aLTerm;   /
18d0: 2a 20 57 68 65 72 65 54 65 72 6d 73 20 75 73 65  * WhereTerms use
18e0: 64 20 2a 2f 0a 20 20 57 68 65 72 65 4c 6f 6f 70  d */.  WhereLoop
18f0: 20 2a 70 4e 65 78 74 4c 6f 6f 70 3b 20 2f 2a 20   *pNextLoop; /* 
1900: 4e 65 78 74 20 57 68 65 72 65 4c 6f 6f 70 20 6f  Next WhereLoop o
1910: 62 6a 65 63 74 20 69 6e 20 74 68 65 20 57 68 65  bject in the Whe
1920: 72 65 43 6c 61 75 73 65 20 2a 2f 0a 20 20 57 68  reClause */.  Wh
1930: 65 72 65 54 65 72 6d 20 2a 61 4c 54 65 72 6d 53  ereTerm *aLTermS
1940: 70 61 63 65 5b 33 5d 3b 20 20 2f 2a 20 49 6e 69  pace[3];  /* Ini
1950: 74 69 61 6c 20 61 4c 54 65 72 6d 5b 5d 20 73 70  tial aLTerm[] sp
1960: 61 63 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 54 68  ace */.};../* Th
1970: 69 73 20 6f 62 6a 65 63 74 20 68 6f 6c 64 73 20  is object holds 
1980: 74 68 65 20 70 72 65 72 65 71 75 69 73 69 74 65  the prerequisite
1990: 73 20 61 6e 64 20 74 68 65 20 63 6f 73 74 20 6f  s and the cost o
19a0: 66 20 72 75 6e 6e 69 6e 67 20 61 0a 2a 2a 20 73  f running a.** s
19b0: 75 62 71 75 65 72 79 20 6f 6e 20 6f 6e 65 20 6f  ubquery on one o
19c0: 70 65 72 61 6e 64 20 6f 66 20 61 6e 20 4f 52 20  perand of an OR 
19d0: 6f 70 65 72 61 74 6f 72 20 69 6e 20 74 68 65 20  operator in the 
19e0: 57 48 45 52 45 20 63 6c 61 75 73 65 2e 0a 2a 2a  WHERE clause..**
19f0: 20 53 65 65 20 57 68 65 72 65 4f 72 53 65 74 20   See WhereOrSet 
1a00: 66 6f 72 20 61 64 64 69 74 69 6f 6e 61 6c 20 69  for additional i
1a10: 6e 66 6f 72 6d 61 74 69 6f 6e 20 0a 2a 2f 0a 73  nformation .*/.s
1a20: 74 72 75 63 74 20 57 68 65 72 65 4f 72 43 6f 73  truct WhereOrCos
1a30: 74 20 7b 0a 20 20 42 69 74 6d 61 73 6b 20 70 72  t {.  Bitmask pr
1a40: 65 72 65 71 3b 20 20 20 20 20 2f 2a 20 50 72 65  ereq;     /* Pre
1a50: 72 65 71 75 69 73 69 74 65 73 20 2a 2f 0a 20 20  requisites */.  
1a60: 4c 6f 67 45 73 74 20 72 52 75 6e 3b 20 20 20 20  LogEst rRun;    
1a70: 20 20 20 20 2f 2a 20 43 6f 73 74 20 6f 66 20 72      /* Cost of r
1a80: 75 6e 6e 69 6e 67 20 74 68 69 73 20 73 75 62 71  unning this subq
1a90: 75 65 72 79 20 2a 2f 0a 20 20 4c 6f 67 45 73 74  uery */.  LogEst
1aa0: 20 6e 4f 75 74 3b 20 20 20 20 20 20 20 20 2f 2a   nOut;        /*
1ab0: 20 4e 75 6d 62 65 72 20 6f 66 20 6f 75 74 70 75   Number of outpu
1ac0: 74 73 20 66 6f 72 20 74 68 69 73 20 73 75 62 71  ts for this subq
1ad0: 75 65 72 79 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 54  uery */.};../* T
1ae0: 68 65 20 57 68 65 72 65 4f 72 53 65 74 20 6f 62  he WhereOrSet ob
1af0: 6a 65 63 74 20 68 6f 6c 64 73 20 61 20 73 65 74  ject holds a set
1b00: 20 6f 66 20 70 6f 73 73 69 62 6c 65 20 57 68 65   of possible Whe
1b10: 72 65 4f 72 43 6f 73 74 73 20 74 68 61 74 0a 2a  reOrCosts that.*
1b20: 2a 20 63 6f 72 72 65 73 70 6f 6e 64 20 74 6f 20  * correspond to 
1b30: 74 68 65 20 73 75 62 71 75 65 72 79 28 73 29 20  the subquery(s) 
1b40: 6f 66 20 4f 52 2d 63 6c 61 75 73 65 20 70 72 6f  of OR-clause pro
1b50: 63 65 73 73 69 6e 67 2e 20 20 4f 6e 6c 79 20 74  cessing.  Only t
1b60: 68 65 0a 2a 2a 20 62 65 73 74 20 4e 5f 4f 52 5f  he.** best N_OR_
1b70: 43 4f 53 54 20 65 6c 65 6d 65 6e 74 73 20 61 72  COST elements ar
1b80: 65 20 72 65 74 61 69 6e 65 64 2e 0a 2a 2f 0a 23  e retained..*/.#
1b90: 64 65 66 69 6e 65 20 4e 5f 4f 52 5f 43 4f 53 54  define N_OR_COST
1ba0: 20 33 0a 73 74 72 75 63 74 20 57 68 65 72 65 4f   3.struct WhereO
1bb0: 72 53 65 74 20 7b 0a 20 20 75 31 36 20 6e 3b 20  rSet {.  u16 n; 
1bc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1bd0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
1be0: 66 20 76 61 6c 69 64 20 61 5b 5d 20 65 6e 74 72  f valid a[] entr
1bf0: 69 65 73 20 2a 2f 0a 20 20 57 68 65 72 65 4f 72  ies */.  WhereOr
1c00: 43 6f 73 74 20 61 5b 4e 5f 4f 52 5f 43 4f 53 54  Cost a[N_OR_COST
1c10: 5d 3b 20 20 20 2f 2a 20 53 65 74 20 6f 66 20 62  ];   /* Set of b
1c20: 65 73 74 20 63 6f 73 74 73 20 2a 2f 0a 7d 3b 0a  est costs */.};.
1c30: 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 69 6e 73 74  ./*.** Each inst
1c40: 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62 6a  ance of this obj
1c50: 65 63 74 20 68 6f 6c 64 73 20 61 20 73 65 71 75  ect holds a sequ
1c60: 65 6e 63 65 20 6f 66 20 57 68 65 72 65 4c 6f 6f  ence of WhereLoo
1c70: 70 20 6f 62 6a 65 63 74 73 0a 2a 2a 20 74 68 61  p objects.** tha
1c80: 74 20 69 6d 70 6c 65 6d 65 6e 74 20 73 6f 6d 65  t implement some
1c90: 20 6f 72 20 61 6c 6c 20 6f 66 20 61 20 71 75 65   or all of a que
1ca0: 72 79 20 70 6c 61 6e 2e 0a 2a 2a 0a 2a 2a 20 54  ry plan..**.** T
1cb0: 68 69 6e 6b 20 6f 66 20 65 61 63 68 20 57 68 65  hink of each Whe
1cc0: 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 20 61 73  reLoop object as
1cd0: 20 61 20 6e 6f 64 65 20 69 6e 20 61 20 67 72 61   a node in a gra
1ce0: 70 68 20 77 69 74 68 20 61 72 63 73 0a 2a 2a 20  ph with arcs.** 
1cf0: 73 68 6f 77 69 6e 67 20 64 65 70 65 6e 64 65 6e  showing dependen
1d00: 63 69 65 73 20 61 6e 64 20 63 6f 73 74 73 20 66  cies and costs f
1d10: 6f 72 20 74 72 61 76 65 6c 6c 69 6e 67 20 62 65  or travelling be
1d20: 74 77 65 65 6e 20 6e 6f 64 65 73 2e 20 20 28 54  tween nodes.  (T
1d30: 68 61 74 20 69 73 0a 2a 2a 20 6e 6f 74 20 61 20  hat is.** not a 
1d40: 63 6f 6d 70 6c 65 74 65 6c 79 20 61 63 63 75 72  completely accur
1d50: 61 74 65 20 64 65 73 63 72 69 70 74 69 6f 6e 20  ate description 
1d60: 62 65 63 61 75 73 65 20 57 68 65 72 65 4c 6f 6f  because WhereLoo
1d70: 70 20 63 6f 73 74 73 20 61 72 65 20 61 0a 2a 2a  p costs are a.**
1d80: 20 76 65 63 74 6f 72 2c 20 6e 6f 74 20 61 20 73   vector, not a s
1d90: 63 61 6c 61 72 2c 20 61 6e 64 20 62 65 63 61 75  calar, and becau
1da0: 73 65 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20  se dependencies 
1db0: 61 72 65 20 6d 61 6e 79 2d 74 6f 2d 6f 6e 65 2c  are many-to-one,
1dc0: 20 6e 6f 74 0a 2a 2a 20 6f 6e 65 2d 74 6f 2d 6f   not.** one-to-o
1dd0: 6e 65 20 61 73 20 61 72 65 20 67 72 61 70 68 20  ne as are graph 
1de0: 6e 6f 64 65 73 2e 20 20 42 75 74 20 69 74 20 69  nodes.  But it i
1df0: 73 20 61 20 75 73 65 66 75 6c 20 76 69 73 75 61  s a useful visua
1e00: 6c 69 7a 61 74 69 6f 6e 20 61 69 64 2e 29 0a 2a  lization aid.).*
1e10: 2a 20 54 68 65 6e 20 61 20 57 68 65 72 65 50 61  * Then a WherePa
1e20: 74 68 20 6f 62 6a 65 63 74 20 69 73 20 61 20 70  th object is a p
1e30: 61 74 68 20 74 68 72 6f 75 67 68 20 74 68 65 20  ath through the 
1e40: 67 72 61 70 68 20 74 68 61 74 20 76 69 73 69 74  graph that visit
1e50: 73 20 73 6f 6d 65 0a 2a 2a 20 6f 72 20 61 6c 6c  s some.** or all
1e60: 20 6f 66 20 74 68 65 20 57 68 65 72 65 4c 6f 6f   of the WhereLoo
1e70: 70 20 6f 62 6a 65 63 74 73 20 6f 6e 63 65 2e 0a  p objects once..
1e80: 2a 2a 0a 2a 2a 20 54 68 65 20 22 73 6f 6c 76 65  **.** The "solve
1e90: 72 22 20 77 6f 72 6b 73 20 62 79 20 63 72 65 61  r" works by crea
1ea0: 74 69 6e 67 20 74 68 65 20 4e 20 62 65 73 74 20  ting the N best 
1eb0: 57 68 65 72 65 50 61 74 68 20 6f 62 6a 65 63 74  WherePath object
1ec0: 73 20 6f 66 20 6c 65 6e 67 74 68 0a 2a 2a 20 31  s of length.** 1
1ed0: 2e 20 20 54 68 65 6e 20 75 73 69 6e 67 20 74 68  .  Then using th
1ee0: 6f 73 65 20 61 73 20 61 20 62 61 73 69 73 20 74  ose as a basis t
1ef0: 6f 20 63 6f 6d 70 75 74 65 20 74 68 65 20 4e 20  o compute the N 
1f00: 62 65 73 74 20 57 68 65 72 65 50 61 74 68 20 6f  best WherePath o
1f10: 62 6a 65 63 74 73 0a 2a 2a 20 6f 66 20 6c 65 6e  bjects.** of len
1f20: 67 74 68 20 32 2e 20 20 41 6e 64 20 73 6f 20 66  gth 2.  And so f
1f30: 6f 72 74 68 20 75 6e 74 69 6c 20 74 68 65 20 6c  orth until the l
1f40: 65 6e 67 74 68 20 6f 66 20 57 68 65 72 65 50 61  ength of WherePa
1f50: 74 68 73 20 65 71 75 61 6c 73 20 74 68 65 0a 2a  ths equals the.*
1f60: 2a 20 6e 75 6d 62 65 72 20 6f 66 20 6e 6f 64 65  * number of node
1f70: 73 20 69 6e 20 74 68 65 20 46 52 4f 4d 20 63 6c  s in the FROM cl
1f80: 61 75 73 65 2e 20 20 54 68 65 20 62 65 73 74 20  ause.  The best 
1f90: 28 6c 6f 77 65 73 74 20 63 6f 73 74 29 20 57 68  (lowest cost) Wh
1fa0: 65 72 65 50 61 74 68 0a 2a 2a 20 61 74 20 74 68  erePath.** at th
1fb0: 65 20 65 6e 64 20 69 73 20 74 68 65 20 63 68 6f  e end is the cho
1fc0: 73 65 6e 20 71 75 65 72 79 20 70 6c 61 6e 2e 0a  sen query plan..
1fd0: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 50  */.struct WhereP
1fe0: 61 74 68 20 7b 0a 20 20 42 69 74 6d 61 73 6b 20  ath {.  Bitmask 
1ff0: 6d 61 73 6b 4c 6f 6f 70 3b 20 20 20 20 20 2f 2a  maskLoop;     /*
2000: 20 42 69 74 6d 61 73 6b 20 6f 66 20 61 6c 6c 20   Bitmask of all 
2010: 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74  WhereLoop object
2020: 73 20 69 6e 20 74 68 69 73 20 70 61 74 68 20 2a  s in this path *
2030: 2f 0a 20 20 42 69 74 6d 61 73 6b 20 72 65 76 4c  /.  Bitmask revL
2040: 6f 6f 70 3b 20 20 20 20 20 20 2f 2a 20 61 4c 6f  oop;      /* aLo
2050: 6f 70 5b 5d 73 20 74 68 61 74 20 73 68 6f 75 6c  op[]s that shoul
2060: 64 20 62 65 20 72 65 76 65 72 73 65 64 20 66 6f  d be reversed fo
2070: 72 20 4f 52 44 45 52 20 42 59 20 2a 2f 0a 20 20  r ORDER BY */.  
2080: 4c 6f 67 45 73 74 20 6e 52 6f 77 3b 20 20 20 20  LogEst nRow;    
2090: 20 20 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74        /* Estimat
20a0: 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77  ed number of row
20b0: 73 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74  s generated by t
20c0: 68 69 73 20 70 61 74 68 20 2a 2f 0a 20 20 4c 6f  his path */.  Lo
20d0: 67 45 73 74 20 72 43 6f 73 74 3b 20 20 20 20 20  gEst rCost;     
20e0: 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 63 6f 73      /* Total cos
20f0: 74 20 6f 66 20 74 68 69 73 20 70 61 74 68 20 2a  t of this path *
2100: 2f 0a 20 20 4c 6f 67 45 73 74 20 72 55 6e 73 6f  /.  LogEst rUnso
2110: 72 74 65 64 3b 20 20 20 20 20 2f 2a 20 54 6f 74  rted;     /* Tot
2120: 61 6c 20 63 6f 73 74 20 6f 66 20 74 68 69 73 20  al cost of this 
2130: 70 61 74 68 20 69 67 6e 6f 72 69 6e 67 20 73 6f  path ignoring so
2140: 72 74 69 6e 67 20 63 6f 73 74 73 20 2a 2f 0a 20  rting costs */. 
2150: 20 69 38 20 69 73 4f 72 64 65 72 65 64 3b 20 20   i8 isOrdered;  
2160: 20 20 20 20 20 20 20 2f 2a 20 4e 6f 2e 20 6f 66         /* No. of
2170: 20 4f 52 44 45 52 20 42 59 20 74 65 72 6d 73 20   ORDER BY terms 
2180: 73 61 74 69 73 66 69 65 64 2e 20 2d 31 20 66 6f  satisfied. -1 fo
2190: 72 20 75 6e 6b 6e 6f 77 6e 20 2a 2f 0a 20 20 57  r unknown */.  W
21a0: 68 65 72 65 4c 6f 6f 70 20 2a 2a 61 4c 6f 6f 70  hereLoop **aLoop
21b0: 3b 20 20 20 20 2f 2a 20 41 72 72 61 79 20 6f 66  ;    /* Array of
21c0: 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63   WhereLoop objec
21d0: 74 73 20 69 6d 70 6c 65 6d 65 6e 74 69 6e 67 20  ts implementing 
21e0: 74 68 69 73 20 70 61 74 68 20 2a 2f 0a 7d 3b 0a  this path */.};.
21f0: 0a 2f 2a 0a 2a 2a 20 54 68 65 20 71 75 65 72 79  ./*.** The query
2200: 20 67 65 6e 65 72 61 74 6f 72 20 75 73 65 73 20   generator uses 
2210: 61 6e 20 61 72 72 61 79 20 6f 66 20 69 6e 73 74  an array of inst
2220: 61 6e 63 65 73 20 6f 66 20 74 68 69 73 20 73 74  ances of this st
2230: 72 75 63 74 75 72 65 20 74 6f 0a 2a 2a 20 68 65  ructure to.** he
2240: 6c 70 20 69 74 20 61 6e 61 6c 79 7a 65 20 74 68  lp it analyze th
2250: 65 20 73 75 62 65 78 70 72 65 73 73 69 6f 6e 73  e subexpressions
2260: 20 6f 66 20 74 68 65 20 57 48 45 52 45 20 63 6c   of the WHERE cl
2270: 61 75 73 65 2e 20 20 45 61 63 68 20 57 48 45 52  ause.  Each WHER
2280: 45 0a 2a 2a 20 63 6c 61 75 73 65 20 73 75 62 65  E.** clause sube
2290: 78 70 72 65 73 73 69 6f 6e 20 69 73 20 73 65 70  xpression is sep
22a0: 61 72 61 74 65 64 20 66 72 6f 6d 20 74 68 65 20  arated from the 
22b0: 6f 74 68 65 72 73 20 62 79 20 41 4e 44 20 6f 70  others by AND op
22c0: 65 72 61 74 6f 72 73 2c 0a 2a 2a 20 75 73 75 61  erators,.** usua
22d0: 6c 6c 79 2c 20 6f 72 20 73 6f 6d 65 74 69 6d 65  lly, or sometime
22e0: 73 20 73 75 62 65 78 70 72 65 73 73 69 6f 6e 73  s subexpressions
22f0: 20 73 65 70 61 72 61 74 65 64 20 62 79 20 4f 52   separated by OR
2300: 2e 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 57 68 65 72  ..**.** All Wher
2310: 65 54 65 72 6d 73 20 61 72 65 20 63 6f 6c 6c 65  eTerms are colle
2320: 63 74 65 64 20 69 6e 74 6f 20 61 20 73 69 6e 67  cted into a sing
2330: 6c 65 20 57 68 65 72 65 43 6c 61 75 73 65 20 73  le WhereClause s
2340: 74 72 75 63 74 75 72 65 2e 20 20 0a 2a 2a 20 54  tructure.  .** T
2350: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 69 64 65  he following ide
2360: 6e 74 69 74 79 20 68 6f 6c 64 73 3a 0a 2a 2a 0a  ntity holds:.**.
2370: 2a 2a 20 20 20 20 20 20 20 20 57 68 65 72 65 54  **        WhereT
2380: 65 72 6d 2e 70 57 43 2d 3e 61 5b 57 68 65 72 65  erm.pWC->a[Where
2390: 54 65 72 6d 2e 69 64 78 5d 20 3d 3d 20 57 68 65  Term.idx] == Whe
23a0: 72 65 54 65 72 6d 0a 2a 2a 0a 2a 2a 20 57 68 65  reTerm.**.** Whe
23b0: 6e 20 61 20 74 65 72 6d 20 69 73 20 6f 66 20 74  n a term is of t
23c0: 68 65 20 66 6f 72 6d 3a 0a 2a 2a 0a 2a 2a 20 20  he form:.**.**  
23d0: 20 20 20 20 20 20 20 20 20 20 20 20 58 20 3c 6f              X <o
23e0: 70 3e 20 3c 65 78 70 72 3e 0a 2a 2a 0a 2a 2a 20  p> <expr>.**.** 
23f0: 77 68 65 72 65 20 58 20 69 73 20 61 20 63 6f 6c  where X is a col
2400: 75 6d 6e 20 6e 61 6d 65 20 61 6e 64 20 3c 6f 70  umn name and <op
2410: 3e 20 69 73 20 6f 6e 65 20 6f 66 20 63 65 72 74  > is one of cert
2420: 61 69 6e 20 6f 70 65 72 61 74 6f 72 73 2c 0a 2a  ain operators,.*
2430: 2a 20 74 68 65 6e 20 57 68 65 72 65 54 65 72 6d  * then WhereTerm
2440: 2e 6c 65 66 74 43 75 72 73 6f 72 20 61 6e 64 20  .leftCursor and 
2450: 57 68 65 72 65 54 65 72 6d 2e 75 2e 6c 65 66 74  WhereTerm.u.left
2460: 43 6f 6c 75 6d 6e 20 72 65 63 6f 72 64 20 74 68  Column record th
2470: 65 0a 2a 2a 20 63 75 72 73 6f 72 20 6e 75 6d 62  e.** cursor numb
2480: 65 72 20 61 6e 64 20 63 6f 6c 75 6d 6e 20 6e 75  er and column nu
2490: 6d 62 65 72 20 66 6f 72 20 58 2e 20 20 57 68 65  mber for X.  Whe
24a0: 72 65 54 65 72 6d 2e 65 4f 70 65 72 61 74 6f 72  reTerm.eOperator
24b0: 20 72 65 63 6f 72 64 73 0a 2a 2a 20 74 68 65 20   records.** the 
24c0: 3c 6f 70 3e 20 75 73 69 6e 67 20 61 20 62 69 74  <op> using a bit
24d0: 6d 61 73 6b 20 65 6e 63 6f 64 69 6e 67 20 64 65  mask encoding de
24e0: 66 69 6e 65 64 20 62 79 20 57 4f 5f 78 78 78 20  fined by WO_xxx 
24f0: 62 65 6c 6f 77 2e 20 20 54 68 65 0a 2a 2a 20 75  below.  The.** u
2500: 73 65 20 6f 66 20 61 20 62 69 74 6d 61 73 6b 20  se of a bitmask 
2510: 65 6e 63 6f 64 69 6e 67 20 66 6f 72 20 74 68 65  encoding for the
2520: 20 6f 70 65 72 61 74 6f 72 20 61 6c 6c 6f 77 73   operator allows
2530: 20 75 73 20 74 6f 20 73 65 61 72 63 68 0a 2a 2a   us to search.**
2540: 20 71 75 69 63 6b 6c 79 20 66 6f 72 20 74 65 72   quickly for ter
2550: 6d 73 20 74 68 61 74 20 6d 61 74 63 68 20 61 6e  ms that match an
2560: 79 20 6f 66 20 73 65 76 65 72 61 6c 20 64 69 66  y of several dif
2570: 66 65 72 65 6e 74 20 6f 70 65 72 61 74 6f 72 73  ferent operators
2580: 2e 0a 2a 2a 0a 2a 2a 20 41 20 57 68 65 72 65 54  ..**.** A WhereT
2590: 65 72 6d 20 6d 69 67 68 74 20 61 6c 73 6f 20 62  erm might also b
25a0: 65 20 74 77 6f 20 6f 72 20 6d 6f 72 65 20 73 75  e two or more su
25b0: 62 74 65 72 6d 73 20 63 6f 6e 6e 65 63 74 65 64  bterms connected
25c0: 20 62 79 20 4f 52 3a 0a 2a 2a 0a 2a 2a 20 20 20   by OR:.**.**   
25d0: 20 20 20 20 20 20 28 74 31 2e 58 20 3c 6f 70 3e        (t1.X <op>
25e0: 20 3c 65 78 70 72 3e 29 20 4f 52 20 28 74 31 2e   <expr>) OR (t1.
25f0: 59 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 29 20 4f  Y <op> <expr>) O
2600: 52 20 2e 2e 2e 2e 0a 2a 2a 0a 2a 2a 20 49 6e 20  R .....**.** In 
2610: 74 68 69 73 20 73 65 63 6f 6e 64 20 63 61 73 65  this second case
2620: 2c 20 77 74 46 6c 61 67 20 68 61 73 20 74 68 65  , wtFlag has the
2630: 20 54 45 52 4d 5f 4f 52 49 4e 46 4f 20 62 69 74   TERM_ORINFO bit
2640: 20 73 65 74 20 61 6e 64 20 65 4f 70 65 72 61 74   set and eOperat
2650: 6f 72 3d 3d 57 4f 5f 4f 52 0a 2a 2a 20 61 6e 64  or==WO_OR.** and
2660: 20 74 68 65 20 57 68 65 72 65 54 65 72 6d 2e 75   the WhereTerm.u
2670: 2e 70 4f 72 49 6e 66 6f 20 66 69 65 6c 64 20 70  .pOrInfo field p
2680: 6f 69 6e 74 73 20 74 6f 20 61 75 78 69 6c 69 61  oints to auxilia
2690: 72 79 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 74  ry information t
26a0: 68 61 74 0a 2a 2a 20 69 73 20 63 6f 6c 6c 65 63  hat.** is collec
26b0: 74 65 64 20 61 62 6f 75 74 20 74 68 65 20 4f 52  ted about the OR
26c0: 20 63 6c 61 75 73 65 2e 0a 2a 2a 0a 2a 2a 20 49   clause..**.** I
26d0: 66 20 61 20 74 65 72 6d 20 69 6e 20 74 68 65 20  f a term in the 
26e0: 57 48 45 52 45 20 63 6c 61 75 73 65 20 64 6f 65  WHERE clause doe
26f0: 73 20 6e 6f 74 20 6d 61 74 63 68 20 65 69 74 68  s not match eith
2700: 65 72 20 6f 66 20 74 68 65 20 74 77 6f 20 70 72  er of the two pr
2710: 65 76 69 6f 75 73 0a 2a 2a 20 63 61 74 65 67 6f  evious.** catego
2720: 72 69 65 73 2c 20 74 68 65 6e 20 65 4f 70 65 72  ries, then eOper
2730: 61 74 6f 72 3d 3d 30 2e 20 20 54 68 65 20 57 68  ator==0.  The Wh
2740: 65 72 65 54 65 72 6d 2e 70 45 78 70 72 20 66 69  ereTerm.pExpr fi
2750: 65 6c 64 20 69 73 20 73 74 69 6c 6c 20 73 65 74  eld is still set
2760: 0a 2a 2a 20 74 6f 20 74 68 65 20 6f 72 69 67 69  .** to the origi
2770: 6e 61 6c 20 73 75 62 65 78 70 72 65 73 73 69 6f  nal subexpressio
2780: 6e 20 63 6f 6e 74 65 6e 74 20 61 6e 64 20 77 74  n content and wt
2790: 46 6c 61 67 73 20 69 73 20 73 65 74 20 75 70 20  Flags is set up 
27a0: 61 70 70 72 6f 70 72 69 61 74 65 6c 79 0a 2a 2a  appropriately.**
27b0: 20 62 75 74 20 6e 6f 20 6f 74 68 65 72 20 66 69   but no other fi
27c0: 65 6c 64 73 20 69 6e 20 74 68 65 20 57 68 65 72  elds in the Wher
27d0: 65 54 65 72 6d 20 6f 62 6a 65 63 74 20 61 72 65  eTerm object are
27e0: 20 6d 65 61 6e 69 6e 67 66 75 6c 2e 0a 2a 2a 0a   meaningful..**.
27f0: 2a 2a 20 57 68 65 6e 20 65 4f 70 65 72 61 74 6f  ** When eOperato
2800: 72 21 3d 30 2c 20 70 72 65 72 65 71 52 69 67 68  r!=0, prereqRigh
2810: 74 20 61 6e 64 20 70 72 65 72 65 71 41 6c 6c 20  t and prereqAll 
2820: 72 65 63 6f 72 64 20 73 65 74 73 20 6f 66 20 63  record sets of c
2830: 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 2c 0a 2a  ursor numbers,.*
2840: 2a 20 62 75 74 20 74 68 65 79 20 64 6f 20 73 6f  * but they do so
2850: 20 69 6e 64 69 72 65 63 74 6c 79 2e 20 20 41 20   indirectly.  A 
2860: 73 69 6e 67 6c 65 20 57 68 65 72 65 4d 61 73 6b  single WhereMask
2870: 53 65 74 20 73 74 72 75 63 74 75 72 65 20 74 72  Set structure tr
2880: 61 6e 73 6c 61 74 65 73 0a 2a 2a 20 63 75 72 73  anslates.** curs
2890: 6f 72 20 6e 75 6d 62 65 72 20 69 6e 74 6f 20 62  or number into b
28a0: 69 74 73 20 61 6e 64 20 74 68 65 20 74 72 61 6e  its and the tran
28b0: 73 6c 61 74 65 64 20 62 69 74 20 69 73 20 73 74  slated bit is st
28c0: 6f 72 65 64 20 69 6e 20 74 68 65 20 70 72 65 72  ored in the prer
28d0: 65 71 0a 2a 2a 20 66 69 65 6c 64 73 2e 20 20 54  eq.** fields.  T
28e0: 68 65 20 74 72 61 6e 73 6c 61 74 69 6f 6e 20 69  he translation i
28f0: 73 20 75 73 65 64 20 69 6e 20 6f 72 64 65 72 20  s used in order 
2900: 74 6f 20 6d 61 78 69 6d 69 7a 65 20 74 68 65 20  to maximize the 
2910: 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 62 69 74  number of.** bit
2920: 73 20 74 68 61 74 20 77 69 6c 6c 20 66 69 74 20  s that will fit 
2930: 69 6e 20 61 20 42 69 74 6d 61 73 6b 2e 20 20 54  in a Bitmask.  T
2940: 68 65 20 56 44 42 45 20 63 75 72 73 6f 72 20 6e  he VDBE cursor n
2950: 75 6d 62 65 72 73 20 6d 69 67 68 74 20 62 65 0a  umbers might be.
2960: 2a 2a 20 73 70 72 65 61 64 20 6f 75 74 20 6f 76  ** spread out ov
2970: 65 72 20 74 68 65 20 6e 6f 6e 2d 6e 65 67 61 74  er the non-negat
2980: 69 76 65 20 69 6e 74 65 67 65 72 73 2e 20 20 46  ive integers.  F
2990: 6f 72 20 65 78 61 6d 70 6c 65 2c 20 74 68 65 20  or example, the 
29a0: 63 75 72 73 6f 72 0a 2a 2a 20 6e 75 6d 62 65 72  cursor.** number
29b0: 73 20 6d 69 67 68 74 20 62 65 20 33 2c 20 38 2c  s might be 3, 8,
29c0: 20 39 2c 20 31 30 2c 20 32 30 2c 20 32 33 2c 20   9, 10, 20, 23, 
29d0: 34 31 2c 20 61 6e 64 20 34 35 2e 20 20 54 68 65  41, and 45.  The
29e0: 20 57 68 65 72 65 4d 61 73 6b 53 65 74 0a 2a 2a   WhereMaskSet.**
29f0: 20 74 72 61 6e 73 6c 61 74 65 73 20 74 68 65 73   translates thes
2a00: 65 20 73 70 61 72 73 65 20 63 75 72 73 6f 72 20  e sparse cursor 
2a10: 6e 75 6d 62 65 72 73 20 69 6e 74 6f 20 63 6f 6e  numbers into con
2a20: 73 65 63 75 74 69 76 65 20 69 6e 74 65 67 65 72  secutive integer
2a30: 73 0a 2a 2a 20 62 65 67 69 6e 6e 69 6e 67 20 77  s.** beginning w
2a40: 69 74 68 20 30 20 69 6e 20 6f 72 64 65 72 20 74  ith 0 in order t
2a50: 6f 20 6d 61 6b 65 20 74 68 65 20 62 65 73 74 20  o make the best 
2a60: 70 6f 73 73 69 62 6c 65 20 75 73 65 20 6f 66 20  possible use of 
2a70: 74 68 65 20 61 76 61 69 6c 61 62 6c 65 0a 2a 2a  the available.**
2a80: 20 62 69 74 73 20 69 6e 20 74 68 65 20 42 69 74   bits in the Bit
2a90: 6d 61 73 6b 2e 20 20 53 6f 2c 20 69 6e 20 74 68  mask.  So, in th
2aa0: 65 20 65 78 61 6d 70 6c 65 20 61 62 6f 76 65 2c  e example above,
2ab0: 20 74 68 65 20 63 75 72 73 6f 72 20 6e 75 6d 62   the cursor numb
2ac0: 65 72 73 0a 2a 2a 20 77 6f 75 6c 64 20 62 65 20  ers.** would be 
2ad0: 6d 61 70 70 65 64 20 69 6e 74 6f 20 69 6e 74 65  mapped into inte
2ae0: 67 65 72 73 20 30 20 74 68 72 6f 75 67 68 20 37  gers 0 through 7
2af0: 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6e 75 6d 62  ..**.** The numb
2b00: 65 72 20 6f 66 20 74 65 72 6d 73 20 69 6e 20 61  er of terms in a
2b10: 20 6a 6f 69 6e 20 69 73 20 6c 69 6d 69 74 65 64   join is limited
2b20: 20 62 79 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   by the number o
2b30: 66 20 62 69 74 73 0a 2a 2a 20 69 6e 20 70 72 65  f bits.** in pre
2b40: 72 65 71 52 69 67 68 74 20 61 6e 64 20 70 72 65  reqRight and pre
2b50: 72 65 71 41 6c 6c 2e 20 20 54 68 65 20 64 65 66  reqAll.  The def
2b60: 61 75 6c 74 20 69 73 20 36 34 20 62 69 74 73 2c  ault is 64 bits,
2b70: 20 68 65 6e 63 65 20 53 51 4c 69 74 65 0a 2a 2a   hence SQLite.**
2b80: 20 69 73 20 6f 6e 6c 79 20 61 62 6c 65 20 74 6f   is only able to
2b90: 20 70 72 6f 63 65 73 73 20 6a 6f 69 6e 73 20 77   process joins w
2ba0: 69 74 68 20 36 34 20 6f 72 20 66 65 77 65 72 20  ith 64 or fewer 
2bb0: 74 61 62 6c 65 73 2e 0a 2a 2f 0a 73 74 72 75 63  tables..*/.struc
2bc0: 74 20 57 68 65 72 65 54 65 72 6d 20 7b 0a 20 20  t WhereTerm {.  
2bd0: 45 78 70 72 20 2a 70 45 78 70 72 3b 20 20 20 20  Expr *pExpr;    
2be0: 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74          /* Point
2bf0: 65 72 20 74 6f 20 74 68 65 20 73 75 62 65 78 70  er to the subexp
2c00: 72 65 73 73 69 6f 6e 20 74 68 61 74 20 69 73 20  ression that is 
2c10: 74 68 69 73 20 74 65 72 6d 20 2a 2f 0a 20 20 69  this term */.  i
2c20: 6e 74 20 69 50 61 72 65 6e 74 3b 20 20 20 20 20  nt iParent;     
2c30: 20 20 20 20 20 20 20 2f 2a 20 44 69 73 61 62 6c         /* Disabl
2c40: 65 20 70 57 43 2d 3e 61 5b 69 50 61 72 65 6e 74  e pWC->a[iParent
2c50: 5d 20 77 68 65 6e 20 74 68 69 73 20 74 65 72 6d  ] when this term
2c60: 20 64 69 73 61 62 6c 65 64 20 2a 2f 0a 20 20 69   disabled */.  i
2c70: 6e 74 20 6c 65 66 74 43 75 72 73 6f 72 3b 20 20  nt leftCursor;  
2c80: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72         /* Cursor
2c90: 20 6e 75 6d 62 65 72 20 6f 66 20 58 20 69 6e 20   number of X in 
2ca0: 22 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 22 20  "X <op> <expr>" 
2cb0: 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b 0a 20 20 20  */.  union {.   
2cc0: 20 69 6e 74 20 6c 65 66 74 43 6f 6c 75 6d 6e 3b   int leftColumn;
2cd0: 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75           /* Colu
2ce0: 6d 6e 20 6e 75 6d 62 65 72 20 6f 66 20 58 20 69  mn number of X i
2cf0: 6e 20 22 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e  n "X <op> <expr>
2d00: 22 20 2a 2f 0a 20 20 20 20 57 68 65 72 65 4f 72  " */.    WhereOr
2d10: 49 6e 66 6f 20 2a 70 4f 72 49 6e 66 6f 3b 20 20  Info *pOrInfo;  
2d20: 20 2f 2a 20 45 78 74 72 61 20 69 6e 66 6f 72 6d   /* Extra inform
2d30: 61 74 69 6f 6e 20 69 66 20 28 65 4f 70 65 72 61  ation if (eOpera
2d40: 74 6f 72 20 26 20 57 4f 5f 4f 52 29 21 3d 30 20  tor & WO_OR)!=0 
2d50: 2a 2f 0a 20 20 20 20 57 68 65 72 65 41 6e 64 49  */.    WhereAndI
2d60: 6e 66 6f 20 2a 70 41 6e 64 49 6e 66 6f 3b 20 2f  nfo *pAndInfo; /
2d70: 2a 20 45 78 74 72 61 20 69 6e 66 6f 72 6d 61 74  * Extra informat
2d80: 69 6f 6e 20 69 66 20 28 65 4f 70 65 72 61 74 6f  ion if (eOperato
2d90: 72 26 20 57 4f 5f 41 4e 44 29 21 3d 30 20 2a 2f  r& WO_AND)!=0 */
2da0: 0a 20 20 7d 20 75 3b 0a 20 20 4c 6f 67 45 73 74  .  } u;.  LogEst
2db0: 20 74 72 75 74 68 50 72 6f 62 3b 20 20 20 20 20   truthProb;     
2dc0: 20 20 2f 2a 20 50 72 6f 62 61 62 69 6c 69 74 79    /* Probability
2dd0: 20 6f 66 20 74 72 75 74 68 20 66 6f 72 20 74 68   of truth for th
2de0: 69 73 20 65 78 70 72 65 73 73 69 6f 6e 20 2a 2f  is expression */
2df0: 0a 20 20 75 31 36 20 65 4f 70 65 72 61 74 6f 72  .  u16 eOperator
2e00: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 20  ;          /* A 
2e10: 57 4f 5f 78 78 20 76 61 6c 75 65 20 64 65 73 63  WO_xx value desc
2e20: 72 69 62 69 6e 67 20 3c 6f 70 3e 20 2a 2f 0a 20  ribing <op> */. 
2e30: 20 75 31 36 20 77 74 46 6c 61 67 73 3b 20 20 20   u16 wtFlags;   
2e40: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 45 52 4d           /* TERM
2e50: 5f 78 78 78 20 62 69 74 20 66 6c 61 67 73 2e 20  _xxx bit flags. 
2e60: 20 53 65 65 20 62 65 6c 6f 77 20 2a 2f 0a 20 20   See below */.  
2e70: 75 38 20 6e 43 68 69 6c 64 3b 20 20 20 20 20 20  u8 nChild;      
2e80: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
2e90: 72 20 6f 66 20 63 68 69 6c 64 72 65 6e 20 74 68  r of children th
2ea0: 61 74 20 6d 75 73 74 20 64 69 73 61 62 6c 65 20  at must disable 
2eb0: 75 73 20 2a 2f 0a 20 20 75 38 20 65 4d 61 74 63  us */.  u8 eMatc
2ec0: 68 4f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20  hOp;            
2ed0: 2f 2a 20 4f 70 20 66 6f 72 20 76 74 61 62 20 4d  /* Op for vtab M
2ee0: 41 54 43 48 2f 4c 49 4b 45 2f 47 4c 4f 42 2f 52  ATCH/LIKE/GLOB/R
2ef0: 45 47 45 58 50 20 74 65 72 6d 73 20 2a 2f 0a 20  EGEXP terms */. 
2f00: 20 57 68 65 72 65 43 6c 61 75 73 65 20 2a 70 57   WhereClause *pW
2f10: 43 3b 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20  C;       /* The 
2f20: 63 6c 61 75 73 65 20 74 68 69 73 20 74 65 72 6d  clause this term
2f30: 20 69 73 20 70 61 72 74 20 6f 66 20 2a 2f 0a 20   is part of */. 
2f40: 20 42 69 74 6d 61 73 6b 20 70 72 65 72 65 71 52   Bitmask prereqR
2f50: 69 67 68 74 3b 20 20 20 20 2f 2a 20 42 69 74 6d  ight;    /* Bitm
2f60: 61 73 6b 20 6f 66 20 74 61 62 6c 65 73 20 75 73  ask of tables us
2f70: 65 64 20 62 79 20 70 45 78 70 72 2d 3e 70 52 69  ed by pExpr->pRi
2f80: 67 68 74 20 2a 2f 0a 20 20 42 69 74 6d 61 73 6b  ght */.  Bitmask
2f90: 20 70 72 65 72 65 71 41 6c 6c 3b 20 20 20 20 20   prereqAll;     
2fa0: 20 2f 2a 20 42 69 74 6d 61 73 6b 20 6f 66 20 74   /* Bitmask of t
2fb0: 61 62 6c 65 73 20 72 65 66 65 72 65 6e 63 65 64  ables referenced
2fc0: 20 62 79 20 70 45 78 70 72 20 2a 2f 0a 7d 3b 0a   by pExpr */.};.
2fd0: 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 77 65 64 20 76  ./*.** Allowed v
2fe0: 61 6c 75 65 73 20 6f 66 20 57 68 65 72 65 54 65  alues of WhereTe
2ff0: 72 6d 2e 77 74 46 6c 61 67 73 0a 2a 2f 0a 23 64  rm.wtFlags.*/.#d
3000: 65 66 69 6e 65 20 54 45 52 4d 5f 44 59 4e 41 4d  efine TERM_DYNAM
3010: 49 43 20 20 20 20 30 78 30 31 20 20 20 2f 2a 20  IC    0x01   /* 
3020: 4e 65 65 64 20 74 6f 20 63 61 6c 6c 20 73 71 6c  Need to call sql
3030: 69 74 65 33 45 78 70 72 44 65 6c 65 74 65 28 64  ite3ExprDelete(d
3040: 62 2c 20 70 45 78 70 72 29 20 2a 2f 0a 23 64 65  b, pExpr) */.#de
3050: 66 69 6e 65 20 54 45 52 4d 5f 56 49 52 54 55 41  fine TERM_VIRTUA
3060: 4c 20 20 20 20 30 78 30 32 20 20 20 2f 2a 20 41  L    0x02   /* A
3070: 64 64 65 64 20 62 79 20 74 68 65 20 6f 70 74 69  dded by the opti
3080: 6d 69 7a 65 72 2e 20 20 44 6f 20 6e 6f 74 20 63  mizer.  Do not c
3090: 6f 64 65 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  ode */.#define T
30a0: 45 52 4d 5f 43 4f 44 45 44 20 20 20 20 20 20 30  ERM_CODED      0
30b0: 78 30 34 20 20 20 2f 2a 20 54 68 69 73 20 74 65  x04   /* This te
30c0: 72 6d 20 69 73 20 61 6c 72 65 61 64 79 20 63 6f  rm is already co
30d0: 64 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  ded */.#define T
30e0: 45 52 4d 5f 43 4f 50 49 45 44 20 20 20 20 20 30  ERM_COPIED     0
30f0: 78 30 38 20 20 20 2f 2a 20 48 61 73 20 61 20 63  x08   /* Has a c
3100: 68 69 6c 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20  hild */.#define 
3110: 54 45 52 4d 5f 4f 52 49 4e 46 4f 20 20 20 20 20  TERM_ORINFO     
3120: 30 78 31 30 20 20 20 2f 2a 20 4e 65 65 64 20 74  0x10   /* Need t
3130: 6f 20 66 72 65 65 20 74 68 65 20 57 68 65 72 65  o free the Where
3140: 54 65 72 6d 2e 75 2e 70 4f 72 49 6e 66 6f 20 6f  Term.u.pOrInfo o
3150: 62 6a 65 63 74 20 2a 2f 0a 23 64 65 66 69 6e 65  bject */.#define
3160: 20 54 45 52 4d 5f 41 4e 44 49 4e 46 4f 20 20 20   TERM_ANDINFO   
3170: 20 30 78 32 30 20 20 20 2f 2a 20 4e 65 65 64 20   0x20   /* Need 
3180: 74 6f 20 66 72 65 65 20 74 68 65 20 57 68 65 72  to free the Wher
3190: 65 54 65 72 6d 2e 75 2e 70 41 6e 64 49 6e 66 6f  eTerm.u.pAndInfo
31a0: 20 6f 62 6a 20 2a 2f 0a 23 64 65 66 69 6e 65 20   obj */.#define 
31b0: 54 45 52 4d 5f 4f 52 5f 4f 4b 20 20 20 20 20 20  TERM_OR_OK      
31c0: 30 78 34 30 20 20 20 2f 2a 20 55 73 65 64 20 64  0x40   /* Used d
31d0: 75 72 69 6e 67 20 4f 52 2d 63 6c 61 75 73 65 20  uring OR-clause 
31e0: 70 72 6f 63 65 73 73 69 6e 67 20 2a 2f 0a 23 69  processing */.#i
31f0: 66 64 65 66 20 53 51 4c 49 54 45 5f 45 4e 41 42  fdef SQLITE_ENAB
3200: 4c 45 5f 53 54 41 54 33 5f 4f 52 5f 53 54 41 54  LE_STAT3_OR_STAT
3210: 34 0a 23 20 20 64 65 66 69 6e 65 20 54 45 52 4d  4.#  define TERM
3220: 5f 56 4e 55 4c 4c 20 20 20 20 30 78 38 30 20 20  _VNULL    0x80  
3230: 20 2f 2a 20 4d 61 6e 75 66 61 63 74 75 72 65 64   /* Manufactured
3240: 20 78 3e 4e 55 4c 4c 20 6f 72 20 78 3c 3d 4e 55   x>NULL or x<=NU
3250: 4c 4c 20 74 65 72 6d 20 2a 2f 0a 23 65 6c 73 65  LL term */.#else
3260: 0a 23 20 20 64 65 66 69 6e 65 20 54 45 52 4d 5f  .#  define TERM_
3270: 56 4e 55 4c 4c 20 20 20 20 30 78 30 30 20 20 20  VNULL    0x00   
3280: 2f 2a 20 44 69 73 61 62 6c 65 64 20 69 66 20 6e  /* Disabled if n
3290: 6f 74 20 75 73 69 6e 67 20 73 74 61 74 33 20 2a  ot using stat3 *
32a0: 2f 0a 23 65 6e 64 69 66 0a 23 64 65 66 69 6e 65  /.#endif.#define
32b0: 20 54 45 52 4d 5f 4c 49 4b 45 4f 50 54 20 20 20   TERM_LIKEOPT   
32c0: 20 30 78 31 30 30 20 20 2f 2a 20 56 69 72 74 75   0x100  /* Virtu
32d0: 61 6c 20 74 65 72 6d 73 20 66 72 6f 6d 20 74 68  al terms from th
32e0: 65 20 4c 49 4b 45 20 6f 70 74 69 6d 69 7a 61 74  e LIKE optimizat
32f0: 69 6f 6e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  ion */.#define T
3300: 45 52 4d 5f 4c 49 4b 45 43 4f 4e 44 20 20 20 30  ERM_LIKECOND   0
3310: 78 32 30 30 20 20 2f 2a 20 43 6f 6e 64 69 74 69  x200  /* Conditi
3320: 6f 6e 61 6c 6c 79 20 74 68 69 73 20 4c 49 4b 45  onally this LIKE
3330: 20 6f 70 65 72 61 74 6f 72 20 74 65 72 6d 20 2a   operator term *
3340: 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f 4c  /.#define TERM_L
3350: 49 4b 45 20 20 20 20 20 20 20 30 78 34 30 30 20  IKE       0x400 
3360: 20 2f 2a 20 54 68 65 20 6f 72 69 67 69 6e 61 6c   /* The original
3370: 20 4c 49 4b 45 20 6f 70 65 72 61 74 6f 72 20 2a   LIKE operator *
3380: 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f 49  /.#define TERM_I
3390: 53 20 20 20 20 20 20 20 20 20 30 78 38 30 30 20  S         0x800 
33a0: 20 2f 2a 20 54 65 72 6d 2e 70 45 78 70 72 20 69   /* Term.pExpr i
33b0: 73 20 61 6e 20 49 53 20 6f 70 65 72 61 74 6f 72  s an IS operator
33c0: 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e   */../*.** An in
33d0: 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 57 68  stance of the Wh
33e0: 65 72 65 53 63 61 6e 20 6f 62 6a 65 63 74 20 69  ereScan object i
33f0: 73 20 75 73 65 64 20 61 73 20 61 6e 20 69 74 65  s used as an ite
3400: 72 61 74 6f 72 20 66 6f 72 20 6c 6f 63 61 74 69  rator for locati
3410: 6e 67 0a 2a 2a 20 74 65 72 6d 73 20 69 6e 20 74  ng.** terms in t
3420: 68 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20  he WHERE clause 
3430: 74 68 61 74 20 61 72 65 20 75 73 65 66 75 6c 20  that are useful 
3440: 74 6f 20 74 68 65 20 71 75 65 72 79 20 70 6c 61  to the query pla
3450: 6e 6e 65 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20  nner..*/.struct 
3460: 57 68 65 72 65 53 63 61 6e 20 7b 0a 20 20 57 68  WhereScan {.  Wh
3470: 65 72 65 43 6c 61 75 73 65 20 2a 70 4f 72 69 67  ereClause *pOrig
3480: 57 43 3b 20 20 20 20 20 20 2f 2a 20 4f 72 69 67  WC;      /* Orig
3490: 69 6e 61 6c 2c 20 69 6e 6e 65 72 6d 6f 73 74 20  inal, innermost 
34a0: 57 68 65 72 65 43 6c 61 75 73 65 20 2a 2f 0a 20  WhereClause */. 
34b0: 20 57 68 65 72 65 43 6c 61 75 73 65 20 2a 70 57   WhereClause *pW
34c0: 43 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57  C;          /* W
34d0: 68 65 72 65 43 6c 61 75 73 65 20 63 75 72 72 65  hereClause curre
34e0: 6e 74 6c 79 20 62 65 69 6e 67 20 73 63 61 6e 6e  ntly being scann
34f0: 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68  ed */.  const ch
3500: 61 72 20 2a 7a 43 6f 6c 6c 4e 61 6d 65 3b 20 20  ar *zCollName;  
3510: 20 20 20 2f 2a 20 52 65 71 75 69 72 65 64 20 63     /* Required c
3520: 6f 6c 6c 61 74 69 6e 67 20 73 65 71 75 65 6e 63  ollating sequenc
3530: 65 2c 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a  e, if not NULL *
3540: 2f 0a 20 20 45 78 70 72 20 2a 70 49 64 78 45 78  /.  Expr *pIdxEx
3550: 70 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  pr;            /
3560: 2a 20 53 65 61 72 63 68 20 66 6f 72 20 74 68 69  * Search for thi
3570: 73 20 69 6e 64 65 78 20 65 78 70 72 65 73 73 69  s index expressi
3580: 6f 6e 20 2a 2f 0a 20 20 63 68 61 72 20 69 64 78  on */.  char idx
3590: 61 66 66 3b 20 20 20 20 20 20 20 20 20 20 20 20  aff;            
35a0: 20 20 20 2f 2a 20 4d 75 73 74 20 6d 61 74 63 68     /* Must match
35b0: 20 74 68 69 73 20 61 66 66 69 6e 69 74 79 2c 20   this affinity, 
35c0: 69 66 20 7a 43 6f 6c 6c 4e 61 6d 65 21 3d 4e 55  if zCollName!=NU
35d0: 4c 4c 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64  LL */.  unsigned
35e0: 20 63 68 61 72 20 6e 45 71 75 69 76 3b 20 20 20   char nEquiv;   
35f0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
3600: 65 6e 74 72 69 65 73 20 69 6e 20 61 45 71 75 69  entries in aEqui
3610: 76 5b 5d 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65  v[] */.  unsigne
3620: 64 20 63 68 61 72 20 69 45 71 75 69 76 3b 20 20  d char iEquiv;  
3630: 20 20 20 20 2f 2a 20 4e 65 78 74 20 75 6e 75 73      /* Next unus
3640: 65 64 20 73 6c 6f 74 20 69 6e 20 61 45 71 75 69  ed slot in aEqui
3650: 76 5b 5d 20 2a 2f 0a 20 20 75 33 32 20 6f 70 4d  v[] */.  u32 opM
3660: 61 73 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20  ask;            
3670: 20 20 20 20 2f 2a 20 41 63 63 65 70 74 61 62 6c      /* Acceptabl
3680: 65 20 6f 70 65 72 61 74 6f 72 73 20 2a 2f 0a 20  e operators */. 
3690: 20 69 6e 74 20 6b 3b 20 20 20 20 20 20 20 20 20   int k;         
36a0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
36b0: 65 73 75 6d 65 20 73 63 61 6e 6e 69 6e 67 20 61  esume scanning a
36c0: 74 20 74 68 69 73 2d 3e 70 57 43 2d 3e 61 5b 74  t this->pWC->a[t
36d0: 68 69 73 2d 3e 6b 5d 20 2a 2f 0a 20 20 69 6e 74  his->k] */.  int
36e0: 20 61 69 43 75 72 5b 31 31 5d 3b 20 20 20 20 20   aiCur[11];     
36f0: 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f          /* Curso
3700: 72 73 20 69 6e 20 74 68 65 20 65 71 75 69 76 61  rs in the equiva
3710: 6c 65 6e 63 65 20 63 6c 61 73 73 20 2a 2f 0a 20  lence class */. 
3720: 20 69 31 36 20 61 69 43 6f 6c 75 6d 6e 5b 31 31   i16 aiColumn[11
3730: 5d 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43  ];          /* C
3740: 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 63 6f 6c  orresponding col
3750: 75 6d 6e 20 6e 75 6d 62 65 72 20 69 6e 20 74 68  umn number in th
3760: 65 20 65 71 2d 63 6c 61 73 73 20 2a 2f 0a 7d 3b  e eq-class */.};
3770: 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61  ../*.** An insta
3780: 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f  nce of the follo
3790: 77 69 6e 67 20 73 74 72 75 63 74 75 72 65 20 68  wing structure h
37a0: 6f 6c 64 73 20 61 6c 6c 20 69 6e 66 6f 72 6d 61  olds all informa
37b0: 74 69 6f 6e 20 61 62 6f 75 74 20 61 0a 2a 2a 20  tion about a.** 
37c0: 57 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20 4d  WHERE clause.  M
37d0: 6f 73 74 6c 79 20 74 68 69 73 20 69 73 20 61 20  ostly this is a 
37e0: 63 6f 6e 74 61 69 6e 65 72 20 66 6f 72 20 6f 6e  container for on
37f0: 65 20 6f 72 20 6d 6f 72 65 20 57 68 65 72 65 54  e or more WhereT
3800: 65 72 6d 73 2e 0a 2a 2a 0a 2a 2a 20 45 78 70 6c  erms..**.** Expl
3810: 61 6e 61 74 69 6f 6e 20 6f 66 20 70 4f 75 74 65  anation of pOute
3820: 72 3a 20 20 46 6f 72 20 61 20 57 48 45 52 45 20  r:  For a WHERE 
3830: 63 6c 61 75 73 65 20 6f 66 20 74 68 65 20 66 6f  clause of the fo
3840: 72 6d 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20  rm.**.**        
3850: 20 20 20 61 20 41 4e 44 20 28 28 62 20 41 4e 44     a AND ((b AND
3860: 20 63 29 20 4f 52 20 28 64 20 41 4e 44 20 65 29   c) OR (d AND e)
3870: 29 20 41 4e 44 20 66 0a 2a 2a 0a 2a 2a 20 54 68  ) AND f.**.** Th
3880: 65 72 65 20 61 72 65 20 73 65 70 61 72 61 74 65  ere are separate
3890: 20 57 68 65 72 65 43 6c 61 75 73 65 20 6f 62 6a   WhereClause obj
38a0: 65 63 74 73 20 66 6f 72 20 74 68 65 20 77 68 6f  ects for the who
38b0: 6c 65 20 63 6c 61 75 73 65 20 61 6e 64 20 66 6f  le clause and fo
38c0: 72 0a 2a 2a 20 74 68 65 20 73 75 62 63 6c 61 75  r.** the subclau
38d0: 73 65 73 20 22 28 62 20 41 4e 44 20 63 29 22 20  ses "(b AND c)" 
38e0: 61 6e 64 20 22 28 64 20 41 4e 44 20 65 29 22 2e  and "(d AND e)".
38f0: 20 20 54 68 65 20 70 4f 75 74 65 72 20 66 69 65    The pOuter fie
3900: 6c 64 20 6f 66 20 74 68 65 0a 2a 2a 20 73 75 62  ld of the.** sub
3910: 63 6c 61 75 73 65 73 20 70 6f 69 6e 74 73 20 74  clauses points t
3920: 6f 20 74 68 65 20 57 68 65 72 65 43 6c 61 75 73  o the WhereClaus
3930: 65 20 6f 62 6a 65 63 74 20 66 6f 72 20 74 68 65  e object for the
3940: 20 77 68 6f 6c 65 20 63 6c 61 75 73 65 2e 0a 2a   whole clause..*
3950: 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 43 6c  /.struct WhereCl
3960: 61 75 73 65 20 7b 0a 20 20 57 68 65 72 65 49 6e  ause {.  WhereIn
3970: 66 6f 20 2a 70 57 49 6e 66 6f 3b 20 20 20 20 20  fo *pWInfo;     
3980: 20 20 2f 2a 20 57 48 45 52 45 20 63 6c 61 75 73    /* WHERE claus
3990: 65 20 70 72 6f 63 65 73 73 69 6e 67 20 63 6f 6e  e processing con
39a0: 74 65 78 74 20 2a 2f 0a 20 20 57 68 65 72 65 43  text */.  WhereC
39b0: 6c 61 75 73 65 20 2a 70 4f 75 74 65 72 3b 20 20  lause *pOuter;  
39c0: 20 20 20 2f 2a 20 4f 75 74 65 72 20 63 6f 6e 6a     /* Outer conj
39d0: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20  unction */.  u8 
39e0: 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  op;             
39f0: 20 20 20 20 20 20 2f 2a 20 53 70 6c 69 74 20 6f        /* Split o
3a00: 70 65 72 61 74 6f 72 2e 20 20 54 4b 5f 41 4e 44  perator.  TK_AND
3a10: 20 6f 72 20 54 4b 5f 4f 52 20 2a 2f 0a 20 20 69   or TK_OR */.  i
3a20: 6e 74 20 6e 54 65 72 6d 3b 20 20 20 20 20 20 20  nt nTerm;       
3a30: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
3a40: 72 20 6f 66 20 74 65 72 6d 73 20 2a 2f 0a 20 20  r of terms */.  
3a50: 69 6e 74 20 6e 53 6c 6f 74 3b 20 20 20 20 20 20  int nSlot;      
3a60: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
3a70: 65 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e  er of entries in
3a80: 20 61 5b 5d 20 2a 2f 0a 20 20 57 68 65 72 65 54   a[] */.  WhereT
3a90: 65 72 6d 20 2a 61 3b 20 20 20 20 20 20 20 20 20  erm *a;         
3aa0: 20 20 20 2f 2a 20 45 61 63 68 20 61 5b 5d 20 64     /* Each a[] d
3ab0: 65 73 63 72 69 62 65 73 20 61 20 74 65 72 6d 20  escribes a term 
3ac0: 6f 66 20 74 68 65 20 57 48 45 52 45 20 63 6c 75  of the WHERE clu
3ad0: 61 73 65 20 2a 2f 0a 23 69 66 20 64 65 66 69 6e  ase */.#if defin
3ae0: 65 64 28 53 51 4c 49 54 45 5f 53 4d 41 4c 4c 5f  ed(SQLITE_SMALL_
3af0: 53 54 41 43 4b 29 0a 20 20 57 68 65 72 65 54 65  STACK).  WhereTe
3b00: 72 6d 20 61 53 74 61 74 69 63 5b 31 5d 3b 20 20  rm aStatic[1];  
3b10: 20 20 2f 2a 20 49 6e 69 74 69 61 6c 20 73 74 61    /* Initial sta
3b20: 74 69 63 20 73 70 61 63 65 20 66 6f 72 20 61 5b  tic space for a[
3b30: 5d 20 2a 2f 0a 23 65 6c 73 65 0a 20 20 57 68 65  ] */.#else.  Whe
3b40: 72 65 54 65 72 6d 20 61 53 74 61 74 69 63 5b 38  reTerm aStatic[8
3b50: 5d 3b 20 20 20 20 2f 2a 20 49 6e 69 74 69 61 6c  ];    /* Initial
3b60: 20 73 74 61 74 69 63 20 73 70 61 63 65 20 66 6f   static space fo
3b70: 72 20 61 5b 5d 20 2a 2f 0a 23 65 6e 64 69 66 0a  r a[] */.#endif.
3b80: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 57 68 65 72  };../*.** A Wher
3b90: 65 54 65 72 6d 20 77 69 74 68 20 65 4f 70 65 72  eTerm with eOper
3ba0: 61 74 6f 72 3d 3d 57 4f 5f 4f 52 20 68 61 73 20  ator==WO_OR has 
3bb0: 69 74 73 20 75 2e 70 4f 72 49 6e 66 6f 20 70 6f  its u.pOrInfo po
3bc0: 69 6e 74 65 72 20 73 65 74 20 74 6f 0a 2a 2a 20  inter set to.** 
3bd0: 61 20 64 79 6e 61 6d 69 63 61 6c 6c 79 20 61 6c  a dynamically al
3be0: 6c 6f 63 61 74 65 64 20 69 6e 73 74 61 6e 63 65  located instance
3bf0: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
3c00: 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2f 0a  g structure..*/.
3c10: 73 74 72 75 63 74 20 57 68 65 72 65 4f 72 49 6e  struct WhereOrIn
3c20: 66 6f 20 7b 0a 20 20 57 68 65 72 65 43 6c 61 75  fo {.  WhereClau
3c30: 73 65 20 77 63 3b 20 20 20 20 20 20 20 20 20 20  se wc;          
3c40: 2f 2a 20 44 65 63 6f 6d 70 6f 73 69 74 69 6f 6e  /* Decomposition
3c50: 20 69 6e 74 6f 20 73 75 62 74 65 72 6d 73 20 2a   into subterms *
3c60: 2f 0a 20 20 42 69 74 6d 61 73 6b 20 69 6e 64 65  /.  Bitmask inde
3c70: 78 61 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20  xable;       /* 
3c80: 42 69 74 6d 61 73 6b 20 6f 66 20 61 6c 6c 20 69  Bitmask of all i
3c90: 6e 64 65 78 61 62 6c 65 20 74 61 62 6c 65 73 20  ndexable tables 
3ca0: 69 6e 20 74 68 65 20 63 6c 61 75 73 65 20 2a 2f  in the clause */
3cb0: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 57 68 65  .};../*.** A Whe
3cc0: 72 65 54 65 72 6d 20 77 69 74 68 20 65 4f 70 65  reTerm with eOpe
3cd0: 72 61 74 6f 72 3d 3d 57 4f 5f 41 4e 44 20 68 61  rator==WO_AND ha
3ce0: 73 20 69 74 73 20 75 2e 70 41 6e 64 49 6e 66 6f  s its u.pAndInfo
3cf0: 20 70 6f 69 6e 74 65 72 20 73 65 74 20 74 6f 0a   pointer set to.
3d00: 2a 2a 20 61 20 64 79 6e 61 6d 69 63 61 6c 6c 79  ** a dynamically
3d10: 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e 73 74 61   allocated insta
3d20: 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f  nce of the follo
3d30: 77 69 6e 67 20 73 74 72 75 63 74 75 72 65 2e 0a  wing structure..
3d40: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 41  */.struct WhereA
3d50: 6e 64 49 6e 66 6f 20 7b 0a 20 20 57 68 65 72 65  ndInfo {.  Where
3d60: 43 6c 61 75 73 65 20 77 63 3b 20 20 20 20 20 20  Clause wc;      
3d70: 20 20 20 20 2f 2a 20 54 68 65 20 73 75 62 65 78      /* The subex
3d80: 70 72 65 73 73 69 6f 6e 20 62 72 6f 6b 65 6e 20  pression broken 
3d90: 6f 75 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  out */.};../*.**
3da0: 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20   An instance of 
3db0: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74  the following st
3dc0: 72 75 63 74 75 72 65 20 6b 65 65 70 73 20 74 72  ructure keeps tr
3dd0: 61 63 6b 20 6f 66 20 61 20 6d 61 70 70 69 6e 67  ack of a mapping
3de0: 0a 2a 2a 20 62 65 74 77 65 65 6e 20 56 44 42 45  .** between VDBE
3df0: 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20   cursor numbers 
3e00: 61 6e 64 20 62 69 74 73 20 6f 66 20 74 68 65 20  and bits of the 
3e10: 62 69 74 6d 61 73 6b 73 20 69 6e 20 57 68 65 72  bitmasks in Wher
3e20: 65 54 65 72 6d 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  eTerm..**.** The
3e30: 20 56 44 42 45 20 63 75 72 73 6f 72 20 6e 75 6d   VDBE cursor num
3e40: 62 65 72 73 20 61 72 65 20 73 6d 61 6c 6c 20 69  bers are small i
3e50: 6e 74 65 67 65 72 73 20 63 6f 6e 74 61 69 6e 65  ntegers containe
3e60: 64 20 69 6e 20 0a 2a 2a 20 53 72 63 4c 69 73 74  d in .** SrcList
3e70: 5f 69 74 65 6d 2e 69 43 75 72 73 6f 72 20 61 6e  _item.iCursor an
3e80: 64 20 45 78 70 72 2e 69 54 61 62 6c 65 20 66 69  d Expr.iTable fi
3e90: 65 6c 64 73 2e 20 20 46 6f 72 20 61 6e 79 20 67  elds.  For any g
3ea0: 69 76 65 6e 20 57 48 45 52 45 20 0a 2a 2a 20 63  iven WHERE .** c
3eb0: 6c 61 75 73 65 2c 20 74 68 65 20 63 75 72 73 6f  lause, the curso
3ec0: 72 20 6e 75 6d 62 65 72 73 20 6d 69 67 68 74 20  r numbers might 
3ed0: 6e 6f 74 20 62 65 67 69 6e 20 77 69 74 68 20 30  not begin with 0
3ee0: 20 61 6e 64 20 74 68 65 79 20 6d 69 67 68 74 0a   and they might.
3ef0: 2a 2a 20 63 6f 6e 74 61 69 6e 20 67 61 70 73 20  ** contain gaps 
3f00: 69 6e 20 74 68 65 20 6e 75 6d 62 65 72 69 6e 67  in the numbering
3f10: 20 73 65 71 75 65 6e 63 65 2e 20 20 42 75 74 20   sequence.  But 
3f20: 77 65 20 77 61 6e 74 20 74 6f 20 6d 61 6b 65 20  we want to make 
3f30: 6d 61 78 69 6d 75 6d 0a 2a 2a 20 75 73 65 20 6f  maximum.** use o
3f40: 66 20 74 68 65 20 62 69 74 73 20 69 6e 20 6f 75  f the bits in ou
3f50: 72 20 62 69 74 6d 61 73 6b 73 2e 20 20 54 68 69  r bitmasks.  Thi
3f60: 73 20 73 74 72 75 63 74 75 72 65 20 70 72 6f 76  s structure prov
3f70: 69 64 65 73 20 61 20 6d 61 70 70 69 6e 67 0a 2a  ides a mapping.*
3f80: 2a 20 66 72 6f 6d 20 74 68 65 20 73 70 61 72 73  * from the spars
3f90: 65 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73  e cursor numbers
3fa0: 20 69 6e 74 6f 20 63 6f 6e 73 65 63 75 74 69 76   into consecutiv
3fb0: 65 20 69 6e 74 65 67 65 72 73 20 62 65 67 69 6e  e integers begin
3fc0: 6e 69 6e 67 0a 2a 2a 20 77 69 74 68 20 30 2e 0a  ning.** with 0..
3fd0: 2a 2a 0a 2a 2a 20 49 66 20 57 68 65 72 65 4d 61  **.** If WhereMa
3fe0: 73 6b 53 65 74 2e 69 78 5b 41 5d 3d 3d 42 20 69  skSet.ix[A]==B i
3ff0: 74 20 6d 65 61 6e 73 20 74 68 61 74 20 54 68 65  t means that The
4000: 20 41 2d 74 68 20 62 69 74 20 6f 66 20 61 20 42   A-th bit of a B
4010: 69 74 6d 61 73 6b 0a 2a 2a 20 63 6f 72 72 65 73  itmask.** corres
4020: 70 6f 6e 64 73 20 56 44 42 45 20 63 75 72 73 6f  ponds VDBE curso
4030: 72 20 6e 75 6d 62 65 72 20 42 2e 20 20 54 68 65  r number B.  The
4040: 20 41 2d 74 68 20 62 69 74 20 6f 66 20 61 20 62   A-th bit of a b
4050: 69 74 6d 61 73 6b 20 69 73 20 31 3c 3c 41 2e 0a  itmask is 1<<A..
4060: 2a 2a 0a 2a 2a 20 46 6f 72 20 65 78 61 6d 70 6c  **.** For exampl
4070: 65 2c 20 69 66 20 74 68 65 20 57 48 45 52 45 20  e, if the WHERE 
4080: 63 6c 61 75 73 65 20 65 78 70 72 65 73 73 69 6f  clause expressio
4090: 6e 20 75 73 65 64 20 74 68 65 73 65 20 56 44 42  n used these VDB
40a0: 45 0a 2a 2a 20 63 75 72 73 6f 72 73 3a 20 20 34  E.** cursors:  4
40b0: 2c 20 35 2c 20 38 2c 20 32 39 2c 20 35 37 2c 20  , 5, 8, 29, 57, 
40c0: 37 33 2e 20 20 54 68 65 6e 20 74 68 65 20 20 57  73.  Then the  W
40d0: 68 65 72 65 4d 61 73 6b 53 65 74 20 73 74 72 75  hereMaskSet stru
40e0: 63 74 75 72 65 0a 2a 2a 20 77 6f 75 6c 64 20 6d  cture.** would m
40f0: 61 70 20 74 68 6f 73 65 20 63 75 72 73 6f 72 20  ap those cursor 
4100: 6e 75 6d 62 65 72 73 20 69 6e 74 6f 20 62 69 74  numbers into bit
4110: 73 20 30 20 74 68 72 6f 75 67 68 20 35 2e 0a 2a  s 0 through 5..*
4120: 2a 0a 2a 2a 20 4e 6f 74 65 20 74 68 61 74 20 74  *.** Note that t
4130: 68 65 20 6d 61 70 70 69 6e 67 20 69 73 20 6e 6f  he mapping is no
4140: 74 20 6e 65 63 65 73 73 61 72 69 6c 79 20 6f 72  t necessarily or
4150: 64 65 72 65 64 2e 20 20 49 6e 20 74 68 65 20 65  dered.  In the e
4160: 78 61 6d 70 6c 65 0a 2a 2a 20 61 62 6f 76 65 2c  xample.** above,
4170: 20 74 68 65 20 6d 61 70 70 69 6e 67 20 6d 69 67   the mapping mig
4180: 68 74 20 67 6f 20 6c 69 6b 65 20 74 68 69 73 3a  ht go like this:
4190: 20 20 34 2d 3e 33 2c 20 35 2d 3e 31 2c 20 38 2d    4->3, 5->1, 8-
41a0: 3e 32 2c 20 32 39 2d 3e 30 2c 0a 2a 2a 20 35 37  >2, 29->0,.** 57
41b0: 2d 3e 35 2c 20 37 33 2d 3e 34 2e 20 20 4f 72 20  ->5, 73->4.  Or 
41c0: 6f 6e 65 20 6f 66 20 37 31 39 20 6f 74 68 65 72  one of 719 other
41d0: 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 73 20 6d 69   combinations mi
41e0: 67 68 74 20 62 65 20 75 73 65 64 2e 20 49 74 0a  ght be used. It.
41f0: 2a 2a 20 64 6f 65 73 20 6e 6f 74 20 72 65 61 6c  ** does not real
4200: 6c 79 20 6d 61 74 74 65 72 2e 20 20 57 68 61 74  ly matter.  What
4210: 20 69 73 20 69 6d 70 6f 72 74 61 6e 74 20 69 73   is important is
4220: 20 74 68 61 74 20 73 70 61 72 73 65 20 63 75 72   that sparse cur
4230: 73 6f 72 0a 2a 2a 20 6e 75 6d 62 65 72 73 20 61  sor.** numbers a
4240: 6c 6c 20 67 65 74 20 6d 61 70 70 65 64 20 69 6e  ll get mapped in
4250: 74 6f 20 62 69 74 20 6e 75 6d 62 65 72 73 20 74  to bit numbers t
4260: 68 61 74 20 62 65 67 69 6e 20 77 69 74 68 20 30  hat begin with 0
4270: 20 61 6e 64 20 63 6f 6e 74 61 69 6e 0a 2a 2a 20   and contain.** 
4280: 6e 6f 20 67 61 70 73 2e 0a 2a 2f 0a 73 74 72 75  no gaps..*/.stru
4290: 63 74 20 57 68 65 72 65 4d 61 73 6b 53 65 74 20  ct WhereMaskSet 
42a0: 7b 0a 20 20 69 6e 74 20 6e 3b 20 20 20 20 20 20  {.  int n;      
42b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
42c0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 61    /* Number of a
42d0: 73 73 69 67 6e 65 64 20 63 75 72 73 6f 72 20 76  ssigned cursor v
42e0: 61 6c 75 65 73 20 2a 2f 0a 20 20 69 6e 74 20 69  alues */.  int i
42f0: 78 5b 42 4d 53 5d 3b 20 20 20 20 20 20 20 20 20  x[BMS];         
4300: 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73           /* Curs
4310: 6f 72 20 61 73 73 69 67 6e 65 64 20 74 6f 20 65  or assigned to e
4320: 61 63 68 20 62 69 74 20 2a 2f 0a 7d 3b 0a 0a 2f  ach bit */.};../
4330: 2a 0a 2a 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20  *.** Initialize 
4340: 61 20 57 68 65 72 65 4d 61 73 6b 53 65 74 20 6f  a WhereMaskSet o
4350: 62 6a 65 63 74 0a 2a 2f 0a 23 64 65 66 69 6e 65  bject.*/.#define
4360: 20 69 6e 69 74 4d 61 73 6b 53 65 74 28 50 29 20   initMaskSet(P) 
4370: 20 28 50 29 2d 3e 6e 3d 30 0a 0a 2f 2a 0a 2a 2a   (P)->n=0../*.**
4380: 20 54 68 69 73 20 6f 62 6a 65 63 74 20 69 73 20   This object is 
4390: 61 20 63 6f 6e 76 65 6e 69 65 6e 63 65 20 77 72  a convenience wr
43a0: 61 70 70 65 72 20 68 6f 6c 64 69 6e 67 20 61 6c  apper holding al
43b0: 6c 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 6e 65  l information ne
43c0: 65 64 65 64 0a 2a 2a 20 74 6f 20 63 6f 6e 73 74  eded.** to const
43d0: 72 75 63 74 20 57 68 65 72 65 4c 6f 6f 70 20 6f  ruct WhereLoop o
43e0: 62 6a 65 63 74 73 20 66 6f 72 20 61 20 70 61 72  bjects for a par
43f0: 74 69 63 75 6c 61 72 20 71 75 65 72 79 2e 0a 2a  ticular query..*
4400: 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 4c 6f  /.struct WhereLo
4410: 6f 70 42 75 69 6c 64 65 72 20 7b 0a 20 20 57 68  opBuilder {.  Wh
4420: 65 72 65 49 6e 66 6f 20 2a 70 57 49 6e 66 6f 3b  ereInfo *pWInfo;
4430: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 66 6f 72          /* Infor
4440: 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 74 68 69  mation about thi
4450: 73 20 57 48 45 52 45 20 2a 2f 0a 20 20 57 68 65  s WHERE */.  Whe
4460: 72 65 43 6c 61 75 73 65 20 2a 70 57 43 3b 20 20  reClause *pWC;  
4470: 20 20 20 20 20 20 20 2f 2a 20 57 48 45 52 45 20         /* WHERE 
4480: 63 6c 61 75 73 65 20 74 65 72 6d 73 20 2a 2f 0a  clause terms */.
4490: 20 20 45 78 70 72 4c 69 73 74 20 2a 70 4f 72 64    ExprList *pOrd
44a0: 65 72 42 79 3b 20 20 20 20 20 20 20 2f 2a 20 4f  erBy;       /* O
44b0: 52 44 45 52 20 42 59 20 63 6c 61 75 73 65 20 2a  RDER BY clause *
44c0: 2f 0a 20 20 57 68 65 72 65 4c 6f 6f 70 20 2a 70  /.  WhereLoop *p
44d0: 4e 65 77 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  New;          /*
44e0: 20 54 65 6d 70 6c 61 74 65 20 57 68 65 72 65 4c   Template WhereL
44f0: 6f 6f 70 20 2a 2f 0a 20 20 57 68 65 72 65 4f 72  oop */.  WhereOr
4500: 53 65 74 20 2a 70 4f 72 53 65 74 3b 20 20 20 20  Set *pOrSet;    
4510: 20 20 20 2f 2a 20 52 65 63 6f 72 64 20 62 65 73     /* Record bes
4520: 74 20 6c 6f 6f 70 73 20 68 65 72 65 2c 20 69 66  t loops here, if
4530: 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f 0a 23 69 66   not NULL */.#if
4540: 64 65 66 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c  def SQLITE_ENABL
4550: 45 5f 53 54 41 54 33 5f 4f 52 5f 53 54 41 54 34  E_STAT3_OR_STAT4
4560: 0a 20 20 55 6e 70 61 63 6b 65 64 52 65 63 6f 72  .  UnpackedRecor
4570: 64 20 2a 70 52 65 63 3b 20 20 20 20 20 2f 2a 20  d *pRec;     /* 
4580: 50 72 6f 62 65 20 66 6f 72 20 73 74 61 74 34 20  Probe for stat4 
4590: 28 69 66 20 72 65 71 75 69 72 65 64 29 20 2a 2f  (if required) */
45a0: 0a 20 20 69 6e 74 20 6e 52 65 63 56 61 6c 69 64  .  int nRecValid
45b0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
45c0: 4e 75 6d 62 65 72 20 6f 66 20 76 61 6c 69 64 20  Number of valid 
45d0: 66 69 65 6c 64 73 20 63 75 72 72 65 6e 74 6c 79  fields currently
45e0: 20 69 6e 20 70 52 65 63 20 2a 2f 0a 23 65 6e 64   in pRec */.#end
45f0: 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  if.};../*.** The
4600: 20 57 48 45 52 45 20 63 6c 61 75 73 65 20 70 72   WHERE clause pr
4610: 6f 63 65 73 73 69 6e 67 20 72 6f 75 74 69 6e 65  ocessing routine
4620: 20 68 61 73 20 74 77 6f 20 68 61 6c 76 65 73 2e   has two halves.
4630: 20 20 54 68 65 0a 2a 2a 20 66 69 72 73 74 20 70    The.** first p
4640: 61 72 74 20 64 6f 65 73 20 74 68 65 20 73 74 61  art does the sta
4650: 72 74 20 6f 66 20 74 68 65 20 57 48 45 52 45 20  rt of the WHERE 
4660: 6c 6f 6f 70 20 61 6e 64 20 74 68 65 20 73 65 63  loop and the sec
4670: 6f 6e 64 0a 2a 2a 20 68 61 6c 66 20 64 6f 65 73  ond.** half does
4680: 20 74 68 65 20 74 61 69 6c 20 6f 66 20 74 68 65   the tail of the
4690: 20 57 48 45 52 45 20 6c 6f 6f 70 2e 20 20 41 6e   WHERE loop.  An
46a0: 20 69 6e 73 74 61 6e 63 65 20 6f 66 0a 2a 2a 20   instance of.** 
46b0: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69  this structure i
46c0: 73 20 72 65 74 75 72 6e 65 64 20 62 79 20 74 68  s returned by th
46d0: 65 20 66 69 72 73 74 20 68 61 6c 66 20 61 6e 64  e first half and
46e0: 20 70 61 73 73 65 64 0a 2a 2a 20 69 6e 74 6f 20   passed.** into 
46f0: 74 68 65 20 73 65 63 6f 6e 64 20 68 61 6c 66 20  the second half 
4700: 74 6f 20 67 69 76 65 20 73 6f 6d 65 20 63 6f 6e  to give some con
4710: 74 69 6e 75 69 74 79 2e 0a 2a 2a 0a 2a 2a 20 41  tinuity..**.** A
4720: 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68  n instance of th
4730: 69 73 20 6f 62 6a 65 63 74 20 68 6f 6c 64 73 20  is object holds 
4740: 74 68 65 20 63 6f 6d 70 6c 65 74 65 20 73 74 61  the complete sta
4750: 74 65 20 6f 66 20 74 68 65 20 71 75 65 72 79 0a  te of the query.
4760: 2a 2a 20 70 6c 61 6e 6e 65 72 2e 0a 2a 2f 0a 73  ** planner..*/.s
4770: 74 72 75 63 74 20 57 68 65 72 65 49 6e 66 6f 20  truct WhereInfo 
4780: 7b 0a 20 20 50 61 72 73 65 20 2a 70 50 61 72 73  {.  Parse *pPars
4790: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  e;            /*
47a0: 20 50 61 72 73 69 6e 67 20 61 6e 64 20 63 6f 64   Parsing and cod
47b0: 65 20 67 65 6e 65 72 61 74 69 6e 67 20 63 6f 6e  e generating con
47c0: 74 65 78 74 20 2a 2f 0a 20 20 53 72 63 4c 69 73  text */.  SrcLis
47d0: 74 20 2a 70 54 61 62 4c 69 73 74 3b 20 20 20 20  t *pTabList;    
47e0: 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f 66 20 74      /* List of t
47f0: 61 62 6c 65 73 20 69 6e 20 74 68 65 20 6a 6f 69  ables in the joi
4800: 6e 20 2a 2f 0a 20 20 45 78 70 72 4c 69 73 74 20  n */.  ExprList 
4810: 2a 70 4f 72 64 65 72 42 79 3b 20 20 20 20 20 20  *pOrderBy;      
4820: 20 2f 2a 20 54 68 65 20 4f 52 44 45 52 20 42 59   /* The ORDER BY
4830: 20 63 6c 61 75 73 65 20 6f 72 20 4e 55 4c 4c 20   clause or NULL 
4840: 2a 2f 0a 20 20 45 78 70 72 4c 69 73 74 20 2a 70  */.  ExprList *p
4850: 52 65 73 75 6c 74 53 65 74 3b 20 20 20 20 20 2f  ResultSet;     /
4860: 2a 20 52 65 73 75 6c 74 20 73 65 74 2e 20 44 49  * Result set. DI
4870: 53 54 49 4e 43 54 20 6f 70 65 72 61 74 65 73 20  STINCT operates 
4880: 6f 6e 20 74 68 65 73 65 20 2a 2f 0a 20 20 57 68  on these */.  Wh
4890: 65 72 65 4c 6f 6f 70 20 2a 70 4c 6f 6f 70 73 3b  ereLoop *pLoops;
48a0: 20 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20          /* List 
48b0: 6f 66 20 61 6c 6c 20 57 68 65 72 65 4c 6f 6f 70  of all WhereLoop
48c0: 20 6f 62 6a 65 63 74 73 20 2a 2f 0a 20 20 42 69   objects */.  Bi
48d0: 74 6d 61 73 6b 20 72 65 76 4d 61 73 6b 3b 20 20  tmask revMask;  
48e0: 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20          /* Mask 
48f0: 6f 66 20 4f 52 44 45 52 20 42 59 20 74 65 72 6d  of ORDER BY term
4900: 73 20 74 68 61 74 20 6e 65 65 64 20 72 65 76 65  s that need reve
4910: 72 73 69 6e 67 20 2a 2f 0a 20 20 4c 6f 67 45 73  rsing */.  LogEs
4920: 74 20 6e 52 6f 77 4f 75 74 3b 20 20 20 20 20 20  t nRowOut;      
4930: 20 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74 65       /* Estimate
4940: 64 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74 70  d number of outp
4950: 75 74 20 72 6f 77 73 20 2a 2f 0a 20 20 75 31 36  ut rows */.  u16
4960: 20 77 63 74 72 6c 46 6c 61 67 73 3b 20 20 20 20   wctrlFlags;    
4970: 20 20 20 20 20 20 20 2f 2a 20 46 6c 61 67 73 20         /* Flags 
4980: 6f 72 69 67 69 6e 61 6c 6c 79 20 70 61 73 73 65  originally passe
4990: 64 20 74 6f 20 73 71 6c 69 74 65 33 57 68 65 72  d to sqlite3Wher
49a0: 65 42 65 67 69 6e 28 29 20 2a 2f 0a 20 20 69 38  eBegin() */.  i8
49b0: 20 6e 4f 42 53 61 74 3b 20 20 20 20 20 20 20 20   nOBSat;        
49c0: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
49d0: 72 20 6f 66 20 4f 52 44 45 52 20 42 59 20 74 65  r of ORDER BY te
49e0: 72 6d 73 20 73 61 74 69 73 66 69 65 64 20 62 79  rms satisfied by
49f0: 20 69 6e 64 69 63 65 73 20 2a 2f 0a 20 20 75 38   indices */.  u8
4a00: 20 73 6f 72 74 65 64 3b 20 20 20 20 20 20 20 20   sorted;        
4a10: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
4a20: 69 66 20 72 65 61 6c 6c 79 20 73 6f 72 74 65 64  if really sorted
4a30: 20 28 6e 6f 74 20 6a 75 73 74 20 67 72 6f 75 70   (not just group
4a40: 65 64 29 20 2a 2f 0a 20 20 75 38 20 65 4f 6e 65  ed) */.  u8 eOne
4a50: 50 61 73 73 3b 20 20 20 20 20 20 20 20 20 20 20  Pass;           
4a60: 20 20 20 2f 2a 20 4f 4e 45 50 41 53 53 5f 4f 46     /* ONEPASS_OF
4a70: 46 2c 20 6f 72 20 5f 53 49 4e 47 4c 45 2c 20 6f  F, or _SINGLE, o
4a80: 72 20 5f 4d 55 4c 54 49 20 2a 2f 0a 20 20 75 38  r _MULTI */.  u8
4a90: 20 75 6e 74 65 73 74 65 64 54 65 72 6d 73 3b 20   untestedTerms; 
4aa0: 20 20 20 20 20 20 20 20 2f 2a 20 4e 6f 74 20 61          /* Not a
4ab0: 6c 6c 20 57 48 45 52 45 20 74 65 72 6d 73 20 72  ll WHERE terms r
4ac0: 65 73 6f 6c 76 65 64 20 62 79 20 6f 75 74 65 72  esolved by outer
4ad0: 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 38 20 65 44   loop */.  u8 eD
4ae0: 69 73 74 69 6e 63 74 3b 20 20 20 20 20 20 20 20  istinct;        
4af0: 20 20 20 20 20 2f 2a 20 4f 6e 65 20 6f 66 20 74       /* One of t
4b00: 68 65 20 57 48 45 52 45 5f 44 49 53 54 49 4e 43  he WHERE_DISTINC
4b10: 54 5f 2a 20 76 61 6c 75 65 73 20 62 65 6c 6f 77  T_* values below
4b20: 20 2a 2f 0a 20 20 75 38 20 6e 4c 65 76 65 6c 3b   */.  u8 nLevel;
4b30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4b40: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6e 65 73  /* Number of nes
4b50: 74 65 64 20 6c 6f 6f 70 20 2a 2f 0a 20 20 69 6e  ted loop */.  in
4b60: 74 20 69 54 6f 70 3b 20 20 20 20 20 20 20 20 20  t iTop;         
4b70: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 76          /* The v
4b80: 65 72 79 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66  ery beginning of
4b90: 20 74 68 65 20 57 48 45 52 45 20 6c 6f 6f 70 20   the WHERE loop 
4ba0: 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6e 74 69 6e  */.  int iContin
4bb0: 75 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  ue;            /
4bc0: 2a 20 4a 75 6d 70 20 68 65 72 65 20 74 6f 20 63  * Jump here to c
4bd0: 6f 6e 74 69 6e 75 65 20 77 69 74 68 20 6e 65 78  ontinue with nex
4be0: 74 20 72 65 63 6f 72 64 20 2a 2f 0a 20 20 69 6e  t record */.  in
4bf0: 74 20 69 42 72 65 61 6b 3b 20 20 20 20 20 20 20  t iBreak;       
4c00: 20 20 20 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20          /* Jump 
4c10: 68 65 72 65 20 74 6f 20 62 72 65 61 6b 20 6f 75  here to break ou
4c20: 74 20 6f 66 20 74 68 65 20 6c 6f 6f 70 20 2a 2f  t of the loop */
4c30: 0a 20 20 69 6e 74 20 73 61 76 65 64 4e 51 75 65  .  int savedNQue
4c40: 72 79 4c 6f 6f 70 3b 20 20 20 20 20 20 2f 2a 20  ryLoop;      /* 
4c50: 70 50 61 72 73 65 2d 3e 6e 51 75 65 72 79 4c 6f  pParse->nQueryLo
4c60: 6f 70 20 6f 75 74 73 69 64 65 20 74 68 65 20 57  op outside the W
4c70: 48 45 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20 20 69  HERE loop */.  i
4c80: 6e 74 20 61 69 43 75 72 4f 6e 65 50 61 73 73 5b  nt aiCurOnePass[
4c90: 32 5d 3b 20 20 20 20 20 20 2f 2a 20 4f 50 5f 4f  2];      /* OP_O
4ca0: 70 65 6e 57 72 69 74 65 20 63 75 72 73 6f 72 73  penWrite cursors
4cb0: 20 66 6f 72 20 74 68 65 20 4f 4e 45 50 41 53 53   for the ONEPASS
4cc0: 20 6f 70 74 20 2a 2f 0a 20 20 57 68 65 72 65 4d   opt */.  WhereM
4cd0: 61 73 6b 53 65 74 20 73 4d 61 73 6b 53 65 74 3b  askSet sMaskSet;
4ce0: 20 20 20 20 2f 2a 20 4d 61 70 20 63 75 72 73 6f      /* Map curso
4cf0: 72 20 6e 75 6d 62 65 72 73 20 74 6f 20 62 69 74  r numbers to bit
4d00: 6d 61 73 6b 73 20 2a 2f 0a 20 20 57 68 65 72 65  masks */.  Where
4d10: 43 6c 61 75 73 65 20 73 57 43 3b 20 20 20 20 20  Clause sWC;     
4d20: 20 20 20 20 20 2f 2a 20 44 65 63 6f 6d 70 6f 73       /* Decompos
4d30: 69 74 69 6f 6e 20 6f 66 20 74 68 65 20 57 48 45  ition of the WHE
4d40: 52 45 20 63 6c 61 75 73 65 20 2a 2f 0a 20 20 57  RE clause */.  W
4d50: 68 65 72 65 4c 65 76 65 6c 20 61 5b 31 5d 3b 20  hereLevel a[1]; 
4d60: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 66 6f           /* Info
4d70: 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 65 61  rmation about ea
4d80: 63 68 20 6e 65 73 74 20 6c 6f 6f 70 20 69 6e 20  ch nest loop in 
4d90: 57 48 45 52 45 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a  WHERE */.};../*.
4da0: 2a 2a 20 50 72 69 76 61 74 65 20 69 6e 74 65 72  ** Private inter
4db0: 66 61 63 65 73 20 2d 20 63 61 6c 6c 61 62 6c 65  faces - callable
4dc0: 20 6f 6e 6c 79 20 62 79 20 6f 74 68 65 72 20 77   only by other w
4dd0: 68 65 72 65 2e 63 20 72 6f 75 74 69 6e 65 73 2e  here.c routines.
4de0: 0a 2a 2a 0a 2a 2a 20 77 68 65 72 65 2e 63 3a 0a  .**.** where.c:.
4df0: 2a 2f 0a 42 69 74 6d 61 73 6b 20 73 71 6c 69 74  */.Bitmask sqlit
4e00: 65 33 57 68 65 72 65 47 65 74 4d 61 73 6b 28 57  e3WhereGetMask(W
4e10: 68 65 72 65 4d 61 73 6b 53 65 74 2a 2c 69 6e 74  hereMaskSet*,int
4e20: 29 3b 0a 57 68 65 72 65 54 65 72 6d 20 2a 73 71  );.WhereTerm *sq
4e30: 6c 69 74 65 33 57 68 65 72 65 46 69 6e 64 54 65  lite3WhereFindTe
4e40: 72 6d 28 0a 20 20 57 68 65 72 65 43 6c 61 75 73  rm(.  WhereClaus
4e50: 65 20 2a 70 57 43 2c 20 20 20 20 20 2f 2a 20 54  e *pWC,     /* T
4e60: 68 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20  he WHERE clause 
4e70: 74 6f 20 62 65 20 73 65 61 72 63 68 65 64 20 2a  to be searched *
4e80: 2f 0a 20 20 69 6e 74 20 69 43 75 72 2c 20 20 20  /.  int iCur,   
4e90: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
4ea0: 73 6f 72 20 6e 75 6d 62 65 72 20 6f 66 20 4c 48  sor number of LH
4eb0: 53 20 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6c 75  S */.  int iColu
4ec0: 6d 6e 2c 20 20 20 20 20 20 20 20 20 20 2f 2a 20  mn,          /* 
4ed0: 43 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20 6f 66  Column number of
4ee0: 20 4c 48 53 20 2a 2f 0a 20 20 42 69 74 6d 61 73   LHS */.  Bitmas
4ef0: 6b 20 6e 6f 74 52 65 61 64 79 2c 20 20 20 20 20  k notReady,     
4f00: 2f 2a 20 52 48 53 20 6d 75 73 74 20 6e 6f 74 20  /* RHS must not 
4f10: 6f 76 65 72 6c 61 70 20 77 69 74 68 20 74 68 69  overlap with thi
4f20: 73 20 6d 61 73 6b 20 2a 2f 0a 20 20 75 33 32 20  s mask */.  u32 
4f30: 6f 70 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  op,             
4f40: 20 20 2f 2a 20 4d 61 73 6b 20 6f 66 20 57 4f 5f    /* Mask of WO_
4f50: 78 78 20 76 61 6c 75 65 73 20 64 65 73 63 72 69  xx values descri
4f60: 62 69 6e 67 20 6f 70 65 72 61 74 6f 72 20 2a 2f  bing operator */
4f70: 0a 20 20 49 6e 64 65 78 20 2a 70 49 64 78 20 20  .  Index *pIdx  
4f80: 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 75 73 74           /* Must
4f90: 20 62 65 20 63 6f 6d 70 61 74 69 62 6c 65 20 77   be compatible w
4fa0: 69 74 68 20 74 68 69 73 20 69 6e 64 65 78 2c 20  ith this index, 
4fb0: 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f 0a 29  if not NULL */.)
4fc0: 3b 0a 0a 2f 2a 20 77 68 65 72 65 63 6f 64 65 2e  ;../* wherecode.
4fd0: 63 3a 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51  c: */.#ifndef SQ
4fe0: 4c 49 54 45 5f 4f 4d 49 54 5f 45 58 50 4c 41 49  LITE_OMIT_EXPLAI
4ff0: 4e 0a 69 6e 74 20 73 71 6c 69 74 65 33 57 68 65  N.int sqlite3Whe
5000: 72 65 45 78 70 6c 61 69 6e 4f 6e 65 53 63 61 6e  reExplainOneScan
5010: 28 0a 20 20 50 61 72 73 65 20 2a 70 50 61 72 73  (.  Parse *pPars
5020: 65 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e,              
5030: 20 20 20 20 2f 2a 20 50 61 72 73 65 20 63 6f 6e      /* Parse con
5040: 74 65 78 74 20 2a 2f 0a 20 20 53 72 63 4c 69 73  text */.  SrcLis
5050: 74 20 2a 70 54 61 62 4c 69 73 74 2c 20 20 20 20  t *pTabList,    
5060: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 61 62            /* Tab
5070: 6c 65 20 6c 69 73 74 20 74 68 69 73 20 6c 6f 6f  le list this loo
5080: 70 20 72 65 66 65 72 73 20 74 6f 20 2a 2f 0a 20  p refers to */. 
5090: 20 57 68 65 72 65 4c 65 76 65 6c 20 2a 70 4c 65   WhereLevel *pLe
50a0: 76 65 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20  vel,            
50b0: 20 2f 2a 20 53 63 61 6e 20 74 6f 20 77 72 69 74   /* Scan to writ
50c0: 65 20 4f 50 5f 45 78 70 6c 61 69 6e 20 6f 70 63  e OP_Explain opc
50d0: 6f 64 65 20 66 6f 72 20 2a 2f 0a 20 20 69 6e 74  ode for */.  int
50e0: 20 69 4c 65 76 65 6c 2c 20 20 20 20 20 20 20 20   iLevel,        
50f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5100: 56 61 6c 75 65 20 66 6f 72 20 22 6c 65 76 65 6c  Value for "level
5110: 22 20 63 6f 6c 75 6d 6e 20 6f 66 20 6f 75 74 70  " column of outp
5120: 75 74 20 2a 2f 0a 20 20 69 6e 74 20 69 46 72 6f  ut */.  int iFro
5130: 6d 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  m,              
5140: 20 20 20 20 20 20 20 20 2f 2a 20 56 61 6c 75 65          /* Value
5150: 20 66 6f 72 20 22 66 72 6f 6d 22 20 63 6f 6c 75   for "from" colu
5160: 6d 6e 20 6f 66 20 6f 75 74 70 75 74 20 2a 2f 0a  mn of output */.
5170: 20 20 75 31 36 20 77 63 74 72 6c 46 6c 61 67 73    u16 wctrlFlags
5180: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5190: 20 20 2f 2a 20 46 6c 61 67 73 20 70 61 73 73 65    /* Flags passe
51a0: 64 20 74 6f 20 73 71 6c 69 74 65 33 57 68 65 72  d to sqlite3Wher
51b0: 65 42 65 67 69 6e 28 29 20 2a 2f 0a 29 3b 0a 23  eBegin() */.);.#
51c0: 65 6c 73 65 0a 23 20 64 65 66 69 6e 65 20 73 71  else.# define sq
51d0: 6c 69 74 65 33 57 68 65 72 65 45 78 70 6c 61 69  lite3WhereExplai
51e0: 6e 4f 6e 65 53 63 61 6e 28 75 2c 76 2c 77 2c 78  nOneScan(u,v,w,x
51f0: 2c 79 2c 7a 29 20 30 0a 23 65 6e 64 69 66 20 2f  ,y,z) 0.#endif /
5200: 2a 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 45 58  * SQLITE_OMIT_EX
5210: 50 4c 41 49 4e 20 2a 2f 0a 23 69 66 64 65 66 20  PLAIN */.#ifdef 
5220: 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 53 54  SQLITE_ENABLE_ST
5230: 4d 54 5f 53 43 41 4e 53 54 41 54 55 53 0a 76 6f  MT_SCANSTATUS.vo
5240: 69 64 20 73 71 6c 69 74 65 33 57 68 65 72 65 41  id sqlite3WhereA
5250: 64 64 53 63 61 6e 53 74 61 74 75 73 28 0a 20 20  ddScanStatus(.  
5260: 56 64 62 65 20 2a 76 2c 20 20 20 20 20 20 20 20  Vdbe *v,        
5270: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5280: 2f 2a 20 56 64 62 65 20 74 6f 20 61 64 64 20 73  /* Vdbe to add s
5290: 63 61 6e 73 74 61 74 75 73 20 65 6e 74 72 79 20  canstatus entry 
52a0: 74 6f 20 2a 2f 0a 20 20 53 72 63 4c 69 73 74 20  to */.  SrcList 
52b0: 2a 70 53 72 63 6c 69 73 74 2c 20 20 20 20 20 20  *pSrclist,      
52c0: 20 20 20 20 20 20 20 20 2f 2a 20 46 52 4f 4d 20          /* FROM 
52d0: 63 6c 61 75 73 65 20 70 4c 76 6c 20 72 65 61 64  clause pLvl read
52e0: 73 20 64 61 74 61 20 66 72 6f 6d 20 2a 2f 0a 20  s data from */. 
52f0: 20 57 68 65 72 65 4c 65 76 65 6c 20 2a 70 4c 76   WhereLevel *pLv
5300: 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l,              
5310: 20 2f 2a 20 4c 65 76 65 6c 20 74 6f 20 61 64 64   /* Level to add
5320: 20 73 63 61 6e 73 74 61 74 75 73 28 29 20 65 6e   scanstatus() en
5330: 74 72 79 20 66 6f 72 20 2a 2f 0a 20 20 69 6e 74  try for */.  int
5340: 20 61 64 64 72 45 78 70 6c 61 69 6e 20 20 20 20   addrExplain    
5350: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5360: 41 64 64 72 65 73 73 20 6f 66 20 4f 50 5f 45 78  Address of OP_Ex
5370: 70 6c 61 69 6e 20 28 6f 72 20 30 29 20 2a 2f 0a  plain (or 0) */.
5380: 29 3b 0a 23 65 6c 73 65 0a 23 20 64 65 66 69 6e  );.#else.# defin
5390: 65 20 73 71 6c 69 74 65 33 57 68 65 72 65 41 64  e sqlite3WhereAd
53a0: 64 53 63 61 6e 53 74 61 74 75 73 28 61 2c 20 62  dScanStatus(a, b
53b0: 2c 20 63 2c 20 64 29 20 28 28 76 6f 69 64 29 64  , c, d) ((void)d
53c0: 29 0a 23 65 6e 64 69 66 0a 42 69 74 6d 61 73 6b  ).#endif.Bitmask
53d0: 20 73 71 6c 69 74 65 33 57 68 65 72 65 43 6f 64   sqlite3WhereCod
53e0: 65 4f 6e 65 4c 6f 6f 70 53 74 61 72 74 28 0a 20  eOneLoopStart(. 
53f0: 20 57 68 65 72 65 49 6e 66 6f 20 2a 70 57 49 6e   WhereInfo *pWIn
5400: 66 6f 2c 20 20 20 2f 2a 20 43 6f 6d 70 6c 65 74  fo,   /* Complet
5410: 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62  e information ab
5420: 6f 75 74 20 74 68 65 20 57 48 45 52 45 20 63 6c  out the WHERE cl
5430: 61 75 73 65 20 2a 2f 0a 20 20 69 6e 74 20 69 4c  ause */.  int iL
5440: 65 76 65 6c 2c 20 20 20 20 20 20 20 20 20 20 2f  evel,          /
5450: 2a 20 57 68 69 63 68 20 6c 65 76 65 6c 20 6f 66  * Which level of
5460: 20 70 57 49 6e 66 6f 2d 3e 61 5b 5d 20 73 68 6f   pWInfo->a[] sho
5470: 75 6c 64 20 62 65 20 63 6f 64 65 64 20 2a 2f 0a  uld be coded */.
5480: 20 20 42 69 74 6d 61 73 6b 20 6e 6f 74 52 65 61    Bitmask notRea
5490: 64 79 20 20 20 20 20 2f 2a 20 57 68 69 63 68 20  dy     /* Which 
54a0: 74 61 62 6c 65 73 20 61 72 65 20 63 75 72 72 65  tables are curre
54b0: 6e 74 6c 79 20 61 76 61 69 6c 61 62 6c 65 20 2a  ntly available *
54c0: 2f 0a 29 3b 0a 0a 2f 2a 20 77 68 65 72 65 65 78  /.);../* whereex
54d0: 70 72 2e 63 3a 20 2a 2f 0a 76 6f 69 64 20 73 71  pr.c: */.void sq
54e0: 6c 69 74 65 33 57 68 65 72 65 43 6c 61 75 73 65  lite3WhereClause
54f0: 49 6e 69 74 28 57 68 65 72 65 43 6c 61 75 73 65  Init(WhereClause
5500: 2a 2c 57 68 65 72 65 49 6e 66 6f 2a 29 3b 0a 76  *,WhereInfo*);.v
5510: 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65 72 65  oid sqlite3Where
5520: 43 6c 61 75 73 65 43 6c 65 61 72 28 57 68 65 72  ClauseClear(Wher
5530: 65 43 6c 61 75 73 65 2a 29 3b 0a 76 6f 69 64 20  eClause*);.void 
5540: 73 71 6c 69 74 65 33 57 68 65 72 65 53 70 6c 69  sqlite3WhereSpli
5550: 74 28 57 68 65 72 65 43 6c 61 75 73 65 2a 2c 45  t(WhereClause*,E
5560: 78 70 72 2a 2c 75 38 29 3b 0a 42 69 74 6d 61 73  xpr*,u8);.Bitmas
5570: 6b 20 73 71 6c 69 74 65 33 57 68 65 72 65 45 78  k sqlite3WhereEx
5580: 70 72 55 73 61 67 65 28 57 68 65 72 65 4d 61 73  prUsage(WhereMas
5590: 6b 53 65 74 2a 2c 20 45 78 70 72 2a 29 3b 0a 42  kSet*, Expr*);.B
55a0: 69 74 6d 61 73 6b 20 73 71 6c 69 74 65 33 57 68  itmask sqlite3Wh
55b0: 65 72 65 45 78 70 72 4c 69 73 74 55 73 61 67 65  ereExprListUsage
55c0: 28 57 68 65 72 65 4d 61 73 6b 53 65 74 2a 2c 20  (WhereMaskSet*, 
55d0: 45 78 70 72 4c 69 73 74 2a 29 3b 0a 76 6f 69 64  ExprList*);.void
55e0: 20 73 71 6c 69 74 65 33 57 68 65 72 65 45 78 70   sqlite3WhereExp
55f0: 72 41 6e 61 6c 79 7a 65 28 53 72 63 4c 69 73 74  rAnalyze(SrcList
5600: 2a 2c 20 57 68 65 72 65 43 6c 61 75 73 65 2a 29  *, WhereClause*)
5610: 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 57 68  ;.void sqlite3Wh
5620: 65 72 65 54 61 62 46 75 6e 63 41 72 67 73 28 50  ereTabFuncArgs(P
5630: 61 72 73 65 2a 2c 20 73 74 72 75 63 74 20 53 72  arse*, struct Sr
5640: 63 4c 69 73 74 5f 69 74 65 6d 2a 2c 20 57 68 65  cList_item*, Whe
5650: 72 65 43 6c 61 75 73 65 2a 29 3b 0a 0a 0a 0a 0a  reClause*);.....
5660: 0a 2f 2a 0a 2a 2a 20 42 69 74 6d 61 73 6b 73 20  ./*.** Bitmasks 
5670: 66 6f 72 20 74 68 65 20 6f 70 65 72 61 74 6f 72  for the operator
5680: 73 20 6f 6e 20 57 68 65 72 65 54 65 72 6d 20 6f  s on WhereTerm o
5690: 62 6a 65 63 74 73 2e 20 20 54 68 65 73 65 20 61  bjects.  These a
56a0: 72 65 20 61 6c 6c 0a 2a 2a 20 6f 70 65 72 61 74  re all.** operat
56b0: 6f 72 73 20 74 68 61 74 20 61 72 65 20 6f 66 20  ors that are of 
56c0: 69 6e 74 65 72 65 73 74 20 74 6f 20 74 68 65 20  interest to the 
56d0: 71 75 65 72 79 20 70 6c 61 6e 6e 65 72 2e 20 20  query planner.  
56e0: 41 6e 0a 2a 2a 20 4f 52 2d 65 64 20 63 6f 6d 62  An.** OR-ed comb
56f0: 69 6e 61 74 69 6f 6e 20 6f 66 20 74 68 65 73 65  ination of these
5700: 20 76 61 6c 75 65 73 20 63 61 6e 20 62 65 20 75   values can be u
5710: 73 65 64 20 77 68 65 6e 20 73 65 61 72 63 68 69  sed when searchi
5720: 6e 67 20 66 6f 72 0a 2a 2a 20 70 61 72 74 69 63  ng for.** partic
5730: 75 6c 61 72 20 57 68 65 72 65 54 65 72 6d 73 20  ular WhereTerms 
5740: 77 69 74 68 69 6e 20 61 20 57 68 65 72 65 43 6c  within a WhereCl
5750: 61 75 73 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  ause..*/.#define
5760: 20 57 4f 5f 49 4e 20 20 20 20 20 30 78 30 30 30   WO_IN     0x000
5770: 31 0a 23 64 65 66 69 6e 65 20 57 4f 5f 45 51 20  1.#define WO_EQ 
5780: 20 20 20 20 30 78 30 30 30 32 0a 23 64 65 66 69      0x0002.#defi
5790: 6e 65 20 57 4f 5f 4c 54 20 20 20 20 20 28 57 4f  ne WO_LT     (WO
57a0: 5f 45 51 3c 3c 28 54 4b 5f 4c 54 2d 54 4b 5f 45  _EQ<<(TK_LT-TK_E
57b0: 51 29 29 0a 23 64 65 66 69 6e 65 20 57 4f 5f 4c  Q)).#define WO_L
57c0: 45 20 20 20 20 20 28 57 4f 5f 45 51 3c 3c 28 54  E     (WO_EQ<<(T
57d0: 4b 5f 4c 45 2d 54 4b 5f 45 51 29 29 0a 23 64 65  K_LE-TK_EQ)).#de
57e0: 66 69 6e 65 20 57 4f 5f 47 54 20 20 20 20 20 28  fine WO_GT     (
57f0: 57 4f 5f 45 51 3c 3c 28 54 4b 5f 47 54 2d 54 4b  WO_EQ<<(TK_GT-TK
5800: 5f 45 51 29 29 0a 23 64 65 66 69 6e 65 20 57 4f  _EQ)).#define WO
5810: 5f 47 45 20 20 20 20 20 28 57 4f 5f 45 51 3c 3c  _GE     (WO_EQ<<
5820: 28 54 4b 5f 47 45 2d 54 4b 5f 45 51 29 29 0a 23  (TK_GE-TK_EQ)).#
5830: 64 65 66 69 6e 65 20 57 4f 5f 4d 41 54 43 48 20  define WO_MATCH 
5840: 20 30 78 30 30 34 30 0a 23 64 65 66 69 6e 65 20   0x0040.#define 
5850: 57 4f 5f 49 53 20 20 20 20 20 30 78 30 30 38 30  WO_IS     0x0080
5860: 0a 23 64 65 66 69 6e 65 20 57 4f 5f 49 53 4e 55  .#define WO_ISNU
5870: 4c 4c 20 30 78 30 31 30 30 0a 23 64 65 66 69 6e  LL 0x0100.#defin
5880: 65 20 57 4f 5f 4f 52 20 20 20 20 20 30 78 30 32  e WO_OR     0x02
5890: 30 30 20 20 20 20 20 20 20 2f 2a 20 54 77 6f 20  00       /* Two 
58a0: 6f 72 20 6d 6f 72 65 20 4f 52 2d 63 6f 6e 6e 65  or more OR-conne
58b0: 63 74 65 64 20 74 65 72 6d 73 20 2a 2f 0a 23 64  cted terms */.#d
58c0: 65 66 69 6e 65 20 57 4f 5f 41 4e 44 20 20 20 20  efine WO_AND    
58d0: 30 78 30 34 30 30 20 20 20 20 20 20 20 2f 2a 20  0x0400       /* 
58e0: 54 77 6f 20 6f 72 20 6d 6f 72 65 20 41 4e 44 2d  Two or more AND-
58f0: 63 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20  connected terms 
5900: 2a 2f 0a 23 64 65 66 69 6e 65 20 57 4f 5f 45 51  */.#define WO_EQ
5910: 55 49 56 20 20 30 78 30 38 30 30 20 20 20 20 20  UIV  0x0800     
5920: 20 20 2f 2a 20 4f 66 20 74 68 65 20 66 6f 72 6d    /* Of the form
5930: 20 41 3d 3d 42 2c 20 62 6f 74 68 20 63 6f 6c 75   A==B, both colu
5940: 6d 6e 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  mns */.#define W
5950: 4f 5f 4e 4f 4f 50 20 20 20 30 78 31 30 30 30 20  O_NOOP   0x1000 
5960: 20 20 20 20 20 20 2f 2a 20 54 68 69 73 20 74 65        /* This te
5970: 72 6d 20 64 6f 65 73 20 6e 6f 74 20 72 65 73 74  rm does not rest
5980: 72 69 63 74 20 73 65 61 72 63 68 20 73 70 61 63  rict search spac
5990: 65 20 2a 2f 0a 0a 23 64 65 66 69 6e 65 20 57 4f  e */..#define WO
59a0: 5f 41 4c 4c 20 20 20 20 30 78 31 66 66 66 20 20  _ALL    0x1fff  
59b0: 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 6f 66 20       /* Mask of 
59c0: 61 6c 6c 20 70 6f 73 73 69 62 6c 65 20 57 4f 5f  all possible WO_
59d0: 2a 20 76 61 6c 75 65 73 20 2a 2f 0a 23 64 65 66  * values */.#def
59e0: 69 6e 65 20 57 4f 5f 53 49 4e 47 4c 45 20 30 78  ine WO_SINGLE 0x
59f0: 30 31 66 66 20 20 20 20 20 20 20 2f 2a 20 4d 61  01ff       /* Ma
5a00: 73 6b 20 6f 66 20 61 6c 6c 20 6e 6f 6e 2d 63 6f  sk of all non-co
5a10: 6d 70 6f 75 6e 64 20 57 4f 5f 2a 20 76 61 6c 75  mpound WO_* valu
5a20: 65 73 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  es */../*.** The
5a30: 73 65 20 61 72 65 20 64 65 66 69 6e 69 74 69 6f  se are definitio
5a40: 6e 73 20 6f 66 20 62 69 74 73 20 69 6e 20 74 68  ns of bits in th
5a50: 65 20 57 68 65 72 65 4c 6f 6f 70 2e 77 73 46 6c  e WhereLoop.wsFl
5a60: 61 67 73 20 66 69 65 6c 64 2e 0a 2a 2a 20 54 68  ags field..** Th
5a70: 65 20 70 61 72 74 69 63 75 6c 61 72 20 63 6f 6d  e particular com
5a80: 62 69 6e 61 74 69 6f 6e 20 6f 66 20 62 69 74 73  bination of bits
5a90: 20 69 6e 20 65 61 63 68 20 57 68 65 72 65 4c 6f   in each WhereLo
5aa0: 6f 70 20 68 65 6c 70 20 74 6f 0a 2a 2a 20 64 65  op help to.** de
5ab0: 74 65 72 6d 69 6e 65 20 74 68 65 20 61 6c 67 6f  termine the algo
5ac0: 72 69 74 68 6d 20 74 68 61 74 20 57 68 65 72 65  rithm that Where
5ad0: 4c 6f 6f 70 20 72 65 70 72 65 73 65 6e 74 73 2e  Loop represents.
5ae0: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52  .*/.#define WHER
5af0: 45 5f 43 4f 4c 55 4d 4e 5f 45 51 20 20 20 20 30  E_COLUMN_EQ    0
5b00: 78 30 30 30 30 30 30 30 31 20 20 2f 2a 20 78 3d  x00000001  /* x=
5b10: 45 58 50 52 20 2a 2f 0a 23 64 65 66 69 6e 65 20  EXPR */.#define 
5b20: 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 52 41 4e  WHERE_COLUMN_RAN
5b30: 47 45 20 30 78 30 30 30 30 30 30 30 32 20 20 2f  GE 0x00000002  /
5b40: 2a 20 78 3c 45 58 50 52 20 61 6e 64 2f 6f 72 20  * x<EXPR and/or 
5b50: 78 3e 45 58 50 52 20 2a 2f 0a 23 64 65 66 69 6e  x>EXPR */.#defin
5b60: 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 49  e WHERE_COLUMN_I
5b70: 4e 20 20 20 20 30 78 30 30 30 30 30 30 30 34 20  N    0x00000004 
5b80: 20 2f 2a 20 78 20 49 4e 20 28 2e 2e 2e 29 20 2a   /* x IN (...) *
5b90: 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f  /.#define WHERE_
5ba0: 43 4f 4c 55 4d 4e 5f 4e 55 4c 4c 20 20 30 78 30  COLUMN_NULL  0x0
5bb0: 30 30 30 30 30 30 38 20 20 2f 2a 20 78 20 49 53  0000008  /* x IS
5bc0: 20 4e 55 4c 4c 20 2a 2f 0a 23 64 65 66 69 6e 65   NULL */.#define
5bd0: 20 57 48 45 52 45 5f 43 4f 4e 53 54 52 41 49 4e   WHERE_CONSTRAIN
5be0: 54 20 20 20 30 78 30 30 30 30 30 30 30 66 20 20  T   0x0000000f  
5bf0: 2f 2a 20 41 6e 79 20 6f 66 20 74 68 65 20 57 48  /* Any of the WH
5c00: 45 52 45 5f 43 4f 4c 55 4d 4e 5f 78 78 78 20 76  ERE_COLUMN_xxx v
5c10: 61 6c 75 65 73 20 2a 2f 0a 23 64 65 66 69 6e 65  alues */.#define
5c20: 20 57 48 45 52 45 5f 54 4f 50 5f 4c 49 4d 49 54   WHERE_TOP_LIMIT
5c30: 20 20 20 20 30 78 30 30 30 30 30 30 31 30 20 20      0x00000010  
5c40: 2f 2a 20 78 3c 45 58 50 52 20 6f 72 20 78 3c 3d  /* x<EXPR or x<=
5c50: 45 58 50 52 20 63 6f 6e 73 74 72 61 69 6e 74 20  EXPR constraint 
5c60: 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45  */.#define WHERE
5c70: 5f 42 54 4d 5f 4c 49 4d 49 54 20 20 20 20 30 78  _BTM_LIMIT    0x
5c80: 30 30 30 30 30 30 32 30 20 20 2f 2a 20 78 3e 45  00000020  /* x>E
5c90: 58 50 52 20 6f 72 20 78 3e 3d 45 58 50 52 20 63  XPR or x>=EXPR c
5ca0: 6f 6e 73 74 72 61 69 6e 74 20 2a 2f 0a 23 64 65  onstraint */.#de
5cb0: 66 69 6e 65 20 57 48 45 52 45 5f 42 4f 54 48 5f  fine WHERE_BOTH_
5cc0: 4c 49 4d 49 54 20 20 20 30 78 30 30 30 30 30 30  LIMIT   0x000000
5cd0: 33 30 20 20 2f 2a 20 42 6f 74 68 20 78 3e 45 58  30  /* Both x>EX
5ce0: 50 52 20 61 6e 64 20 78 3c 45 58 50 52 20 2a 2f  PR and x<EXPR */
5cf0: 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f 49  .#define WHERE_I
5d00: 44 58 5f 4f 4e 4c 59 20 20 20 20 20 30 78 30 30  DX_ONLY     0x00
5d10: 30 30 30 30 34 30 20 20 2f 2a 20 55 73 65 20 69  000040  /* Use i
5d20: 6e 64 65 78 20 6f 6e 6c 79 20 2d 20 6f 6d 69 74  ndex only - omit
5d30: 20 74 61 62 6c 65 20 2a 2f 0a 23 64 65 66 69 6e   table */.#defin
5d40: 65 20 57 48 45 52 45 5f 49 50 4b 20 20 20 20 20  e WHERE_IPK     
5d50: 20 20 20 20 20 30 78 30 30 30 30 30 31 30 30 20       0x00000100 
5d60: 20 2f 2a 20 78 20 69 73 20 74 68 65 20 49 4e 54   /* x is the INT
5d70: 45 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59  EGER PRIMARY KEY
5d80: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52   */.#define WHER
5d90: 45 5f 49 4e 44 45 58 45 44 20 20 20 20 20 20 30  E_INDEXED      0
5da0: 78 30 30 30 30 30 32 30 30 20 20 2f 2a 20 57 68  x00000200  /* Wh
5db0: 65 72 65 4c 6f 6f 70 2e 75 2e 62 74 72 65 65 2e  ereLoop.u.btree.
5dc0: 70 49 6e 64 65 78 20 69 73 20 76 61 6c 69 64 20  pIndex is valid 
5dd0: 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45  */.#define WHERE
5de0: 5f 56 49 52 54 55 41 4c 54 41 42 4c 45 20 30 78  _VIRTUALTABLE 0x
5df0: 30 30 30 30 30 34 30 30 20 20 2f 2a 20 57 68 65  00000400  /* Whe
5e00: 72 65 4c 6f 6f 70 2e 75 2e 76 74 61 62 20 69 73  reLoop.u.vtab is
5e10: 20 76 61 6c 69 64 20 2a 2f 0a 23 64 65 66 69 6e   valid */.#defin
5e20: 65 20 57 48 45 52 45 5f 49 4e 5f 41 42 4c 45 20  e WHERE_IN_ABLE 
5e30: 20 20 20 20 20 30 78 30 30 30 30 30 38 30 30 20       0x00000800 
5e40: 20 2f 2a 20 41 62 6c 65 20 74 6f 20 73 75 70 70   /* Able to supp
5e50: 6f 72 74 20 61 6e 20 49 4e 20 6f 70 65 72 61 74  ort an IN operat
5e60: 6f 72 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  or */.#define WH
5e70: 45 52 45 5f 4f 4e 45 52 4f 57 20 20 20 20 20 20  ERE_ONEROW      
5e80: 20 30 78 30 30 30 30 31 30 30 30 20 20 2f 2a 20   0x00001000  /* 
5e90: 53 65 6c 65 63 74 73 20 6e 6f 20 6d 6f 72 65 20  Selects no more 
5ea0: 74 68 61 6e 20 6f 6e 65 20 72 6f 77 20 2a 2f 0a  than one row */.
5eb0: 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f 4d 55  #define WHERE_MU
5ec0: 4c 54 49 5f 4f 52 20 20 20 20 20 30 78 30 30 30  LTI_OR     0x000
5ed0: 30 32 30 30 30 20 20 2f 2a 20 4f 52 20 75 73 69  02000  /* OR usi
5ee0: 6e 67 20 6d 75 6c 74 69 70 6c 65 20 69 6e 64 69  ng multiple indi
5ef0: 63 65 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  ces */.#define W
5f00: 48 45 52 45 5f 41 55 54 4f 5f 49 4e 44 45 58 20  HERE_AUTO_INDEX 
5f10: 20 20 30 78 30 30 30 30 34 30 30 30 20 20 2f 2a    0x00004000  /*
5f20: 20 55 73 65 73 20 61 6e 20 65 70 68 65 6d 65 72   Uses an ephemer
5f30: 61 6c 20 69 6e 64 65 78 20 2a 2f 0a 23 64 65 66  al index */.#def
5f40: 69 6e 65 20 57 48 45 52 45 5f 53 4b 49 50 53 43  ine WHERE_SKIPSC
5f50: 41 4e 20 20 20 20 20 30 78 30 30 30 30 38 30 30  AN     0x0000800
5f60: 30 20 20 2f 2a 20 55 73 65 73 20 74 68 65 20 73  0  /* Uses the s
5f70: 6b 69 70 2d 73 63 61 6e 20 61 6c 67 6f 72 69 74  kip-scan algorit
5f80: 68 6d 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  hm */.#define WH
5f90: 45 52 45 5f 55 4e 51 5f 57 41 4e 54 45 44 20 20  ERE_UNQ_WANTED  
5fa0: 20 30 78 30 30 30 31 30 30 30 30 20 20 2f 2a 20   0x00010000  /* 
5fb0: 57 48 45 52 45 5f 4f 4e 45 52 4f 57 20 77 6f 75  WHERE_ONEROW wou
5fc0: 6c 64 20 68 61 76 65 20 62 65 65 6e 20 68 65 6c  ld have been hel
5fd0: 70 66 75 6c 2a 2f 0a 23 64 65 66 69 6e 65 20 57  pful*/.#define W
5fe0: 48 45 52 45 5f 50 41 52 54 49 41 4c 49 44 58 20  HERE_PARTIALIDX 
5ff0: 20 20 30 78 30 30 30 32 30 30 30 30 20 20 2f 2a    0x00020000  /*
6000: 20 54 68 65 20 61 75 74 6f 6d 61 74 69 63 20 69   The automatic i
6010: 6e 64 65 78 20 69 73 20 70 61 72 74 69 61 6c 20  ndex is partial 
6020: 2a 2f 0a                                         */.