/ Hex Artifact Content
Login

Artifact 82c04c5075308abbac59180c8bad5ecb45b07453981f60a53f3c7dee21e1e971:


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 75 33 32  ATCH_BLOBS.  u32
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 28 74 69  ter register (ti
0b20: 6d 65 73 20 32 29 20 2a 2f 0a 20 20 69 6e 74 20  mes 2) */.  int 
0b30: 61 64 64 72 4c 69 6b 65 52 65 70 3b 20 20 20 20  addrLikeRep;    
0b40: 20 20 2f 2a 20 4c 49 4b 45 20 72 61 6e 67 65 20    /* LIKE range 
0b50: 70 72 6f 63 65 73 73 69 6e 67 20 61 64 64 72 65  processing addre
0b60: 73 73 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  ss */.#endif.  u
0b70: 38 20 69 46 72 6f 6d 3b 20 20 20 20 20 20 20 20  8 iFrom;        
0b80: 20 20 20 20 20 2f 2a 20 57 68 69 63 68 20 65 6e       /* Which en
0b90: 74 72 79 20 69 6e 20 74 68 65 20 46 52 4f 4d 20  try in the FROM 
0ba0: 63 6c 61 75 73 65 20 2a 2f 0a 20 20 75 38 20 6f  clause */.  u8 o
0bb0: 70 2c 20 70 33 2c 20 70 35 3b 20 20 20 20 20 20  p, p3, p5;      
0bc0: 20 20 2f 2a 20 4f 70 63 6f 64 65 2c 20 50 33 20    /* Opcode, P3 
0bd0: 26 20 50 35 20 6f 66 20 74 68 65 20 6f 70 63 6f  & P5 of the opco
0be0: 64 65 20 74 68 61 74 20 65 6e 64 73 20 74 68 65  de that ends the
0bf0: 20 6c 6f 6f 70 20 2a 2f 0a 20 20 69 6e 74 20 70   loop */.  int p
0c00: 31 2c 20 70 32 3b 20 20 20 20 20 20 20 20 20 20  1, p2;          
0c10: 20 2f 2a 20 4f 70 65 72 61 6e 64 73 20 6f 66 20   /* Operands of 
0c20: 74 68 65 20 6f 70 63 6f 64 65 20 75 73 65 64 20  the opcode used 
0c30: 74 6f 20 65 6e 64 73 20 74 68 65 20 6c 6f 6f 70  to ends the loop
0c40: 20 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b 20 20 20   */.  union {   
0c50: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
0c60: 6e 66 6f 72 6d 61 74 69 6f 6e 20 74 68 61 74 20  nformation that 
0c70: 64 65 70 65 6e 64 73 20 6f 6e 20 70 57 4c 6f 6f  depends on pWLoo
0c80: 70 2d 3e 77 73 46 6c 61 67 73 20 2a 2f 0a 20 20  p->wsFlags */.  
0c90: 20 20 73 74 72 75 63 74 20 7b 0a 20 20 20 20 20    struct {.     
0ca0: 20 69 6e 74 20 6e 49 6e 3b 20 20 20 20 20 20 20   int nIn;       
0cb0: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
0cc0: 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 61   of entries in a
0cd0: 49 6e 4c 6f 6f 70 5b 5d 20 2a 2f 0a 20 20 20 20  InLoop[] */.    
0ce0: 20 20 73 74 72 75 63 74 20 49 6e 4c 6f 6f 70 20    struct InLoop 
0cf0: 7b 0a 20 20 20 20 20 20 20 20 69 6e 74 20 69 43  {.        int iC
0d00: 75 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ur;             
0d10: 20 2f 2a 20 54 68 65 20 56 44 42 45 20 63 75 72   /* The VDBE cur
0d20: 73 6f 72 20 75 73 65 64 20 62 79 20 74 68 69 73  sor used by this
0d30: 20 49 4e 20 6f 70 65 72 61 74 6f 72 20 2a 2f 0a   IN operator */.
0d40: 20 20 20 20 20 20 20 20 69 6e 74 20 61 64 64 72          int addr
0d50: 49 6e 54 6f 70 3b 20 20 20 20 20 20 20 20 20 2f  InTop;         /
0d60: 2a 20 54 6f 70 20 6f 66 20 74 68 65 20 49 4e 20  * Top of the IN 
0d70: 6c 6f 6f 70 20 2a 2f 0a 20 20 20 20 20 20 20 20  loop */.        
0d80: 75 38 20 65 45 6e 64 4c 6f 6f 70 4f 70 3b 20 20  u8 eEndLoopOp;  
0d90: 20 20 20 20 20 20 20 2f 2a 20 49 4e 20 4c 6f 6f         /* IN Loo
0da0: 70 20 74 65 72 6d 69 6e 61 74 6f 72 2e 20 4f 50  p terminator. OP
0db0: 5f 4e 65 78 74 20 6f 72 20 4f 50 5f 50 72 65 76  _Next or OP_Prev
0dc0: 20 2a 2f 0a 20 20 20 20 20 20 7d 20 2a 61 49 6e   */.      } *aIn
0dd0: 4c 6f 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20  Loop;           
0de0: 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61  /* Information a
0df0: 62 6f 75 74 20 65 61 63 68 20 6e 65 73 74 65 64  bout each nested
0e00: 20 49 4e 20 6f 70 65 72 61 74 6f 72 20 2a 2f 0a   IN operator */.
0e10: 20 20 20 20 7d 20 69 6e 3b 20 20 20 20 20 20 20      } in;       
0e20: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65            /* Use
0e30: 64 20 77 68 65 6e 20 70 57 4c 6f 6f 70 2d 3e 77  d when pWLoop->w
0e40: 73 46 6c 61 67 73 26 57 48 45 52 45 5f 49 4e 5f  sFlags&WHERE_IN_
0e50: 41 42 4c 45 20 2a 2f 0a 20 20 20 20 49 6e 64 65  ABLE */.    Inde
0e60: 78 20 2a 70 43 6f 76 69 64 78 3b 20 20 20 20 20  x *pCovidx;     
0e70: 20 20 2f 2a 20 50 6f 73 73 69 62 6c 65 20 63 6f    /* Possible co
0e80: 76 65 72 69 6e 67 20 69 6e 64 65 78 20 66 6f 72  vering index for
0e90: 20 57 48 45 52 45 5f 4d 55 4c 54 49 5f 4f 52 20   WHERE_MULTI_OR 
0ea0: 2a 2f 0a 20 20 7d 20 75 3b 0a 20 20 73 74 72 75  */.  } u;.  stru
0eb0: 63 74 20 57 68 65 72 65 4c 6f 6f 70 20 2a 70 57  ct WhereLoop *pW
0ec0: 4c 6f 6f 70 3b 20 20 2f 2a 20 54 68 65 20 73 65  Loop;  /* The se
0ed0: 6c 65 63 74 65 64 20 57 68 65 72 65 4c 6f 6f 70  lected WhereLoop
0ee0: 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 42 69 74   object */.  Bit
0ef0: 6d 61 73 6b 20 6e 6f 74 52 65 61 64 79 3b 20 20  mask notReady;  
0f00: 20 20 20 20 20 20 20 20 2f 2a 20 46 52 4f 4d 20          /* FROM 
0f10: 65 6e 74 72 69 65 73 20 6e 6f 74 20 75 73 61 62  entries not usab
0f20: 6c 65 20 61 74 20 74 68 69 73 20 6c 65 76 65 6c  le at this level
0f30: 20 2a 2f 0a 23 69 66 64 65 66 20 53 51 4c 49 54   */.#ifdef SQLIT
0f40: 45 5f 45 4e 41 42 4c 45 5f 53 54 4d 54 5f 53 43  E_ENABLE_STMT_SC
0f50: 41 4e 53 54 41 54 55 53 0a 20 20 69 6e 74 20 61  ANSTATUS.  int a
0f60: 64 64 72 56 69 73 69 74 3b 20 20 20 20 20 20 20  ddrVisit;       
0f70: 20 2f 2a 20 41 64 64 72 65 73 73 20 61 74 20 77   /* Address at w
0f80: 68 69 63 68 20 72 6f 77 20 69 73 20 76 69 73 69  hich row is visi
0f90: 74 65 64 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d 3b  ted */.#endif.};
0fa0: 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 69 6e 73  ../*.** Each ins
0fb0: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
0fc0: 6a 65 63 74 20 72 65 70 72 65 73 65 6e 74 73 20  ject represents 
0fd0: 61 6e 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f 72  an algorithm for
0fe0: 20 65 76 61 6c 75 61 74 69 6e 67 20 6f 6e 65 0a   evaluating one.
0ff0: 2a 2a 20 74 65 72 6d 20 6f 66 20 61 20 6a 6f 69  ** term of a joi
1000: 6e 2e 20 20 45 76 65 72 79 20 74 65 72 6d 20 6f  n.  Every term o
1010: 66 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73  f the FROM claus
1020: 65 20 77 69 6c 6c 20 68 61 76 65 20 61 74 20 6c  e will have at l
1030: 65 61 73 74 0a 2a 2a 20 6f 6e 65 20 63 6f 72 72  east.** one corr
1040: 65 73 70 6f 6e 64 69 6e 67 20 57 68 65 72 65 4c  esponding WhereL
1050: 6f 6f 70 20 6f 62 6a 65 63 74 20 28 75 6e 6c 65  oop object (unle
1060: 73 73 20 49 4e 44 45 58 45 44 20 42 59 20 63 6f  ss INDEXED BY co
1070: 6e 73 74 72 61 69 6e 74 73 0a 2a 2a 20 70 72 65  nstraints.** pre
1080: 76 65 6e 74 20 61 20 71 75 65 72 79 20 73 6f 6c  vent a query sol
1090: 75 74 69 6f 6e 20 2d 20 77 68 69 63 68 20 69 73  ution - which is
10a0: 20 61 6e 20 65 72 72 6f 72 29 20 61 6e 64 20 6d   an error) and m
10b0: 61 6e 79 20 74 65 72 6d 73 20 6f 66 20 74 68 65  any terms of the
10c0: 0a 2a 2a 20 46 52 4f 4d 20 63 6c 61 75 73 65 20  .** FROM clause 
10d0: 77 69 6c 6c 20 68 61 76 65 20 6d 75 6c 74 69 70  will have multip
10e0: 6c 65 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a  le WhereLoop obj
10f0: 65 63 74 73 2c 20 65 61 63 68 20 64 65 73 63 72  ects, each descr
1100: 69 62 69 6e 67 20 61 0a 2a 2a 20 70 6f 74 65 6e  ibing a.** poten
1110: 74 69 61 6c 20 77 61 79 20 6f 66 20 69 6d 70 6c  tial way of impl
1120: 65 6d 65 6e 74 69 6e 67 20 74 68 61 74 20 46 52  ementing that FR
1130: 4f 4d 2d 63 6c 61 75 73 65 20 74 65 72 6d 2c 20  OM-clause term, 
1140: 74 6f 67 65 74 68 65 72 20 77 69 74 68 0a 2a 2a  together with.**
1150: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 6e   dependencies an
1160: 64 20 63 6f 73 74 20 65 73 74 69 6d 61 74 65 73  d cost estimates
1170: 20 66 6f 72 20 75 73 69 6e 67 20 74 68 65 20 63   for using the c
1180: 68 6f 73 65 6e 20 61 6c 67 6f 72 69 74 68 6d 2e  hosen algorithm.
1190: 0a 2a 2a 0a 2a 2a 20 51 75 65 72 79 20 70 6c 61  .**.** Query pla
11a0: 6e 6e 69 6e 67 20 63 6f 6e 73 69 73 74 73 20 6f  nning consists o
11b0: 66 20 62 75 69 6c 64 69 6e 67 20 75 70 20 61 20  f building up a 
11c0: 63 6f 6c 6c 65 63 74 69 6f 6e 20 6f 66 20 74 68  collection of th
11d0: 65 73 65 20 57 68 65 72 65 4c 6f 6f 70 0a 2a 2a  ese WhereLoop.**
11e0: 20 6f 62 6a 65 63 74 73 2c 20 74 68 65 6e 20 63   objects, then c
11f0: 6f 6d 70 75 74 69 6e 67 20 61 20 70 61 72 74 69  omputing a parti
1200: 63 75 6c 61 72 20 73 65 71 75 65 6e 63 65 20 6f  cular sequence o
1210: 66 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65  f WhereLoop obje
1220: 63 74 73 2c 20 77 69 74 68 0a 2a 2a 20 6f 6e 65  cts, with.** one
1230: 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63   WhereLoop objec
1240: 74 20 70 65 72 20 46 52 4f 4d 20 63 6c 61 75 73  t per FROM claus
1250: 65 20 74 65 72 6d 2c 20 74 68 61 74 20 73 61 74  e term, that sat
1260: 69 73 66 79 20 61 6c 6c 20 64 65 70 65 6e 64 65  isfy all depende
1270: 6e 63 69 65 73 0a 2a 2a 20 61 6e 64 20 74 68 61  ncies.** and tha
1280: 74 20 6d 69 6e 69 6d 69 7a 65 20 74 68 65 20 6f  t minimize the o
1290: 76 65 72 61 6c 6c 20 63 6f 73 74 2e 0a 2a 2f 0a  verall cost..*/.
12a0: 73 74 72 75 63 74 20 57 68 65 72 65 4c 6f 6f 70  struct WhereLoop
12b0: 20 7b 0a 20 20 42 69 74 6d 61 73 6b 20 70 72 65   {.  Bitmask pre
12c0: 72 65 71 3b 20 20 20 20 20 20 20 2f 2a 20 42 69  req;       /* Bi
12d0: 74 6d 61 73 6b 20 6f 66 20 6f 74 68 65 72 20 6c  tmask of other l
12e0: 6f 6f 70 73 20 74 68 61 74 20 6d 75 73 74 20 72  oops that must r
12f0: 75 6e 20 66 69 72 73 74 20 2a 2f 0a 20 20 42 69  un first */.  Bi
1300: 74 6d 61 73 6b 20 6d 61 73 6b 53 65 6c 66 3b 20  tmask maskSelf; 
1310: 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b 20 69      /* Bitmask i
1320: 64 65 6e 74 69 66 79 69 6e 67 20 74 61 62 6c 65  dentifying table
1330: 20 69 54 61 62 20 2a 2f 0a 23 69 66 64 65 66 20   iTab */.#ifdef 
1340: 53 51 4c 49 54 45 5f 44 45 42 55 47 0a 20 20 63  SQLITE_DEBUG.  c
1350: 68 61 72 20 63 49 64 3b 20 20 20 20 20 20 20 20  har cId;        
1360: 20 20 20 20 20 2f 2a 20 53 79 6d 62 6f 6c 69 63       /* Symbolic
1370: 20 49 44 20 6f 66 20 74 68 69 73 20 6c 6f 6f 70   ID of this loop
1380: 20 66 6f 72 20 64 65 62 75 67 67 69 6e 67 20 75   for debugging u
1390: 73 65 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  se */.#endif.  u
13a0: 38 20 69 54 61 62 3b 20 20 20 20 20 20 20 20 20  8 iTab;         
13b0: 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e       /* Position
13c0: 20 69 6e 20 46 52 4f 4d 20 63 6c 61 75 73 65 20   in FROM clause 
13d0: 6f 66 20 74 61 62 6c 65 20 66 6f 72 20 74 68 69  of table for thi
13e0: 73 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 38 20 69  s loop */.  u8 i
13f0: 53 6f 72 74 49 64 78 3b 20 20 20 20 20 20 20 20  SortIdx;        
1400: 20 20 2f 2a 20 53 6f 72 74 69 6e 67 20 69 6e 64    /* Sorting ind
1410: 65 78 20 6e 75 6d 62 65 72 2e 20 20 30 3d 3d 4e  ex number.  0==N
1420: 6f 6e 65 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20  one */.  LogEst 
1430: 72 53 65 74 75 70 3b 20 20 20 20 20 20 20 20 2f  rSetup;        /
1440: 2a 20 4f 6e 65 2d 74 69 6d 65 20 73 65 74 75 70  * One-time setup
1450: 20 63 6f 73 74 20 28 65 78 3a 20 63 72 65 61 74   cost (ex: creat
1460: 65 20 74 72 61 6e 73 69 65 6e 74 20 69 6e 64 65  e transient inde
1470: 78 29 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72  x) */.  LogEst r
1480: 52 75 6e 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  Run;          /*
1490: 20 43 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e 67   Cost of running
14a0: 20 65 61 63 68 20 6c 6f 6f 70 20 2a 2f 0a 20 20   each loop */.  
14b0: 4c 6f 67 45 73 74 20 6e 4f 75 74 3b 20 20 20 20  LogEst nOut;    
14c0: 20 20 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74        /* Estimat
14d0: 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74  ed number of out
14e0: 70 75 74 20 72 6f 77 73 20 2a 2f 0a 20 20 75 6e  put rows */.  un
14f0: 69 6f 6e 20 7b 0a 20 20 20 20 73 74 72 75 63 74  ion {.    struct
1500: 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 20 20   {              
1510: 20 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20   /* Information 
1520: 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 62 74 72  for internal btr
1530: 65 65 20 74 61 62 6c 65 73 20 2a 2f 0a 20 20 20  ee tables */.   
1540: 20 20 20 75 31 36 20 6e 45 71 3b 20 20 20 20 20     u16 nEq;     
1550: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1560: 62 65 72 20 6f 66 20 65 71 75 61 6c 69 74 79 20  ber of equality 
1570: 63 6f 6e 73 74 72 61 69 6e 74 73 20 2a 2f 0a 20  constraints */. 
1580: 20 20 20 20 20 75 31 36 20 6e 42 74 6d 3b 20 20       u16 nBtm;  
1590: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53              /* S
15a0: 69 7a 65 20 6f 66 20 42 54 4d 20 76 65 63 74 6f  ize of BTM vecto
15b0: 72 20 2a 2f 0a 20 20 20 20 20 20 75 31 36 20 6e  r */.      u16 n
15c0: 54 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20  Top;            
15d0: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 54 4f 50    /* Size of TOP
15e0: 20 76 65 63 74 6f 72 20 2a 2f 0a 20 20 20 20 20   vector */.     
15f0: 20 75 31 36 20 6e 49 64 78 43 6f 6c 3b 20 20 20   u16 nIdxCol;   
1600: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78          /* Index
1610: 20 63 6f 6c 75 6d 6e 20 75 73 65 64 20 66 6f 72   column used for
1620: 20 4f 52 44 45 52 20 42 59 20 2a 2f 0a 20 20 20   ORDER BY */.   
1630: 20 20 20 49 6e 64 65 78 20 2a 70 49 6e 64 65 78     Index *pIndex
1640: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64  ;         /* Ind
1650: 65 78 20 75 73 65 64 2c 20 6f 72 20 4e 55 4c 4c  ex used, or NULL
1660: 20 2a 2f 0a 20 20 20 20 7d 20 62 74 72 65 65 3b   */.    } btree;
1670: 0a 20 20 20 20 73 74 72 75 63 74 20 7b 20 20 20  .    struct {   
1680: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
1690: 6e 66 6f 72 6d 61 74 69 6f 6e 20 66 6f 72 20 76  nformation for v
16a0: 69 72 74 75 61 6c 20 74 61 62 6c 65 73 20 2a 2f  irtual tables */
16b0: 0a 20 20 20 20 20 20 69 6e 74 20 69 64 78 4e 75  .      int idxNu
16c0: 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  m;            /*
16d0: 20 49 6e 64 65 78 20 6e 75 6d 62 65 72 20 2a 2f   Index number */
16e0: 0a 20 20 20 20 20 20 75 38 20 6e 65 65 64 46 72  .      u8 needFr
16f0: 65 65 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ee;           /*
1700: 20 54 72 75 65 20 69 66 20 73 71 6c 69 74 65 33   True if sqlite3
1710: 5f 66 72 65 65 28 69 64 78 53 74 72 29 20 69 73  _free(idxStr) is
1720: 20 6e 65 65 64 65 64 20 2a 2f 0a 20 20 20 20 20   needed */.     
1730: 20 69 38 20 69 73 4f 72 64 65 72 65 64 3b 20 20   i8 isOrdered;  
1740: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
1750: 69 66 20 73 61 74 69 73 66 69 65 73 20 4f 52 44  if satisfies ORD
1760: 45 52 20 42 59 20 2a 2f 0a 20 20 20 20 20 20 75  ER BY */.      u
1770: 31 36 20 6f 6d 69 74 4d 61 73 6b 3b 20 20 20 20  16 omitMask;    
1780: 20 20 20 20 20 20 2f 2a 20 54 65 72 6d 73 20 74        /* Terms t
1790: 68 61 74 20 6d 61 79 20 62 65 20 6f 6d 69 74 74  hat may be omitt
17a0: 65 64 20 2a 2f 0a 20 20 20 20 20 20 63 68 61 72  ed */.      char
17b0: 20 2a 69 64 78 53 74 72 3b 20 20 20 20 20 20 20   *idxStr;       
17c0: 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 64 65 6e     /* Index iden
17d0: 74 69 66 69 65 72 20 73 74 72 69 6e 67 20 2a 2f  tifier string */
17e0: 0a 20 20 20 20 7d 20 76 74 61 62 3b 0a 20 20 7d  .    } vtab;.  }
17f0: 20 75 3b 0a 20 20 75 33 32 20 77 73 46 6c 61 67   u;.  u32 wsFlag
1800: 73 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57  s;          /* W
1810: 48 45 52 45 5f 2a 20 66 6c 61 67 73 20 64 65 73  HERE_* flags des
1820: 63 72 69 62 69 6e 67 20 74 68 65 20 70 6c 61 6e  cribing the plan
1830: 20 2a 2f 0a 20 20 75 31 36 20 6e 4c 54 65 72 6d   */.  u16 nLTerm
1840: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e  ;           /* N
1850: 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73  umber of entries
1860: 20 69 6e 20 61 4c 54 65 72 6d 5b 5d 20 2a 2f 0a   in aLTerm[] */.
1870: 20 20 75 31 36 20 6e 53 6b 69 70 3b 20 20 20 20    u16 nSkip;    
1880: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
1890: 72 20 6f 66 20 4e 55 4c 4c 20 61 4c 54 65 72 6d  r of NULL aLTerm
18a0: 5b 5d 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20  [] entries */.  
18b0: 2f 2a 2a 2a 2a 20 77 68 65 72 65 4c 6f 6f 70 58  /**** whereLoopX
18c0: 66 65 72 28 29 20 63 6f 70 69 65 73 20 66 69 65  fer() copies fie
18d0: 6c 64 73 20 61 62 6f 76 65 20 2a 2a 2a 2a 2a 2a  lds above ******
18e0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
18f0: 2a 2f 0a 23 20 64 65 66 69 6e 65 20 57 48 45 52  */.# define WHER
1900: 45 5f 4c 4f 4f 50 5f 58 46 45 52 5f 53 5a 20 6f  E_LOOP_XFER_SZ o
1910: 66 66 73 65 74 6f 66 28 57 68 65 72 65 4c 6f 6f  ffsetof(WhereLoo
1920: 70 2c 6e 4c 53 6c 6f 74 29 0a 20 20 75 31 36 20  p,nLSlot).  u16 
1930: 6e 4c 53 6c 6f 74 3b 20 20 20 20 20 20 20 20 20  nLSlot;         
1940: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 73    /* Number of s
1950: 6c 6f 74 73 20 61 6c 6c 6f 63 61 74 65 64 20 66  lots allocated f
1960: 6f 72 20 61 4c 54 65 72 6d 5b 5d 20 2a 2f 0a 20  or aLTerm[] */. 
1970: 20 57 68 65 72 65 54 65 72 6d 20 2a 2a 61 4c 54   WhereTerm **aLT
1980: 65 72 6d 3b 20 20 20 2f 2a 20 57 68 65 72 65 54  erm;   /* WhereT
1990: 65 72 6d 73 20 75 73 65 64 20 2a 2f 0a 20 20 57  erms used */.  W
19a0: 68 65 72 65 4c 6f 6f 70 20 2a 70 4e 65 78 74 4c  hereLoop *pNextL
19b0: 6f 6f 70 3b 20 2f 2a 20 4e 65 78 74 20 57 68 65  oop; /* Next Whe
19c0: 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 20 69 6e  reLoop object in
19d0: 20 74 68 65 20 57 68 65 72 65 43 6c 61 75 73 65   the WhereClause
19e0: 20 2a 2f 0a 20 20 57 68 65 72 65 54 65 72 6d 20   */.  WhereTerm 
19f0: 2a 61 4c 54 65 72 6d 53 70 61 63 65 5b 33 5d 3b  *aLTermSpace[3];
1a00: 20 20 2f 2a 20 49 6e 69 74 69 61 6c 20 61 4c 54    /* Initial aLT
1a10: 65 72 6d 5b 5d 20 73 70 61 63 65 20 2a 2f 0a 7d  erm[] space */.}
1a20: 3b 0a 0a 2f 2a 20 54 68 69 73 20 6f 62 6a 65 63  ;../* This objec
1a30: 74 20 68 6f 6c 64 73 20 74 68 65 20 70 72 65 72  t holds the prer
1a40: 65 71 75 69 73 69 74 65 73 20 61 6e 64 20 74 68  equisites and th
1a50: 65 20 63 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e  e cost of runnin
1a60: 67 20 61 0a 2a 2a 20 73 75 62 71 75 65 72 79 20  g a.** subquery 
1a70: 6f 6e 20 6f 6e 65 20 6f 70 65 72 61 6e 64 20 6f  on one operand o
1a80: 66 20 61 6e 20 4f 52 20 6f 70 65 72 61 74 6f 72  f an OR operator
1a90: 20 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c   in the WHERE cl
1aa0: 61 75 73 65 2e 0a 2a 2a 20 53 65 65 20 57 68 65  ause..** See Whe
1ab0: 72 65 4f 72 53 65 74 20 66 6f 72 20 61 64 64 69  reOrSet for addi
1ac0: 74 69 6f 6e 61 6c 20 69 6e 66 6f 72 6d 61 74 69  tional informati
1ad0: 6f 6e 20 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68  on .*/.struct Wh
1ae0: 65 72 65 4f 72 43 6f 73 74 20 7b 0a 20 20 42 69  ereOrCost {.  Bi
1af0: 74 6d 61 73 6b 20 70 72 65 72 65 71 3b 20 20 20  tmask prereq;   
1b00: 20 20 2f 2a 20 50 72 65 72 65 71 75 69 73 69 74    /* Prerequisit
1b10: 65 73 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72  es */.  LogEst r
1b20: 52 75 6e 3b 20 20 20 20 20 20 20 20 2f 2a 20 43  Run;        /* C
1b30: 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e 67 20 74  ost of running t
1b40: 68 69 73 20 73 75 62 71 75 65 72 79 20 2a 2f 0a  his subquery */.
1b50: 20 20 4c 6f 67 45 73 74 20 6e 4f 75 74 3b 20 20    LogEst nOut;  
1b60: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
1b70: 6f 66 20 6f 75 74 70 75 74 73 20 66 6f 72 20 74  of outputs for t
1b80: 68 69 73 20 73 75 62 71 75 65 72 79 20 2a 2f 0a  his subquery */.
1b90: 7d 3b 0a 0a 2f 2a 20 54 68 65 20 57 68 65 72 65  };../* The Where
1ba0: 4f 72 53 65 74 20 6f 62 6a 65 63 74 20 68 6f 6c  OrSet object hol
1bb0: 64 73 20 61 20 73 65 74 20 6f 66 20 70 6f 73 73  ds a set of poss
1bc0: 69 62 6c 65 20 57 68 65 72 65 4f 72 43 6f 73 74  ible WhereOrCost
1bd0: 73 20 74 68 61 74 0a 2a 2a 20 63 6f 72 72 65 73  s that.** corres
1be0: 70 6f 6e 64 20 74 6f 20 74 68 65 20 73 75 62 71  pond to the subq
1bf0: 75 65 72 79 28 73 29 20 6f 66 20 4f 52 2d 63 6c  uery(s) of OR-cl
1c00: 61 75 73 65 20 70 72 6f 63 65 73 73 69 6e 67 2e  ause processing.
1c10: 20 20 4f 6e 6c 79 20 74 68 65 0a 2a 2a 20 62 65    Only the.** be
1c20: 73 74 20 4e 5f 4f 52 5f 43 4f 53 54 20 65 6c 65  st N_OR_COST ele
1c30: 6d 65 6e 74 73 20 61 72 65 20 72 65 74 61 69 6e  ments are retain
1c40: 65 64 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4e  ed..*/.#define N
1c50: 5f 4f 52 5f 43 4f 53 54 20 33 0a 73 74 72 75 63  _OR_COST 3.struc
1c60: 74 20 57 68 65 72 65 4f 72 53 65 74 20 7b 0a 20  t WhereOrSet {. 
1c70: 20 75 31 36 20 6e 3b 20 20 20 20 20 20 20 20 20   u16 n;         
1c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1c90: 4e 75 6d 62 65 72 20 6f 66 20 76 61 6c 69 64 20  Number of valid 
1ca0: 61 5b 5d 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20  a[] entries */. 
1cb0: 20 57 68 65 72 65 4f 72 43 6f 73 74 20 61 5b 4e   WhereOrCost a[N
1cc0: 5f 4f 52 5f 43 4f 53 54 5d 3b 20 20 20 2f 2a 20  _OR_COST];   /* 
1cd0: 53 65 74 20 6f 66 20 62 65 73 74 20 63 6f 73 74  Set of best cost
1ce0: 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 45  s */.};../*.** E
1cf0: 61 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20  ach instance of 
1d00: 74 68 69 73 20 6f 62 6a 65 63 74 20 68 6f 6c 64  this object hold
1d10: 73 20 61 20 73 65 71 75 65 6e 63 65 20 6f 66 20  s a sequence of 
1d20: 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74  WhereLoop object
1d30: 73 0a 2a 2a 20 74 68 61 74 20 69 6d 70 6c 65 6d  s.** that implem
1d40: 65 6e 74 20 73 6f 6d 65 20 6f 72 20 61 6c 6c 20  ent some or all 
1d50: 6f 66 20 61 20 71 75 65 72 79 20 70 6c 61 6e 2e  of a query plan.
1d60: 0a 2a 2a 0a 2a 2a 20 54 68 69 6e 6b 20 6f 66 20  .**.** Think of 
1d70: 65 61 63 68 20 57 68 65 72 65 4c 6f 6f 70 20 6f  each WhereLoop o
1d80: 62 6a 65 63 74 20 61 73 20 61 20 6e 6f 64 65 20  bject as a node 
1d90: 69 6e 20 61 20 67 72 61 70 68 20 77 69 74 68 20  in a graph with 
1da0: 61 72 63 73 0a 2a 2a 20 73 68 6f 77 69 6e 67 20  arcs.** showing 
1db0: 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 6e 64  dependencies and
1dc0: 20 63 6f 73 74 73 20 66 6f 72 20 74 72 61 76 65   costs for trave
1dd0: 6c 6c 69 6e 67 20 62 65 74 77 65 65 6e 20 6e 6f  lling between no
1de0: 64 65 73 2e 20 20 28 54 68 61 74 20 69 73 0a 2a  des.  (That is.*
1df0: 2a 20 6e 6f 74 20 61 20 63 6f 6d 70 6c 65 74 65  * not a complete
1e00: 6c 79 20 61 63 63 75 72 61 74 65 20 64 65 73 63  ly accurate desc
1e10: 72 69 70 74 69 6f 6e 20 62 65 63 61 75 73 65 20  ription because 
1e20: 57 68 65 72 65 4c 6f 6f 70 20 63 6f 73 74 73 20  WhereLoop costs 
1e30: 61 72 65 20 61 0a 2a 2a 20 76 65 63 74 6f 72 2c  are a.** vector,
1e40: 20 6e 6f 74 20 61 20 73 63 61 6c 61 72 2c 20 61   not a scalar, a
1e50: 6e 64 20 62 65 63 61 75 73 65 20 64 65 70 65 6e  nd because depen
1e60: 64 65 6e 63 69 65 73 20 61 72 65 20 6d 61 6e 79  dencies are many
1e70: 2d 74 6f 2d 6f 6e 65 2c 20 6e 6f 74 0a 2a 2a 20  -to-one, not.** 
1e80: 6f 6e 65 2d 74 6f 2d 6f 6e 65 20 61 73 20 61 72  one-to-one as ar
1e90: 65 20 67 72 61 70 68 20 6e 6f 64 65 73 2e 20 20  e graph nodes.  
1ea0: 42 75 74 20 69 74 20 69 73 20 61 20 75 73 65 66  But it is a usef
1eb0: 75 6c 20 76 69 73 75 61 6c 69 7a 61 74 69 6f 6e  ul visualization
1ec0: 20 61 69 64 2e 29 0a 2a 2a 20 54 68 65 6e 20 61   aid.).** Then a
1ed0: 20 57 68 65 72 65 50 61 74 68 20 6f 62 6a 65 63   WherePath objec
1ee0: 74 20 69 73 20 61 20 70 61 74 68 20 74 68 72 6f  t is a path thro
1ef0: 75 67 68 20 74 68 65 20 67 72 61 70 68 20 74 68  ugh the graph th
1f00: 61 74 20 76 69 73 69 74 73 20 73 6f 6d 65 0a 2a  at visits some.*
1f10: 2a 20 6f 72 20 61 6c 6c 20 6f 66 20 74 68 65 20  * or all of the 
1f20: 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74  WhereLoop object
1f30: 73 20 6f 6e 63 65 2e 0a 2a 2a 0a 2a 2a 20 54 68  s once..**.** Th
1f40: 65 20 22 73 6f 6c 76 65 72 22 20 77 6f 72 6b 73  e "solver" works
1f50: 20 62 79 20 63 72 65 61 74 69 6e 67 20 74 68 65   by creating the
1f60: 20 4e 20 62 65 73 74 20 57 68 65 72 65 50 61 74   N best WherePat
1f70: 68 20 6f 62 6a 65 63 74 73 20 6f 66 20 6c 65 6e  h objects of len
1f80: 67 74 68 0a 2a 2a 20 31 2e 20 20 54 68 65 6e 20  gth.** 1.  Then 
1f90: 75 73 69 6e 67 20 74 68 6f 73 65 20 61 73 20 61  using those as a
1fa0: 20 62 61 73 69 73 20 74 6f 20 63 6f 6d 70 75 74   basis to comput
1fb0: 65 20 74 68 65 20 4e 20 62 65 73 74 20 57 68 65  e the N best Whe
1fc0: 72 65 50 61 74 68 20 6f 62 6a 65 63 74 73 0a 2a  rePath objects.*
1fd0: 2a 20 6f 66 20 6c 65 6e 67 74 68 20 32 2e 20 20  * of length 2.  
1fe0: 41 6e 64 20 73 6f 20 66 6f 72 74 68 20 75 6e 74  And so forth unt
1ff0: 69 6c 20 74 68 65 20 6c 65 6e 67 74 68 20 6f 66  il the length of
2000: 20 57 68 65 72 65 50 61 74 68 73 20 65 71 75 61   WherePaths equa
2010: 6c 73 20 74 68 65 0a 2a 2a 20 6e 75 6d 62 65 72  ls the.** number
2020: 20 6f 66 20 6e 6f 64 65 73 20 69 6e 20 74 68 65   of nodes in the
2030: 20 46 52 4f 4d 20 63 6c 61 75 73 65 2e 20 20 54   FROM clause.  T
2040: 68 65 20 62 65 73 74 20 28 6c 6f 77 65 73 74 20  he best (lowest 
2050: 63 6f 73 74 29 20 57 68 65 72 65 50 61 74 68 0a  cost) WherePath.
2060: 2a 2a 20 61 74 20 74 68 65 20 65 6e 64 20 69 73  ** at the end is
2070: 20 74 68 65 20 63 68 6f 73 65 6e 20 71 75 65 72   the chosen quer
2080: 79 20 70 6c 61 6e 2e 0a 2a 2f 0a 73 74 72 75 63  y plan..*/.struc
2090: 74 20 57 68 65 72 65 50 61 74 68 20 7b 0a 20 20  t WherePath {.  
20a0: 42 69 74 6d 61 73 6b 20 6d 61 73 6b 4c 6f 6f 70  Bitmask maskLoop
20b0: 3b 20 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b  ;     /* Bitmask
20c0: 20 6f 66 20 61 6c 6c 20 57 68 65 72 65 4c 6f 6f   of all WhereLoo
20d0: 70 20 6f 62 6a 65 63 74 73 20 69 6e 20 74 68 69  p objects in thi
20e0: 73 20 70 61 74 68 20 2a 2f 0a 20 20 42 69 74 6d  s path */.  Bitm
20f0: 61 73 6b 20 72 65 76 4c 6f 6f 70 3b 20 20 20 20  ask revLoop;    
2100: 20 20 2f 2a 20 61 4c 6f 6f 70 5b 5d 73 20 74 68    /* aLoop[]s th
2110: 61 74 20 73 68 6f 75 6c 64 20 62 65 20 72 65 76  at should be rev
2120: 65 72 73 65 64 20 66 6f 72 20 4f 52 44 45 52 20  ersed for ORDER 
2130: 42 59 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 6e  BY */.  LogEst n
2140: 52 6f 77 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  Row;          /*
2150: 20 45 73 74 69 6d 61 74 65 64 20 6e 75 6d 62 65   Estimated numbe
2160: 72 20 6f 66 20 72 6f 77 73 20 67 65 6e 65 72 61  r of rows genera
2170: 74 65 64 20 62 79 20 74 68 69 73 20 70 61 74 68  ted by this path
2180: 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72 43 6f   */.  LogEst rCo
2190: 73 74 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54  st;         /* T
21a0: 6f 74 61 6c 20 63 6f 73 74 20 6f 66 20 74 68 69  otal cost of thi
21b0: 73 20 70 61 74 68 20 2a 2f 0a 20 20 4c 6f 67 45  s path */.  LogE
21c0: 73 74 20 72 55 6e 73 6f 72 74 65 64 3b 20 20 20  st rUnsorted;   
21d0: 20 20 2f 2a 20 54 6f 74 61 6c 20 63 6f 73 74 20    /* Total cost 
21e0: 6f 66 20 74 68 69 73 20 70 61 74 68 20 69 67 6e  of this path ign
21f0: 6f 72 69 6e 67 20 73 6f 72 74 69 6e 67 20 63 6f  oring sorting co
2200: 73 74 73 20 2a 2f 0a 20 20 69 38 20 69 73 4f 72  sts */.  i8 isOr
2210: 64 65 72 65 64 3b 20 20 20 20 20 20 20 20 20 2f  dered;         /
2220: 2a 20 4e 6f 2e 20 6f 66 20 4f 52 44 45 52 20 42  * No. of ORDER B
2230: 59 20 74 65 72 6d 73 20 73 61 74 69 73 66 69 65  Y terms satisfie
2240: 64 2e 20 2d 31 20 66 6f 72 20 75 6e 6b 6e 6f 77  d. -1 for unknow
2250: 6e 20 2a 2f 0a 20 20 57 68 65 72 65 4c 6f 6f 70  n */.  WhereLoop
2260: 20 2a 2a 61 4c 6f 6f 70 3b 20 20 20 20 2f 2a 20   **aLoop;    /* 
2270: 41 72 72 61 79 20 6f 66 20 57 68 65 72 65 4c 6f  Array of WhereLo
2280: 6f 70 20 6f 62 6a 65 63 74 73 20 69 6d 70 6c 65  op objects imple
2290: 6d 65 6e 74 69 6e 67 20 74 68 69 73 20 70 61 74  menting this pat
22a0: 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54  h */.};../*.** T
22b0: 68 65 20 71 75 65 72 79 20 67 65 6e 65 72 61 74  he query generat
22c0: 6f 72 20 75 73 65 73 20 61 6e 20 61 72 72 61 79  or uses an array
22d0: 20 6f 66 20 69 6e 73 74 61 6e 63 65 73 20 6f 66   of instances of
22e0: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20   this structure 
22f0: 74 6f 0a 2a 2a 20 68 65 6c 70 20 69 74 20 61 6e  to.** help it an
2300: 61 6c 79 7a 65 20 74 68 65 20 73 75 62 65 78 70  alyze the subexp
2310: 72 65 73 73 69 6f 6e 73 20 6f 66 20 74 68 65 20  ressions of the 
2320: 57 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20 45  WHERE clause.  E
2330: 61 63 68 20 57 48 45 52 45 0a 2a 2a 20 63 6c 61  ach WHERE.** cla
2340: 75 73 65 20 73 75 62 65 78 70 72 65 73 73 69 6f  use subexpressio
2350: 6e 20 69 73 20 73 65 70 61 72 61 74 65 64 20 66  n is separated f
2360: 72 6f 6d 20 74 68 65 20 6f 74 68 65 72 73 20 62  rom the others b
2370: 79 20 41 4e 44 20 6f 70 65 72 61 74 6f 72 73 2c  y AND operators,
2380: 0a 2a 2a 20 75 73 75 61 6c 6c 79 2c 20 6f 72 20  .** usually, or 
2390: 73 6f 6d 65 74 69 6d 65 73 20 73 75 62 65 78 70  sometimes subexp
23a0: 72 65 73 73 69 6f 6e 73 20 73 65 70 61 72 61 74  ressions separat
23b0: 65 64 20 62 79 20 4f 52 2e 0a 2a 2a 0a 2a 2a 20  ed by OR..**.** 
23c0: 41 6c 6c 20 57 68 65 72 65 54 65 72 6d 73 20 61  All WhereTerms a
23d0: 72 65 20 63 6f 6c 6c 65 63 74 65 64 20 69 6e 74  re collected int
23e0: 6f 20 61 20 73 69 6e 67 6c 65 20 57 68 65 72 65  o a single Where
23f0: 43 6c 61 75 73 65 20 73 74 72 75 63 74 75 72 65  Clause structure
2400: 2e 20 20 0a 2a 2a 20 54 68 65 20 66 6f 6c 6c 6f  .  .** The follo
2410: 77 69 6e 67 20 69 64 65 6e 74 69 74 79 20 68 6f  wing identity ho
2420: 6c 64 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20  lds:.**.**      
2430: 20 20 57 68 65 72 65 54 65 72 6d 2e 70 57 43 2d    WhereTerm.pWC-
2440: 3e 61 5b 57 68 65 72 65 54 65 72 6d 2e 69 64 78  >a[WhereTerm.idx
2450: 5d 20 3d 3d 20 57 68 65 72 65 54 65 72 6d 0a 2a  ] == WhereTerm.*
2460: 2a 0a 2a 2a 20 57 68 65 6e 20 61 20 74 65 72 6d  *.** When a term
2470: 20 69 73 20 6f 66 20 74 68 65 20 66 6f 72 6d 3a   is of the form:
2480: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  .**.**          
2490: 20 20 20 20 58 20 3c 6f 70 3e 20 3c 65 78 70 72      X <op> <expr
24a0: 3e 0a 2a 2a 0a 2a 2a 20 77 68 65 72 65 20 58 20  >.**.** where X 
24b0: 69 73 20 61 20 63 6f 6c 75 6d 6e 20 6e 61 6d 65  is a column name
24c0: 20 61 6e 64 20 3c 6f 70 3e 20 69 73 20 6f 6e 65   and <op> is one
24d0: 20 6f 66 20 63 65 72 74 61 69 6e 20 6f 70 65 72   of certain oper
24e0: 61 74 6f 72 73 2c 0a 2a 2a 20 74 68 65 6e 20 57  ators,.** then W
24f0: 68 65 72 65 54 65 72 6d 2e 6c 65 66 74 43 75 72  hereTerm.leftCur
2500: 73 6f 72 20 61 6e 64 20 57 68 65 72 65 54 65 72  sor and WhereTer
2510: 6d 2e 75 2e 6c 65 66 74 43 6f 6c 75 6d 6e 20 72  m.u.leftColumn r
2520: 65 63 6f 72 64 20 74 68 65 0a 2a 2a 20 63 75 72  ecord the.** cur
2530: 73 6f 72 20 6e 75 6d 62 65 72 20 61 6e 64 20 63  sor number and c
2540: 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20 66 6f 72  olumn number for
2550: 20 58 2e 20 20 57 68 65 72 65 54 65 72 6d 2e 65   X.  WhereTerm.e
2560: 4f 70 65 72 61 74 6f 72 20 72 65 63 6f 72 64 73  Operator records
2570: 0a 2a 2a 20 74 68 65 20 3c 6f 70 3e 20 75 73 69  .** the <op> usi
2580: 6e 67 20 61 20 62 69 74 6d 61 73 6b 20 65 6e 63  ng a bitmask enc
2590: 6f 64 69 6e 67 20 64 65 66 69 6e 65 64 20 62 79  oding defined by
25a0: 20 57 4f 5f 78 78 78 20 62 65 6c 6f 77 2e 20 20   WO_xxx below.  
25b0: 54 68 65 0a 2a 2a 20 75 73 65 20 6f 66 20 61 20  The.** use of a 
25c0: 62 69 74 6d 61 73 6b 20 65 6e 63 6f 64 69 6e 67  bitmask encoding
25d0: 20 66 6f 72 20 74 68 65 20 6f 70 65 72 61 74 6f   for the operato
25e0: 72 20 61 6c 6c 6f 77 73 20 75 73 20 74 6f 20 73  r allows us to s
25f0: 65 61 72 63 68 0a 2a 2a 20 71 75 69 63 6b 6c 79  earch.** quickly
2600: 20 66 6f 72 20 74 65 72 6d 73 20 74 68 61 74 20   for terms that 
2610: 6d 61 74 63 68 20 61 6e 79 20 6f 66 20 73 65 76  match any of sev
2620: 65 72 61 6c 20 64 69 66 66 65 72 65 6e 74 20 6f  eral different o
2630: 70 65 72 61 74 6f 72 73 2e 0a 2a 2a 0a 2a 2a 20  perators..**.** 
2640: 41 20 57 68 65 72 65 54 65 72 6d 20 6d 69 67 68  A WhereTerm migh
2650: 74 20 61 6c 73 6f 20 62 65 20 74 77 6f 20 6f 72  t also be two or
2660: 20 6d 6f 72 65 20 73 75 62 74 65 72 6d 73 20 63   more subterms c
2670: 6f 6e 6e 65 63 74 65 64 20 62 79 20 4f 52 3a 0a  onnected by OR:.
2680: 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20 28 74  **.**         (t
2690: 31 2e 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 29  1.X <op> <expr>)
26a0: 20 4f 52 20 28 74 31 2e 59 20 3c 6f 70 3e 20 3c   OR (t1.Y <op> <
26b0: 65 78 70 72 3e 29 20 4f 52 20 2e 2e 2e 2e 0a 2a  expr>) OR .....*
26c0: 2a 0a 2a 2a 20 49 6e 20 74 68 69 73 20 73 65 63  *.** In this sec
26d0: 6f 6e 64 20 63 61 73 65 2c 20 77 74 46 6c 61 67  ond case, wtFlag
26e0: 20 68 61 73 20 74 68 65 20 54 45 52 4d 5f 4f 52   has the TERM_OR
26f0: 49 4e 46 4f 20 62 69 74 20 73 65 74 20 61 6e 64  INFO bit set and
2700: 20 65 4f 70 65 72 61 74 6f 72 3d 3d 57 4f 5f 4f   eOperator==WO_O
2710: 52 0a 2a 2a 20 61 6e 64 20 74 68 65 20 57 68 65  R.** and the Whe
2720: 72 65 54 65 72 6d 2e 75 2e 70 4f 72 49 6e 66 6f  reTerm.u.pOrInfo
2730: 20 66 69 65 6c 64 20 70 6f 69 6e 74 73 20 74 6f   field points to
2740: 20 61 75 78 69 6c 69 61 72 79 20 69 6e 66 6f 72   auxiliary infor
2750: 6d 61 74 69 6f 6e 20 74 68 61 74 0a 2a 2a 20 69  mation that.** i
2760: 73 20 63 6f 6c 6c 65 63 74 65 64 20 61 62 6f 75  s collected abou
2770: 74 20 74 68 65 20 4f 52 20 63 6c 61 75 73 65 2e  t the OR clause.
2780: 0a 2a 2a 0a 2a 2a 20 49 66 20 61 20 74 65 72 6d  .**.** If a term
2790: 20 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c   in the WHERE cl
27a0: 61 75 73 65 20 64 6f 65 73 20 6e 6f 74 20 6d 61  ause does not ma
27b0: 74 63 68 20 65 69 74 68 65 72 20 6f 66 20 74 68  tch either of th
27c0: 65 20 74 77 6f 20 70 72 65 76 69 6f 75 73 0a 2a  e two previous.*
27d0: 2a 20 63 61 74 65 67 6f 72 69 65 73 2c 20 74 68  * categories, th
27e0: 65 6e 20 65 4f 70 65 72 61 74 6f 72 3d 3d 30 2e  en eOperator==0.
27f0: 20 20 54 68 65 20 57 68 65 72 65 54 65 72 6d 2e    The WhereTerm.
2800: 70 45 78 70 72 20 66 69 65 6c 64 20 69 73 20 73  pExpr field is s
2810: 74 69 6c 6c 20 73 65 74 0a 2a 2a 20 74 6f 20 74  till set.** to t
2820: 68 65 20 6f 72 69 67 69 6e 61 6c 20 73 75 62 65  he original sube
2830: 78 70 72 65 73 73 69 6f 6e 20 63 6f 6e 74 65 6e  xpression conten
2840: 74 20 61 6e 64 20 77 74 46 6c 61 67 73 20 69 73  t and wtFlags is
2850: 20 73 65 74 20 75 70 20 61 70 70 72 6f 70 72 69   set up appropri
2860: 61 74 65 6c 79 0a 2a 2a 20 62 75 74 20 6e 6f 20  ately.** but no 
2870: 6f 74 68 65 72 20 66 69 65 6c 64 73 20 69 6e 20  other fields in 
2880: 74 68 65 20 57 68 65 72 65 54 65 72 6d 20 6f 62  the WhereTerm ob
2890: 6a 65 63 74 20 61 72 65 20 6d 65 61 6e 69 6e 67  ject are meaning
28a0: 66 75 6c 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20  ful..**.** When 
28b0: 65 4f 70 65 72 61 74 6f 72 21 3d 30 2c 20 70 72  eOperator!=0, pr
28c0: 65 72 65 71 52 69 67 68 74 20 61 6e 64 20 70 72  ereqRight and pr
28d0: 65 72 65 71 41 6c 6c 20 72 65 63 6f 72 64 20 73  ereqAll record s
28e0: 65 74 73 20 6f 66 20 63 75 72 73 6f 72 20 6e 75  ets of cursor nu
28f0: 6d 62 65 72 73 2c 0a 2a 2a 20 62 75 74 20 74 68  mbers,.** but th
2900: 65 79 20 64 6f 20 73 6f 20 69 6e 64 69 72 65 63  ey do so indirec
2910: 74 6c 79 2e 20 20 41 20 73 69 6e 67 6c 65 20 57  tly.  A single W
2920: 68 65 72 65 4d 61 73 6b 53 65 74 20 73 74 72 75  hereMaskSet stru
2930: 63 74 75 72 65 20 74 72 61 6e 73 6c 61 74 65 73  cture translates
2940: 0a 2a 2a 20 63 75 72 73 6f 72 20 6e 75 6d 62 65  .** cursor numbe
2950: 72 20 69 6e 74 6f 20 62 69 74 73 20 61 6e 64 20  r into bits and 
2960: 74 68 65 20 74 72 61 6e 73 6c 61 74 65 64 20 62  the translated b
2970: 69 74 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20  it is stored in 
2980: 74 68 65 20 70 72 65 72 65 71 0a 2a 2a 20 66 69  the prereq.** fi
2990: 65 6c 64 73 2e 20 20 54 68 65 20 74 72 61 6e 73  elds.  The trans
29a0: 6c 61 74 69 6f 6e 20 69 73 20 75 73 65 64 20 69  lation is used i
29b0: 6e 20 6f 72 64 65 72 20 74 6f 20 6d 61 78 69 6d  n order to maxim
29c0: 69 7a 65 20 74 68 65 20 6e 75 6d 62 65 72 20 6f  ize the number o
29d0: 66 0a 2a 2a 20 62 69 74 73 20 74 68 61 74 20 77  f.** bits that w
29e0: 69 6c 6c 20 66 69 74 20 69 6e 20 61 20 42 69 74  ill fit in a Bit
29f0: 6d 61 73 6b 2e 20 20 54 68 65 20 56 44 42 45 20  mask.  The VDBE 
2a00: 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 6d  cursor numbers m
2a10: 69 67 68 74 20 62 65 0a 2a 2a 20 73 70 72 65 61  ight be.** sprea
2a20: 64 20 6f 75 74 20 6f 76 65 72 20 74 68 65 20 6e  d out over the n
2a30: 6f 6e 2d 6e 65 67 61 74 69 76 65 20 69 6e 74 65  on-negative inte
2a40: 67 65 72 73 2e 20 20 46 6f 72 20 65 78 61 6d 70  gers.  For examp
2a50: 6c 65 2c 20 74 68 65 20 63 75 72 73 6f 72 0a 2a  le, the cursor.*
2a60: 2a 20 6e 75 6d 62 65 72 73 20 6d 69 67 68 74 20  * numbers might 
2a70: 62 65 20 33 2c 20 38 2c 20 39 2c 20 31 30 2c 20  be 3, 8, 9, 10, 
2a80: 32 30 2c 20 32 33 2c 20 34 31 2c 20 61 6e 64 20  20, 23, 41, and 
2a90: 34 35 2e 20 20 54 68 65 20 57 68 65 72 65 4d 61  45.  The WhereMa
2aa0: 73 6b 53 65 74 0a 2a 2a 20 74 72 61 6e 73 6c 61  skSet.** transla
2ab0: 74 65 73 20 74 68 65 73 65 20 73 70 61 72 73 65  tes these sparse
2ac0: 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20   cursor numbers 
2ad0: 69 6e 74 6f 20 63 6f 6e 73 65 63 75 74 69 76 65  into consecutive
2ae0: 20 69 6e 74 65 67 65 72 73 0a 2a 2a 20 62 65 67   integers.** beg
2af0: 69 6e 6e 69 6e 67 20 77 69 74 68 20 30 20 69 6e  inning with 0 in
2b00: 20 6f 72 64 65 72 20 74 6f 20 6d 61 6b 65 20 74   order to make t
2b10: 68 65 20 62 65 73 74 20 70 6f 73 73 69 62 6c 65  he best possible
2b20: 20 75 73 65 20 6f 66 20 74 68 65 20 61 76 61 69   use of the avai
2b30: 6c 61 62 6c 65 0a 2a 2a 20 62 69 74 73 20 69 6e  lable.** bits in
2b40: 20 74 68 65 20 42 69 74 6d 61 73 6b 2e 20 20 53   the Bitmask.  S
2b50: 6f 2c 20 69 6e 20 74 68 65 20 65 78 61 6d 70 6c  o, in the exampl
2b60: 65 20 61 62 6f 76 65 2c 20 74 68 65 20 63 75 72  e above, the cur
2b70: 73 6f 72 20 6e 75 6d 62 65 72 73 0a 2a 2a 20 77  sor numbers.** w
2b80: 6f 75 6c 64 20 62 65 20 6d 61 70 70 65 64 20 69  ould be mapped i
2b90: 6e 74 6f 20 69 6e 74 65 67 65 72 73 20 30 20 74  nto integers 0 t
2ba0: 68 72 6f 75 67 68 20 37 2e 0a 2a 2a 0a 2a 2a 20  hrough 7..**.** 
2bb0: 54 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 65  The number of te
2bc0: 72 6d 73 20 69 6e 20 61 20 6a 6f 69 6e 20 69 73  rms in a join is
2bd0: 20 6c 69 6d 69 74 65 64 20 62 79 20 74 68 65 20   limited by the 
2be0: 6e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 0a 2a  number of bits.*
2bf0: 2a 20 69 6e 20 70 72 65 72 65 71 52 69 67 68 74  * in prereqRight
2c00: 20 61 6e 64 20 70 72 65 72 65 71 41 6c 6c 2e 20   and prereqAll. 
2c10: 20 54 68 65 20 64 65 66 61 75 6c 74 20 69 73 20   The default is 
2c20: 36 34 20 62 69 74 73 2c 20 68 65 6e 63 65 20 53  64 bits, hence S
2c30: 51 4c 69 74 65 0a 2a 2a 20 69 73 20 6f 6e 6c 79  QLite.** is only
2c40: 20 61 62 6c 65 20 74 6f 20 70 72 6f 63 65 73 73   able to process
2c50: 20 6a 6f 69 6e 73 20 77 69 74 68 20 36 34 20 6f   joins with 64 o
2c60: 72 20 66 65 77 65 72 20 74 61 62 6c 65 73 2e 0a  r fewer tables..
2c70: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 54  */.struct WhereT
2c80: 65 72 6d 20 7b 0a 20 20 45 78 70 72 20 2a 70 45  erm {.  Expr *pE
2c90: 78 70 72 3b 20 20 20 20 20 20 20 20 20 20 20 20  xpr;            
2ca0: 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 74 68  /* Pointer to th
2cb0: 65 20 73 75 62 65 78 70 72 65 73 73 69 6f 6e 20  e subexpression 
2cc0: 74 68 61 74 20 69 73 20 74 68 69 73 20 74 65 72  that is this ter
2cd0: 6d 20 2a 2f 0a 20 20 57 68 65 72 65 43 6c 61 75  m */.  WhereClau
2ce0: 73 65 20 2a 70 57 43 3b 20 20 20 20 20 20 20 2f  se *pWC;       /
2cf0: 2a 20 54 68 65 20 63 6c 61 75 73 65 20 74 68 69  * The clause thi
2d00: 73 20 74 65 72 6d 20 69 73 20 70 61 72 74 20 6f  s term is part o
2d10: 66 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 74 72  f */.  LogEst tr
2d20: 75 74 68 50 72 6f 62 3b 20 20 20 20 20 20 20 2f  uthProb;       /
2d30: 2a 20 50 72 6f 62 61 62 69 6c 69 74 79 20 6f 66  * Probability of
2d40: 20 74 72 75 74 68 20 66 6f 72 20 74 68 69 73 20   truth for this 
2d50: 65 78 70 72 65 73 73 69 6f 6e 20 2a 2f 0a 20 20  expression */.  
2d60: 75 31 36 20 77 74 46 6c 61 67 73 3b 20 20 20 20  u16 wtFlags;    
2d70: 20 20 20 20 20 20 20 20 2f 2a 20 54 45 52 4d 5f          /* TERM_
2d80: 78 78 78 20 62 69 74 20 66 6c 61 67 73 2e 20 20  xxx bit flags.  
2d90: 53 65 65 20 62 65 6c 6f 77 20 2a 2f 0a 20 20 75  See below */.  u
2da0: 31 36 20 65 4f 70 65 72 61 74 6f 72 3b 20 20 20  16 eOperator;   
2db0: 20 20 20 20 20 20 20 2f 2a 20 41 20 57 4f 5f 78         /* A WO_x
2dc0: 78 20 76 61 6c 75 65 20 64 65 73 63 72 69 62 69  x value describi
2dd0: 6e 67 20 3c 6f 70 3e 20 2a 2f 0a 20 20 75 38 20  ng <op> */.  u8 
2de0: 6e 43 68 69 6c 64 3b 20 20 20 20 20 20 20 20 20  nChild;         
2df0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
2e00: 66 20 63 68 69 6c 64 72 65 6e 20 74 68 61 74 20  f children that 
2e10: 6d 75 73 74 20 64 69 73 61 62 6c 65 20 75 73 20  must disable us 
2e20: 2a 2f 0a 20 20 75 38 20 65 4d 61 74 63 68 4f 70  */.  u8 eMatchOp
2e30: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
2e40: 4f 70 20 66 6f 72 20 76 74 61 62 20 4d 41 54 43  Op for vtab MATC
2e50: 48 2f 4c 49 4b 45 2f 47 4c 4f 42 2f 52 45 47 45  H/LIKE/GLOB/REGE
2e60: 58 50 20 74 65 72 6d 73 20 2a 2f 0a 20 20 69 6e  XP terms */.  in
2e70: 74 20 69 50 61 72 65 6e 74 3b 20 20 20 20 20 20  t iParent;      
2e80: 20 20 20 20 20 20 2f 2a 20 44 69 73 61 62 6c 65        /* Disable
2e90: 20 70 57 43 2d 3e 61 5b 69 50 61 72 65 6e 74 5d   pWC->a[iParent]
2ea0: 20 77 68 65 6e 20 74 68 69 73 20 74 65 72 6d 20   when this term 
2eb0: 64 69 73 61 62 6c 65 64 20 2a 2f 0a 20 20 69 6e  disabled */.  in
2ec0: 74 20 6c 65 66 74 43 75 72 73 6f 72 3b 20 20 20  t leftCursor;   
2ed0: 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 20        /* Cursor 
2ee0: 6e 75 6d 62 65 72 20 6f 66 20 58 20 69 6e 20 22  number of X in "
2ef0: 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 22 20 2a  X <op> <expr>" *
2f00: 2f 0a 20 20 69 6e 74 20 69 46 69 65 6c 64 3b 20  /.  int iField; 
2f10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46              /* F
2f20: 69 65 6c 64 20 69 6e 20 28 3f 2c 3f 2c 3f 29 20  ield in (?,?,?) 
2f30: 49 4e 20 28 53 45 4c 45 43 54 2e 2e 2e 29 20 76  IN (SELECT...) v
2f40: 65 63 74 6f 72 20 2a 2f 0a 20 20 75 6e 69 6f 6e  ector */.  union
2f50: 20 7b 0a 20 20 20 20 69 6e 74 20 6c 65 66 74 43   {.    int leftC
2f60: 6f 6c 75 6d 6e 3b 20 20 20 20 20 20 20 20 20 2f  olumn;         /
2f70: 2a 20 43 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20  * Column number 
2f80: 6f 66 20 58 20 69 6e 20 22 58 20 3c 6f 70 3e 20  of X in "X <op> 
2f90: 3c 65 78 70 72 3e 22 20 2a 2f 0a 20 20 20 20 57  <expr>" */.    W
2fa0: 68 65 72 65 4f 72 49 6e 66 6f 20 2a 70 4f 72 49  hereOrInfo *pOrI
2fb0: 6e 66 6f 3b 20 20 20 2f 2a 20 45 78 74 72 61 20  nfo;   /* Extra 
2fc0: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 69 66 20 28  information if (
2fd0: 65 4f 70 65 72 61 74 6f 72 20 26 20 57 4f 5f 4f  eOperator & WO_O
2fe0: 52 29 21 3d 30 20 2a 2f 0a 20 20 20 20 57 68 65  R)!=0 */.    Whe
2ff0: 72 65 41 6e 64 49 6e 66 6f 20 2a 70 41 6e 64 49  reAndInfo *pAndI
3000: 6e 66 6f 3b 20 2f 2a 20 45 78 74 72 61 20 69 6e  nfo; /* Extra in
3010: 66 6f 72 6d 61 74 69 6f 6e 20 69 66 20 28 65 4f  formation if (eO
3020: 70 65 72 61 74 6f 72 26 20 57 4f 5f 41 4e 44 29  perator& WO_AND)
3030: 21 3d 30 20 2a 2f 0a 20 20 7d 20 75 3b 0a 20 20  !=0 */.  } u;.  
3040: 42 69 74 6d 61 73 6b 20 70 72 65 72 65 71 52 69  Bitmask prereqRi
3050: 67 68 74 3b 20 20 20 20 2f 2a 20 42 69 74 6d 61  ght;    /* Bitma
3060: 73 6b 20 6f 66 20 74 61 62 6c 65 73 20 75 73 65  sk of tables use
3070: 64 20 62 79 20 70 45 78 70 72 2d 3e 70 52 69 67  d by pExpr->pRig
3080: 68 74 20 2a 2f 0a 20 20 42 69 74 6d 61 73 6b 20  ht */.  Bitmask 
3090: 70 72 65 72 65 71 41 6c 6c 3b 20 20 20 20 20 20  prereqAll;      
30a0: 2f 2a 20 42 69 74 6d 61 73 6b 20 6f 66 20 74 61  /* Bitmask of ta
30b0: 62 6c 65 73 20 72 65 66 65 72 65 6e 63 65 64 20  bles referenced 
30c0: 62 79 20 70 45 78 70 72 20 2a 2f 0a 7d 3b 0a 0a  by pExpr */.};..
30d0: 2f 2a 0a 2a 2a 20 41 6c 6c 6f 77 65 64 20 76 61  /*.** Allowed va
30e0: 6c 75 65 73 20 6f 66 20 57 68 65 72 65 54 65 72  lues of WhereTer
30f0: 6d 2e 77 74 46 6c 61 67 73 0a 2a 2f 0a 23 64 65  m.wtFlags.*/.#de
3100: 66 69 6e 65 20 54 45 52 4d 5f 44 59 4e 41 4d 49  fine TERM_DYNAMI
3110: 43 20 20 20 20 30 78 30 31 20 20 20 2f 2a 20 4e  C    0x01   /* N
3120: 65 65 64 20 74 6f 20 63 61 6c 6c 20 73 71 6c 69  eed to call sqli
3130: 74 65 33 45 78 70 72 44 65 6c 65 74 65 28 64 62  te3ExprDelete(db
3140: 2c 20 70 45 78 70 72 29 20 2a 2f 0a 23 64 65 66  , pExpr) */.#def
3150: 69 6e 65 20 54 45 52 4d 5f 56 49 52 54 55 41 4c  ine TERM_VIRTUAL
3160: 20 20 20 20 30 78 30 32 20 20 20 2f 2a 20 41 64      0x02   /* Ad
3170: 64 65 64 20 62 79 20 74 68 65 20 6f 70 74 69 6d  ded by the optim
3180: 69 7a 65 72 2e 20 20 44 6f 20 6e 6f 74 20 63 6f  izer.  Do not co
3190: 64 65 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  de */.#define TE
31a0: 52 4d 5f 43 4f 44 45 44 20 20 20 20 20 20 30 78  RM_CODED      0x
31b0: 30 34 20 20 20 2f 2a 20 54 68 69 73 20 74 65 72  04   /* This ter
31c0: 6d 20 69 73 20 61 6c 72 65 61 64 79 20 63 6f 64  m is already cod
31d0: 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  ed */.#define TE
31e0: 52 4d 5f 43 4f 50 49 45 44 20 20 20 20 20 30 78  RM_COPIED     0x
31f0: 30 38 20 20 20 2f 2a 20 48 61 73 20 61 20 63 68  08   /* Has a ch
3200: 69 6c 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  ild */.#define T
3210: 45 52 4d 5f 4f 52 49 4e 46 4f 20 20 20 20 20 30  ERM_ORINFO     0
3220: 78 31 30 20 20 20 2f 2a 20 4e 65 65 64 20 74 6f  x10   /* Need to
3230: 20 66 72 65 65 20 74 68 65 20 57 68 65 72 65 54   free the WhereT
3240: 65 72 6d 2e 75 2e 70 4f 72 49 6e 66 6f 20 6f 62  erm.u.pOrInfo ob
3250: 6a 65 63 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20  ject */.#define 
3260: 54 45 52 4d 5f 41 4e 44 49 4e 46 4f 20 20 20 20  TERM_ANDINFO    
3270: 30 78 32 30 20 20 20 2f 2a 20 4e 65 65 64 20 74  0x20   /* Need t
3280: 6f 20 66 72 65 65 20 74 68 65 20 57 68 65 72 65  o free the Where
3290: 54 65 72 6d 2e 75 2e 70 41 6e 64 49 6e 66 6f 20  Term.u.pAndInfo 
32a0: 6f 62 6a 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  obj */.#define T
32b0: 45 52 4d 5f 4f 52 5f 4f 4b 20 20 20 20 20 20 30  ERM_OR_OK      0
32c0: 78 34 30 20 20 20 2f 2a 20 55 73 65 64 20 64 75  x40   /* Used du
32d0: 72 69 6e 67 20 4f 52 2d 63 6c 61 75 73 65 20 70  ring OR-clause p
32e0: 72 6f 63 65 73 73 69 6e 67 20 2a 2f 0a 23 69 66  rocessing */.#if
32f0: 64 65 66 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c  def SQLITE_ENABL
3300: 45 5f 53 54 41 54 33 5f 4f 52 5f 53 54 41 54 34  E_STAT3_OR_STAT4
3310: 0a 23 20 20 64 65 66 69 6e 65 20 54 45 52 4d 5f  .#  define TERM_
3320: 56 4e 55 4c 4c 20 20 20 20 30 78 38 30 20 20 20  VNULL    0x80   
3330: 2f 2a 20 4d 61 6e 75 66 61 63 74 75 72 65 64 20  /* Manufactured 
3340: 78 3e 4e 55 4c 4c 20 6f 72 20 78 3c 3d 4e 55 4c  x>NULL or x<=NUL
3350: 4c 20 74 65 72 6d 20 2a 2f 0a 23 65 6c 73 65 0a  L term */.#else.
3360: 23 20 20 64 65 66 69 6e 65 20 54 45 52 4d 5f 56  #  define TERM_V
3370: 4e 55 4c 4c 20 20 20 20 30 78 30 30 20 20 20 2f  NULL    0x00   /
3380: 2a 20 44 69 73 61 62 6c 65 64 20 69 66 20 6e 6f  * Disabled if no
3390: 74 20 75 73 69 6e 67 20 73 74 61 74 33 20 2a 2f  t using stat3 */
33a0: 0a 23 65 6e 64 69 66 0a 23 64 65 66 69 6e 65 20  .#endif.#define 
33b0: 54 45 52 4d 5f 4c 49 4b 45 4f 50 54 20 20 20 20  TERM_LIKEOPT    
33c0: 30 78 31 30 30 20 20 2f 2a 20 56 69 72 74 75 61  0x100  /* Virtua
33d0: 6c 20 74 65 72 6d 73 20 66 72 6f 6d 20 74 68 65  l terms from the
33e0: 20 4c 49 4b 45 20 6f 70 74 69 6d 69 7a 61 74 69   LIKE optimizati
33f0: 6f 6e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  on */.#define TE
3400: 52 4d 5f 4c 49 4b 45 43 4f 4e 44 20 20 20 30 78  RM_LIKECOND   0x
3410: 32 30 30 20 20 2f 2a 20 43 6f 6e 64 69 74 69 6f  200  /* Conditio
3420: 6e 61 6c 6c 79 20 74 68 69 73 20 4c 49 4b 45 20  nally this LIKE 
3430: 6f 70 65 72 61 74 6f 72 20 74 65 72 6d 20 2a 2f  operator term */
3440: 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f 4c 49  .#define TERM_LI
3450: 4b 45 20 20 20 20 20 20 20 30 78 34 30 30 20 20  KE       0x400  
3460: 2f 2a 20 54 68 65 20 6f 72 69 67 69 6e 61 6c 20  /* The original 
3470: 4c 49 4b 45 20 6f 70 65 72 61 74 6f 72 20 2a 2f  LIKE operator */
3480: 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f 49 53  .#define TERM_IS
3490: 20 20 20 20 20 20 20 20 20 30 78 38 30 30 20 20           0x800  
34a0: 2f 2a 20 54 65 72 6d 2e 70 45 78 70 72 20 69 73  /* Term.pExpr is
34b0: 20 61 6e 20 49 53 20 6f 70 65 72 61 74 6f 72 20   an IS operator 
34c0: 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f  */.#define TERM_
34d0: 56 41 52 53 45 4c 45 43 54 20 20 30 78 31 30 30  VARSELECT  0x100
34e0: 30 20 2f 2a 20 54 65 72 6d 2e 70 45 78 70 72 20  0 /* Term.pExpr 
34f0: 63 6f 6e 74 61 69 6e 73 20 61 20 63 6f 72 72 65  contains a corre
3500: 6c 61 74 65 64 20 73 75 62 2d 71 75 65 72 79 20  lated sub-query 
3510: 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73  */../*.** An ins
3520: 74 61 6e 63 65 20 6f 66 20 74 68 65 20 57 68 65  tance of the Whe
3530: 72 65 53 63 61 6e 20 6f 62 6a 65 63 74 20 69 73  reScan object is
3540: 20 75 73 65 64 20 61 73 20 61 6e 20 69 74 65 72   used as an iter
3550: 61 74 6f 72 20 66 6f 72 20 6c 6f 63 61 74 69 6e  ator for locatin
3560: 67 0a 2a 2a 20 74 65 72 6d 73 20 69 6e 20 74 68  g.** terms in th
3570: 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20 74  e WHERE clause t
3580: 68 61 74 20 61 72 65 20 75 73 65 66 75 6c 20 74  hat are useful t
3590: 6f 20 74 68 65 20 71 75 65 72 79 20 70 6c 61 6e  o the query plan
35a0: 6e 65 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57  ner..*/.struct W
35b0: 68 65 72 65 53 63 61 6e 20 7b 0a 20 20 57 68 65  hereScan {.  Whe
35c0: 72 65 43 6c 61 75 73 65 20 2a 70 4f 72 69 67 57  reClause *pOrigW
35d0: 43 3b 20 20 20 20 20 20 2f 2a 20 4f 72 69 67 69  C;      /* Origi
35e0: 6e 61 6c 2c 20 69 6e 6e 65 72 6d 6f 73 74 20 57  nal, innermost W
35f0: 68 65 72 65 43 6c 61 75 73 65 20 2a 2f 0a 20 20  hereClause */.  
3600: 57 68 65 72 65 43 6c 61 75 73 65 20 2a 70 57 43  WhereClause *pWC
3610: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57 68  ;          /* Wh
3620: 65 72 65 43 6c 61 75 73 65 20 63 75 72 72 65 6e  ereClause curren
3630: 74 6c 79 20 62 65 69 6e 67 20 73 63 61 6e 6e 65  tly being scanne
3640: 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  d */.  const cha
3650: 72 20 2a 7a 43 6f 6c 6c 4e 61 6d 65 3b 20 20 20  r *zCollName;   
3660: 20 20 2f 2a 20 52 65 71 75 69 72 65 64 20 63 6f    /* Required co
3670: 6c 6c 61 74 69 6e 67 20 73 65 71 75 65 6e 63 65  llating sequence
3680: 2c 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f  , if not NULL */
3690: 0a 20 20 45 78 70 72 20 2a 70 49 64 78 45 78 70  .  Expr *pIdxExp
36a0: 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  r;            /*
36b0: 20 53 65 61 72 63 68 20 66 6f 72 20 74 68 69 73   Search for this
36c0: 20 69 6e 64 65 78 20 65 78 70 72 65 73 73 69 6f   index expressio
36d0: 6e 20 2a 2f 0a 20 20 63 68 61 72 20 69 64 78 61  n */.  char idxa
36e0: 66 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ff;             
36f0: 20 20 2f 2a 20 4d 75 73 74 20 6d 61 74 63 68 20    /* Must match 
3700: 74 68 69 73 20 61 66 66 69 6e 69 74 79 2c 20 69  this affinity, i
3710: 66 20 7a 43 6f 6c 6c 4e 61 6d 65 21 3d 4e 55 4c  f zCollName!=NUL
3720: 4c 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20  L */.  unsigned 
3730: 63 68 61 72 20 6e 45 71 75 69 76 3b 20 20 20 20  char nEquiv;    
3740: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65    /* Number of e
3750: 6e 74 72 69 65 73 20 69 6e 20 61 45 71 75 69 76  ntries in aEquiv
3760: 5b 5d 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64  [] */.  unsigned
3770: 20 63 68 61 72 20 69 45 71 75 69 76 3b 20 20 20   char iEquiv;   
3780: 20 20 20 2f 2a 20 4e 65 78 74 20 75 6e 75 73 65     /* Next unuse
3790: 64 20 73 6c 6f 74 20 69 6e 20 61 45 71 75 69 76  d slot in aEquiv
37a0: 5b 5d 20 2a 2f 0a 20 20 75 33 32 20 6f 70 4d 61  [] */.  u32 opMa
37b0: 73 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  sk;             
37c0: 20 20 20 2f 2a 20 41 63 63 65 70 74 61 62 6c 65     /* Acceptable
37d0: 20 6f 70 65 72 61 74 6f 72 73 20 2a 2f 0a 20 20   operators */.  
37e0: 69 6e 74 20 6b 3b 20 20 20 20 20 20 20 20 20 20  int k;          
37f0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 65             /* Re
3800: 73 75 6d 65 20 73 63 61 6e 6e 69 6e 67 20 61 74  sume scanning at
3810: 20 74 68 69 73 2d 3e 70 57 43 2d 3e 61 5b 74 68   this->pWC->a[th
3820: 69 73 2d 3e 6b 5d 20 2a 2f 0a 20 20 69 6e 74 20  is->k] */.  int 
3830: 61 69 43 75 72 5b 31 31 5d 3b 20 20 20 20 20 20  aiCur[11];      
3840: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72         /* Cursor
3850: 73 20 69 6e 20 74 68 65 20 65 71 75 69 76 61 6c  s in the equival
3860: 65 6e 63 65 20 63 6c 61 73 73 20 2a 2f 0a 20 20  ence class */.  
3870: 69 31 36 20 61 69 43 6f 6c 75 6d 6e 5b 31 31 5d  i16 aiColumn[11]
3880: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f  ;          /* Co
3890: 72 72 65 73 70 6f 6e 64 69 6e 67 20 63 6f 6c 75  rresponding colu
38a0: 6d 6e 20 6e 75 6d 62 65 72 20 69 6e 20 74 68 65  mn number in the
38b0: 20 65 71 2d 63 6c 61 73 73 20 2a 2f 0a 7d 3b 0a   eq-class */.};.
38c0: 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e  ./*.** An instan
38d0: 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77  ce of the follow
38e0: 69 6e 67 20 73 74 72 75 63 74 75 72 65 20 68 6f  ing structure ho
38f0: 6c 64 73 20 61 6c 6c 20 69 6e 66 6f 72 6d 61 74  lds all informat
3900: 69 6f 6e 20 61 62 6f 75 74 20 61 0a 2a 2a 20 57  ion about a.** W
3910: 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20 4d 6f  HERE clause.  Mo
3920: 73 74 6c 79 20 74 68 69 73 20 69 73 20 61 20 63  stly this is a c
3930: 6f 6e 74 61 69 6e 65 72 20 66 6f 72 20 6f 6e 65  ontainer for one
3940: 20 6f 72 20 6d 6f 72 65 20 57 68 65 72 65 54 65   or more WhereTe
3950: 72 6d 73 2e 0a 2a 2a 0a 2a 2a 20 45 78 70 6c 61  rms..**.** Expla
3960: 6e 61 74 69 6f 6e 20 6f 66 20 70 4f 75 74 65 72  nation of pOuter
3970: 3a 20 20 46 6f 72 20 61 20 57 48 45 52 45 20 63  :  For a WHERE c
3980: 6c 61 75 73 65 20 6f 66 20 74 68 65 20 66 6f 72  lause of the for
3990: 6d 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20  m.**.**         
39a0: 20 20 61 20 41 4e 44 20 28 28 62 20 41 4e 44 20    a AND ((b AND 
39b0: 63 29 20 4f 52 20 28 64 20 41 4e 44 20 65 29 29  c) OR (d AND e))
39c0: 20 41 4e 44 20 66 0a 2a 2a 0a 2a 2a 20 54 68 65   AND f.**.** The
39d0: 72 65 20 61 72 65 20 73 65 70 61 72 61 74 65 20  re are separate 
39e0: 57 68 65 72 65 43 6c 61 75 73 65 20 6f 62 6a 65  WhereClause obje
39f0: 63 74 73 20 66 6f 72 20 74 68 65 20 77 68 6f 6c  cts for the whol
3a00: 65 20 63 6c 61 75 73 65 20 61 6e 64 20 66 6f 72  e clause and for
3a10: 0a 2a 2a 20 74 68 65 20 73 75 62 63 6c 61 75 73  .** the subclaus
3a20: 65 73 20 22 28 62 20 41 4e 44 20 63 29 22 20 61  es "(b AND c)" a
3a30: 6e 64 20 22 28 64 20 41 4e 44 20 65 29 22 2e 20  nd "(d AND e)". 
3a40: 20 54 68 65 20 70 4f 75 74 65 72 20 66 69 65 6c   The pOuter fiel
3a50: 64 20 6f 66 20 74 68 65 0a 2a 2a 20 73 75 62 63  d of the.** subc
3a60: 6c 61 75 73 65 73 20 70 6f 69 6e 74 73 20 74 6f  lauses points to
3a70: 20 74 68 65 20 57 68 65 72 65 43 6c 61 75 73 65   the WhereClause
3a80: 20 6f 62 6a 65 63 74 20 66 6f 72 20 74 68 65 20   object for the 
3a90: 77 68 6f 6c 65 20 63 6c 61 75 73 65 2e 0a 2a 2f  whole clause..*/
3aa0: 0a 73 74 72 75 63 74 20 57 68 65 72 65 43 6c 61  .struct WhereCla
3ab0: 75 73 65 20 7b 0a 20 20 57 68 65 72 65 49 6e 66  use {.  WhereInf
3ac0: 6f 20 2a 70 57 49 6e 66 6f 3b 20 20 20 20 20 20  o *pWInfo;      
3ad0: 20 2f 2a 20 57 48 45 52 45 20 63 6c 61 75 73 65   /* WHERE clause
3ae0: 20 70 72 6f 63 65 73 73 69 6e 67 20 63 6f 6e 74   processing cont
3af0: 65 78 74 20 2a 2f 0a 20 20 57 68 65 72 65 43 6c  ext */.  WhereCl
3b00: 61 75 73 65 20 2a 70 4f 75 74 65 72 3b 20 20 20  ause *pOuter;   
3b10: 20 20 2f 2a 20 4f 75 74 65 72 20 63 6f 6e 6a 75    /* Outer conju
3b20: 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20 6f  nction */.  u8 o
3b30: 70 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  p;              
3b40: 20 20 20 20 20 2f 2a 20 53 70 6c 69 74 20 6f 70       /* Split op
3b50: 65 72 61 74 6f 72 2e 20 20 54 4b 5f 41 4e 44 20  erator.  TK_AND 
3b60: 6f 72 20 54 4b 5f 4f 52 20 2a 2f 0a 20 20 69 6e  or TK_OR */.  in
3b70: 74 20 6e 54 65 72 6d 3b 20 20 20 20 20 20 20 20  t nTerm;        
3b80: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
3b90: 20 6f 66 20 74 65 72 6d 73 20 2a 2f 0a 20 20 69   of terms */.  i
3ba0: 6e 74 20 6e 53 6c 6f 74 3b 20 20 20 20 20 20 20  nt nSlot;       
3bb0: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
3bc0: 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20  r of entries in 
3bd0: 61 5b 5d 20 2a 2f 0a 20 20 57 68 65 72 65 54 65  a[] */.  WhereTe
3be0: 72 6d 20 2a 61 3b 20 20 20 20 20 20 20 20 20 20  rm *a;          
3bf0: 20 20 2f 2a 20 45 61 63 68 20 61 5b 5d 20 64 65    /* Each a[] de
3c00: 73 63 72 69 62 65 73 20 61 20 74 65 72 6d 20 6f  scribes a term o
3c10: 66 20 74 68 65 20 57 48 45 52 45 20 63 6c 75 61  f the WHERE clua
3c20: 73 65 20 2a 2f 0a 23 69 66 20 64 65 66 69 6e 65  se */.#if define
3c30: 64 28 53 51 4c 49 54 45 5f 53 4d 41 4c 4c 5f 53  d(SQLITE_SMALL_S
3c40: 54 41 43 4b 29 0a 20 20 57 68 65 72 65 54 65 72  TACK).  WhereTer
3c50: 6d 20 61 53 74 61 74 69 63 5b 31 5d 3b 20 20 20  m aStatic[1];   
3c60: 20 2f 2a 20 49 6e 69 74 69 61 6c 20 73 74 61 74   /* Initial stat
3c70: 69 63 20 73 70 61 63 65 20 66 6f 72 20 61 5b 5d  ic space for a[]
3c80: 20 2a 2f 0a 23 65 6c 73 65 0a 20 20 57 68 65 72   */.#else.  Wher
3c90: 65 54 65 72 6d 20 61 53 74 61 74 69 63 5b 38 5d  eTerm aStatic[8]
3ca0: 3b 20 20 20 20 2f 2a 20 49 6e 69 74 69 61 6c 20  ;    /* Initial 
3cb0: 73 74 61 74 69 63 20 73 70 61 63 65 20 66 6f 72  static space for
3cc0: 20 61 5b 5d 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d   a[] */.#endif.}
3cd0: 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 57 68 65 72 65  ;../*.** A Where
3ce0: 54 65 72 6d 20 77 69 74 68 20 65 4f 70 65 72 61  Term with eOpera
3cf0: 74 6f 72 3d 3d 57 4f 5f 4f 52 20 68 61 73 20 69  tor==WO_OR has i
3d00: 74 73 20 75 2e 70 4f 72 49 6e 66 6f 20 70 6f 69  ts u.pOrInfo poi
3d10: 6e 74 65 72 20 73 65 74 20 74 6f 0a 2a 2a 20 61  nter set to.** a
3d20: 20 64 79 6e 61 6d 69 63 61 6c 6c 79 20 61 6c 6c   dynamically all
3d30: 6f 63 61 74 65 64 20 69 6e 73 74 61 6e 63 65 20  ocated instance 
3d40: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
3d50: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2f 0a 73   structure..*/.s
3d60: 74 72 75 63 74 20 57 68 65 72 65 4f 72 49 6e 66  truct WhereOrInf
3d70: 6f 20 7b 0a 20 20 57 68 65 72 65 43 6c 61 75 73  o {.  WhereClaus
3d80: 65 20 77 63 3b 20 20 20 20 20 20 20 20 20 20 2f  e wc;          /
3d90: 2a 20 44 65 63 6f 6d 70 6f 73 69 74 69 6f 6e 20  * Decomposition 
3da0: 69 6e 74 6f 20 73 75 62 74 65 72 6d 73 20 2a 2f  into subterms */
3db0: 0a 20 20 42 69 74 6d 61 73 6b 20 69 6e 64 65 78  .  Bitmask index
3dc0: 61 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20 42  able;       /* B
3dd0: 69 74 6d 61 73 6b 20 6f 66 20 61 6c 6c 20 69 6e  itmask of all in
3de0: 64 65 78 61 62 6c 65 20 74 61 62 6c 65 73 20 69  dexable tables i
3df0: 6e 20 74 68 65 20 63 6c 61 75 73 65 20 2a 2f 0a  n the clause */.
3e00: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 57 68 65 72  };../*.** A Wher
3e10: 65 54 65 72 6d 20 77 69 74 68 20 65 4f 70 65 72  eTerm with eOper
3e20: 61 74 6f 72 3d 3d 57 4f 5f 41 4e 44 20 68 61 73  ator==WO_AND has
3e30: 20 69 74 73 20 75 2e 70 41 6e 64 49 6e 66 6f 20   its u.pAndInfo 
3e40: 70 6f 69 6e 74 65 72 20 73 65 74 20 74 6f 0a 2a  pointer set to.*
3e50: 2a 20 61 20 64 79 6e 61 6d 69 63 61 6c 6c 79 20  * a dynamically 
3e60: 61 6c 6c 6f 63 61 74 65 64 20 69 6e 73 74 61 6e  allocated instan
3e70: 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77  ce of the follow
3e80: 69 6e 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a  ing structure..*
3e90: 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 41 6e  /.struct WhereAn
3ea0: 64 49 6e 66 6f 20 7b 0a 20 20 57 68 65 72 65 43  dInfo {.  WhereC
3eb0: 6c 61 75 73 65 20 77 63 3b 20 20 20 20 20 20 20  lause wc;       
3ec0: 20 20 20 2f 2a 20 54 68 65 20 73 75 62 65 78 70     /* The subexp
3ed0: 72 65 73 73 69 6f 6e 20 62 72 6f 6b 65 6e 20 6f  ression broken o
3ee0: 75 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20  ut */.};../*.** 
3ef0: 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74  An instance of t
3f00: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72  he following str
3f10: 75 63 74 75 72 65 20 6b 65 65 70 73 20 74 72 61  ucture keeps tra
3f20: 63 6b 20 6f 66 20 61 20 6d 61 70 70 69 6e 67 0a  ck of a mapping.
3f30: 2a 2a 20 62 65 74 77 65 65 6e 20 56 44 42 45 20  ** between VDBE 
3f40: 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 61  cursor numbers a
3f50: 6e 64 20 62 69 74 73 20 6f 66 20 74 68 65 20 62  nd bits of the b
3f60: 69 74 6d 61 73 6b 73 20 69 6e 20 57 68 65 72 65  itmasks in Where
3f70: 54 65 72 6d 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  Term..**.** The 
3f80: 56 44 42 45 20 63 75 72 73 6f 72 20 6e 75 6d 62  VDBE cursor numb
3f90: 65 72 73 20 61 72 65 20 73 6d 61 6c 6c 20 69 6e  ers are small in
3fa0: 74 65 67 65 72 73 20 63 6f 6e 74 61 69 6e 65 64  tegers contained
3fb0: 20 69 6e 20 0a 2a 2a 20 53 72 63 4c 69 73 74 5f   in .** SrcList_
3fc0: 69 74 65 6d 2e 69 43 75 72 73 6f 72 20 61 6e 64  item.iCursor and
3fd0: 20 45 78 70 72 2e 69 54 61 62 6c 65 20 66 69 65   Expr.iTable fie
3fe0: 6c 64 73 2e 20 20 46 6f 72 20 61 6e 79 20 67 69  lds.  For any gi
3ff0: 76 65 6e 20 57 48 45 52 45 20 0a 2a 2a 20 63 6c  ven WHERE .** cl
4000: 61 75 73 65 2c 20 74 68 65 20 63 75 72 73 6f 72  ause, the cursor
4010: 20 6e 75 6d 62 65 72 73 20 6d 69 67 68 74 20 6e   numbers might n
4020: 6f 74 20 62 65 67 69 6e 20 77 69 74 68 20 30 20  ot begin with 0 
4030: 61 6e 64 20 74 68 65 79 20 6d 69 67 68 74 0a 2a  and they might.*
4040: 2a 20 63 6f 6e 74 61 69 6e 20 67 61 70 73 20 69  * contain gaps i
4050: 6e 20 74 68 65 20 6e 75 6d 62 65 72 69 6e 67 20  n the numbering 
4060: 73 65 71 75 65 6e 63 65 2e 20 20 42 75 74 20 77  sequence.  But w
4070: 65 20 77 61 6e 74 20 74 6f 20 6d 61 6b 65 20 6d  e want to make m
4080: 61 78 69 6d 75 6d 0a 2a 2a 20 75 73 65 20 6f 66  aximum.** use of
4090: 20 74 68 65 20 62 69 74 73 20 69 6e 20 6f 75 72   the bits in our
40a0: 20 62 69 74 6d 61 73 6b 73 2e 20 20 54 68 69 73   bitmasks.  This
40b0: 20 73 74 72 75 63 74 75 72 65 20 70 72 6f 76 69   structure provi
40c0: 64 65 73 20 61 20 6d 61 70 70 69 6e 67 0a 2a 2a  des a mapping.**
40d0: 20 66 72 6f 6d 20 74 68 65 20 73 70 61 72 73 65   from the sparse
40e0: 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20   cursor numbers 
40f0: 69 6e 74 6f 20 63 6f 6e 73 65 63 75 74 69 76 65  into consecutive
4100: 20 69 6e 74 65 67 65 72 73 20 62 65 67 69 6e 6e   integers beginn
4110: 69 6e 67 0a 2a 2a 20 77 69 74 68 20 30 2e 0a 2a  ing.** with 0..*
4120: 2a 0a 2a 2a 20 49 66 20 57 68 65 72 65 4d 61 73  *.** If WhereMas
4130: 6b 53 65 74 2e 69 78 5b 41 5d 3d 3d 42 20 69 74  kSet.ix[A]==B it
4140: 20 6d 65 61 6e 73 20 74 68 61 74 20 54 68 65 20   means that The 
4150: 41 2d 74 68 20 62 69 74 20 6f 66 20 61 20 42 69  A-th bit of a Bi
4160: 74 6d 61 73 6b 0a 2a 2a 20 63 6f 72 72 65 73 70  tmask.** corresp
4170: 6f 6e 64 73 20 56 44 42 45 20 63 75 72 73 6f 72  onds VDBE cursor
4180: 20 6e 75 6d 62 65 72 20 42 2e 20 20 54 68 65 20   number B.  The 
4190: 41 2d 74 68 20 62 69 74 20 6f 66 20 61 20 62 69  A-th bit of a bi
41a0: 74 6d 61 73 6b 20 69 73 20 31 3c 3c 41 2e 0a 2a  tmask is 1<<A..*
41b0: 2a 0a 2a 2a 20 46 6f 72 20 65 78 61 6d 70 6c 65  *.** For example
41c0: 2c 20 69 66 20 74 68 65 20 57 48 45 52 45 20 63  , if the WHERE c
41d0: 6c 61 75 73 65 20 65 78 70 72 65 73 73 69 6f 6e  lause expression
41e0: 20 75 73 65 64 20 74 68 65 73 65 20 56 44 42 45   used these VDBE
41f0: 0a 2a 2a 20 63 75 72 73 6f 72 73 3a 20 20 34 2c  .** cursors:  4,
4200: 20 35 2c 20 38 2c 20 32 39 2c 20 35 37 2c 20 37   5, 8, 29, 57, 7
4210: 33 2e 20 20 54 68 65 6e 20 74 68 65 20 20 57 68  3.  Then the  Wh
4220: 65 72 65 4d 61 73 6b 53 65 74 20 73 74 72 75 63  ereMaskSet struc
4230: 74 75 72 65 0a 2a 2a 20 77 6f 75 6c 64 20 6d 61  ture.** would ma
4240: 70 20 74 68 6f 73 65 20 63 75 72 73 6f 72 20 6e  p those cursor n
4250: 75 6d 62 65 72 73 20 69 6e 74 6f 20 62 69 74 73  umbers into bits
4260: 20 30 20 74 68 72 6f 75 67 68 20 35 2e 0a 2a 2a   0 through 5..**
4270: 0a 2a 2a 20 4e 6f 74 65 20 74 68 61 74 20 74 68  .** Note that th
4280: 65 20 6d 61 70 70 69 6e 67 20 69 73 20 6e 6f 74  e mapping is not
4290: 20 6e 65 63 65 73 73 61 72 69 6c 79 20 6f 72 64   necessarily ord
42a0: 65 72 65 64 2e 20 20 49 6e 20 74 68 65 20 65 78  ered.  In the ex
42b0: 61 6d 70 6c 65 0a 2a 2a 20 61 62 6f 76 65 2c 20  ample.** above, 
42c0: 74 68 65 20 6d 61 70 70 69 6e 67 20 6d 69 67 68  the mapping migh
42d0: 74 20 67 6f 20 6c 69 6b 65 20 74 68 69 73 3a 20  t go like this: 
42e0: 20 34 2d 3e 33 2c 20 35 2d 3e 31 2c 20 38 2d 3e   4->3, 5->1, 8->
42f0: 32 2c 20 32 39 2d 3e 30 2c 0a 2a 2a 20 35 37 2d  2, 29->0,.** 57-
4300: 3e 35 2c 20 37 33 2d 3e 34 2e 20 20 4f 72 20 6f  >5, 73->4.  Or o
4310: 6e 65 20 6f 66 20 37 31 39 20 6f 74 68 65 72 20  ne of 719 other 
4320: 63 6f 6d 62 69 6e 61 74 69 6f 6e 73 20 6d 69 67  combinations mig
4330: 68 74 20 62 65 20 75 73 65 64 2e 20 49 74 0a 2a  ht be used. It.*
4340: 2a 20 64 6f 65 73 20 6e 6f 74 20 72 65 61 6c 6c  * does not reall
4350: 79 20 6d 61 74 74 65 72 2e 20 20 57 68 61 74 20  y matter.  What 
4360: 69 73 20 69 6d 70 6f 72 74 61 6e 74 20 69 73 20  is important is 
4370: 74 68 61 74 20 73 70 61 72 73 65 20 63 75 72 73  that sparse curs
4380: 6f 72 0a 2a 2a 20 6e 75 6d 62 65 72 73 20 61 6c  or.** numbers al
4390: 6c 20 67 65 74 20 6d 61 70 70 65 64 20 69 6e 74  l get mapped int
43a0: 6f 20 62 69 74 20 6e 75 6d 62 65 72 73 20 74 68  o bit numbers th
43b0: 61 74 20 62 65 67 69 6e 20 77 69 74 68 20 30 20  at begin with 0 
43c0: 61 6e 64 20 63 6f 6e 74 61 69 6e 0a 2a 2a 20 6e  and contain.** n
43d0: 6f 20 67 61 70 73 2e 0a 2a 2f 0a 73 74 72 75 63  o gaps..*/.struc
43e0: 74 20 57 68 65 72 65 4d 61 73 6b 53 65 74 20 7b  t WhereMaskSet {
43f0: 0a 20 20 69 6e 74 20 62 56 61 72 53 65 6c 65 63  .  int bVarSelec
4400: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
4410: 20 2f 2a 20 55 73 65 64 20 62 79 20 73 71 6c 69   /* Used by sqli
4420: 74 65 33 57 68 65 72 65 45 78 70 72 55 73 61 67  te3WhereExprUsag
4430: 65 28 29 20 2a 2f 0a 20 20 69 6e 74 20 6e 3b 20  e() */.  int n; 
4440: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4450: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
4460: 20 6f 66 20 61 73 73 69 67 6e 65 64 20 63 75 72   of assigned cur
4470: 73 6f 72 20 76 61 6c 75 65 73 20 2a 2f 0a 20 20  sor values */.  
4480: 69 6e 74 20 69 78 5b 42 4d 53 5d 3b 20 20 20 20  int ix[BMS];    
4490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
44a0: 20 43 75 72 73 6f 72 20 61 73 73 69 67 6e 65 64   Cursor assigned
44b0: 20 74 6f 20 65 61 63 68 20 62 69 74 20 2a 2f 0a   to each bit */.
44c0: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61  };../*.** Initia
44d0: 6c 69 7a 65 20 61 20 57 68 65 72 65 4d 61 73 6b  lize a WhereMask
44e0: 53 65 74 20 6f 62 6a 65 63 74 0a 2a 2f 0a 23 64  Set object.*/.#d
44f0: 65 66 69 6e 65 20 69 6e 69 74 4d 61 73 6b 53 65  efine initMaskSe
4500: 74 28 50 29 20 20 28 50 29 2d 3e 6e 3d 30 0a 0a  t(P)  (P)->n=0..
4510: 2f 2a 0a 2a 2a 20 54 68 69 73 20 6f 62 6a 65 63  /*.** This objec
4520: 74 20 69 73 20 61 20 63 6f 6e 76 65 6e 69 65 6e  t is a convenien
4530: 63 65 20 77 72 61 70 70 65 72 20 68 6f 6c 64 69  ce wrapper holdi
4540: 6e 67 20 61 6c 6c 20 69 6e 66 6f 72 6d 61 74 69  ng all informati
4550: 6f 6e 20 6e 65 65 64 65 64 0a 2a 2a 20 74 6f 20  on needed.** to 
4560: 63 6f 6e 73 74 72 75 63 74 20 57 68 65 72 65 4c  construct WhereL
4570: 6f 6f 70 20 6f 62 6a 65 63 74 73 20 66 6f 72 20  oop objects for 
4580: 61 20 70 61 72 74 69 63 75 6c 61 72 20 71 75 65  a particular que
4590: 72 79 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68  ry..*/.struct Wh
45a0: 65 72 65 4c 6f 6f 70 42 75 69 6c 64 65 72 20 7b  ereLoopBuilder {
45b0: 0a 20 20 57 68 65 72 65 49 6e 66 6f 20 2a 70 57  .  WhereInfo *pW
45c0: 49 6e 66 6f 3b 20 20 20 20 20 20 20 20 2f 2a 20  Info;        /* 
45d0: 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75  Information abou
45e0: 74 20 74 68 69 73 20 57 48 45 52 45 20 2a 2f 0a  t this WHERE */.
45f0: 20 20 57 68 65 72 65 43 6c 61 75 73 65 20 2a 70    WhereClause *p
4600: 57 43 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 57  WC;         /* W
4610: 48 45 52 45 20 63 6c 61 75 73 65 20 74 65 72 6d  HERE clause term
4620: 73 20 2a 2f 0a 20 20 45 78 70 72 4c 69 73 74 20  s */.  ExprList 
4630: 2a 70 4f 72 64 65 72 42 79 3b 20 20 20 20 20 20  *pOrderBy;      
4640: 20 2f 2a 20 4f 52 44 45 52 20 42 59 20 63 6c 61   /* ORDER BY cla
4650: 75 73 65 20 2a 2f 0a 20 20 57 68 65 72 65 4c 6f  use */.  WhereLo
4660: 6f 70 20 2a 70 4e 65 77 3b 20 20 20 20 20 20 20  op *pNew;       
4670: 20 20 20 2f 2a 20 54 65 6d 70 6c 61 74 65 20 57     /* Template W
4680: 68 65 72 65 4c 6f 6f 70 20 2a 2f 0a 20 20 57 68  hereLoop */.  Wh
4690: 65 72 65 4f 72 53 65 74 20 2a 70 4f 72 53 65 74  ereOrSet *pOrSet
46a0: 3b 20 20 20 20 20 20 20 2f 2a 20 52 65 63 6f 72  ;       /* Recor
46b0: 64 20 62 65 73 74 20 6c 6f 6f 70 73 20 68 65 72  d best loops her
46c0: 65 2c 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a  e, if not NULL *
46d0: 2f 0a 23 69 66 64 65 66 20 53 51 4c 49 54 45 5f  /.#ifdef SQLITE_
46e0: 45 4e 41 42 4c 45 5f 53 54 41 54 33 5f 4f 52 5f  ENABLE_STAT3_OR_
46f0: 53 54 41 54 34 0a 20 20 55 6e 70 61 63 6b 65 64  STAT4.  Unpacked
4700: 52 65 63 6f 72 64 20 2a 70 52 65 63 3b 20 20 20  Record *pRec;   
4710: 20 20 2f 2a 20 50 72 6f 62 65 20 66 6f 72 20 73    /* Probe for s
4720: 74 61 74 34 20 28 69 66 20 72 65 71 75 69 72 65  tat4 (if require
4730: 64 29 20 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 63  d) */.  int nRec
4740: 56 61 6c 69 64 3b 20 20 20 20 20 20 20 20 20 20  Valid;          
4750: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 76    /* Number of v
4760: 61 6c 69 64 20 66 69 65 6c 64 73 20 63 75 72 72  alid fields curr
4770: 65 6e 74 6c 79 20 69 6e 20 70 52 65 63 20 2a 2f  ently in pRec */
4780: 0a 23 65 6e 64 69 66 0a 20 20 75 6e 73 69 67 6e  .#endif.  unsign
4790: 65 64 20 69 6e 74 20 62 6c 64 46 6c 61 67 73 3b  ed int bldFlags;
47a0: 20 20 20 20 2f 2a 20 53 51 4c 49 54 45 5f 42 4c      /* SQLITE_BL
47b0: 44 46 5f 2a 20 66 6c 61 67 73 20 2a 2f 0a 7d 3b  DF_* flags */.};
47c0: 0a 0a 2f 2a 20 41 6c 6c 6f 77 65 64 20 76 61 6c  ../* Allowed val
47d0: 75 65 73 20 66 6f 72 20 57 68 65 72 65 4c 6f 6f  ues for WhereLoo
47e0: 70 42 75 69 64 65 72 2e 62 6c 64 46 6c 61 67 73  pBuider.bldFlags
47f0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 51 4c 49   */.#define SQLI
4800: 54 45 5f 42 4c 44 46 5f 49 4e 44 45 58 45 44 20  TE_BLDF_INDEXED 
4810: 20 30 78 30 30 30 31 20 20 20 2f 2a 20 41 6e 20   0x0001   /* An 
4820: 69 6e 64 65 78 20 69 73 20 75 73 65 64 20 2a 2f  index is used */
4830: 0a 23 64 65 66 69 6e 65 20 53 51 4c 49 54 45 5f  .#define SQLITE_
4840: 42 4c 44 46 5f 55 4e 49 51 55 45 20 20 20 30 78  BLDF_UNIQUE   0x
4850: 30 30 30 32 20 20 20 2f 2a 20 41 6c 6c 20 6b 65  0002   /* All ke
4860: 79 73 20 6f 66 20 61 20 55 4e 49 51 55 45 20 69  ys of a UNIQUE i
4870: 6e 64 65 78 20 75 73 65 64 20 2a 2f 0a 0a 2f 2a  ndex used */../*
4880: 0a 2a 2a 20 54 68 65 20 57 48 45 52 45 20 63 6c  .** The WHERE cl
4890: 61 75 73 65 20 70 72 6f 63 65 73 73 69 6e 67 20  ause processing 
48a0: 72 6f 75 74 69 6e 65 20 68 61 73 20 74 77 6f 20  routine has two 
48b0: 68 61 6c 76 65 73 2e 20 20 54 68 65 0a 2a 2a 20  halves.  The.** 
48c0: 66 69 72 73 74 20 70 61 72 74 20 64 6f 65 73 20  first part does 
48d0: 74 68 65 20 73 74 61 72 74 20 6f 66 20 74 68 65  the start of the
48e0: 20 57 48 45 52 45 20 6c 6f 6f 70 20 61 6e 64 20   WHERE loop and 
48f0: 74 68 65 20 73 65 63 6f 6e 64 0a 2a 2a 20 68 61  the second.** ha
4900: 6c 66 20 64 6f 65 73 20 74 68 65 20 74 61 69 6c  lf does the tail
4910: 20 6f 66 20 74 68 65 20 57 48 45 52 45 20 6c 6f   of the WHERE lo
4920: 6f 70 2e 20 20 41 6e 20 69 6e 73 74 61 6e 63 65  op.  An instance
4930: 20 6f 66 0a 2a 2a 20 74 68 69 73 20 73 74 72 75   of.** this stru
4940: 63 74 75 72 65 20 69 73 20 72 65 74 75 72 6e 65  cture is returne
4950: 64 20 62 79 20 74 68 65 20 66 69 72 73 74 20 68  d by the first h
4960: 61 6c 66 20 61 6e 64 20 70 61 73 73 65 64 0a 2a  alf and passed.*
4970: 2a 20 69 6e 74 6f 20 74 68 65 20 73 65 63 6f 6e  * into the secon
4980: 64 20 68 61 6c 66 20 74 6f 20 67 69 76 65 20 73  d half to give s
4990: 6f 6d 65 20 63 6f 6e 74 69 6e 75 69 74 79 2e 0a  ome continuity..
49a0: 2a 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63  **.** An instanc
49b0: 65 20 6f 66 20 74 68 69 73 20 6f 62 6a 65 63 74  e of this object
49c0: 20 68 6f 6c 64 73 20 74 68 65 20 63 6f 6d 70 6c   holds the compl
49d0: 65 74 65 20 73 74 61 74 65 20 6f 66 20 74 68 65  ete state of the
49e0: 20 71 75 65 72 79 0a 2a 2a 20 70 6c 61 6e 6e 65   query.** planne
49f0: 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68 65  r..*/.struct Whe
4a00: 72 65 49 6e 66 6f 20 7b 0a 20 20 50 61 72 73 65  reInfo {.  Parse
4a10: 20 2a 70 50 61 72 73 65 3b 20 20 20 20 20 20 20   *pParse;       
4a20: 20 20 20 20 20 2f 2a 20 50 61 72 73 69 6e 67 20       /* Parsing 
4a30: 61 6e 64 20 63 6f 64 65 20 67 65 6e 65 72 61 74  and code generat
4a40: 69 6e 67 20 63 6f 6e 74 65 78 74 20 2a 2f 0a 20  ing context */. 
4a50: 20 53 72 63 4c 69 73 74 20 2a 70 54 61 62 4c 69   SrcList *pTabLi
4a60: 73 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69  st;        /* Li
4a70: 73 74 20 6f 66 20 74 61 62 6c 65 73 20 69 6e 20  st of tables in 
4a80: 74 68 65 20 6a 6f 69 6e 20 2a 2f 0a 20 20 45 78  the join */.  Ex
4a90: 70 72 4c 69 73 74 20 2a 70 4f 72 64 65 72 42 79  prList *pOrderBy
4aa0: 3b 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 4f  ;       /* The O
4ab0: 52 44 45 52 20 42 59 20 63 6c 61 75 73 65 20 6f  RDER BY clause o
4ac0: 72 20 4e 55 4c 4c 20 2a 2f 0a 20 20 45 78 70 72  r NULL */.  Expr
4ad0: 4c 69 73 74 20 2a 70 52 65 73 75 6c 74 53 65 74  List *pResultSet
4ae0: 3b 20 20 20 20 20 2f 2a 20 52 65 73 75 6c 74 20  ;     /* Result 
4af0: 73 65 74 20 6f 66 20 74 68 65 20 71 75 65 72 79  set of the query
4b00: 20 2a 2f 0a 20 20 45 78 70 72 20 2a 70 57 68 65   */.  Expr *pWhe
4b10: 72 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  re;             
4b20: 2f 2a 20 54 68 65 20 63 6f 6d 70 6c 65 74 65 20  /* The complete 
4b30: 57 48 45 52 45 20 63 6c 61 75 73 65 20 2a 2f 0a  WHERE clause */.
4b40: 20 20 4c 6f 67 45 73 74 20 69 4c 69 6d 69 74 3b    LogEst iLimit;
4b50: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c              /* L
4b60: 49 4d 49 54 20 69 66 20 77 63 74 72 6c 46 6c 61  IMIT if wctrlFla
4b70: 67 73 20 68 61 73 20 57 48 45 52 45 5f 55 53 45  gs has WHERE_USE
4b80: 5f 4c 49 4d 49 54 20 2a 2f 0a 20 20 69 6e 74 20  _LIMIT */.  int 
4b90: 61 69 43 75 72 4f 6e 65 50 61 73 73 5b 32 5d 3b  aiCurOnePass[2];
4ba0: 20 20 20 20 20 20 2f 2a 20 4f 50 5f 4f 70 65 6e        /* OP_Open
4bb0: 57 72 69 74 65 20 63 75 72 73 6f 72 73 20 66 6f  Write cursors fo
4bc0: 72 20 74 68 65 20 4f 4e 45 50 41 53 53 20 6f 70  r the ONEPASS op
4bd0: 74 20 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6e 74  t */.  int iCont
4be0: 69 6e 75 65 3b 20 20 20 20 20 20 20 20 20 20 20  inue;           
4bf0: 20 2f 2a 20 4a 75 6d 70 20 68 65 72 65 20 74 6f   /* Jump here to
4c00: 20 63 6f 6e 74 69 6e 75 65 20 77 69 74 68 20 6e   continue with n
4c10: 65 78 74 20 72 65 63 6f 72 64 20 2a 2f 0a 20 20  ext record */.  
4c20: 69 6e 74 20 69 42 72 65 61 6b 3b 20 20 20 20 20  int iBreak;     
4c30: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4a 75 6d            /* Jum
4c40: 70 20 68 65 72 65 20 74 6f 20 62 72 65 61 6b 20  p here to break 
4c50: 6f 75 74 20 6f 66 20 74 68 65 20 6c 6f 6f 70 20  out of the loop 
4c60: 2a 2f 0a 20 20 69 6e 74 20 73 61 76 65 64 4e 51  */.  int savedNQ
4c70: 75 65 72 79 4c 6f 6f 70 3b 20 20 20 20 20 20 2f  ueryLoop;      /
4c80: 2a 20 70 50 61 72 73 65 2d 3e 6e 51 75 65 72 79  * pParse->nQuery
4c90: 4c 6f 6f 70 20 6f 75 74 73 69 64 65 20 74 68 65  Loop outside the
4ca0: 20 57 48 45 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20   WHERE loop */. 
4cb0: 20 75 31 36 20 77 63 74 72 6c 46 6c 61 67 73 3b   u16 wctrlFlags;
4cc0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 6c             /* Fl
4cd0: 61 67 73 20 6f 72 69 67 69 6e 61 6c 6c 79 20 70  ags originally p
4ce0: 61 73 73 65 64 20 74 6f 20 73 71 6c 69 74 65 33  assed to sqlite3
4cf0: 57 68 65 72 65 42 65 67 69 6e 28 29 20 2a 2f 0a  WhereBegin() */.
4d00: 20 20 75 38 20 6e 4c 65 76 65 6c 3b 20 20 20 20    u8 nLevel;    
4d10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
4d20: 75 6d 62 65 72 20 6f 66 20 6e 65 73 74 65 64 20  umber of nested 
4d30: 6c 6f 6f 70 20 2a 2f 0a 20 20 69 38 20 6e 4f 42  loop */.  i8 nOB
4d40: 53 61 74 3b 20 20 20 20 20 20 20 20 20 20 20 20  Sat;            
4d50: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
4d60: 20 4f 52 44 45 52 20 42 59 20 74 65 72 6d 73 20   ORDER BY terms 
4d70: 73 61 74 69 73 66 69 65 64 20 62 79 20 69 6e 64  satisfied by ind
4d80: 69 63 65 73 20 2a 2f 0a 20 20 75 38 20 73 6f 72  ices */.  u8 sor
4d90: 74 65 64 3b 20 20 20 20 20 20 20 20 20 20 20 20  ted;            
4da0: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 72      /* True if r
4db0: 65 61 6c 6c 79 20 73 6f 72 74 65 64 20 28 6e 6f  eally sorted (no
4dc0: 74 20 6a 75 73 74 20 67 72 6f 75 70 65 64 29 20  t just grouped) 
4dd0: 2a 2f 0a 20 20 75 38 20 65 4f 6e 65 50 61 73 73  */.  u8 eOnePass
4de0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  ;              /
4df0: 2a 20 4f 4e 45 50 41 53 53 5f 4f 46 46 2c 20 6f  * ONEPASS_OFF, o
4e00: 72 20 5f 53 49 4e 47 4c 45 2c 20 6f 72 20 5f 4d  r _SINGLE, or _M
4e10: 55 4c 54 49 20 2a 2f 0a 20 20 75 38 20 75 6e 74  ULTI */.  u8 unt
4e20: 65 73 74 65 64 54 65 72 6d 73 3b 20 20 20 20 20  estedTerms;     
4e30: 20 20 20 20 2f 2a 20 4e 6f 74 20 61 6c 6c 20 57      /* Not all W
4e40: 48 45 52 45 20 74 65 72 6d 73 20 72 65 73 6f 6c  HERE terms resol
4e50: 76 65 64 20 62 79 20 6f 75 74 65 72 20 6c 6f 6f  ved by outer loo
4e60: 70 20 2a 2f 0a 20 20 75 38 20 65 44 69 73 74 69  p */.  u8 eDisti
4e70: 6e 63 74 3b 20 20 20 20 20 20 20 20 20 20 20 20  nct;            
4e80: 20 2f 2a 20 4f 6e 65 20 6f 66 20 74 68 65 20 57   /* One of the W
4e90: 48 45 52 45 5f 44 49 53 54 49 4e 43 54 5f 2a 20  HERE_DISTINCT_* 
4ea0: 76 61 6c 75 65 73 20 2a 2f 0a 20 20 75 38 20 62  values */.  u8 b
4eb0: 4f 72 64 65 72 65 64 49 6e 6e 65 72 4c 6f 6f 70  OrderedInnerLoop
4ec0: 3b 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66  ;     /* True if
4ed0: 20 6f 6e 6c 79 20 74 68 65 20 69 6e 6e 65 72 2d   only the inner-
4ee0: 6d 6f 73 74 20 6c 6f 6f 70 20 69 73 20 6f 72 64  most loop is ord
4ef0: 65 72 65 64 20 2a 2f 0a 20 20 69 6e 74 20 69 54  ered */.  int iT
4f00: 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  op;             
4f10: 20 20 20 20 2f 2a 20 54 68 65 20 76 65 72 79 20      /* The very 
4f20: 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65  beginning of the
4f30: 20 57 48 45 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20   WHERE loop */. 
4f40: 20 57 68 65 72 65 4c 6f 6f 70 20 2a 70 4c 6f 6f   WhereLoop *pLoo
4f50: 70 73 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69  ps;        /* Li
4f60: 73 74 20 6f 66 20 61 6c 6c 20 57 68 65 72 65 4c  st of all WhereL
4f70: 6f 6f 70 20 6f 62 6a 65 63 74 73 20 2a 2f 0a 20  oop objects */. 
4f80: 20 42 69 74 6d 61 73 6b 20 72 65 76 4d 61 73 6b   Bitmask revMask
4f90: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61  ;          /* Ma
4fa0: 73 6b 20 6f 66 20 4f 52 44 45 52 20 42 59 20 74  sk of ORDER BY t
4fb0: 65 72 6d 73 20 74 68 61 74 20 6e 65 65 64 20 72  erms that need r
4fc0: 65 76 65 72 73 69 6e 67 20 2a 2f 0a 20 20 4c 6f  eversing */.  Lo
4fd0: 67 45 73 74 20 6e 52 6f 77 4f 75 74 3b 20 20 20  gEst nRowOut;   
4fe0: 20 20 20 20 20 20 20 20 2f 2a 20 45 73 74 69 6d          /* Estim
4ff0: 61 74 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 6f  ated number of o
5000: 75 74 70 75 74 20 72 6f 77 73 20 2a 2f 0a 20 20  utput rows */.  
5010: 57 68 65 72 65 43 6c 61 75 73 65 20 73 57 43 3b  WhereClause sWC;
5020: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 65 63            /* Dec
5030: 6f 6d 70 6f 73 69 74 69 6f 6e 20 6f 66 20 74 68  omposition of th
5040: 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20 2a  e WHERE clause *
5050: 2f 0a 20 20 57 68 65 72 65 4d 61 73 6b 53 65 74  /.  WhereMaskSet
5060: 20 73 4d 61 73 6b 53 65 74 3b 20 20 20 20 2f 2a   sMaskSet;    /*
5070: 20 4d 61 70 20 63 75 72 73 6f 72 20 6e 75 6d 62   Map cursor numb
5080: 65 72 73 20 74 6f 20 62 69 74 6d 61 73 6b 73 20  ers to bitmasks 
5090: 2a 2f 0a 20 20 57 68 65 72 65 4c 65 76 65 6c 20  */.  WhereLevel 
50a0: 61 5b 31 5d 3b 20 20 20 20 20 20 20 20 20 20 2f  a[1];          /
50b0: 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62  * Information ab
50c0: 6f 75 74 20 65 61 63 68 20 6e 65 73 74 20 6c 6f  out each nest lo
50d0: 6f 70 20 69 6e 20 57 48 45 52 45 20 2a 2f 0a 7d  op in WHERE */.}
50e0: 3b 0a 0a 2f 2a 0a 2a 2a 20 50 72 69 76 61 74 65  ;../*.** Private
50f0: 20 69 6e 74 65 72 66 61 63 65 73 20 2d 20 63 61   interfaces - ca
5100: 6c 6c 61 62 6c 65 20 6f 6e 6c 79 20 62 79 20 6f  llable only by o
5110: 74 68 65 72 20 77 68 65 72 65 2e 63 20 72 6f 75  ther where.c rou
5120: 74 69 6e 65 73 2e 0a 2a 2a 0a 2a 2a 20 77 68 65  tines..**.** whe
5130: 72 65 2e 63 3a 0a 2a 2f 0a 42 69 74 6d 61 73 6b  re.c:.*/.Bitmask
5140: 20 73 71 6c 69 74 65 33 57 68 65 72 65 47 65 74   sqlite3WhereGet
5150: 4d 61 73 6b 28 57 68 65 72 65 4d 61 73 6b 53 65  Mask(WhereMaskSe
5160: 74 2a 2c 69 6e 74 29 3b 0a 23 69 66 64 65 66 20  t*,int);.#ifdef 
5170: 57 48 45 52 45 54 52 41 43 45 5f 45 4e 41 42 4c  WHERETRACE_ENABL
5180: 45 44 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 57  ED.void sqlite3W
5190: 68 65 72 65 43 6c 61 75 73 65 50 72 69 6e 74 28  hereClausePrint(
51a0: 57 68 65 72 65 43 6c 61 75 73 65 20 2a 70 57 43  WhereClause *pWC
51b0: 29 3b 0a 23 65 6e 64 69 66 0a 57 68 65 72 65 54  );.#endif.WhereT
51c0: 65 72 6d 20 2a 73 71 6c 69 74 65 33 57 68 65 72  erm *sqlite3Wher
51d0: 65 46 69 6e 64 54 65 72 6d 28 0a 20 20 57 68 65  eFindTerm(.  Whe
51e0: 72 65 43 6c 61 75 73 65 20 2a 70 57 43 2c 20 20  reClause *pWC,  
51f0: 20 20 20 2f 2a 20 54 68 65 20 57 48 45 52 45 20     /* The WHERE 
5200: 63 6c 61 75 73 65 20 74 6f 20 62 65 20 73 65 61  clause to be sea
5210: 72 63 68 65 64 20 2a 2f 0a 20 20 69 6e 74 20 69  rched */.  int i
5220: 43 75 72 2c 20 20 20 20 20 20 20 20 20 20 20 20  Cur,            
5230: 20 2f 2a 20 43 75 72 73 6f 72 20 6e 75 6d 62 65   /* Cursor numbe
5240: 72 20 6f 66 20 4c 48 53 20 2a 2f 0a 20 20 69 6e  r of LHS */.  in
5250: 74 20 69 43 6f 6c 75 6d 6e 2c 20 20 20 20 20 20  t iColumn,      
5260: 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 6e 75      /* Column nu
5270: 6d 62 65 72 20 6f 66 20 4c 48 53 20 2a 2f 0a 20  mber of LHS */. 
5280: 20 42 69 74 6d 61 73 6b 20 6e 6f 74 52 65 61 64   Bitmask notRead
5290: 79 2c 20 20 20 20 20 2f 2a 20 52 48 53 20 6d 75  y,     /* RHS mu
52a0: 73 74 20 6e 6f 74 20 6f 76 65 72 6c 61 70 20 77  st not overlap w
52b0: 69 74 68 20 74 68 69 73 20 6d 61 73 6b 20 2a 2f  ith this mask */
52c0: 0a 20 20 75 33 32 20 6f 70 2c 20 20 20 20 20 20  .  u32 op,      
52d0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b           /* Mask
52e0: 20 6f 66 20 57 4f 5f 78 78 20 76 61 6c 75 65 73   of WO_xx values
52f0: 20 64 65 73 63 72 69 62 69 6e 67 20 6f 70 65 72   describing oper
5300: 61 74 6f 72 20 2a 2f 0a 20 20 49 6e 64 65 78 20  ator */.  Index 
5310: 2a 70 49 64 78 20 20 20 20 20 20 20 20 20 20 20  *pIdx           
5320: 2f 2a 20 4d 75 73 74 20 62 65 20 63 6f 6d 70 61  /* Must be compa
5330: 74 69 62 6c 65 20 77 69 74 68 20 74 68 69 73 20  tible with this 
5340: 69 6e 64 65 78 2c 20 69 66 20 6e 6f 74 20 4e 55  index, if not NU
5350: 4c 4c 20 2a 2f 0a 29 3b 0a 0a 2f 2a 20 77 68 65  LL */.);../* whe
5360: 72 65 63 6f 64 65 2e 63 3a 20 2a 2f 0a 23 69 66  recode.c: */.#if
5370: 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54  ndef SQLITE_OMIT
5380: 5f 45 58 50 4c 41 49 4e 0a 69 6e 74 20 73 71 6c  _EXPLAIN.int sql
5390: 69 74 65 33 57 68 65 72 65 45 78 70 6c 61 69 6e  ite3WhereExplain
53a0: 4f 6e 65 53 63 61 6e 28 0a 20 20 50 61 72 73 65  OneScan(.  Parse
53b0: 20 2a 70 50 61 72 73 65 2c 20 20 20 20 20 20 20   *pParse,       
53c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 61             /* Pa
53d0: 72 73 65 20 63 6f 6e 74 65 78 74 20 2a 2f 0a 20  rse context */. 
53e0: 20 53 72 63 4c 69 73 74 20 2a 70 54 61 62 4c 69   SrcList *pTabLi
53f0: 73 74 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  st,             
5400: 20 2f 2a 20 54 61 62 6c 65 20 6c 69 73 74 20 74   /* Table list t
5410: 68 69 73 20 6c 6f 6f 70 20 72 65 66 65 72 73 20  his loop refers 
5420: 74 6f 20 2a 2f 0a 20 20 57 68 65 72 65 4c 65 76  to */.  WhereLev
5430: 65 6c 20 2a 70 4c 65 76 65 6c 2c 20 20 20 20 20  el *pLevel,     
5440: 20 20 20 20 20 20 20 20 2f 2a 20 53 63 61 6e 20          /* Scan 
5450: 74 6f 20 77 72 69 74 65 20 4f 50 5f 45 78 70 6c  to write OP_Expl
5460: 61 69 6e 20 6f 70 63 6f 64 65 20 66 6f 72 20 2a  ain opcode for *
5470: 2f 0a 20 20 69 6e 74 20 69 4c 65 76 65 6c 2c 20  /.  int iLevel, 
5480: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5490: 20 20 20 20 2f 2a 20 56 61 6c 75 65 20 66 6f 72      /* Value for
54a0: 20 22 6c 65 76 65 6c 22 20 63 6f 6c 75 6d 6e 20   "level" column 
54b0: 6f 66 20 6f 75 74 70 75 74 20 2a 2f 0a 20 20 69  of output */.  i
54c0: 6e 74 20 69 46 72 6f 6d 2c 20 20 20 20 20 20 20  nt iFrom,       
54d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
54e0: 2a 20 56 61 6c 75 65 20 66 6f 72 20 22 66 72 6f  * Value for "fro
54f0: 6d 22 20 63 6f 6c 75 6d 6e 20 6f 66 20 6f 75 74  m" column of out
5500: 70 75 74 20 2a 2f 0a 20 20 75 31 36 20 77 63 74  put */.  u16 wct
5510: 72 6c 46 6c 61 67 73 20 20 20 20 20 20 20 20 20  rlFlags         
5520: 20 20 20 20 20 20 20 20 20 2f 2a 20 46 6c 61 67           /* Flag
5530: 73 20 70 61 73 73 65 64 20 74 6f 20 73 71 6c 69  s passed to sqli
5540: 74 65 33 57 68 65 72 65 42 65 67 69 6e 28 29 20  te3WhereBegin() 
5550: 2a 2f 0a 29 3b 0a 23 65 6c 73 65 0a 23 20 64 65  */.);.#else.# de
5560: 66 69 6e 65 20 73 71 6c 69 74 65 33 57 68 65 72  fine sqlite3Wher
5570: 65 45 78 70 6c 61 69 6e 4f 6e 65 53 63 61 6e 28  eExplainOneScan(
5580: 75 2c 76 2c 77 2c 78 2c 79 2c 7a 29 20 30 0a 23  u,v,w,x,y,z) 0.#
5590: 65 6e 64 69 66 20 2f 2a 20 53 51 4c 49 54 45 5f  endif /* SQLITE_
55a0: 4f 4d 49 54 5f 45 58 50 4c 41 49 4e 20 2a 2f 0a  OMIT_EXPLAIN */.
55b0: 23 69 66 64 65 66 20 53 51 4c 49 54 45 5f 45 4e  #ifdef SQLITE_EN
55c0: 41 42 4c 45 5f 53 54 4d 54 5f 53 43 41 4e 53 54  ABLE_STMT_SCANST
55d0: 41 54 55 53 0a 76 6f 69 64 20 73 71 6c 69 74 65  ATUS.void sqlite
55e0: 33 57 68 65 72 65 41 64 64 53 63 61 6e 53 74 61  3WhereAddScanSta
55f0: 74 75 73 28 0a 20 20 56 64 62 65 20 2a 76 2c 20  tus(.  Vdbe *v, 
5600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5610: 20 20 20 20 20 20 20 2f 2a 20 56 64 62 65 20 74         /* Vdbe t
5620: 6f 20 61 64 64 20 73 63 61 6e 73 74 61 74 75 73  o add scanstatus
5630: 20 65 6e 74 72 79 20 74 6f 20 2a 2f 0a 20 20 53   entry to */.  S
5640: 72 63 4c 69 73 74 20 2a 70 53 72 63 6c 69 73 74  rcList *pSrclist
5650: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  ,              /
5660: 2a 20 46 52 4f 4d 20 63 6c 61 75 73 65 20 70 4c  * FROM clause pL
5670: 76 6c 20 72 65 61 64 73 20 64 61 74 61 20 66 72  vl reads data fr
5680: 6f 6d 20 2a 2f 0a 20 20 57 68 65 72 65 4c 65 76  om */.  WhereLev
5690: 65 6c 20 2a 70 4c 76 6c 2c 20 20 20 20 20 20 20  el *pLvl,       
56a0: 20 20 20 20 20 20 20 20 2f 2a 20 4c 65 76 65 6c          /* Level
56b0: 20 74 6f 20 61 64 64 20 73 63 61 6e 73 74 61 74   to add scanstat
56c0: 75 73 28 29 20 65 6e 74 72 79 20 66 6f 72 20 2a  us() entry for *
56d0: 2f 0a 20 20 69 6e 74 20 61 64 64 72 45 78 70 6c  /.  int addrExpl
56e0: 61 69 6e 20 20 20 20 20 20 20 20 20 20 20 20 20  ain             
56f0: 20 20 20 20 2f 2a 20 41 64 64 72 65 73 73 20 6f      /* Address o
5700: 66 20 4f 50 5f 45 78 70 6c 61 69 6e 20 28 6f 72  f OP_Explain (or
5710: 20 30 29 20 2a 2f 0a 29 3b 0a 23 65 6c 73 65 0a   0) */.);.#else.
5720: 23 20 64 65 66 69 6e 65 20 73 71 6c 69 74 65 33  # define sqlite3
5730: 57 68 65 72 65 41 64 64 53 63 61 6e 53 74 61 74  WhereAddScanStat
5740: 75 73 28 61 2c 20 62 2c 20 63 2c 20 64 29 20 28  us(a, b, c, d) (
5750: 28 76 6f 69 64 29 64 29 0a 23 65 6e 64 69 66 0a  (void)d).#endif.
5760: 42 69 74 6d 61 73 6b 20 73 71 6c 69 74 65 33 57  Bitmask sqlite3W
5770: 68 65 72 65 43 6f 64 65 4f 6e 65 4c 6f 6f 70 53  hereCodeOneLoopS
5780: 74 61 72 74 28 0a 20 20 57 68 65 72 65 49 6e 66  tart(.  WhereInf
5790: 6f 20 2a 70 57 49 6e 66 6f 2c 20 20 20 2f 2a 20  o *pWInfo,   /* 
57a0: 43 6f 6d 70 6c 65 74 65 20 69 6e 66 6f 72 6d 61  Complete informa
57b0: 74 69 6f 6e 20 61 62 6f 75 74 20 74 68 65 20 57  tion about the W
57c0: 48 45 52 45 20 63 6c 61 75 73 65 20 2a 2f 0a 20  HERE clause */. 
57d0: 20 69 6e 74 20 69 4c 65 76 65 6c 2c 20 20 20 20   int iLevel,    
57e0: 20 20 20 20 20 20 2f 2a 20 57 68 69 63 68 20 6c        /* Which l
57f0: 65 76 65 6c 20 6f 66 20 70 57 49 6e 66 6f 2d 3e  evel of pWInfo->
5800: 61 5b 5d 20 73 68 6f 75 6c 64 20 62 65 20 63 6f  a[] should be co
5810: 64 65 64 20 2a 2f 0a 20 20 42 69 74 6d 61 73 6b  ded */.  Bitmask
5820: 20 6e 6f 74 52 65 61 64 79 20 20 20 20 20 2f 2a   notReady     /*
5830: 20 57 68 69 63 68 20 74 61 62 6c 65 73 20 61 72   Which tables ar
5840: 65 20 63 75 72 72 65 6e 74 6c 79 20 61 76 61 69  e currently avai
5850: 6c 61 62 6c 65 20 2a 2f 0a 29 3b 0a 0a 2f 2a 20  lable */.);../* 
5860: 77 68 65 72 65 65 78 70 72 2e 63 3a 20 2a 2f 0a  whereexpr.c: */.
5870: 76 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65 72  void sqlite3Wher
5880: 65 43 6c 61 75 73 65 49 6e 69 74 28 57 68 65 72  eClauseInit(Wher
5890: 65 43 6c 61 75 73 65 2a 2c 57 68 65 72 65 49 6e  eClause*,WhereIn
58a0: 66 6f 2a 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74  fo*);.void sqlit
58b0: 65 33 57 68 65 72 65 43 6c 61 75 73 65 43 6c 65  e3WhereClauseCle
58c0: 61 72 28 57 68 65 72 65 43 6c 61 75 73 65 2a 29  ar(WhereClause*)
58d0: 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 57 68  ;.void sqlite3Wh
58e0: 65 72 65 53 70 6c 69 74 28 57 68 65 72 65 43 6c  ereSplit(WhereCl
58f0: 61 75 73 65 2a 2c 45 78 70 72 2a 2c 75 38 29 3b  ause*,Expr*,u8);
5900: 0a 42 69 74 6d 61 73 6b 20 73 71 6c 69 74 65 33  .Bitmask sqlite3
5910: 57 68 65 72 65 45 78 70 72 55 73 61 67 65 28 57  WhereExprUsage(W
5920: 68 65 72 65 4d 61 73 6b 53 65 74 2a 2c 20 45 78  hereMaskSet*, Ex
5930: 70 72 2a 29 3b 0a 42 69 74 6d 61 73 6b 20 73 71  pr*);.Bitmask sq
5940: 6c 69 74 65 33 57 68 65 72 65 45 78 70 72 4c 69  lite3WhereExprLi
5950: 73 74 55 73 61 67 65 28 57 68 65 72 65 4d 61 73  stUsage(WhereMas
5960: 6b 53 65 74 2a 2c 20 45 78 70 72 4c 69 73 74 2a  kSet*, ExprList*
5970: 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 57  );.void sqlite3W
5980: 68 65 72 65 45 78 70 72 41 6e 61 6c 79 7a 65 28  hereExprAnalyze(
5990: 53 72 63 4c 69 73 74 2a 2c 20 57 68 65 72 65 43  SrcList*, WhereC
59a0: 6c 61 75 73 65 2a 29 3b 0a 76 6f 69 64 20 73 71  lause*);.void sq
59b0: 6c 69 74 65 33 57 68 65 72 65 54 61 62 46 75 6e  lite3WhereTabFun
59c0: 63 41 72 67 73 28 50 61 72 73 65 2a 2c 20 73 74  cArgs(Parse*, st
59d0: 72 75 63 74 20 53 72 63 4c 69 73 74 5f 69 74 65  ruct SrcList_ite
59e0: 6d 2a 2c 20 57 68 65 72 65 43 6c 61 75 73 65 2a  m*, WhereClause*
59f0: 29 3b 0a 0a 0a 0a 0a 0a 2f 2a 0a 2a 2a 20 42 69  );....../*.** Bi
5a00: 74 6d 61 73 6b 73 20 66 6f 72 20 74 68 65 20 6f  tmasks for the o
5a10: 70 65 72 61 74 6f 72 73 20 6f 6e 20 57 68 65 72  perators on Wher
5a20: 65 54 65 72 6d 20 6f 62 6a 65 63 74 73 2e 20 20  eTerm objects.  
5a30: 54 68 65 73 65 20 61 72 65 20 61 6c 6c 0a 2a 2a  These are all.**
5a40: 20 6f 70 65 72 61 74 6f 72 73 20 74 68 61 74 20   operators that 
5a50: 61 72 65 20 6f 66 20 69 6e 74 65 72 65 73 74 20  are of interest 
5a60: 74 6f 20 74 68 65 20 71 75 65 72 79 20 70 6c 61  to the query pla
5a70: 6e 6e 65 72 2e 20 20 41 6e 0a 2a 2a 20 4f 52 2d  nner.  An.** OR-
5a80: 65 64 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f  ed combination o
5a90: 66 20 74 68 65 73 65 20 76 61 6c 75 65 73 20 63  f these values c
5aa0: 61 6e 20 62 65 20 75 73 65 64 20 77 68 65 6e 20  an be used when 
5ab0: 73 65 61 72 63 68 69 6e 67 20 66 6f 72 0a 2a 2a  searching for.**
5ac0: 20 70 61 72 74 69 63 75 6c 61 72 20 57 68 65 72   particular Wher
5ad0: 65 54 65 72 6d 73 20 77 69 74 68 69 6e 20 61 20  eTerms within a 
5ae0: 57 68 65 72 65 43 6c 61 75 73 65 2e 0a 2a 2a 0a  WhereClause..**.
5af0: 2a 2a 20 56 61 6c 75 65 20 63 6f 6e 73 74 72 61  ** Value constra
5b00: 69 6e 74 73 3a 0a 2a 2a 20 20 20 20 20 57 4f 5f  ints:.**     WO_
5b10: 45 51 20 20 20 20 3d 3d 20 53 51 4c 49 54 45 5f  EQ    == SQLITE_
5b20: 49 4e 44 45 58 5f 43 4f 4e 53 54 52 41 49 4e 54  INDEX_CONSTRAINT
5b30: 5f 45 51 0a 2a 2a 20 20 20 20 20 57 4f 5f 4c 54  _EQ.**     WO_LT
5b40: 20 20 20 20 3d 3d 20 53 51 4c 49 54 45 5f 49 4e      == SQLITE_IN
5b50: 44 45 58 5f 43 4f 4e 53 54 52 41 49 4e 54 5f 4c  DEX_CONSTRAINT_L
5b60: 54 0a 2a 2a 20 20 20 20 20 57 4f 5f 4c 45 20 20  T.**     WO_LE  
5b70: 20 20 3d 3d 20 53 51 4c 49 54 45 5f 49 4e 44 45    == SQLITE_INDE
5b80: 58 5f 43 4f 4e 53 54 52 41 49 4e 54 5f 4c 45 0a  X_CONSTRAINT_LE.
5b90: 2a 2a 20 20 20 20 20 57 4f 5f 47 54 20 20 20 20  **     WO_GT    
5ba0: 3d 3d 20 53 51 4c 49 54 45 5f 49 4e 44 45 58 5f  == SQLITE_INDEX_
5bb0: 43 4f 4e 53 54 52 41 49 4e 54 5f 47 54 0a 2a 2a  CONSTRAINT_GT.**
5bc0: 20 20 20 20 20 57 4f 5f 47 45 20 20 20 20 3d 3d       WO_GE    ==
5bd0: 20 53 51 4c 49 54 45 5f 49 4e 44 45 58 5f 43 4f   SQLITE_INDEX_CO
5be0: 4e 53 54 52 41 49 4e 54 5f 47 45 0a 2a 2f 0a 23  NSTRAINT_GE.*/.#
5bf0: 64 65 66 69 6e 65 20 57 4f 5f 49 4e 20 20 20 20  define WO_IN    
5c00: 20 30 78 30 30 30 31 0a 23 64 65 66 69 6e 65 20   0x0001.#define 
5c10: 57 4f 5f 45 51 20 20 20 20 20 30 78 30 30 30 32  WO_EQ     0x0002
5c20: 0a 23 64 65 66 69 6e 65 20 57 4f 5f 4c 54 20 20  .#define WO_LT  
5c30: 20 20 20 28 57 4f 5f 45 51 3c 3c 28 54 4b 5f 4c     (WO_EQ<<(TK_L
5c40: 54 2d 54 4b 5f 45 51 29 29 0a 23 64 65 66 69 6e  T-TK_EQ)).#defin
5c50: 65 20 57 4f 5f 4c 45 20 20 20 20 20 28 57 4f 5f  e WO_LE     (WO_
5c60: 45 51 3c 3c 28 54 4b 5f 4c 45 2d 54 4b 5f 45 51  EQ<<(TK_LE-TK_EQ
5c70: 29 29 0a 23 64 65 66 69 6e 65 20 57 4f 5f 47 54  )).#define WO_GT
5c80: 20 20 20 20 20 28 57 4f 5f 45 51 3c 3c 28 54 4b       (WO_EQ<<(TK
5c90: 5f 47 54 2d 54 4b 5f 45 51 29 29 0a 23 64 65 66  _GT-TK_EQ)).#def
5ca0: 69 6e 65 20 57 4f 5f 47 45 20 20 20 20 20 28 57  ine WO_GE     (W
5cb0: 4f 5f 45 51 3c 3c 28 54 4b 5f 47 45 2d 54 4b 5f  O_EQ<<(TK_GE-TK_
5cc0: 45 51 29 29 0a 23 64 65 66 69 6e 65 20 57 4f 5f  EQ)).#define WO_
5cd0: 41 55 58 20 20 20 20 30 78 30 30 34 30 20 20 20  AUX    0x0040   
5ce0: 20 20 20 20 2f 2a 20 4f 70 20 75 73 65 66 75 6c      /* Op useful
5cf0: 20 74 6f 20 76 69 72 74 75 61 6c 20 74 61 62 6c   to virtual tabl
5d00: 65 73 20 6f 6e 6c 79 20 2a 2f 0a 23 64 65 66 69  es only */.#defi
5d10: 6e 65 20 57 4f 5f 49 53 20 20 20 20 20 30 78 30  ne WO_IS     0x0
5d20: 30 38 30 0a 23 64 65 66 69 6e 65 20 57 4f 5f 49  080.#define WO_I
5d30: 53 4e 55 4c 4c 20 30 78 30 31 30 30 0a 23 64 65  SNULL 0x0100.#de
5d40: 66 69 6e 65 20 57 4f 5f 4f 52 20 20 20 20 20 30  fine WO_OR     0
5d50: 78 30 32 30 30 20 20 20 20 20 20 20 2f 2a 20 54  x0200       /* T
5d60: 77 6f 20 6f 72 20 6d 6f 72 65 20 4f 52 2d 63 6f  wo or more OR-co
5d70: 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20 2a 2f  nnected terms */
5d80: 0a 23 64 65 66 69 6e 65 20 57 4f 5f 41 4e 44 20  .#define WO_AND 
5d90: 20 20 20 30 78 30 34 30 30 20 20 20 20 20 20 20     0x0400       
5da0: 2f 2a 20 54 77 6f 20 6f 72 20 6d 6f 72 65 20 41  /* Two or more A
5db0: 4e 44 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72  ND-connected ter
5dc0: 6d 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 4f  ms */.#define WO
5dd0: 5f 45 51 55 49 56 20 20 30 78 30 38 30 30 20 20  _EQUIV  0x0800  
5de0: 20 20 20 20 20 2f 2a 20 4f 66 20 74 68 65 20 66       /* Of the f
5df0: 6f 72 6d 20 41 3d 3d 42 2c 20 62 6f 74 68 20 63  orm A==B, both c
5e00: 6f 6c 75 6d 6e 73 20 2a 2f 0a 23 64 65 66 69 6e  olumns */.#defin
5e10: 65 20 57 4f 5f 4e 4f 4f 50 20 20 20 30 78 31 30  e WO_NOOP   0x10
5e20: 30 30 20 20 20 20 20 20 20 2f 2a 20 54 68 69 73  00       /* This
5e30: 20 74 65 72 6d 20 64 6f 65 73 20 6e 6f 74 20 72   term does not r
5e40: 65 73 74 72 69 63 74 20 73 65 61 72 63 68 20 73  estrict search s
5e50: 70 61 63 65 20 2a 2f 0a 0a 23 64 65 66 69 6e 65  pace */..#define
5e60: 20 57 4f 5f 41 4c 4c 20 20 20 20 30 78 31 66 66   WO_ALL    0x1ff
5e70: 66 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20  f       /* Mask 
5e80: 6f 66 20 61 6c 6c 20 70 6f 73 73 69 62 6c 65 20  of all possible 
5e90: 57 4f 5f 2a 20 76 61 6c 75 65 73 20 2a 2f 0a 23  WO_* values */.#
5ea0: 64 65 66 69 6e 65 20 57 4f 5f 53 49 4e 47 4c 45  define WO_SINGLE
5eb0: 20 30 78 30 31 66 66 20 20 20 20 20 20 20 2f 2a   0x01ff       /*
5ec0: 20 4d 61 73 6b 20 6f 66 20 61 6c 6c 20 6e 6f 6e   Mask of all non
5ed0: 2d 63 6f 6d 70 6f 75 6e 64 20 57 4f 5f 2a 20 76  -compound WO_* v
5ee0: 61 6c 75 65 73 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20  alues */../*.** 
5ef0: 54 68 65 73 65 20 61 72 65 20 64 65 66 69 6e 69  These are defini
5f00: 74 69 6f 6e 73 20 6f 66 20 62 69 74 73 20 69 6e  tions of bits in
5f10: 20 74 68 65 20 57 68 65 72 65 4c 6f 6f 70 2e 77   the WhereLoop.w
5f20: 73 46 6c 61 67 73 20 66 69 65 6c 64 2e 0a 2a 2a  sFlags field..**
5f30: 20 54 68 65 20 70 61 72 74 69 63 75 6c 61 72 20   The particular 
5f40: 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f 66 20 62  combination of b
5f50: 69 74 73 20 69 6e 20 65 61 63 68 20 57 68 65 72  its in each Wher
5f60: 65 4c 6f 6f 70 20 68 65 6c 70 20 74 6f 0a 2a 2a  eLoop help to.**
5f70: 20 64 65 74 65 72 6d 69 6e 65 20 74 68 65 20 61   determine the a
5f80: 6c 67 6f 72 69 74 68 6d 20 74 68 61 74 20 57 68  lgorithm that Wh
5f90: 65 72 65 4c 6f 6f 70 20 72 65 70 72 65 73 65 6e  ereLoop represen
5fa0: 74 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 57  ts..*/.#define W
5fb0: 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 45 51 20 20  HERE_COLUMN_EQ  
5fc0: 20 20 30 78 30 30 30 30 30 30 30 31 20 20 2f 2a    0x00000001  /*
5fd0: 20 78 3d 45 58 50 52 20 2a 2f 0a 23 64 65 66 69   x=EXPR */.#defi
5fe0: 6e 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f  ne WHERE_COLUMN_
5ff0: 52 41 4e 47 45 20 30 78 30 30 30 30 30 30 30 32  RANGE 0x00000002
6000: 20 20 2f 2a 20 78 3c 45 58 50 52 20 61 6e 64 2f    /* x<EXPR and/
6010: 6f 72 20 78 3e 45 58 50 52 20 2a 2f 0a 23 64 65  or x>EXPR */.#de
6020: 66 69 6e 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d  fine WHERE_COLUM
6030: 4e 5f 49 4e 20 20 20 20 30 78 30 30 30 30 30 30  N_IN    0x000000
6040: 30 34 20 20 2f 2a 20 78 20 49 4e 20 28 2e 2e 2e  04  /* x IN (...
6050: 29 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45  ) */.#define WHE
6060: 52 45 5f 43 4f 4c 55 4d 4e 5f 4e 55 4c 4c 20 20  RE_COLUMN_NULL  
6070: 30 78 30 30 30 30 30 30 30 38 20 20 2f 2a 20 78  0x00000008  /* x
6080: 20 49 53 20 4e 55 4c 4c 20 2a 2f 0a 23 64 65 66   IS NULL */.#def
6090: 69 6e 65 20 57 48 45 52 45 5f 43 4f 4e 53 54 52  ine WHERE_CONSTR
60a0: 41 49 4e 54 20 20 20 30 78 30 30 30 30 30 30 30  AINT   0x0000000
60b0: 66 20 20 2f 2a 20 41 6e 79 20 6f 66 20 74 68 65  f  /* Any of the
60c0: 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 78 78   WHERE_COLUMN_xx
60d0: 78 20 76 61 6c 75 65 73 20 2a 2f 0a 23 64 65 66  x values */.#def
60e0: 69 6e 65 20 57 48 45 52 45 5f 54 4f 50 5f 4c 49  ine WHERE_TOP_LI
60f0: 4d 49 54 20 20 20 20 30 78 30 30 30 30 30 30 31  MIT    0x0000001
6100: 30 20 20 2f 2a 20 78 3c 45 58 50 52 20 6f 72 20  0  /* x<EXPR or 
6110: 78 3c 3d 45 58 50 52 20 63 6f 6e 73 74 72 61 69  x<=EXPR constrai
6120: 6e 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  nt */.#define WH
6130: 45 52 45 5f 42 54 4d 5f 4c 49 4d 49 54 20 20 20  ERE_BTM_LIMIT   
6140: 20 30 78 30 30 30 30 30 30 32 30 20 20 2f 2a 20   0x00000020  /* 
6150: 78 3e 45 58 50 52 20 6f 72 20 78 3e 3d 45 58 50  x>EXPR or x>=EXP
6160: 52 20 63 6f 6e 73 74 72 61 69 6e 74 20 2a 2f 0a  R constraint */.
6170: 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f 42 4f  #define WHERE_BO
6180: 54 48 5f 4c 49 4d 49 54 20 20 20 30 78 30 30 30  TH_LIMIT   0x000
6190: 30 30 30 33 30 20 20 2f 2a 20 42 6f 74 68 20 78  00030  /* Both x
61a0: 3e 45 58 50 52 20 61 6e 64 20 78 3c 45 58 50 52  >EXPR and x<EXPR
61b0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52   */.#define WHER
61c0: 45 5f 49 44 58 5f 4f 4e 4c 59 20 20 20 20 20 30  E_IDX_ONLY     0
61d0: 78 30 30 30 30 30 30 34 30 20 20 2f 2a 20 55 73  x00000040  /* Us
61e0: 65 20 69 6e 64 65 78 20 6f 6e 6c 79 20 2d 20 6f  e index only - o
61f0: 6d 69 74 20 74 61 62 6c 65 20 2a 2f 0a 23 64 65  mit table */.#de
6200: 66 69 6e 65 20 57 48 45 52 45 5f 49 50 4b 20 20  fine WHERE_IPK  
6210: 20 20 20 20 20 20 20 20 30 78 30 30 30 30 30 31          0x000001
6220: 30 30 20 20 2f 2a 20 78 20 69 73 20 74 68 65 20  00  /* x is the 
6230: 49 4e 54 45 47 45 52 20 50 52 49 4d 41 52 59 20  INTEGER PRIMARY 
6240: 4b 45 59 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  KEY */.#define W
6250: 48 45 52 45 5f 49 4e 44 45 58 45 44 20 20 20 20  HERE_INDEXED    
6260: 20 20 30 78 30 30 30 30 30 32 30 30 20 20 2f 2a    0x00000200  /*
6270: 20 57 68 65 72 65 4c 6f 6f 70 2e 75 2e 62 74 72   WhereLoop.u.btr
6280: 65 65 2e 70 49 6e 64 65 78 20 69 73 20 76 61 6c  ee.pIndex is val
6290: 69 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  id */.#define WH
62a0: 45 52 45 5f 56 49 52 54 55 41 4c 54 41 42 4c 45  ERE_VIRTUALTABLE
62b0: 20 30 78 30 30 30 30 30 34 30 30 20 20 2f 2a 20   0x00000400  /* 
62c0: 57 68 65 72 65 4c 6f 6f 70 2e 75 2e 76 74 61 62  WhereLoop.u.vtab
62d0: 20 69 73 20 76 61 6c 69 64 20 2a 2f 0a 23 64 65   is valid */.#de
62e0: 66 69 6e 65 20 57 48 45 52 45 5f 49 4e 5f 41 42  fine WHERE_IN_AB
62f0: 4c 45 20 20 20 20 20 20 30 78 30 30 30 30 30 38  LE      0x000008
6300: 30 30 20 20 2f 2a 20 41 62 6c 65 20 74 6f 20 73  00  /* Able to s
6310: 75 70 70 6f 72 74 20 61 6e 20 49 4e 20 6f 70 65  upport an IN ope
6320: 72 61 74 6f 72 20 2a 2f 0a 23 64 65 66 69 6e 65  rator */.#define
6330: 20 57 48 45 52 45 5f 4f 4e 45 52 4f 57 20 20 20   WHERE_ONEROW   
6340: 20 20 20 20 30 78 30 30 30 30 31 30 30 30 20 20      0x00001000  
6350: 2f 2a 20 53 65 6c 65 63 74 73 20 6e 6f 20 6d 6f  /* Selects no mo
6360: 72 65 20 74 68 61 6e 20 6f 6e 65 20 72 6f 77 20  re than one row 
6370: 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45  */.#define WHERE
6380: 5f 4d 55 4c 54 49 5f 4f 52 20 20 20 20 20 30 78  _MULTI_OR     0x
6390: 30 30 30 30 32 30 30 30 20 20 2f 2a 20 4f 52 20  00002000  /* OR 
63a0: 75 73 69 6e 67 20 6d 75 6c 74 69 70 6c 65 20 69  using multiple i
63b0: 6e 64 69 63 65 73 20 2a 2f 0a 23 64 65 66 69 6e  ndices */.#defin
63c0: 65 20 57 48 45 52 45 5f 41 55 54 4f 5f 49 4e 44  e WHERE_AUTO_IND
63d0: 45 58 20 20 20 30 78 30 30 30 30 34 30 30 30 20  EX   0x00004000 
63e0: 20 2f 2a 20 55 73 65 73 20 61 6e 20 65 70 68 65   /* Uses an ephe
63f0: 6d 65 72 61 6c 20 69 6e 64 65 78 20 2a 2f 0a 23  meral index */.#
6400: 64 65 66 69 6e 65 20 57 48 45 52 45 5f 53 4b 49  define WHERE_SKI
6410: 50 53 43 41 4e 20 20 20 20 20 30 78 30 30 30 30  PSCAN     0x0000
6420: 38 30 30 30 20 20 2f 2a 20 55 73 65 73 20 74 68  8000  /* Uses th
6430: 65 20 73 6b 69 70 2d 73 63 61 6e 20 61 6c 67 6f  e skip-scan algo
6440: 72 69 74 68 6d 20 2a 2f 0a 23 64 65 66 69 6e 65  rithm */.#define
6450: 20 57 48 45 52 45 5f 55 4e 51 5f 57 41 4e 54 45   WHERE_UNQ_WANTE
6460: 44 20 20 20 30 78 30 30 30 31 30 30 30 30 20 20  D   0x00010000  
6470: 2f 2a 20 57 48 45 52 45 5f 4f 4e 45 52 4f 57 20  /* WHERE_ONEROW 
6480: 77 6f 75 6c 64 20 68 61 76 65 20 62 65 65 6e 20  would have been 
6490: 68 65 6c 70 66 75 6c 2a 2f 0a 23 64 65 66 69 6e  helpful*/.#defin
64a0: 65 20 57 48 45 52 45 5f 50 41 52 54 49 41 4c 49  e WHERE_PARTIALI
64b0: 44 58 20 20 20 30 78 30 30 30 32 30 30 30 30 20  DX   0x00020000 
64c0: 20 2f 2a 20 54 68 65 20 61 75 74 6f 6d 61 74 69   /* The automati
64d0: 63 20 69 6e 64 65 78 20 69 73 20 70 61 72 74 69  c index is parti
64e0: 61 6c 20 2a 2f 0a                                al */.