/ Hex Artifact Content
Login

Artifact 1b728f71654ebf8421a1715497a587f02d6f538e819af58dc826908f8577e810:


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 23 69  r editing..*/.#i
0230: 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 57 48 45  fndef SQLITE_WHE
0240: 52 45 49 4e 54 5f 48 0a 23 64 65 66 69 6e 65 20  REINT_H.#define 
0250: 53 51 4c 49 54 45 5f 57 48 45 52 45 49 4e 54 5f  SQLITE_WHEREINT_
0260: 48 0a 0a 2f 2a 0a 2a 2a 20 54 72 61 63 65 20 6f  H../*.** Trace o
0270: 75 74 70 75 74 20 6d 61 63 72 6f 73 0a 2a 2f 0a  utput macros.*/.
0280: 23 69 66 20 64 65 66 69 6e 65 64 28 53 51 4c 49  #if defined(SQLI
0290: 54 45 5f 54 45 53 54 29 20 7c 7c 20 64 65 66 69  TE_TEST) || defi
02a0: 6e 65 64 28 53 51 4c 49 54 45 5f 44 45 42 55 47  ned(SQLITE_DEBUG
02b0: 29 0a 2f 2a 2a 2a 2f 20 65 78 74 65 72 6e 20 69  )./***/ extern i
02c0: 6e 74 20 73 71 6c 69 74 65 33 57 68 65 72 65 54  nt sqlite3WhereT
02d0: 72 61 63 65 3b 0a 23 65 6e 64 69 66 0a 23 69 66  race;.#endif.#if
02e0: 20 64 65 66 69 6e 65 64 28 53 51 4c 49 54 45 5f   defined(SQLITE_
02f0: 44 45 42 55 47 29 20 5c 0a 20 20 20 20 26 26 20  DEBUG) \.    && 
0300: 28 64 65 66 69 6e 65 64 28 53 51 4c 49 54 45 5f  (defined(SQLITE_
0310: 54 45 53 54 29 20 7c 7c 20 64 65 66 69 6e 65 64  TEST) || defined
0320: 28 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 57  (SQLITE_ENABLE_W
0330: 48 45 52 45 54 52 41 43 45 29 29 0a 23 20 64 65  HERETRACE)).# de
0340: 66 69 6e 65 20 57 48 45 52 45 54 52 41 43 45 28  fine WHERETRACE(
0350: 4b 2c 58 29 20 20 69 66 28 73 71 6c 69 74 65 33  K,X)  if(sqlite3
0360: 57 68 65 72 65 54 72 61 63 65 26 28 4b 29 29 20  WhereTrace&(K)) 
0370: 73 71 6c 69 74 65 33 44 65 62 75 67 50 72 69 6e  sqlite3DebugPrin
0380: 74 66 20 58 0a 23 20 64 65 66 69 6e 65 20 57 48  tf X.# define WH
0390: 45 52 45 54 52 41 43 45 5f 45 4e 41 42 4c 45 44  ERETRACE_ENABLED
03a0: 20 31 0a 23 65 6c 73 65 0a 23 20 64 65 66 69 6e   1.#else.# defin
03b0: 65 20 57 48 45 52 45 54 52 41 43 45 28 4b 2c 58  e WHERETRACE(K,X
03c0: 29 0a 23 65 6e 64 69 66 0a 0a 2f 2a 20 46 6f 72  ).#endif../* For
03d0: 77 61 72 64 20 72 65 66 65 72 65 6e 63 65 73 0a  ward references.
03e0: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
03f0: 74 20 57 68 65 72 65 43 6c 61 75 73 65 20 57 68  t WhereClause Wh
0400: 65 72 65 43 6c 61 75 73 65 3b 0a 74 79 70 65 64  ereClause;.typed
0410: 65 66 20 73 74 72 75 63 74 20 57 68 65 72 65 4d  ef struct WhereM
0420: 61 73 6b 53 65 74 20 57 68 65 72 65 4d 61 73 6b  askSet WhereMask
0430: 53 65 74 3b 0a 74 79 70 65 64 65 66 20 73 74 72  Set;.typedef str
0440: 75 63 74 20 57 68 65 72 65 4f 72 49 6e 66 6f 20  uct WhereOrInfo 
0450: 57 68 65 72 65 4f 72 49 6e 66 6f 3b 0a 74 79 70  WhereOrInfo;.typ
0460: 65 64 65 66 20 73 74 72 75 63 74 20 57 68 65 72  edef struct Wher
0470: 65 41 6e 64 49 6e 66 6f 20 57 68 65 72 65 41 6e  eAndInfo WhereAn
0480: 64 49 6e 66 6f 3b 0a 74 79 70 65 64 65 66 20 73  dInfo;.typedef s
0490: 74 72 75 63 74 20 57 68 65 72 65 4c 65 76 65 6c  truct WhereLevel
04a0: 20 57 68 65 72 65 4c 65 76 65 6c 3b 0a 74 79 70   WhereLevel;.typ
04b0: 65 64 65 66 20 73 74 72 75 63 74 20 57 68 65 72  edef struct Wher
04c0: 65 4c 6f 6f 70 20 57 68 65 72 65 4c 6f 6f 70 3b  eLoop WhereLoop;
04d0: 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20  .typedef struct 
04e0: 57 68 65 72 65 50 61 74 68 20 57 68 65 72 65 50  WherePath WhereP
04f0: 61 74 68 3b 0a 74 79 70 65 64 65 66 20 73 74 72  ath;.typedef str
0500: 75 63 74 20 57 68 65 72 65 54 65 72 6d 20 57 68  uct WhereTerm Wh
0510: 65 72 65 54 65 72 6d 3b 0a 74 79 70 65 64 65 66  ereTerm;.typedef
0520: 20 73 74 72 75 63 74 20 57 68 65 72 65 4c 6f 6f   struct WhereLoo
0530: 70 42 75 69 6c 64 65 72 20 57 68 65 72 65 4c 6f  pBuilder WhereLo
0540: 6f 70 42 75 69 6c 64 65 72 3b 0a 74 79 70 65 64  opBuilder;.typed
0550: 65 66 20 73 74 72 75 63 74 20 57 68 65 72 65 53  ef struct WhereS
0560: 63 61 6e 20 57 68 65 72 65 53 63 61 6e 3b 0a 74  can WhereScan;.t
0570: 79 70 65 64 65 66 20 73 74 72 75 63 74 20 57 68  ypedef struct Wh
0580: 65 72 65 4f 72 43 6f 73 74 20 57 68 65 72 65 4f  ereOrCost WhereO
0590: 72 43 6f 73 74 3b 0a 74 79 70 65 64 65 66 20 73  rCost;.typedef s
05a0: 74 72 75 63 74 20 57 68 65 72 65 4f 72 53 65 74  truct WhereOrSet
05b0: 20 57 68 65 72 65 4f 72 53 65 74 3b 0a 0a 2f 2a   WhereOrSet;../*
05c0: 0a 2a 2a 20 54 68 69 73 20 6f 62 6a 65 63 74 20  .** This object 
05d0: 63 6f 6e 74 61 69 6e 73 20 69 6e 66 6f 72 6d 61  contains informa
05e0: 74 69 6f 6e 20 6e 65 65 64 65 64 20 74 6f 20 69  tion needed to i
05f0: 6d 70 6c 65 6d 65 6e 74 20 61 20 73 69 6e 67 6c  mplement a singl
0600: 65 20 6e 65 73 74 65 64 0a 2a 2a 20 6c 6f 6f 70  e nested.** loop
0610: 20 69 6e 20 57 48 45 52 45 20 63 6c 61 75 73 65   in WHERE clause
0620: 2e 0a 2a 2a 0a 2a 2a 20 43 6f 6e 74 72 61 73 74  ..**.** Contrast
0630: 20 74 68 69 73 20 6f 62 6a 65 63 74 20 77 69 74   this object wit
0640: 68 20 57 68 65 72 65 4c 6f 6f 70 2e 20 20 54 68  h WhereLoop.  Th
0650: 69 73 20 6f 62 6a 65 63 74 20 64 65 73 63 72 69  is object descri
0660: 62 65 73 20 74 68 65 0a 2a 2a 20 69 6d 70 6c 65  bes the.** imple
0670: 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 74 68 65  mentation of the
0680: 20 6c 6f 6f 70 2e 20 20 57 68 65 72 65 4c 6f 6f   loop.  WhereLoo
0690: 70 20 64 65 73 63 72 69 62 65 73 20 74 68 65 20  p describes the 
06a0: 61 6c 67 6f 72 69 74 68 6d 2e 0a 2a 2a 20 54 68  algorithm..** Th
06b0: 69 73 20 6f 62 6a 65 63 74 20 63 6f 6e 74 61 69  is object contai
06c0: 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  ns a pointer to 
06d0: 74 68 65 20 57 68 65 72 65 4c 6f 6f 70 20 61 6c  the WhereLoop al
06e0: 67 6f 72 69 74 68 6d 20 61 73 20 6f 6e 65 20 6f  gorithm as one o
06f0: 66 0a 2a 2a 20 69 74 73 20 65 6c 65 6d 65 6e 74  f.** its element
0700: 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 57 68 65  s..**.** The Whe
0710: 72 65 49 6e 66 6f 20 6f 62 6a 65 63 74 20 63 6f  reInfo object co
0720: 6e 74 61 69 6e 73 20 61 20 73 69 6e 67 6c 65 20  ntains a single 
0730: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 69 73  instance of this
0740: 20 6f 62 6a 65 63 74 20 66 6f 72 0a 2a 2a 20 65   object for.** e
0750: 61 63 68 20 74 65 72 6d 20 69 6e 20 74 68 65 20  ach term in the 
0760: 46 52 4f 4d 20 63 6c 61 75 73 65 20 28 77 68 69  FROM clause (whi
0770: 63 68 20 69 73 20 74 6f 20 73 61 79 2c 20 66 6f  ch is to say, fo
0780: 72 20 65 61 63 68 20 6f 66 20 74 68 65 0a 2a 2a  r each of the.**
0790: 20 6e 65 73 74 65 64 20 6c 6f 6f 70 73 20 61 73   nested loops as
07a0: 20 69 6d 70 6c 65 6d 65 6e 74 65 64 29 2e 20 20   implemented).  
07b0: 54 68 65 20 6f 72 64 65 72 20 6f 66 20 57 68 65  The order of Whe
07c0: 72 65 4c 65 76 65 6c 20 6f 62 6a 65 63 74 73 20  reLevel objects 
07d0: 64 65 74 65 72 6d 69 6e 65 73 0a 2a 2a 20 74 68  determines.** th
07e0: 65 20 6c 6f 6f 70 20 6e 65 73 74 65 64 20 6f 72  e loop nested or
07f0: 64 65 72 2c 20 77 69 74 68 20 57 68 65 72 65 49  der, with WhereI
0800: 6e 66 6f 2e 61 5b 30 5d 20 62 65 69 6e 67 20 74  nfo.a[0] being t
0810: 68 65 20 6f 75 74 65 72 20 6c 6f 6f 70 20 61 6e  he outer loop an
0820: 64 0a 2a 2a 20 57 68 65 72 65 49 6e 66 6f 2e 61  d.** WhereInfo.a
0830: 5b 57 68 65 72 65 49 6e 66 6f 2e 6e 4c 65 76 65  [WhereInfo.nLeve
0840: 6c 2d 31 5d 20 62 65 69 6e 67 20 74 68 65 20 69  l-1] being the i
0850: 6e 6e 65 72 20 6c 6f 6f 70 2e 0a 2a 2f 0a 73 74  nner loop..*/.st
0860: 72 75 63 74 20 57 68 65 72 65 4c 65 76 65 6c 20  ruct WhereLevel 
0870: 7b 0a 20 20 69 6e 74 20 69 4c 65 66 74 4a 6f 69  {.  int iLeftJoi
0880: 6e 3b 20 20 20 20 20 20 20 20 2f 2a 20 4d 65 6d  n;        /* Mem
0890: 6f 72 79 20 63 65 6c 6c 20 75 73 65 64 20 74 6f  ory cell used to
08a0: 20 69 6d 70 6c 65 6d 65 6e 74 20 4c 45 46 54 20   implement LEFT 
08b0: 4f 55 54 45 52 20 4a 4f 49 4e 20 2a 2f 0a 20 20  OUTER JOIN */.  
08c0: 69 6e 74 20 69 54 61 62 43 75 72 3b 20 20 20 20  int iTabCur;    
08d0: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 56 44 42        /* The VDB
08e0: 45 20 63 75 72 73 6f 72 20 75 73 65 64 20 74 6f  E cursor used to
08f0: 20 61 63 63 65 73 73 20 74 68 65 20 74 61 62 6c   access the tabl
0900: 65 20 2a 2f 0a 20 20 69 6e 74 20 69 49 64 78 43  e */.  int iIdxC
0910: 75 72 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ur;          /* 
0920: 54 68 65 20 56 44 42 45 20 63 75 72 73 6f 72 20  The VDBE cursor 
0930: 75 73 65 64 20 74 6f 20 61 63 63 65 73 73 20 70  used to access p
0940: 49 64 78 20 2a 2f 0a 20 20 69 6e 74 20 61 64 64  Idx */.  int add
0950: 72 42 72 6b 3b 20 20 20 20 20 20 20 20 20 20 2f  rBrk;          /
0960: 2a 20 4a 75 6d 70 20 68 65 72 65 20 74 6f 20 62  * Jump here to b
0970: 72 65 61 6b 20 6f 75 74 20 6f 66 20 74 68 65 20  reak out of the 
0980: 6c 6f 6f 70 20 2a 2f 0a 20 20 69 6e 74 20 61 64  loop */.  int ad
0990: 64 72 4e 78 74 3b 20 20 20 20 20 20 20 20 20 20  drNxt;          
09a0: 2f 2a 20 4a 75 6d 70 20 68 65 72 65 20 74 6f 20  /* Jump here to 
09b0: 73 74 61 72 74 20 74 68 65 20 6e 65 78 74 20 49  start the next I
09c0: 4e 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 2a 2f  N combination */
09d0: 0a 20 20 69 6e 74 20 61 64 64 72 53 6b 69 70 3b  .  int addrSkip;
09e0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4a 75 6d 70           /* Jump
09f0: 20 68 65 72 65 20 66 6f 72 20 6e 65 78 74 20 69   here for next i
0a00: 74 65 72 61 74 69 6f 6e 20 6f 66 20 73 6b 69 70  teration of skip
0a10: 2d 73 63 61 6e 20 2a 2f 0a 20 20 69 6e 74 20 61  -scan */.  int a
0a20: 64 64 72 43 6f 6e 74 3b 20 20 20 20 20 20 20 20  ddrCont;        
0a30: 20 2f 2a 20 4a 75 6d 70 20 68 65 72 65 20 74 6f   /* Jump here to
0a40: 20 63 6f 6e 74 69 6e 75 65 20 77 69 74 68 20 74   continue with t
0a50: 68 65 20 6e 65 78 74 20 6c 6f 6f 70 20 63 79 63  he next loop cyc
0a60: 6c 65 20 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72  le */.  int addr
0a70: 46 69 72 73 74 3b 20 20 20 20 20 20 20 20 2f 2a  First;        /*
0a80: 20 46 69 72 73 74 20 69 6e 73 74 72 75 63 74 69   First instructi
0a90: 6f 6e 20 6f 66 20 69 6e 74 65 72 69 6f 72 20 6f  on of interior o
0aa0: 66 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20 20  f the loop */.  
0ab0: 69 6e 74 20 61 64 64 72 42 6f 64 79 3b 20 20 20  int addrBody;   
0ac0: 20 20 20 20 20 20 2f 2a 20 42 65 67 69 6e 6e 69        /* Beginni
0ad0: 6e 67 20 6f 66 20 74 68 65 20 62 6f 64 79 20 6f  ng of the body o
0ae0: 66 20 74 68 69 73 20 6c 6f 6f 70 20 2a 2f 0a 23  f this loop */.#
0af0: 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4c 49  ifndef SQLITE_LI
0b00: 4b 45 5f 44 4f 45 53 4e 54 5f 4d 41 54 43 48 5f  KE_DOESNT_MATCH_
0b10: 42 4c 4f 42 53 0a 20 20 75 33 32 20 69 4c 69 6b  BLOBS.  u32 iLik
0b20: 65 52 65 70 43 6e 74 72 3b 20 20 20 20 20 2f 2a  eRepCntr;     /*
0b30: 20 4c 49 4b 45 20 72 61 6e 67 65 20 70 72 6f 63   LIKE range proc
0b40: 65 73 73 69 6e 67 20 63 6f 75 6e 74 65 72 20 72  essing counter r
0b50: 65 67 69 73 74 65 72 20 28 74 69 6d 65 73 20 32  egister (times 2
0b60: 29 20 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72 4c  ) */.  int addrL
0b70: 69 6b 65 52 65 70 3b 20 20 20 20 20 20 2f 2a 20  ikeRep;      /* 
0b80: 4c 49 4b 45 20 72 61 6e 67 65 20 70 72 6f 63 65  LIKE range proce
0b90: 73 73 69 6e 67 20 61 64 64 72 65 73 73 20 2a 2f  ssing address */
0ba0: 0a 23 65 6e 64 69 66 0a 20 20 75 38 20 69 46 72  .#endif.  u8 iFr
0bb0: 6f 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  om;             
0bc0: 2f 2a 20 57 68 69 63 68 20 65 6e 74 72 79 20 69  /* Which entry i
0bd0: 6e 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73  n the FROM claus
0be0: 65 20 2a 2f 0a 20 20 75 38 20 6f 70 2c 20 70 33  e */.  u8 op, p3
0bf0: 2c 20 70 35 3b 20 20 20 20 20 20 20 20 2f 2a 20  , p5;        /* 
0c00: 4f 70 63 6f 64 65 2c 20 50 33 20 26 20 50 35 20  Opcode, P3 & P5 
0c10: 6f 66 20 74 68 65 20 6f 70 63 6f 64 65 20 74 68  of the opcode th
0c20: 61 74 20 65 6e 64 73 20 74 68 65 20 6c 6f 6f 70  at ends the loop
0c30: 20 2a 2f 0a 20 20 69 6e 74 20 70 31 2c 20 70 32   */.  int p1, p2
0c40: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f  ;           /* O
0c50: 70 65 72 61 6e 64 73 20 6f 66 20 74 68 65 20 6f  perands of the o
0c60: 70 63 6f 64 65 20 75 73 65 64 20 74 6f 20 65 6e  pcode used to en
0c70: 64 73 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20  ds the loop */. 
0c80: 20 75 6e 69 6f 6e 20 7b 20 20 20 20 20 20 20 20   union {        
0c90: 20 20 20 20 20 20 20 2f 2a 20 49 6e 66 6f 72 6d         /* Inform
0ca0: 61 74 69 6f 6e 20 74 68 61 74 20 64 65 70 65 6e  ation that depen
0cb0: 64 73 20 6f 6e 20 70 57 4c 6f 6f 70 2d 3e 77 73  ds on pWLoop->ws
0cc0: 46 6c 61 67 73 20 2a 2f 0a 20 20 20 20 73 74 72  Flags */.    str
0cd0: 75 63 74 20 7b 0a 20 20 20 20 20 20 69 6e 74 20  uct {.      int 
0ce0: 6e 49 6e 3b 20 20 20 20 20 20 20 20 20 20 20 20  nIn;            
0cf0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65    /* Number of e
0d00: 6e 74 72 69 65 73 20 69 6e 20 61 49 6e 4c 6f 6f  ntries in aInLoo
0d10: 70 5b 5d 20 2a 2f 0a 20 20 20 20 20 20 73 74 72  p[] */.      str
0d20: 75 63 74 20 49 6e 4c 6f 6f 70 20 7b 0a 20 20 20  uct InLoop {.   
0d30: 20 20 20 20 20 69 6e 74 20 69 43 75 72 3b 20 20       int iCur;  
0d40: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
0d50: 68 65 20 56 44 42 45 20 63 75 72 73 6f 72 20 75  he VDBE cursor u
0d60: 73 65 64 20 62 79 20 74 68 69 73 20 49 4e 20 6f  sed by this IN o
0d70: 70 65 72 61 74 6f 72 20 2a 2f 0a 20 20 20 20 20  perator */.     
0d80: 20 20 20 69 6e 74 20 61 64 64 72 49 6e 54 6f 70     int addrInTop
0d90: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f 70  ;         /* Top
0da0: 20 6f 66 20 74 68 65 20 49 4e 20 6c 6f 6f 70 20   of the IN loop 
0db0: 2a 2f 0a 20 20 20 20 20 20 20 20 69 6e 74 20 69  */.        int i
0dc0: 42 61 73 65 3b 20 20 20 20 20 20 20 20 20 20 20  Base;           
0dd0: 20 20 2f 2a 20 42 61 73 65 20 72 65 67 69 73 74    /* Base regist
0de0: 65 72 20 6f 66 20 6d 75 6c 74 69 2d 6b 65 79 20  er of multi-key 
0df0: 69 6e 64 65 78 20 72 65 63 6f 72 64 20 2a 2f 0a  index record */.
0e00: 20 20 20 20 20 20 20 20 69 6e 74 20 6e 50 72 65          int nPre
0e10: 66 69 78 3b 20 20 20 20 20 20 20 20 20 20 20 2f  fix;           /
0e20: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 72 69 6f  * Number of prio
0e30: 72 20 65 6e 74 69 72 65 73 20 69 6e 20 74 68 65  r entires in the
0e40: 20 6b 65 79 20 2a 2f 0a 20 20 20 20 20 20 20 20   key */.        
0e50: 75 38 20 65 45 6e 64 4c 6f 6f 70 4f 70 3b 20 20  u8 eEndLoopOp;  
0e60: 20 20 20 20 20 20 20 2f 2a 20 49 4e 20 4c 6f 6f         /* IN Loo
0e70: 70 20 74 65 72 6d 69 6e 61 74 6f 72 2e 20 4f 50  p terminator. OP
0e80: 5f 4e 65 78 74 20 6f 72 20 4f 50 5f 50 72 65 76  _Next or OP_Prev
0e90: 20 2a 2f 0a 20 20 20 20 20 20 7d 20 2a 61 49 6e   */.      } *aIn
0ea0: 4c 6f 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20  Loop;           
0eb0: 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61  /* Information a
0ec0: 62 6f 75 74 20 65 61 63 68 20 6e 65 73 74 65 64  bout each nested
0ed0: 20 49 4e 20 6f 70 65 72 61 74 6f 72 20 2a 2f 0a   IN operator */.
0ee0: 20 20 20 20 7d 20 69 6e 3b 20 20 20 20 20 20 20      } in;       
0ef0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65            /* Use
0f00: 64 20 77 68 65 6e 20 70 57 4c 6f 6f 70 2d 3e 77  d when pWLoop->w
0f10: 73 46 6c 61 67 73 26 57 48 45 52 45 5f 49 4e 5f  sFlags&WHERE_IN_
0f20: 41 42 4c 45 20 2a 2f 0a 20 20 20 20 49 6e 64 65  ABLE */.    Inde
0f30: 78 20 2a 70 43 6f 76 69 64 78 3b 20 20 20 20 20  x *pCovidx;     
0f40: 20 20 2f 2a 20 50 6f 73 73 69 62 6c 65 20 63 6f    /* Possible co
0f50: 76 65 72 69 6e 67 20 69 6e 64 65 78 20 66 6f 72  vering index for
0f60: 20 57 48 45 52 45 5f 4d 55 4c 54 49 5f 4f 52 20   WHERE_MULTI_OR 
0f70: 2a 2f 0a 20 20 7d 20 75 3b 0a 20 20 73 74 72 75  */.  } u;.  stru
0f80: 63 74 20 57 68 65 72 65 4c 6f 6f 70 20 2a 70 57  ct WhereLoop *pW
0f90: 4c 6f 6f 70 3b 20 20 2f 2a 20 54 68 65 20 73 65  Loop;  /* The se
0fa0: 6c 65 63 74 65 64 20 57 68 65 72 65 4c 6f 6f 70  lected WhereLoop
0fb0: 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 42 69 74   object */.  Bit
0fc0: 6d 61 73 6b 20 6e 6f 74 52 65 61 64 79 3b 20 20  mask notReady;  
0fd0: 20 20 20 20 20 20 20 20 2f 2a 20 46 52 4f 4d 20          /* FROM 
0fe0: 65 6e 74 72 69 65 73 20 6e 6f 74 20 75 73 61 62  entries not usab
0ff0: 6c 65 20 61 74 20 74 68 69 73 20 6c 65 76 65 6c  le at this level
1000: 20 2a 2f 0a 23 69 66 64 65 66 20 53 51 4c 49 54   */.#ifdef SQLIT
1010: 45 5f 45 4e 41 42 4c 45 5f 53 54 4d 54 5f 53 43  E_ENABLE_STMT_SC
1020: 41 4e 53 54 41 54 55 53 0a 20 20 69 6e 74 20 61  ANSTATUS.  int a
1030: 64 64 72 56 69 73 69 74 3b 20 20 20 20 20 20 20  ddrVisit;       
1040: 20 2f 2a 20 41 64 64 72 65 73 73 20 61 74 20 77   /* Address at w
1050: 68 69 63 68 20 72 6f 77 20 69 73 20 76 69 73 69  hich row is visi
1060: 74 65 64 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d 3b  ted */.#endif.};
1070: 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 69 6e 73  ../*.** Each ins
1080: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
1090: 6a 65 63 74 20 72 65 70 72 65 73 65 6e 74 73 20  ject represents 
10a0: 61 6e 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f 72  an algorithm for
10b0: 20 65 76 61 6c 75 61 74 69 6e 67 20 6f 6e 65 0a   evaluating one.
10c0: 2a 2a 20 74 65 72 6d 20 6f 66 20 61 20 6a 6f 69  ** term of a joi
10d0: 6e 2e 20 20 45 76 65 72 79 20 74 65 72 6d 20 6f  n.  Every term o
10e0: 66 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73  f the FROM claus
10f0: 65 20 77 69 6c 6c 20 68 61 76 65 20 61 74 20 6c  e will have at l
1100: 65 61 73 74 0a 2a 2a 20 6f 6e 65 20 63 6f 72 72  east.** one corr
1110: 65 73 70 6f 6e 64 69 6e 67 20 57 68 65 72 65 4c  esponding WhereL
1120: 6f 6f 70 20 6f 62 6a 65 63 74 20 28 75 6e 6c 65  oop object (unle
1130: 73 73 20 49 4e 44 45 58 45 44 20 42 59 20 63 6f  ss INDEXED BY co
1140: 6e 73 74 72 61 69 6e 74 73 0a 2a 2a 20 70 72 65  nstraints.** pre
1150: 76 65 6e 74 20 61 20 71 75 65 72 79 20 73 6f 6c  vent a query sol
1160: 75 74 69 6f 6e 20 2d 20 77 68 69 63 68 20 69 73  ution - which is
1170: 20 61 6e 20 65 72 72 6f 72 29 20 61 6e 64 20 6d   an error) and m
1180: 61 6e 79 20 74 65 72 6d 73 20 6f 66 20 74 68 65  any terms of the
1190: 0a 2a 2a 20 46 52 4f 4d 20 63 6c 61 75 73 65 20  .** FROM clause 
11a0: 77 69 6c 6c 20 68 61 76 65 20 6d 75 6c 74 69 70  will have multip
11b0: 6c 65 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a  le WhereLoop obj
11c0: 65 63 74 73 2c 20 65 61 63 68 20 64 65 73 63 72  ects, each descr
11d0: 69 62 69 6e 67 20 61 0a 2a 2a 20 70 6f 74 65 6e  ibing a.** poten
11e0: 74 69 61 6c 20 77 61 79 20 6f 66 20 69 6d 70 6c  tial way of impl
11f0: 65 6d 65 6e 74 69 6e 67 20 74 68 61 74 20 46 52  ementing that FR
1200: 4f 4d 2d 63 6c 61 75 73 65 20 74 65 72 6d 2c 20  OM-clause term, 
1210: 74 6f 67 65 74 68 65 72 20 77 69 74 68 0a 2a 2a  together with.**
1220: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 6e   dependencies an
1230: 64 20 63 6f 73 74 20 65 73 74 69 6d 61 74 65 73  d cost estimates
1240: 20 66 6f 72 20 75 73 69 6e 67 20 74 68 65 20 63   for using the c
1250: 68 6f 73 65 6e 20 61 6c 67 6f 72 69 74 68 6d 2e  hosen algorithm.
1260: 0a 2a 2a 0a 2a 2a 20 51 75 65 72 79 20 70 6c 61  .**.** Query pla
1270: 6e 6e 69 6e 67 20 63 6f 6e 73 69 73 74 73 20 6f  nning consists o
1280: 66 20 62 75 69 6c 64 69 6e 67 20 75 70 20 61 20  f building up a 
1290: 63 6f 6c 6c 65 63 74 69 6f 6e 20 6f 66 20 74 68  collection of th
12a0: 65 73 65 20 57 68 65 72 65 4c 6f 6f 70 0a 2a 2a  ese WhereLoop.**
12b0: 20 6f 62 6a 65 63 74 73 2c 20 74 68 65 6e 20 63   objects, then c
12c0: 6f 6d 70 75 74 69 6e 67 20 61 20 70 61 72 74 69  omputing a parti
12d0: 63 75 6c 61 72 20 73 65 71 75 65 6e 63 65 20 6f  cular sequence o
12e0: 66 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65  f WhereLoop obje
12f0: 63 74 73 2c 20 77 69 74 68 0a 2a 2a 20 6f 6e 65  cts, with.** one
1300: 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63   WhereLoop objec
1310: 74 20 70 65 72 20 46 52 4f 4d 20 63 6c 61 75 73  t per FROM claus
1320: 65 20 74 65 72 6d 2c 20 74 68 61 74 20 73 61 74  e term, that sat
1330: 69 73 66 79 20 61 6c 6c 20 64 65 70 65 6e 64 65  isfy all depende
1340: 6e 63 69 65 73 0a 2a 2a 20 61 6e 64 20 74 68 61  ncies.** and tha
1350: 74 20 6d 69 6e 69 6d 69 7a 65 20 74 68 65 20 6f  t minimize the o
1360: 76 65 72 61 6c 6c 20 63 6f 73 74 2e 0a 2a 2f 0a  verall cost..*/.
1370: 73 74 72 75 63 74 20 57 68 65 72 65 4c 6f 6f 70  struct WhereLoop
1380: 20 7b 0a 20 20 42 69 74 6d 61 73 6b 20 70 72 65   {.  Bitmask pre
1390: 72 65 71 3b 20 20 20 20 20 20 20 2f 2a 20 42 69  req;       /* Bi
13a0: 74 6d 61 73 6b 20 6f 66 20 6f 74 68 65 72 20 6c  tmask of other l
13b0: 6f 6f 70 73 20 74 68 61 74 20 6d 75 73 74 20 72  oops that must r
13c0: 75 6e 20 66 69 72 73 74 20 2a 2f 0a 20 20 42 69  un first */.  Bi
13d0: 74 6d 61 73 6b 20 6d 61 73 6b 53 65 6c 66 3b 20  tmask maskSelf; 
13e0: 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b 20 69      /* Bitmask i
13f0: 64 65 6e 74 69 66 79 69 6e 67 20 74 61 62 6c 65  dentifying table
1400: 20 69 54 61 62 20 2a 2f 0a 23 69 66 64 65 66 20   iTab */.#ifdef 
1410: 53 51 4c 49 54 45 5f 44 45 42 55 47 0a 20 20 63  SQLITE_DEBUG.  c
1420: 68 61 72 20 63 49 64 3b 20 20 20 20 20 20 20 20  har cId;        
1430: 20 20 20 20 20 2f 2a 20 53 79 6d 62 6f 6c 69 63       /* Symbolic
1440: 20 49 44 20 6f 66 20 74 68 69 73 20 6c 6f 6f 70   ID of this loop
1450: 20 66 6f 72 20 64 65 62 75 67 67 69 6e 67 20 75   for debugging u
1460: 73 65 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  se */.#endif.  u
1470: 38 20 69 54 61 62 3b 20 20 20 20 20 20 20 20 20  8 iTab;         
1480: 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e       /* Position
1490: 20 69 6e 20 46 52 4f 4d 20 63 6c 61 75 73 65 20   in FROM clause 
14a0: 6f 66 20 74 61 62 6c 65 20 66 6f 72 20 74 68 69  of table for thi
14b0: 73 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 38 20 69  s loop */.  u8 i
14c0: 53 6f 72 74 49 64 78 3b 20 20 20 20 20 20 20 20  SortIdx;        
14d0: 20 20 2f 2a 20 53 6f 72 74 69 6e 67 20 69 6e 64    /* Sorting ind
14e0: 65 78 20 6e 75 6d 62 65 72 2e 20 20 30 3d 3d 4e  ex number.  0==N
14f0: 6f 6e 65 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20  one */.  LogEst 
1500: 72 53 65 74 75 70 3b 20 20 20 20 20 20 20 20 2f  rSetup;        /
1510: 2a 20 4f 6e 65 2d 74 69 6d 65 20 73 65 74 75 70  * One-time setup
1520: 20 63 6f 73 74 20 28 65 78 3a 20 63 72 65 61 74   cost (ex: creat
1530: 65 20 74 72 61 6e 73 69 65 6e 74 20 69 6e 64 65  e transient inde
1540: 78 29 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72  x) */.  LogEst r
1550: 52 75 6e 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  Run;          /*
1560: 20 43 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e 67   Cost of running
1570: 20 65 61 63 68 20 6c 6f 6f 70 20 2a 2f 0a 20 20   each loop */.  
1580: 4c 6f 67 45 73 74 20 6e 4f 75 74 3b 20 20 20 20  LogEst nOut;    
1590: 20 20 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74        /* Estimat
15a0: 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74  ed number of out
15b0: 70 75 74 20 72 6f 77 73 20 2a 2f 0a 20 20 75 6e  put rows */.  un
15c0: 69 6f 6e 20 7b 0a 20 20 20 20 73 74 72 75 63 74  ion {.    struct
15d0: 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 20 20   {              
15e0: 20 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20   /* Information 
15f0: 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 62 74 72  for internal btr
1600: 65 65 20 74 61 62 6c 65 73 20 2a 2f 0a 20 20 20  ee tables */.   
1610: 20 20 20 75 31 36 20 6e 45 71 3b 20 20 20 20 20     u16 nEq;     
1620: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1630: 62 65 72 20 6f 66 20 65 71 75 61 6c 69 74 79 20  ber of equality 
1640: 63 6f 6e 73 74 72 61 69 6e 74 73 20 2a 2f 0a 20  constraints */. 
1650: 20 20 20 20 20 75 31 36 20 6e 42 74 6d 3b 20 20       u16 nBtm;  
1660: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53              /* S
1670: 69 7a 65 20 6f 66 20 42 54 4d 20 76 65 63 74 6f  ize of BTM vecto
1680: 72 20 2a 2f 0a 20 20 20 20 20 20 75 31 36 20 6e  r */.      u16 n
1690: 54 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20  Top;            
16a0: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 54 4f 50    /* Size of TOP
16b0: 20 76 65 63 74 6f 72 20 2a 2f 0a 20 20 20 20 20   vector */.     
16c0: 20 75 31 36 20 6e 49 64 78 43 6f 6c 3b 20 20 20   u16 nIdxCol;   
16d0: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78          /* Index
16e0: 20 63 6f 6c 75 6d 6e 20 75 73 65 64 20 66 6f 72   column used for
16f0: 20 4f 52 44 45 52 20 42 59 20 2a 2f 0a 20 20 20   ORDER BY */.   
1700: 20 20 20 49 6e 64 65 78 20 2a 70 49 6e 64 65 78     Index *pIndex
1710: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64  ;         /* Ind
1720: 65 78 20 75 73 65 64 2c 20 6f 72 20 4e 55 4c 4c  ex used, or NULL
1730: 20 2a 2f 0a 20 20 20 20 7d 20 62 74 72 65 65 3b   */.    } btree;
1740: 0a 20 20 20 20 73 74 72 75 63 74 20 7b 20 20 20  .    struct {   
1750: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
1760: 6e 66 6f 72 6d 61 74 69 6f 6e 20 66 6f 72 20 76  nformation for v
1770: 69 72 74 75 61 6c 20 74 61 62 6c 65 73 20 2a 2f  irtual tables */
1780: 0a 20 20 20 20 20 20 69 6e 74 20 69 64 78 4e 75  .      int idxNu
1790: 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  m;            /*
17a0: 20 49 6e 64 65 78 20 6e 75 6d 62 65 72 20 2a 2f   Index number */
17b0: 0a 20 20 20 20 20 20 75 38 20 6e 65 65 64 46 72  .      u8 needFr
17c0: 65 65 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ee;           /*
17d0: 20 54 72 75 65 20 69 66 20 73 71 6c 69 74 65 33   True if sqlite3
17e0: 5f 66 72 65 65 28 69 64 78 53 74 72 29 20 69 73  _free(idxStr) is
17f0: 20 6e 65 65 64 65 64 20 2a 2f 0a 20 20 20 20 20   needed */.     
1800: 20 69 38 20 69 73 4f 72 64 65 72 65 64 3b 20 20   i8 isOrdered;  
1810: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
1820: 69 66 20 73 61 74 69 73 66 69 65 73 20 4f 52 44  if satisfies ORD
1830: 45 52 20 42 59 20 2a 2f 0a 20 20 20 20 20 20 75  ER BY */.      u
1840: 31 36 20 6f 6d 69 74 4d 61 73 6b 3b 20 20 20 20  16 omitMask;    
1850: 20 20 20 20 20 20 2f 2a 20 54 65 72 6d 73 20 74        /* Terms t
1860: 68 61 74 20 6d 61 79 20 62 65 20 6f 6d 69 74 74  hat may be omitt
1870: 65 64 20 2a 2f 0a 20 20 20 20 20 20 63 68 61 72  ed */.      char
1880: 20 2a 69 64 78 53 74 72 3b 20 20 20 20 20 20 20   *idxStr;       
1890: 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 64 65 6e     /* Index iden
18a0: 74 69 66 69 65 72 20 73 74 72 69 6e 67 20 2a 2f  tifier string */
18b0: 0a 20 20 20 20 7d 20 76 74 61 62 3b 0a 20 20 7d  .    } vtab;.  }
18c0: 20 75 3b 0a 20 20 75 33 32 20 77 73 46 6c 61 67   u;.  u32 wsFlag
18d0: 73 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57  s;          /* W
18e0: 48 45 52 45 5f 2a 20 66 6c 61 67 73 20 64 65 73  HERE_* flags des
18f0: 63 72 69 62 69 6e 67 20 74 68 65 20 70 6c 61 6e  cribing the plan
1900: 20 2a 2f 0a 20 20 75 31 36 20 6e 4c 54 65 72 6d   */.  u16 nLTerm
1910: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e  ;           /* N
1920: 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73  umber of entries
1930: 20 69 6e 20 61 4c 54 65 72 6d 5b 5d 20 2a 2f 0a   in aLTerm[] */.
1940: 20 20 75 31 36 20 6e 53 6b 69 70 3b 20 20 20 20    u16 nSkip;    
1950: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
1960: 72 20 6f 66 20 4e 55 4c 4c 20 61 4c 54 65 72 6d  r of NULL aLTerm
1970: 5b 5d 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20  [] entries */.  
1980: 2f 2a 2a 2a 2a 20 77 68 65 72 65 4c 6f 6f 70 58  /**** whereLoopX
1990: 66 65 72 28 29 20 63 6f 70 69 65 73 20 66 69 65  fer() copies fie
19a0: 6c 64 73 20 61 62 6f 76 65 20 2a 2a 2a 2a 2a 2a  lds above ******
19b0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
19c0: 2a 2f 0a 23 20 64 65 66 69 6e 65 20 57 48 45 52  */.# define WHER
19d0: 45 5f 4c 4f 4f 50 5f 58 46 45 52 5f 53 5a 20 6f  E_LOOP_XFER_SZ o
19e0: 66 66 73 65 74 6f 66 28 57 68 65 72 65 4c 6f 6f  ffsetof(WhereLoo
19f0: 70 2c 6e 4c 53 6c 6f 74 29 0a 20 20 75 31 36 20  p,nLSlot).  u16 
1a00: 6e 4c 53 6c 6f 74 3b 20 20 20 20 20 20 20 20 20  nLSlot;         
1a10: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 73    /* Number of s
1a20: 6c 6f 74 73 20 61 6c 6c 6f 63 61 74 65 64 20 66  lots allocated f
1a30: 6f 72 20 61 4c 54 65 72 6d 5b 5d 20 2a 2f 0a 20  or aLTerm[] */. 
1a40: 20 57 68 65 72 65 54 65 72 6d 20 2a 2a 61 4c 54   WhereTerm **aLT
1a50: 65 72 6d 3b 20 20 20 2f 2a 20 57 68 65 72 65 54  erm;   /* WhereT
1a60: 65 72 6d 73 20 75 73 65 64 20 2a 2f 0a 20 20 57  erms used */.  W
1a70: 68 65 72 65 4c 6f 6f 70 20 2a 70 4e 65 78 74 4c  hereLoop *pNextL
1a80: 6f 6f 70 3b 20 2f 2a 20 4e 65 78 74 20 57 68 65  oop; /* Next Whe
1a90: 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 20 69 6e  reLoop object in
1aa0: 20 74 68 65 20 57 68 65 72 65 43 6c 61 75 73 65   the WhereClause
1ab0: 20 2a 2f 0a 20 20 57 68 65 72 65 54 65 72 6d 20   */.  WhereTerm 
1ac0: 2a 61 4c 54 65 72 6d 53 70 61 63 65 5b 33 5d 3b  *aLTermSpace[3];
1ad0: 20 20 2f 2a 20 49 6e 69 74 69 61 6c 20 61 4c 54    /* Initial aLT
1ae0: 65 72 6d 5b 5d 20 73 70 61 63 65 20 2a 2f 0a 7d  erm[] space */.}
1af0: 3b 0a 0a 2f 2a 20 54 68 69 73 20 6f 62 6a 65 63  ;../* This objec
1b00: 74 20 68 6f 6c 64 73 20 74 68 65 20 70 72 65 72  t holds the prer
1b10: 65 71 75 69 73 69 74 65 73 20 61 6e 64 20 74 68  equisites and th
1b20: 65 20 63 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e  e cost of runnin
1b30: 67 20 61 0a 2a 2a 20 73 75 62 71 75 65 72 79 20  g a.** subquery 
1b40: 6f 6e 20 6f 6e 65 20 6f 70 65 72 61 6e 64 20 6f  on one operand o
1b50: 66 20 61 6e 20 4f 52 20 6f 70 65 72 61 74 6f 72  f an OR operator
1b60: 20 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c   in the WHERE cl
1b70: 61 75 73 65 2e 0a 2a 2a 20 53 65 65 20 57 68 65  ause..** See Whe
1b80: 72 65 4f 72 53 65 74 20 66 6f 72 20 61 64 64 69  reOrSet for addi
1b90: 74 69 6f 6e 61 6c 20 69 6e 66 6f 72 6d 61 74 69  tional informati
1ba0: 6f 6e 20 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68  on .*/.struct Wh
1bb0: 65 72 65 4f 72 43 6f 73 74 20 7b 0a 20 20 42 69  ereOrCost {.  Bi
1bc0: 74 6d 61 73 6b 20 70 72 65 72 65 71 3b 20 20 20  tmask prereq;   
1bd0: 20 20 2f 2a 20 50 72 65 72 65 71 75 69 73 69 74    /* Prerequisit
1be0: 65 73 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72  es */.  LogEst r
1bf0: 52 75 6e 3b 20 20 20 20 20 20 20 20 2f 2a 20 43  Run;        /* C
1c00: 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e 67 20 74  ost of running t
1c10: 68 69 73 20 73 75 62 71 75 65 72 79 20 2a 2f 0a  his subquery */.
1c20: 20 20 4c 6f 67 45 73 74 20 6e 4f 75 74 3b 20 20    LogEst nOut;  
1c30: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
1c40: 6f 66 20 6f 75 74 70 75 74 73 20 66 6f 72 20 74  of outputs for t
1c50: 68 69 73 20 73 75 62 71 75 65 72 79 20 2a 2f 0a  his subquery */.
1c60: 7d 3b 0a 0a 2f 2a 20 54 68 65 20 57 68 65 72 65  };../* The Where
1c70: 4f 72 53 65 74 20 6f 62 6a 65 63 74 20 68 6f 6c  OrSet object hol
1c80: 64 73 20 61 20 73 65 74 20 6f 66 20 70 6f 73 73  ds a set of poss
1c90: 69 62 6c 65 20 57 68 65 72 65 4f 72 43 6f 73 74  ible WhereOrCost
1ca0: 73 20 74 68 61 74 0a 2a 2a 20 63 6f 72 72 65 73  s that.** corres
1cb0: 70 6f 6e 64 20 74 6f 20 74 68 65 20 73 75 62 71  pond to the subq
1cc0: 75 65 72 79 28 73 29 20 6f 66 20 4f 52 2d 63 6c  uery(s) of OR-cl
1cd0: 61 75 73 65 20 70 72 6f 63 65 73 73 69 6e 67 2e  ause processing.
1ce0: 20 20 4f 6e 6c 79 20 74 68 65 0a 2a 2a 20 62 65    Only the.** be
1cf0: 73 74 20 4e 5f 4f 52 5f 43 4f 53 54 20 65 6c 65  st N_OR_COST ele
1d00: 6d 65 6e 74 73 20 61 72 65 20 72 65 74 61 69 6e  ments are retain
1d10: 65 64 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4e  ed..*/.#define N
1d20: 5f 4f 52 5f 43 4f 53 54 20 33 0a 73 74 72 75 63  _OR_COST 3.struc
1d30: 74 20 57 68 65 72 65 4f 72 53 65 74 20 7b 0a 20  t WhereOrSet {. 
1d40: 20 75 31 36 20 6e 3b 20 20 20 20 20 20 20 20 20   u16 n;         
1d50: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1d60: 4e 75 6d 62 65 72 20 6f 66 20 76 61 6c 69 64 20  Number of valid 
1d70: 61 5b 5d 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20  a[] entries */. 
1d80: 20 57 68 65 72 65 4f 72 43 6f 73 74 20 61 5b 4e   WhereOrCost a[N
1d90: 5f 4f 52 5f 43 4f 53 54 5d 3b 20 20 20 2f 2a 20  _OR_COST];   /* 
1da0: 53 65 74 20 6f 66 20 62 65 73 74 20 63 6f 73 74  Set of best cost
1db0: 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 45  s */.};../*.** E
1dc0: 61 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20  ach instance of 
1dd0: 74 68 69 73 20 6f 62 6a 65 63 74 20 68 6f 6c 64  this object hold
1de0: 73 20 61 20 73 65 71 75 65 6e 63 65 20 6f 66 20  s a sequence of 
1df0: 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74  WhereLoop object
1e00: 73 0a 2a 2a 20 74 68 61 74 20 69 6d 70 6c 65 6d  s.** that implem
1e10: 65 6e 74 20 73 6f 6d 65 20 6f 72 20 61 6c 6c 20  ent some or all 
1e20: 6f 66 20 61 20 71 75 65 72 79 20 70 6c 61 6e 2e  of a query plan.
1e30: 0a 2a 2a 0a 2a 2a 20 54 68 69 6e 6b 20 6f 66 20  .**.** Think of 
1e40: 65 61 63 68 20 57 68 65 72 65 4c 6f 6f 70 20 6f  each WhereLoop o
1e50: 62 6a 65 63 74 20 61 73 20 61 20 6e 6f 64 65 20  bject as a node 
1e60: 69 6e 20 61 20 67 72 61 70 68 20 77 69 74 68 20  in a graph with 
1e70: 61 72 63 73 0a 2a 2a 20 73 68 6f 77 69 6e 67 20  arcs.** showing 
1e80: 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 6e 64  dependencies and
1e90: 20 63 6f 73 74 73 20 66 6f 72 20 74 72 61 76 65   costs for trave
1ea0: 6c 6c 69 6e 67 20 62 65 74 77 65 65 6e 20 6e 6f  lling between no
1eb0: 64 65 73 2e 20 20 28 54 68 61 74 20 69 73 0a 2a  des.  (That is.*
1ec0: 2a 20 6e 6f 74 20 61 20 63 6f 6d 70 6c 65 74 65  * not a complete
1ed0: 6c 79 20 61 63 63 75 72 61 74 65 20 64 65 73 63  ly accurate desc
1ee0: 72 69 70 74 69 6f 6e 20 62 65 63 61 75 73 65 20  ription because 
1ef0: 57 68 65 72 65 4c 6f 6f 70 20 63 6f 73 74 73 20  WhereLoop costs 
1f00: 61 72 65 20 61 0a 2a 2a 20 76 65 63 74 6f 72 2c  are a.** vector,
1f10: 20 6e 6f 74 20 61 20 73 63 61 6c 61 72 2c 20 61   not a scalar, a
1f20: 6e 64 20 62 65 63 61 75 73 65 20 64 65 70 65 6e  nd because depen
1f30: 64 65 6e 63 69 65 73 20 61 72 65 20 6d 61 6e 79  dencies are many
1f40: 2d 74 6f 2d 6f 6e 65 2c 20 6e 6f 74 0a 2a 2a 20  -to-one, not.** 
1f50: 6f 6e 65 2d 74 6f 2d 6f 6e 65 20 61 73 20 61 72  one-to-one as ar
1f60: 65 20 67 72 61 70 68 20 6e 6f 64 65 73 2e 20 20  e graph nodes.  
1f70: 42 75 74 20 69 74 20 69 73 20 61 20 75 73 65 66  But it is a usef
1f80: 75 6c 20 76 69 73 75 61 6c 69 7a 61 74 69 6f 6e  ul visualization
1f90: 20 61 69 64 2e 29 0a 2a 2a 20 54 68 65 6e 20 61   aid.).** Then a
1fa0: 20 57 68 65 72 65 50 61 74 68 20 6f 62 6a 65 63   WherePath objec
1fb0: 74 20 69 73 20 61 20 70 61 74 68 20 74 68 72 6f  t is a path thro
1fc0: 75 67 68 20 74 68 65 20 67 72 61 70 68 20 74 68  ugh the graph th
1fd0: 61 74 20 76 69 73 69 74 73 20 73 6f 6d 65 0a 2a  at visits some.*
1fe0: 2a 20 6f 72 20 61 6c 6c 20 6f 66 20 74 68 65 20  * or all of the 
1ff0: 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74  WhereLoop object
2000: 73 20 6f 6e 63 65 2e 0a 2a 2a 0a 2a 2a 20 54 68  s once..**.** Th
2010: 65 20 22 73 6f 6c 76 65 72 22 20 77 6f 72 6b 73  e "solver" works
2020: 20 62 79 20 63 72 65 61 74 69 6e 67 20 74 68 65   by creating the
2030: 20 4e 20 62 65 73 74 20 57 68 65 72 65 50 61 74   N best WherePat
2040: 68 20 6f 62 6a 65 63 74 73 20 6f 66 20 6c 65 6e  h objects of len
2050: 67 74 68 0a 2a 2a 20 31 2e 20 20 54 68 65 6e 20  gth.** 1.  Then 
2060: 75 73 69 6e 67 20 74 68 6f 73 65 20 61 73 20 61  using those as a
2070: 20 62 61 73 69 73 20 74 6f 20 63 6f 6d 70 75 74   basis to comput
2080: 65 20 74 68 65 20 4e 20 62 65 73 74 20 57 68 65  e the N best Whe
2090: 72 65 50 61 74 68 20 6f 62 6a 65 63 74 73 0a 2a  rePath objects.*
20a0: 2a 20 6f 66 20 6c 65 6e 67 74 68 20 32 2e 20 20  * of length 2.  
20b0: 41 6e 64 20 73 6f 20 66 6f 72 74 68 20 75 6e 74  And so forth unt
20c0: 69 6c 20 74 68 65 20 6c 65 6e 67 74 68 20 6f 66  il the length of
20d0: 20 57 68 65 72 65 50 61 74 68 73 20 65 71 75 61   WherePaths equa
20e0: 6c 73 20 74 68 65 0a 2a 2a 20 6e 75 6d 62 65 72  ls the.** number
20f0: 20 6f 66 20 6e 6f 64 65 73 20 69 6e 20 74 68 65   of nodes in the
2100: 20 46 52 4f 4d 20 63 6c 61 75 73 65 2e 20 20 54   FROM clause.  T
2110: 68 65 20 62 65 73 74 20 28 6c 6f 77 65 73 74 20  he best (lowest 
2120: 63 6f 73 74 29 20 57 68 65 72 65 50 61 74 68 0a  cost) WherePath.
2130: 2a 2a 20 61 74 20 74 68 65 20 65 6e 64 20 69 73  ** at the end is
2140: 20 74 68 65 20 63 68 6f 73 65 6e 20 71 75 65 72   the chosen quer
2150: 79 20 70 6c 61 6e 2e 0a 2a 2f 0a 73 74 72 75 63  y plan..*/.struc
2160: 74 20 57 68 65 72 65 50 61 74 68 20 7b 0a 20 20  t WherePath {.  
2170: 42 69 74 6d 61 73 6b 20 6d 61 73 6b 4c 6f 6f 70  Bitmask maskLoop
2180: 3b 20 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b  ;     /* Bitmask
2190: 20 6f 66 20 61 6c 6c 20 57 68 65 72 65 4c 6f 6f   of all WhereLoo
21a0: 70 20 6f 62 6a 65 63 74 73 20 69 6e 20 74 68 69  p objects in thi
21b0: 73 20 70 61 74 68 20 2a 2f 0a 20 20 42 69 74 6d  s path */.  Bitm
21c0: 61 73 6b 20 72 65 76 4c 6f 6f 70 3b 20 20 20 20  ask revLoop;    
21d0: 20 20 2f 2a 20 61 4c 6f 6f 70 5b 5d 73 20 74 68    /* aLoop[]s th
21e0: 61 74 20 73 68 6f 75 6c 64 20 62 65 20 72 65 76  at should be rev
21f0: 65 72 73 65 64 20 66 6f 72 20 4f 52 44 45 52 20  ersed for ORDER 
2200: 42 59 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 6e  BY */.  LogEst n
2210: 52 6f 77 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  Row;          /*
2220: 20 45 73 74 69 6d 61 74 65 64 20 6e 75 6d 62 65   Estimated numbe
2230: 72 20 6f 66 20 72 6f 77 73 20 67 65 6e 65 72 61  r of rows genera
2240: 74 65 64 20 62 79 20 74 68 69 73 20 70 61 74 68  ted by this path
2250: 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72 43 6f   */.  LogEst rCo
2260: 73 74 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54  st;         /* T
2270: 6f 74 61 6c 20 63 6f 73 74 20 6f 66 20 74 68 69  otal cost of thi
2280: 73 20 70 61 74 68 20 2a 2f 0a 20 20 4c 6f 67 45  s path */.  LogE
2290: 73 74 20 72 55 6e 73 6f 72 74 65 64 3b 20 20 20  st rUnsorted;   
22a0: 20 20 2f 2a 20 54 6f 74 61 6c 20 63 6f 73 74 20    /* Total cost 
22b0: 6f 66 20 74 68 69 73 20 70 61 74 68 20 69 67 6e  of this path ign
22c0: 6f 72 69 6e 67 20 73 6f 72 74 69 6e 67 20 63 6f  oring sorting co
22d0: 73 74 73 20 2a 2f 0a 20 20 69 38 20 69 73 4f 72  sts */.  i8 isOr
22e0: 64 65 72 65 64 3b 20 20 20 20 20 20 20 20 20 2f  dered;         /
22f0: 2a 20 4e 6f 2e 20 6f 66 20 4f 52 44 45 52 20 42  * No. of ORDER B
2300: 59 20 74 65 72 6d 73 20 73 61 74 69 73 66 69 65  Y terms satisfie
2310: 64 2e 20 2d 31 20 66 6f 72 20 75 6e 6b 6e 6f 77  d. -1 for unknow
2320: 6e 20 2a 2f 0a 20 20 57 68 65 72 65 4c 6f 6f 70  n */.  WhereLoop
2330: 20 2a 2a 61 4c 6f 6f 70 3b 20 20 20 20 2f 2a 20   **aLoop;    /* 
2340: 41 72 72 61 79 20 6f 66 20 57 68 65 72 65 4c 6f  Array of WhereLo
2350: 6f 70 20 6f 62 6a 65 63 74 73 20 69 6d 70 6c 65  op objects imple
2360: 6d 65 6e 74 69 6e 67 20 74 68 69 73 20 70 61 74  menting this pat
2370: 68 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54  h */.};../*.** T
2380: 68 65 20 71 75 65 72 79 20 67 65 6e 65 72 61 74  he query generat
2390: 6f 72 20 75 73 65 73 20 61 6e 20 61 72 72 61 79  or uses an array
23a0: 20 6f 66 20 69 6e 73 74 61 6e 63 65 73 20 6f 66   of instances of
23b0: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20   this structure 
23c0: 74 6f 0a 2a 2a 20 68 65 6c 70 20 69 74 20 61 6e  to.** help it an
23d0: 61 6c 79 7a 65 20 74 68 65 20 73 75 62 65 78 70  alyze the subexp
23e0: 72 65 73 73 69 6f 6e 73 20 6f 66 20 74 68 65 20  ressions of the 
23f0: 57 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20 45  WHERE clause.  E
2400: 61 63 68 20 57 48 45 52 45 0a 2a 2a 20 63 6c 61  ach WHERE.** cla
2410: 75 73 65 20 73 75 62 65 78 70 72 65 73 73 69 6f  use subexpressio
2420: 6e 20 69 73 20 73 65 70 61 72 61 74 65 64 20 66  n is separated f
2430: 72 6f 6d 20 74 68 65 20 6f 74 68 65 72 73 20 62  rom the others b
2440: 79 20 41 4e 44 20 6f 70 65 72 61 74 6f 72 73 2c  y AND operators,
2450: 0a 2a 2a 20 75 73 75 61 6c 6c 79 2c 20 6f 72 20  .** usually, or 
2460: 73 6f 6d 65 74 69 6d 65 73 20 73 75 62 65 78 70  sometimes subexp
2470: 72 65 73 73 69 6f 6e 73 20 73 65 70 61 72 61 74  ressions separat
2480: 65 64 20 62 79 20 4f 52 2e 0a 2a 2a 0a 2a 2a 20  ed by OR..**.** 
2490: 41 6c 6c 20 57 68 65 72 65 54 65 72 6d 73 20 61  All WhereTerms a
24a0: 72 65 20 63 6f 6c 6c 65 63 74 65 64 20 69 6e 74  re collected int
24b0: 6f 20 61 20 73 69 6e 67 6c 65 20 57 68 65 72 65  o a single Where
24c0: 43 6c 61 75 73 65 20 73 74 72 75 63 74 75 72 65  Clause structure
24d0: 2e 20 20 0a 2a 2a 20 54 68 65 20 66 6f 6c 6c 6f  .  .** The follo
24e0: 77 69 6e 67 20 69 64 65 6e 74 69 74 79 20 68 6f  wing identity ho
24f0: 6c 64 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20  lds:.**.**      
2500: 20 20 57 68 65 72 65 54 65 72 6d 2e 70 57 43 2d    WhereTerm.pWC-
2510: 3e 61 5b 57 68 65 72 65 54 65 72 6d 2e 69 64 78  >a[WhereTerm.idx
2520: 5d 20 3d 3d 20 57 68 65 72 65 54 65 72 6d 0a 2a  ] == WhereTerm.*
2530: 2a 0a 2a 2a 20 57 68 65 6e 20 61 20 74 65 72 6d  *.** When a term
2540: 20 69 73 20 6f 66 20 74 68 65 20 66 6f 72 6d 3a   is of the form:
2550: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  .**.**          
2560: 20 20 20 20 58 20 3c 6f 70 3e 20 3c 65 78 70 72      X <op> <expr
2570: 3e 0a 2a 2a 0a 2a 2a 20 77 68 65 72 65 20 58 20  >.**.** where X 
2580: 69 73 20 61 20 63 6f 6c 75 6d 6e 20 6e 61 6d 65  is a column name
2590: 20 61 6e 64 20 3c 6f 70 3e 20 69 73 20 6f 6e 65   and <op> is one
25a0: 20 6f 66 20 63 65 72 74 61 69 6e 20 6f 70 65 72   of certain oper
25b0: 61 74 6f 72 73 2c 0a 2a 2a 20 74 68 65 6e 20 57  ators,.** then W
25c0: 68 65 72 65 54 65 72 6d 2e 6c 65 66 74 43 75 72  hereTerm.leftCur
25d0: 73 6f 72 20 61 6e 64 20 57 68 65 72 65 54 65 72  sor and WhereTer
25e0: 6d 2e 75 2e 6c 65 66 74 43 6f 6c 75 6d 6e 20 72  m.u.leftColumn r
25f0: 65 63 6f 72 64 20 74 68 65 0a 2a 2a 20 63 75 72  ecord the.** cur
2600: 73 6f 72 20 6e 75 6d 62 65 72 20 61 6e 64 20 63  sor number and c
2610: 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20 66 6f 72  olumn number for
2620: 20 58 2e 20 20 57 68 65 72 65 54 65 72 6d 2e 65   X.  WhereTerm.e
2630: 4f 70 65 72 61 74 6f 72 20 72 65 63 6f 72 64 73  Operator records
2640: 0a 2a 2a 20 74 68 65 20 3c 6f 70 3e 20 75 73 69  .** the <op> usi
2650: 6e 67 20 61 20 62 69 74 6d 61 73 6b 20 65 6e 63  ng a bitmask enc
2660: 6f 64 69 6e 67 20 64 65 66 69 6e 65 64 20 62 79  oding defined by
2670: 20 57 4f 5f 78 78 78 20 62 65 6c 6f 77 2e 20 20   WO_xxx below.  
2680: 54 68 65 0a 2a 2a 20 75 73 65 20 6f 66 20 61 20  The.** use of a 
2690: 62 69 74 6d 61 73 6b 20 65 6e 63 6f 64 69 6e 67  bitmask encoding
26a0: 20 66 6f 72 20 74 68 65 20 6f 70 65 72 61 74 6f   for the operato
26b0: 72 20 61 6c 6c 6f 77 73 20 75 73 20 74 6f 20 73  r allows us to s
26c0: 65 61 72 63 68 0a 2a 2a 20 71 75 69 63 6b 6c 79  earch.** quickly
26d0: 20 66 6f 72 20 74 65 72 6d 73 20 74 68 61 74 20   for terms that 
26e0: 6d 61 74 63 68 20 61 6e 79 20 6f 66 20 73 65 76  match any of sev
26f0: 65 72 61 6c 20 64 69 66 66 65 72 65 6e 74 20 6f  eral different o
2700: 70 65 72 61 74 6f 72 73 2e 0a 2a 2a 0a 2a 2a 20  perators..**.** 
2710: 41 20 57 68 65 72 65 54 65 72 6d 20 6d 69 67 68  A WhereTerm migh
2720: 74 20 61 6c 73 6f 20 62 65 20 74 77 6f 20 6f 72  t also be two or
2730: 20 6d 6f 72 65 20 73 75 62 74 65 72 6d 73 20 63   more subterms c
2740: 6f 6e 6e 65 63 74 65 64 20 62 79 20 4f 52 3a 0a  onnected by OR:.
2750: 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20 28 74  **.**         (t
2760: 31 2e 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 29  1.X <op> <expr>)
2770: 20 4f 52 20 28 74 31 2e 59 20 3c 6f 70 3e 20 3c   OR (t1.Y <op> <
2780: 65 78 70 72 3e 29 20 4f 52 20 2e 2e 2e 2e 0a 2a  expr>) OR .....*
2790: 2a 0a 2a 2a 20 49 6e 20 74 68 69 73 20 73 65 63  *.** In this sec
27a0: 6f 6e 64 20 63 61 73 65 2c 20 77 74 46 6c 61 67  ond case, wtFlag
27b0: 20 68 61 73 20 74 68 65 20 54 45 52 4d 5f 4f 52   has the TERM_OR
27c0: 49 4e 46 4f 20 62 69 74 20 73 65 74 20 61 6e 64  INFO bit set and
27d0: 20 65 4f 70 65 72 61 74 6f 72 3d 3d 57 4f 5f 4f   eOperator==WO_O
27e0: 52 0a 2a 2a 20 61 6e 64 20 74 68 65 20 57 68 65  R.** and the Whe
27f0: 72 65 54 65 72 6d 2e 75 2e 70 4f 72 49 6e 66 6f  reTerm.u.pOrInfo
2800: 20 66 69 65 6c 64 20 70 6f 69 6e 74 73 20 74 6f   field points to
2810: 20 61 75 78 69 6c 69 61 72 79 20 69 6e 66 6f 72   auxiliary infor
2820: 6d 61 74 69 6f 6e 20 74 68 61 74 0a 2a 2a 20 69  mation that.** i
2830: 73 20 63 6f 6c 6c 65 63 74 65 64 20 61 62 6f 75  s collected abou
2840: 74 20 74 68 65 20 4f 52 20 63 6c 61 75 73 65 2e  t the OR clause.
2850: 0a 2a 2a 0a 2a 2a 20 49 66 20 61 20 74 65 72 6d  .**.** If a term
2860: 20 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c   in the WHERE cl
2870: 61 75 73 65 20 64 6f 65 73 20 6e 6f 74 20 6d 61  ause does not ma
2880: 74 63 68 20 65 69 74 68 65 72 20 6f 66 20 74 68  tch either of th
2890: 65 20 74 77 6f 20 70 72 65 76 69 6f 75 73 0a 2a  e two previous.*
28a0: 2a 20 63 61 74 65 67 6f 72 69 65 73 2c 20 74 68  * categories, th
28b0: 65 6e 20 65 4f 70 65 72 61 74 6f 72 3d 3d 30 2e  en eOperator==0.
28c0: 20 20 54 68 65 20 57 68 65 72 65 54 65 72 6d 2e    The WhereTerm.
28d0: 70 45 78 70 72 20 66 69 65 6c 64 20 69 73 20 73  pExpr field is s
28e0: 74 69 6c 6c 20 73 65 74 0a 2a 2a 20 74 6f 20 74  till set.** to t
28f0: 68 65 20 6f 72 69 67 69 6e 61 6c 20 73 75 62 65  he original sube
2900: 78 70 72 65 73 73 69 6f 6e 20 63 6f 6e 74 65 6e  xpression conten
2910: 74 20 61 6e 64 20 77 74 46 6c 61 67 73 20 69 73  t and wtFlags is
2920: 20 73 65 74 20 75 70 20 61 70 70 72 6f 70 72 69   set up appropri
2930: 61 74 65 6c 79 0a 2a 2a 20 62 75 74 20 6e 6f 20  ately.** but no 
2940: 6f 74 68 65 72 20 66 69 65 6c 64 73 20 69 6e 20  other fields in 
2950: 74 68 65 20 57 68 65 72 65 54 65 72 6d 20 6f 62  the WhereTerm ob
2960: 6a 65 63 74 20 61 72 65 20 6d 65 61 6e 69 6e 67  ject are meaning
2970: 66 75 6c 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20  ful..**.** When 
2980: 65 4f 70 65 72 61 74 6f 72 21 3d 30 2c 20 70 72  eOperator!=0, pr
2990: 65 72 65 71 52 69 67 68 74 20 61 6e 64 20 70 72  ereqRight and pr
29a0: 65 72 65 71 41 6c 6c 20 72 65 63 6f 72 64 20 73  ereqAll record s
29b0: 65 74 73 20 6f 66 20 63 75 72 73 6f 72 20 6e 75  ets of cursor nu
29c0: 6d 62 65 72 73 2c 0a 2a 2a 20 62 75 74 20 74 68  mbers,.** but th
29d0: 65 79 20 64 6f 20 73 6f 20 69 6e 64 69 72 65 63  ey do so indirec
29e0: 74 6c 79 2e 20 20 41 20 73 69 6e 67 6c 65 20 57  tly.  A single W
29f0: 68 65 72 65 4d 61 73 6b 53 65 74 20 73 74 72 75  hereMaskSet stru
2a00: 63 74 75 72 65 20 74 72 61 6e 73 6c 61 74 65 73  cture translates
2a10: 0a 2a 2a 20 63 75 72 73 6f 72 20 6e 75 6d 62 65  .** cursor numbe
2a20: 72 20 69 6e 74 6f 20 62 69 74 73 20 61 6e 64 20  r into bits and 
2a30: 74 68 65 20 74 72 61 6e 73 6c 61 74 65 64 20 62  the translated b
2a40: 69 74 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20  it is stored in 
2a50: 74 68 65 20 70 72 65 72 65 71 0a 2a 2a 20 66 69  the prereq.** fi
2a60: 65 6c 64 73 2e 20 20 54 68 65 20 74 72 61 6e 73  elds.  The trans
2a70: 6c 61 74 69 6f 6e 20 69 73 20 75 73 65 64 20 69  lation is used i
2a80: 6e 20 6f 72 64 65 72 20 74 6f 20 6d 61 78 69 6d  n order to maxim
2a90: 69 7a 65 20 74 68 65 20 6e 75 6d 62 65 72 20 6f  ize the number o
2aa0: 66 0a 2a 2a 20 62 69 74 73 20 74 68 61 74 20 77  f.** bits that w
2ab0: 69 6c 6c 20 66 69 74 20 69 6e 20 61 20 42 69 74  ill fit in a Bit
2ac0: 6d 61 73 6b 2e 20 20 54 68 65 20 56 44 42 45 20  mask.  The VDBE 
2ad0: 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 6d  cursor numbers m
2ae0: 69 67 68 74 20 62 65 0a 2a 2a 20 73 70 72 65 61  ight be.** sprea
2af0: 64 20 6f 75 74 20 6f 76 65 72 20 74 68 65 20 6e  d out over the n
2b00: 6f 6e 2d 6e 65 67 61 74 69 76 65 20 69 6e 74 65  on-negative inte
2b10: 67 65 72 73 2e 20 20 46 6f 72 20 65 78 61 6d 70  gers.  For examp
2b20: 6c 65 2c 20 74 68 65 20 63 75 72 73 6f 72 0a 2a  le, the cursor.*
2b30: 2a 20 6e 75 6d 62 65 72 73 20 6d 69 67 68 74 20  * numbers might 
2b40: 62 65 20 33 2c 20 38 2c 20 39 2c 20 31 30 2c 20  be 3, 8, 9, 10, 
2b50: 32 30 2c 20 32 33 2c 20 34 31 2c 20 61 6e 64 20  20, 23, 41, and 
2b60: 34 35 2e 20 20 54 68 65 20 57 68 65 72 65 4d 61  45.  The WhereMa
2b70: 73 6b 53 65 74 0a 2a 2a 20 74 72 61 6e 73 6c 61  skSet.** transla
2b80: 74 65 73 20 74 68 65 73 65 20 73 70 61 72 73 65  tes these sparse
2b90: 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20   cursor numbers 
2ba0: 69 6e 74 6f 20 63 6f 6e 73 65 63 75 74 69 76 65  into consecutive
2bb0: 20 69 6e 74 65 67 65 72 73 0a 2a 2a 20 62 65 67   integers.** beg
2bc0: 69 6e 6e 69 6e 67 20 77 69 74 68 20 30 20 69 6e  inning with 0 in
2bd0: 20 6f 72 64 65 72 20 74 6f 20 6d 61 6b 65 20 74   order to make t
2be0: 68 65 20 62 65 73 74 20 70 6f 73 73 69 62 6c 65  he best possible
2bf0: 20 75 73 65 20 6f 66 20 74 68 65 20 61 76 61 69   use of the avai
2c00: 6c 61 62 6c 65 0a 2a 2a 20 62 69 74 73 20 69 6e  lable.** bits in
2c10: 20 74 68 65 20 42 69 74 6d 61 73 6b 2e 20 20 53   the Bitmask.  S
2c20: 6f 2c 20 69 6e 20 74 68 65 20 65 78 61 6d 70 6c  o, in the exampl
2c30: 65 20 61 62 6f 76 65 2c 20 74 68 65 20 63 75 72  e above, the cur
2c40: 73 6f 72 20 6e 75 6d 62 65 72 73 0a 2a 2a 20 77  sor numbers.** w
2c50: 6f 75 6c 64 20 62 65 20 6d 61 70 70 65 64 20 69  ould be mapped i
2c60: 6e 74 6f 20 69 6e 74 65 67 65 72 73 20 30 20 74  nto integers 0 t
2c70: 68 72 6f 75 67 68 20 37 2e 0a 2a 2a 0a 2a 2a 20  hrough 7..**.** 
2c80: 54 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 65  The number of te
2c90: 72 6d 73 20 69 6e 20 61 20 6a 6f 69 6e 20 69 73  rms in a join is
2ca0: 20 6c 69 6d 69 74 65 64 20 62 79 20 74 68 65 20   limited by the 
2cb0: 6e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 0a 2a  number of bits.*
2cc0: 2a 20 69 6e 20 70 72 65 72 65 71 52 69 67 68 74  * in prereqRight
2cd0: 20 61 6e 64 20 70 72 65 72 65 71 41 6c 6c 2e 20   and prereqAll. 
2ce0: 20 54 68 65 20 64 65 66 61 75 6c 74 20 69 73 20   The default is 
2cf0: 36 34 20 62 69 74 73 2c 20 68 65 6e 63 65 20 53  64 bits, hence S
2d00: 51 4c 69 74 65 0a 2a 2a 20 69 73 20 6f 6e 6c 79  QLite.** is only
2d10: 20 61 62 6c 65 20 74 6f 20 70 72 6f 63 65 73 73   able to process
2d20: 20 6a 6f 69 6e 73 20 77 69 74 68 20 36 34 20 6f   joins with 64 o
2d30: 72 20 66 65 77 65 72 20 74 61 62 6c 65 73 2e 0a  r fewer tables..
2d40: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 54  */.struct WhereT
2d50: 65 72 6d 20 7b 0a 20 20 45 78 70 72 20 2a 70 45  erm {.  Expr *pE
2d60: 78 70 72 3b 20 20 20 20 20 20 20 20 20 20 20 20  xpr;            
2d70: 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 74 68  /* Pointer to th
2d80: 65 20 73 75 62 65 78 70 72 65 73 73 69 6f 6e 20  e subexpression 
2d90: 74 68 61 74 20 69 73 20 74 68 69 73 20 74 65 72  that is this ter
2da0: 6d 20 2a 2f 0a 20 20 57 68 65 72 65 43 6c 61 75  m */.  WhereClau
2db0: 73 65 20 2a 70 57 43 3b 20 20 20 20 20 20 20 2f  se *pWC;       /
2dc0: 2a 20 54 68 65 20 63 6c 61 75 73 65 20 74 68 69  * The clause thi
2dd0: 73 20 74 65 72 6d 20 69 73 20 70 61 72 74 20 6f  s term is part o
2de0: 66 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 74 72  f */.  LogEst tr
2df0: 75 74 68 50 72 6f 62 3b 20 20 20 20 20 20 20 2f  uthProb;       /
2e00: 2a 20 50 72 6f 62 61 62 69 6c 69 74 79 20 6f 66  * Probability of
2e10: 20 74 72 75 74 68 20 66 6f 72 20 74 68 69 73 20   truth for this 
2e20: 65 78 70 72 65 73 73 69 6f 6e 20 2a 2f 0a 20 20  expression */.  
2e30: 75 31 36 20 77 74 46 6c 61 67 73 3b 20 20 20 20  u16 wtFlags;    
2e40: 20 20 20 20 20 20 20 20 2f 2a 20 54 45 52 4d 5f          /* TERM_
2e50: 78 78 78 20 62 69 74 20 66 6c 61 67 73 2e 20 20  xxx bit flags.  
2e60: 53 65 65 20 62 65 6c 6f 77 20 2a 2f 0a 20 20 75  See below */.  u
2e70: 31 36 20 65 4f 70 65 72 61 74 6f 72 3b 20 20 20  16 eOperator;   
2e80: 20 20 20 20 20 20 20 2f 2a 20 41 20 57 4f 5f 78         /* A WO_x
2e90: 78 20 76 61 6c 75 65 20 64 65 73 63 72 69 62 69  x value describi
2ea0: 6e 67 20 3c 6f 70 3e 20 2a 2f 0a 20 20 75 38 20  ng <op> */.  u8 
2eb0: 6e 43 68 69 6c 64 3b 20 20 20 20 20 20 20 20 20  nChild;         
2ec0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
2ed0: 66 20 63 68 69 6c 64 72 65 6e 20 74 68 61 74 20  f children that 
2ee0: 6d 75 73 74 20 64 69 73 61 62 6c 65 20 75 73 20  must disable us 
2ef0: 2a 2f 0a 20 20 75 38 20 65 4d 61 74 63 68 4f 70  */.  u8 eMatchOp
2f00: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
2f10: 4f 70 20 66 6f 72 20 76 74 61 62 20 4d 41 54 43  Op for vtab MATC
2f20: 48 2f 4c 49 4b 45 2f 47 4c 4f 42 2f 52 45 47 45  H/LIKE/GLOB/REGE
2f30: 58 50 20 74 65 72 6d 73 20 2a 2f 0a 20 20 69 6e  XP terms */.  in
2f40: 74 20 69 50 61 72 65 6e 74 3b 20 20 20 20 20 20  t iParent;      
2f50: 20 20 20 20 20 20 2f 2a 20 44 69 73 61 62 6c 65        /* Disable
2f60: 20 70 57 43 2d 3e 61 5b 69 50 61 72 65 6e 74 5d   pWC->a[iParent]
2f70: 20 77 68 65 6e 20 74 68 69 73 20 74 65 72 6d 20   when this term 
2f80: 64 69 73 61 62 6c 65 64 20 2a 2f 0a 20 20 69 6e  disabled */.  in
2f90: 74 20 6c 65 66 74 43 75 72 73 6f 72 3b 20 20 20  t leftCursor;   
2fa0: 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 20        /* Cursor 
2fb0: 6e 75 6d 62 65 72 20 6f 66 20 58 20 69 6e 20 22  number of X in "
2fc0: 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 22 20 2a  X <op> <expr>" *
2fd0: 2f 0a 20 20 69 6e 74 20 69 46 69 65 6c 64 3b 20  /.  int iField; 
2fe0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46              /* F
2ff0: 69 65 6c 64 20 69 6e 20 28 3f 2c 3f 2c 3f 29 20  ield in (?,?,?) 
3000: 49 4e 20 28 53 45 4c 45 43 54 2e 2e 2e 29 20 76  IN (SELECT...) v
3010: 65 63 74 6f 72 20 2a 2f 0a 20 20 75 6e 69 6f 6e  ector */.  union
3020: 20 7b 0a 20 20 20 20 69 6e 74 20 6c 65 66 74 43   {.    int leftC
3030: 6f 6c 75 6d 6e 3b 20 20 20 20 20 20 20 20 20 2f  olumn;         /
3040: 2a 20 43 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20  * Column number 
3050: 6f 66 20 58 20 69 6e 20 22 58 20 3c 6f 70 3e 20  of X in "X <op> 
3060: 3c 65 78 70 72 3e 22 20 2a 2f 0a 20 20 20 20 57  <expr>" */.    W
3070: 68 65 72 65 4f 72 49 6e 66 6f 20 2a 70 4f 72 49  hereOrInfo *pOrI
3080: 6e 66 6f 3b 20 20 20 2f 2a 20 45 78 74 72 61 20  nfo;   /* Extra 
3090: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 69 66 20 28  information if (
30a0: 65 4f 70 65 72 61 74 6f 72 20 26 20 57 4f 5f 4f  eOperator & WO_O
30b0: 52 29 21 3d 30 20 2a 2f 0a 20 20 20 20 57 68 65  R)!=0 */.    Whe
30c0: 72 65 41 6e 64 49 6e 66 6f 20 2a 70 41 6e 64 49  reAndInfo *pAndI
30d0: 6e 66 6f 3b 20 2f 2a 20 45 78 74 72 61 20 69 6e  nfo; /* Extra in
30e0: 66 6f 72 6d 61 74 69 6f 6e 20 69 66 20 28 65 4f  formation if (eO
30f0: 70 65 72 61 74 6f 72 26 20 57 4f 5f 41 4e 44 29  perator& WO_AND)
3100: 21 3d 30 20 2a 2f 0a 20 20 7d 20 75 3b 0a 20 20  !=0 */.  } u;.  
3110: 42 69 74 6d 61 73 6b 20 70 72 65 72 65 71 52 69  Bitmask prereqRi
3120: 67 68 74 3b 20 20 20 20 2f 2a 20 42 69 74 6d 61  ght;    /* Bitma
3130: 73 6b 20 6f 66 20 74 61 62 6c 65 73 20 75 73 65  sk of tables use
3140: 64 20 62 79 20 70 45 78 70 72 2d 3e 70 52 69 67  d by pExpr->pRig
3150: 68 74 20 2a 2f 0a 20 20 42 69 74 6d 61 73 6b 20  ht */.  Bitmask 
3160: 70 72 65 72 65 71 41 6c 6c 3b 20 20 20 20 20 20  prereqAll;      
3170: 2f 2a 20 42 69 74 6d 61 73 6b 20 6f 66 20 74 61  /* Bitmask of ta
3180: 62 6c 65 73 20 72 65 66 65 72 65 6e 63 65 64 20  bles referenced 
3190: 62 79 20 70 45 78 70 72 20 2a 2f 0a 7d 3b 0a 0a  by pExpr */.};..
31a0: 2f 2a 0a 2a 2a 20 41 6c 6c 6f 77 65 64 20 76 61  /*.** Allowed va
31b0: 6c 75 65 73 20 6f 66 20 57 68 65 72 65 54 65 72  lues of WhereTer
31c0: 6d 2e 77 74 46 6c 61 67 73 0a 2a 2f 0a 23 64 65  m.wtFlags.*/.#de
31d0: 66 69 6e 65 20 54 45 52 4d 5f 44 59 4e 41 4d 49  fine TERM_DYNAMI
31e0: 43 20 20 20 20 30 78 30 31 20 20 20 2f 2a 20 4e  C    0x01   /* N
31f0: 65 65 64 20 74 6f 20 63 61 6c 6c 20 73 71 6c 69  eed to call sqli
3200: 74 65 33 45 78 70 72 44 65 6c 65 74 65 28 64 62  te3ExprDelete(db
3210: 2c 20 70 45 78 70 72 29 20 2a 2f 0a 23 64 65 66  , pExpr) */.#def
3220: 69 6e 65 20 54 45 52 4d 5f 56 49 52 54 55 41 4c  ine TERM_VIRTUAL
3230: 20 20 20 20 30 78 30 32 20 20 20 2f 2a 20 41 64      0x02   /* Ad
3240: 64 65 64 20 62 79 20 74 68 65 20 6f 70 74 69 6d  ded by the optim
3250: 69 7a 65 72 2e 20 20 44 6f 20 6e 6f 74 20 63 6f  izer.  Do not co
3260: 64 65 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  de */.#define TE
3270: 52 4d 5f 43 4f 44 45 44 20 20 20 20 20 20 30 78  RM_CODED      0x
3280: 30 34 20 20 20 2f 2a 20 54 68 69 73 20 74 65 72  04   /* This ter
3290: 6d 20 69 73 20 61 6c 72 65 61 64 79 20 63 6f 64  m is already cod
32a0: 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  ed */.#define TE
32b0: 52 4d 5f 43 4f 50 49 45 44 20 20 20 20 20 30 78  RM_COPIED     0x
32c0: 30 38 20 20 20 2f 2a 20 48 61 73 20 61 20 63 68  08   /* Has a ch
32d0: 69 6c 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  ild */.#define T
32e0: 45 52 4d 5f 4f 52 49 4e 46 4f 20 20 20 20 20 30  ERM_ORINFO     0
32f0: 78 31 30 20 20 20 2f 2a 20 4e 65 65 64 20 74 6f  x10   /* Need to
3300: 20 66 72 65 65 20 74 68 65 20 57 68 65 72 65 54   free the WhereT
3310: 65 72 6d 2e 75 2e 70 4f 72 49 6e 66 6f 20 6f 62  erm.u.pOrInfo ob
3320: 6a 65 63 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20  ject */.#define 
3330: 54 45 52 4d 5f 41 4e 44 49 4e 46 4f 20 20 20 20  TERM_ANDINFO    
3340: 30 78 32 30 20 20 20 2f 2a 20 4e 65 65 64 20 74  0x20   /* Need t
3350: 6f 20 66 72 65 65 20 74 68 65 20 57 68 65 72 65  o free the Where
3360: 54 65 72 6d 2e 75 2e 70 41 6e 64 49 6e 66 6f 20  Term.u.pAndInfo 
3370: 6f 62 6a 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54  obj */.#define T
3380: 45 52 4d 5f 4f 52 5f 4f 4b 20 20 20 20 20 20 30  ERM_OR_OK      0
3390: 78 34 30 20 20 20 2f 2a 20 55 73 65 64 20 64 75  x40   /* Used du
33a0: 72 69 6e 67 20 4f 52 2d 63 6c 61 75 73 65 20 70  ring OR-clause p
33b0: 72 6f 63 65 73 73 69 6e 67 20 2a 2f 0a 23 69 66  rocessing */.#if
33c0: 64 65 66 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c  def SQLITE_ENABL
33d0: 45 5f 53 54 41 54 33 5f 4f 52 5f 53 54 41 54 34  E_STAT3_OR_STAT4
33e0: 0a 23 20 20 64 65 66 69 6e 65 20 54 45 52 4d 5f  .#  define TERM_
33f0: 56 4e 55 4c 4c 20 20 20 20 30 78 38 30 20 20 20  VNULL    0x80   
3400: 2f 2a 20 4d 61 6e 75 66 61 63 74 75 72 65 64 20  /* Manufactured 
3410: 78 3e 4e 55 4c 4c 20 6f 72 20 78 3c 3d 4e 55 4c  x>NULL or x<=NUL
3420: 4c 20 74 65 72 6d 20 2a 2f 0a 23 65 6c 73 65 0a  L term */.#else.
3430: 23 20 20 64 65 66 69 6e 65 20 54 45 52 4d 5f 56  #  define TERM_V
3440: 4e 55 4c 4c 20 20 20 20 30 78 30 30 20 20 20 2f  NULL    0x00   /
3450: 2a 20 44 69 73 61 62 6c 65 64 20 69 66 20 6e 6f  * Disabled if no
3460: 74 20 75 73 69 6e 67 20 73 74 61 74 33 20 2a 2f  t using stat3 */
3470: 0a 23 65 6e 64 69 66 0a 23 64 65 66 69 6e 65 20  .#endif.#define 
3480: 54 45 52 4d 5f 4c 49 4b 45 4f 50 54 20 20 20 20  TERM_LIKEOPT    
3490: 30 78 31 30 30 20 20 2f 2a 20 56 69 72 74 75 61  0x100  /* Virtua
34a0: 6c 20 74 65 72 6d 73 20 66 72 6f 6d 20 74 68 65  l terms from the
34b0: 20 4c 49 4b 45 20 6f 70 74 69 6d 69 7a 61 74 69   LIKE optimizati
34c0: 6f 6e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  on */.#define TE
34d0: 52 4d 5f 4c 49 4b 45 43 4f 4e 44 20 20 20 30 78  RM_LIKECOND   0x
34e0: 32 30 30 20 20 2f 2a 20 43 6f 6e 64 69 74 69 6f  200  /* Conditio
34f0: 6e 61 6c 6c 79 20 74 68 69 73 20 4c 49 4b 45 20  nally this LIKE 
3500: 6f 70 65 72 61 74 6f 72 20 74 65 72 6d 20 2a 2f  operator term */
3510: 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f 4c 49  .#define TERM_LI
3520: 4b 45 20 20 20 20 20 20 20 30 78 34 30 30 20 20  KE       0x400  
3530: 2f 2a 20 54 68 65 20 6f 72 69 67 69 6e 61 6c 20  /* The original 
3540: 4c 49 4b 45 20 6f 70 65 72 61 74 6f 72 20 2a 2f  LIKE operator */
3550: 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f 49 53  .#define TERM_IS
3560: 20 20 20 20 20 20 20 20 20 30 78 38 30 30 20 20           0x800  
3570: 2f 2a 20 54 65 72 6d 2e 70 45 78 70 72 20 69 73  /* Term.pExpr is
3580: 20 61 6e 20 49 53 20 6f 70 65 72 61 74 6f 72 20   an IS operator 
3590: 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d 5f  */.#define TERM_
35a0: 56 41 52 53 45 4c 45 43 54 20 20 30 78 31 30 30  VARSELECT  0x100
35b0: 30 20 2f 2a 20 54 65 72 6d 2e 70 45 78 70 72 20  0 /* Term.pExpr 
35c0: 63 6f 6e 74 61 69 6e 73 20 61 20 63 6f 72 72 65  contains a corre
35d0: 6c 61 74 65 64 20 73 75 62 2d 71 75 65 72 79 20  lated sub-query 
35e0: 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73  */../*.** An ins
35f0: 74 61 6e 63 65 20 6f 66 20 74 68 65 20 57 68 65  tance of the Whe
3600: 72 65 53 63 61 6e 20 6f 62 6a 65 63 74 20 69 73  reScan object is
3610: 20 75 73 65 64 20 61 73 20 61 6e 20 69 74 65 72   used as an iter
3620: 61 74 6f 72 20 66 6f 72 20 6c 6f 63 61 74 69 6e  ator for locatin
3630: 67 0a 2a 2a 20 74 65 72 6d 73 20 69 6e 20 74 68  g.** terms in th
3640: 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20 74  e WHERE clause t
3650: 68 61 74 20 61 72 65 20 75 73 65 66 75 6c 20 74  hat are useful t
3660: 6f 20 74 68 65 20 71 75 65 72 79 20 70 6c 61 6e  o the query plan
3670: 6e 65 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57  ner..*/.struct W
3680: 68 65 72 65 53 63 61 6e 20 7b 0a 20 20 57 68 65  hereScan {.  Whe
3690: 72 65 43 6c 61 75 73 65 20 2a 70 4f 72 69 67 57  reClause *pOrigW
36a0: 43 3b 20 20 20 20 20 20 2f 2a 20 4f 72 69 67 69  C;      /* Origi
36b0: 6e 61 6c 2c 20 69 6e 6e 65 72 6d 6f 73 74 20 57  nal, innermost W
36c0: 68 65 72 65 43 6c 61 75 73 65 20 2a 2f 0a 20 20  hereClause */.  
36d0: 57 68 65 72 65 43 6c 61 75 73 65 20 2a 70 57 43  WhereClause *pWC
36e0: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57 68  ;          /* Wh
36f0: 65 72 65 43 6c 61 75 73 65 20 63 75 72 72 65 6e  ereClause curren
3700: 74 6c 79 20 62 65 69 6e 67 20 73 63 61 6e 6e 65  tly being scanne
3710: 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  d */.  const cha
3720: 72 20 2a 7a 43 6f 6c 6c 4e 61 6d 65 3b 20 20 20  r *zCollName;   
3730: 20 20 2f 2a 20 52 65 71 75 69 72 65 64 20 63 6f    /* Required co
3740: 6c 6c 61 74 69 6e 67 20 73 65 71 75 65 6e 63 65  llating sequence
3750: 2c 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f  , if not NULL */
3760: 0a 20 20 45 78 70 72 20 2a 70 49 64 78 45 78 70  .  Expr *pIdxExp
3770: 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  r;            /*
3780: 20 53 65 61 72 63 68 20 66 6f 72 20 74 68 69 73   Search for this
3790: 20 69 6e 64 65 78 20 65 78 70 72 65 73 73 69 6f   index expressio
37a0: 6e 20 2a 2f 0a 20 20 63 68 61 72 20 69 64 78 61  n */.  char idxa
37b0: 66 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ff;             
37c0: 20 20 2f 2a 20 4d 75 73 74 20 6d 61 74 63 68 20    /* Must match 
37d0: 74 68 69 73 20 61 66 66 69 6e 69 74 79 2c 20 69  this affinity, i
37e0: 66 20 7a 43 6f 6c 6c 4e 61 6d 65 21 3d 4e 55 4c  f zCollName!=NUL
37f0: 4c 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20  L */.  unsigned 
3800: 63 68 61 72 20 6e 45 71 75 69 76 3b 20 20 20 20  char nEquiv;    
3810: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65    /* Number of e
3820: 6e 74 72 69 65 73 20 69 6e 20 61 45 71 75 69 76  ntries in aEquiv
3830: 5b 5d 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64  [] */.  unsigned
3840: 20 63 68 61 72 20 69 45 71 75 69 76 3b 20 20 20   char iEquiv;   
3850: 20 20 20 2f 2a 20 4e 65 78 74 20 75 6e 75 73 65     /* Next unuse
3860: 64 20 73 6c 6f 74 20 69 6e 20 61 45 71 75 69 76  d slot in aEquiv
3870: 5b 5d 20 2a 2f 0a 20 20 75 33 32 20 6f 70 4d 61  [] */.  u32 opMa
3880: 73 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  sk;             
3890: 20 20 20 2f 2a 20 41 63 63 65 70 74 61 62 6c 65     /* Acceptable
38a0: 20 6f 70 65 72 61 74 6f 72 73 20 2a 2f 0a 20 20   operators */.  
38b0: 69 6e 74 20 6b 3b 20 20 20 20 20 20 20 20 20 20  int k;          
38c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 65             /* Re
38d0: 73 75 6d 65 20 73 63 61 6e 6e 69 6e 67 20 61 74  sume scanning at
38e0: 20 74 68 69 73 2d 3e 70 57 43 2d 3e 61 5b 74 68   this->pWC->a[th
38f0: 69 73 2d 3e 6b 5d 20 2a 2f 0a 20 20 69 6e 74 20  is->k] */.  int 
3900: 61 69 43 75 72 5b 31 31 5d 3b 20 20 20 20 20 20  aiCur[11];      
3910: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72         /* Cursor
3920: 73 20 69 6e 20 74 68 65 20 65 71 75 69 76 61 6c  s in the equival
3930: 65 6e 63 65 20 63 6c 61 73 73 20 2a 2f 0a 20 20  ence class */.  
3940: 69 31 36 20 61 69 43 6f 6c 75 6d 6e 5b 31 31 5d  i16 aiColumn[11]
3950: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f  ;          /* Co
3960: 72 72 65 73 70 6f 6e 64 69 6e 67 20 63 6f 6c 75  rresponding colu
3970: 6d 6e 20 6e 75 6d 62 65 72 20 69 6e 20 74 68 65  mn number in the
3980: 20 65 71 2d 63 6c 61 73 73 20 2a 2f 0a 7d 3b 0a   eq-class */.};.
3990: 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e  ./*.** An instan
39a0: 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77  ce of the follow
39b0: 69 6e 67 20 73 74 72 75 63 74 75 72 65 20 68 6f  ing structure ho
39c0: 6c 64 73 20 61 6c 6c 20 69 6e 66 6f 72 6d 61 74  lds all informat
39d0: 69 6f 6e 20 61 62 6f 75 74 20 61 0a 2a 2a 20 57  ion about a.** W
39e0: 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20 4d 6f  HERE clause.  Mo
39f0: 73 74 6c 79 20 74 68 69 73 20 69 73 20 61 20 63  stly this is a c
3a00: 6f 6e 74 61 69 6e 65 72 20 66 6f 72 20 6f 6e 65  ontainer for one
3a10: 20 6f 72 20 6d 6f 72 65 20 57 68 65 72 65 54 65   or more WhereTe
3a20: 72 6d 73 2e 0a 2a 2a 0a 2a 2a 20 45 78 70 6c 61  rms..**.** Expla
3a30: 6e 61 74 69 6f 6e 20 6f 66 20 70 4f 75 74 65 72  nation of pOuter
3a40: 3a 20 20 46 6f 72 20 61 20 57 48 45 52 45 20 63  :  For a WHERE c
3a50: 6c 61 75 73 65 20 6f 66 20 74 68 65 20 66 6f 72  lause of the for
3a60: 6d 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20  m.**.**         
3a70: 20 20 61 20 41 4e 44 20 28 28 62 20 41 4e 44 20    a AND ((b AND 
3a80: 63 29 20 4f 52 20 28 64 20 41 4e 44 20 65 29 29  c) OR (d AND e))
3a90: 20 41 4e 44 20 66 0a 2a 2a 0a 2a 2a 20 54 68 65   AND f.**.** The
3aa0: 72 65 20 61 72 65 20 73 65 70 61 72 61 74 65 20  re are separate 
3ab0: 57 68 65 72 65 43 6c 61 75 73 65 20 6f 62 6a 65  WhereClause obje
3ac0: 63 74 73 20 66 6f 72 20 74 68 65 20 77 68 6f 6c  cts for the whol
3ad0: 65 20 63 6c 61 75 73 65 20 61 6e 64 20 66 6f 72  e clause and for
3ae0: 0a 2a 2a 20 74 68 65 20 73 75 62 63 6c 61 75 73  .** the subclaus
3af0: 65 73 20 22 28 62 20 41 4e 44 20 63 29 22 20 61  es "(b AND c)" a
3b00: 6e 64 20 22 28 64 20 41 4e 44 20 65 29 22 2e 20  nd "(d AND e)". 
3b10: 20 54 68 65 20 70 4f 75 74 65 72 20 66 69 65 6c   The pOuter fiel
3b20: 64 20 6f 66 20 74 68 65 0a 2a 2a 20 73 75 62 63  d of the.** subc
3b30: 6c 61 75 73 65 73 20 70 6f 69 6e 74 73 20 74 6f  lauses points to
3b40: 20 74 68 65 20 57 68 65 72 65 43 6c 61 75 73 65   the WhereClause
3b50: 20 6f 62 6a 65 63 74 20 66 6f 72 20 74 68 65 20   object for the 
3b60: 77 68 6f 6c 65 20 63 6c 61 75 73 65 2e 0a 2a 2f  whole clause..*/
3b70: 0a 73 74 72 75 63 74 20 57 68 65 72 65 43 6c 61  .struct WhereCla
3b80: 75 73 65 20 7b 0a 20 20 57 68 65 72 65 49 6e 66  use {.  WhereInf
3b90: 6f 20 2a 70 57 49 6e 66 6f 3b 20 20 20 20 20 20  o *pWInfo;      
3ba0: 20 2f 2a 20 57 48 45 52 45 20 63 6c 61 75 73 65   /* WHERE clause
3bb0: 20 70 72 6f 63 65 73 73 69 6e 67 20 63 6f 6e 74   processing cont
3bc0: 65 78 74 20 2a 2f 0a 20 20 57 68 65 72 65 43 6c  ext */.  WhereCl
3bd0: 61 75 73 65 20 2a 70 4f 75 74 65 72 3b 20 20 20  ause *pOuter;   
3be0: 20 20 2f 2a 20 4f 75 74 65 72 20 63 6f 6e 6a 75    /* Outer conju
3bf0: 6e 63 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20 6f  nction */.  u8 o
3c00: 70 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  p;              
3c10: 20 20 20 20 20 2f 2a 20 53 70 6c 69 74 20 6f 70       /* Split op
3c20: 65 72 61 74 6f 72 2e 20 20 54 4b 5f 41 4e 44 20  erator.  TK_AND 
3c30: 6f 72 20 54 4b 5f 4f 52 20 2a 2f 0a 20 20 75 38  or TK_OR */.  u8
3c40: 20 68 61 73 4f 72 3b 20 20 20 20 20 20 20 20 20   hasOr;         
3c50: 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69         /* True i
3c60: 66 20 61 6e 79 20 61 5b 5d 2e 65 4f 70 65 72 61  f any a[].eOpera
3c70: 74 6f 72 20 69 73 20 57 4f 5f 4f 52 20 2a 2f 0a  tor is WO_OR */.
3c80: 20 20 69 6e 74 20 6e 54 65 72 6d 3b 20 20 20 20    int nTerm;    
3c90: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
3ca0: 6d 62 65 72 20 6f 66 20 74 65 72 6d 73 20 2a 2f  mber of terms */
3cb0: 0a 20 20 69 6e 74 20 6e 53 6c 6f 74 3b 20 20 20  .  int nSlot;   
3cc0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
3cd0: 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73  umber of entries
3ce0: 20 69 6e 20 61 5b 5d 20 2a 2f 0a 20 20 57 68 65   in a[] */.  Whe
3cf0: 72 65 54 65 72 6d 20 2a 61 3b 20 20 20 20 20 20  reTerm *a;      
3d00: 20 20 20 20 20 20 2f 2a 20 45 61 63 68 20 61 5b        /* Each a[
3d10: 5d 20 64 65 73 63 72 69 62 65 73 20 61 20 74 65  ] describes a te
3d20: 72 6d 20 6f 66 20 74 68 65 20 57 48 45 52 45 20  rm of the WHERE 
3d30: 63 6c 75 61 73 65 20 2a 2f 0a 23 69 66 20 64 65  cluase */.#if de
3d40: 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 53 4d 41  fined(SQLITE_SMA
3d50: 4c 4c 5f 53 54 41 43 4b 29 0a 20 20 57 68 65 72  LL_STACK).  Wher
3d60: 65 54 65 72 6d 20 61 53 74 61 74 69 63 5b 31 5d  eTerm aStatic[1]
3d70: 3b 20 20 20 20 2f 2a 20 49 6e 69 74 69 61 6c 20  ;    /* Initial 
3d80: 73 74 61 74 69 63 20 73 70 61 63 65 20 66 6f 72  static space for
3d90: 20 61 5b 5d 20 2a 2f 0a 23 65 6c 73 65 0a 20 20   a[] */.#else.  
3da0: 57 68 65 72 65 54 65 72 6d 20 61 53 74 61 74 69  WhereTerm aStati
3db0: 63 5b 38 5d 3b 20 20 20 20 2f 2a 20 49 6e 69 74  c[8];    /* Init
3dc0: 69 61 6c 20 73 74 61 74 69 63 20 73 70 61 63 65  ial static space
3dd0: 20 66 6f 72 20 61 5b 5d 20 2a 2f 0a 23 65 6e 64   for a[] */.#end
3de0: 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 57  if.};../*.** A W
3df0: 68 65 72 65 54 65 72 6d 20 77 69 74 68 20 65 4f  hereTerm with eO
3e00: 70 65 72 61 74 6f 72 3d 3d 57 4f 5f 4f 52 20 68  perator==WO_OR h
3e10: 61 73 20 69 74 73 20 75 2e 70 4f 72 49 6e 66 6f  as its u.pOrInfo
3e20: 20 70 6f 69 6e 74 65 72 20 73 65 74 20 74 6f 0a   pointer set to.
3e30: 2a 2a 20 61 20 64 79 6e 61 6d 69 63 61 6c 6c 79  ** a dynamically
3e40: 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e 73 74 61   allocated insta
3e50: 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f  nce of the follo
3e60: 77 69 6e 67 20 73 74 72 75 63 74 75 72 65 2e 0a  wing structure..
3e70: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 4f  */.struct WhereO
3e80: 72 49 6e 66 6f 20 7b 0a 20 20 57 68 65 72 65 43  rInfo {.  WhereC
3e90: 6c 61 75 73 65 20 77 63 3b 20 20 20 20 20 20 20  lause wc;       
3ea0: 20 20 20 2f 2a 20 44 65 63 6f 6d 70 6f 73 69 74     /* Decomposit
3eb0: 69 6f 6e 20 69 6e 74 6f 20 73 75 62 74 65 72 6d  ion into subterm
3ec0: 73 20 2a 2f 0a 20 20 42 69 74 6d 61 73 6b 20 69  s */.  Bitmask i
3ed0: 6e 64 65 78 61 62 6c 65 3b 20 20 20 20 20 20 20  ndexable;       
3ee0: 2f 2a 20 42 69 74 6d 61 73 6b 20 6f 66 20 61 6c  /* Bitmask of al
3ef0: 6c 20 69 6e 64 65 78 61 62 6c 65 20 74 61 62 6c  l indexable tabl
3f00: 65 73 20 69 6e 20 74 68 65 20 63 6c 61 75 73 65  es in the clause
3f10: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20   */.};../*.** A 
3f20: 57 68 65 72 65 54 65 72 6d 20 77 69 74 68 20 65  WhereTerm with e
3f30: 4f 70 65 72 61 74 6f 72 3d 3d 57 4f 5f 41 4e 44  Operator==WO_AND
3f40: 20 68 61 73 20 69 74 73 20 75 2e 70 41 6e 64 49   has its u.pAndI
3f50: 6e 66 6f 20 70 6f 69 6e 74 65 72 20 73 65 74 20  nfo pointer set 
3f60: 74 6f 0a 2a 2a 20 61 20 64 79 6e 61 6d 69 63 61  to.** a dynamica
3f70: 6c 6c 79 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e  lly allocated in
3f80: 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66 6f  stance of the fo
3f90: 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75 72  llowing structur
3fa0: 65 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68 65  e..*/.struct Whe
3fb0: 72 65 41 6e 64 49 6e 66 6f 20 7b 0a 20 20 57 68  reAndInfo {.  Wh
3fc0: 65 72 65 43 6c 61 75 73 65 20 77 63 3b 20 20 20  ereClause wc;   
3fd0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 73 75         /* The su
3fe0: 62 65 78 70 72 65 73 73 69 6f 6e 20 62 72 6f 6b  bexpression brok
3ff0: 65 6e 20 6f 75 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a  en out */.};../*
4000: 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20  .** An instance 
4010: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
4020: 20 73 74 72 75 63 74 75 72 65 20 6b 65 65 70 73   structure keeps
4030: 20 74 72 61 63 6b 20 6f 66 20 61 20 6d 61 70 70   track of a mapp
4040: 69 6e 67 0a 2a 2a 20 62 65 74 77 65 65 6e 20 56  ing.** between V
4050: 44 42 45 20 63 75 72 73 6f 72 20 6e 75 6d 62 65  DBE cursor numbe
4060: 72 73 20 61 6e 64 20 62 69 74 73 20 6f 66 20 74  rs and bits of t
4070: 68 65 20 62 69 74 6d 61 73 6b 73 20 69 6e 20 57  he bitmasks in W
4080: 68 65 72 65 54 65 72 6d 2e 0a 2a 2a 0a 2a 2a 20  hereTerm..**.** 
4090: 54 68 65 20 56 44 42 45 20 63 75 72 73 6f 72 20  The VDBE cursor 
40a0: 6e 75 6d 62 65 72 73 20 61 72 65 20 73 6d 61 6c  numbers are smal
40b0: 6c 20 69 6e 74 65 67 65 72 73 20 63 6f 6e 74 61  l integers conta
40c0: 69 6e 65 64 20 69 6e 20 0a 2a 2a 20 53 72 63 4c  ined in .** SrcL
40d0: 69 73 74 5f 69 74 65 6d 2e 69 43 75 72 73 6f 72  ist_item.iCursor
40e0: 20 61 6e 64 20 45 78 70 72 2e 69 54 61 62 6c 65   and Expr.iTable
40f0: 20 66 69 65 6c 64 73 2e 20 20 46 6f 72 20 61 6e   fields.  For an
4100: 79 20 67 69 76 65 6e 20 57 48 45 52 45 20 0a 2a  y given WHERE .*
4110: 2a 20 63 6c 61 75 73 65 2c 20 74 68 65 20 63 75  * clause, the cu
4120: 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 6d 69 67  rsor numbers mig
4130: 68 74 20 6e 6f 74 20 62 65 67 69 6e 20 77 69 74  ht not begin wit
4140: 68 20 30 20 61 6e 64 20 74 68 65 79 20 6d 69 67  h 0 and they mig
4150: 68 74 0a 2a 2a 20 63 6f 6e 74 61 69 6e 20 67 61  ht.** contain ga
4160: 70 73 20 69 6e 20 74 68 65 20 6e 75 6d 62 65 72  ps in the number
4170: 69 6e 67 20 73 65 71 75 65 6e 63 65 2e 20 20 42  ing sequence.  B
4180: 75 74 20 77 65 20 77 61 6e 74 20 74 6f 20 6d 61  ut we want to ma
4190: 6b 65 20 6d 61 78 69 6d 75 6d 0a 2a 2a 20 75 73  ke maximum.** us
41a0: 65 20 6f 66 20 74 68 65 20 62 69 74 73 20 69 6e  e of the bits in
41b0: 20 6f 75 72 20 62 69 74 6d 61 73 6b 73 2e 20 20   our bitmasks.  
41c0: 54 68 69 73 20 73 74 72 75 63 74 75 72 65 20 70  This structure p
41d0: 72 6f 76 69 64 65 73 20 61 20 6d 61 70 70 69 6e  rovides a mappin
41e0: 67 0a 2a 2a 20 66 72 6f 6d 20 74 68 65 20 73 70  g.** from the sp
41f0: 61 72 73 65 20 63 75 72 73 6f 72 20 6e 75 6d 62  arse cursor numb
4200: 65 72 73 20 69 6e 74 6f 20 63 6f 6e 73 65 63 75  ers into consecu
4210: 74 69 76 65 20 69 6e 74 65 67 65 72 73 20 62 65  tive integers be
4220: 67 69 6e 6e 69 6e 67 0a 2a 2a 20 77 69 74 68 20  ginning.** with 
4230: 30 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 57 68 65 72  0..**.** If Wher
4240: 65 4d 61 73 6b 53 65 74 2e 69 78 5b 41 5d 3d 3d  eMaskSet.ix[A]==
4250: 42 20 69 74 20 6d 65 61 6e 73 20 74 68 61 74 20  B it means that 
4260: 54 68 65 20 41 2d 74 68 20 62 69 74 20 6f 66 20  The A-th bit of 
4270: 61 20 42 69 74 6d 61 73 6b 0a 2a 2a 20 63 6f 72  a Bitmask.** cor
4280: 72 65 73 70 6f 6e 64 73 20 56 44 42 45 20 63 75  responds VDBE cu
4290: 72 73 6f 72 20 6e 75 6d 62 65 72 20 42 2e 20 20  rsor number B.  
42a0: 54 68 65 20 41 2d 74 68 20 62 69 74 20 6f 66 20  The A-th bit of 
42b0: 61 20 62 69 74 6d 61 73 6b 20 69 73 20 31 3c 3c  a bitmask is 1<<
42c0: 41 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 65 78 61  A..**.** For exa
42d0: 6d 70 6c 65 2c 20 69 66 20 74 68 65 20 57 48 45  mple, if the WHE
42e0: 52 45 20 63 6c 61 75 73 65 20 65 78 70 72 65 73  RE clause expres
42f0: 73 69 6f 6e 20 75 73 65 64 20 74 68 65 73 65 20  sion used these 
4300: 56 44 42 45 0a 2a 2a 20 63 75 72 73 6f 72 73 3a  VDBE.** cursors:
4310: 20 20 34 2c 20 35 2c 20 38 2c 20 32 39 2c 20 35    4, 5, 8, 29, 5
4320: 37 2c 20 37 33 2e 20 20 54 68 65 6e 20 74 68 65  7, 73.  Then the
4330: 20 20 57 68 65 72 65 4d 61 73 6b 53 65 74 20 73    WhereMaskSet s
4340: 74 72 75 63 74 75 72 65 0a 2a 2a 20 77 6f 75 6c  tructure.** woul
4350: 64 20 6d 61 70 20 74 68 6f 73 65 20 63 75 72 73  d map those curs
4360: 6f 72 20 6e 75 6d 62 65 72 73 20 69 6e 74 6f 20  or numbers into 
4370: 62 69 74 73 20 30 20 74 68 72 6f 75 67 68 20 35  bits 0 through 5
4380: 2e 0a 2a 2a 0a 2a 2a 20 4e 6f 74 65 20 74 68 61  ..**.** Note tha
4390: 74 20 74 68 65 20 6d 61 70 70 69 6e 67 20 69 73  t the mapping is
43a0: 20 6e 6f 74 20 6e 65 63 65 73 73 61 72 69 6c 79   not necessarily
43b0: 20 6f 72 64 65 72 65 64 2e 20 20 49 6e 20 74 68   ordered.  In th
43c0: 65 20 65 78 61 6d 70 6c 65 0a 2a 2a 20 61 62 6f  e example.** abo
43d0: 76 65 2c 20 74 68 65 20 6d 61 70 70 69 6e 67 20  ve, the mapping 
43e0: 6d 69 67 68 74 20 67 6f 20 6c 69 6b 65 20 74 68  might go like th
43f0: 69 73 3a 20 20 34 2d 3e 33 2c 20 35 2d 3e 31 2c  is:  4->3, 5->1,
4400: 20 38 2d 3e 32 2c 20 32 39 2d 3e 30 2c 0a 2a 2a   8->2, 29->0,.**
4410: 20 35 37 2d 3e 35 2c 20 37 33 2d 3e 34 2e 20 20   57->5, 73->4.  
4420: 4f 72 20 6f 6e 65 20 6f 66 20 37 31 39 20 6f 74  Or one of 719 ot
4430: 68 65 72 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 73  her combinations
4440: 20 6d 69 67 68 74 20 62 65 20 75 73 65 64 2e 20   might be used. 
4450: 49 74 0a 2a 2a 20 64 6f 65 73 20 6e 6f 74 20 72  It.** does not r
4460: 65 61 6c 6c 79 20 6d 61 74 74 65 72 2e 20 20 57  eally matter.  W
4470: 68 61 74 20 69 73 20 69 6d 70 6f 72 74 61 6e 74  hat is important
4480: 20 69 73 20 74 68 61 74 20 73 70 61 72 73 65 20   is that sparse 
4490: 63 75 72 73 6f 72 0a 2a 2a 20 6e 75 6d 62 65 72  cursor.** number
44a0: 73 20 61 6c 6c 20 67 65 74 20 6d 61 70 70 65 64  s all get mapped
44b0: 20 69 6e 74 6f 20 62 69 74 20 6e 75 6d 62 65 72   into bit number
44c0: 73 20 74 68 61 74 20 62 65 67 69 6e 20 77 69 74  s that begin wit
44d0: 68 20 30 20 61 6e 64 20 63 6f 6e 74 61 69 6e 0a  h 0 and contain.
44e0: 2a 2a 20 6e 6f 20 67 61 70 73 2e 0a 2a 2f 0a 73  ** no gaps..*/.s
44f0: 74 72 75 63 74 20 57 68 65 72 65 4d 61 73 6b 53  truct WhereMaskS
4500: 65 74 20 7b 0a 20 20 69 6e 74 20 62 56 61 72 53  et {.  int bVarS
4510: 65 6c 65 63 74 3b 20 20 20 20 20 20 20 20 20 20  elect;          
4520: 20 20 20 20 20 2f 2a 20 55 73 65 64 20 62 79 20       /* Used by 
4530: 73 71 6c 69 74 65 33 57 68 65 72 65 45 78 70 72  sqlite3WhereExpr
4540: 55 73 61 67 65 28 29 20 2a 2f 0a 20 20 69 6e 74  Usage() */.  int
4550: 20 6e 3b 20 20 20 20 20 20 20 20 20 20 20 20 20   n;             
4560: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
4570: 6d 62 65 72 20 6f 66 20 61 73 73 69 67 6e 65 64  mber of assigned
4580: 20 63 75 72 73 6f 72 20 76 61 6c 75 65 73 20 2a   cursor values *
4590: 2f 0a 20 20 69 6e 74 20 69 78 5b 42 4d 53 5d 3b  /.  int ix[BMS];
45a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
45b0: 20 20 2f 2a 20 43 75 72 73 6f 72 20 61 73 73 69    /* Cursor assi
45c0: 67 6e 65 64 20 74 6f 20 65 61 63 68 20 62 69 74  gned to each bit
45d0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 49 6e   */.};../*.** In
45e0: 69 74 69 61 6c 69 7a 65 20 61 20 57 68 65 72 65  itialize a Where
45f0: 4d 61 73 6b 53 65 74 20 6f 62 6a 65 63 74 0a 2a  MaskSet object.*
4600: 2f 0a 23 64 65 66 69 6e 65 20 69 6e 69 74 4d 61  /.#define initMa
4610: 73 6b 53 65 74 28 50 29 20 20 28 50 29 2d 3e 6e  skSet(P)  (P)->n
4620: 3d 30 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 6f  =0../*.** This o
4630: 62 6a 65 63 74 20 69 73 20 61 20 63 6f 6e 76 65  bject is a conve
4640: 6e 69 65 6e 63 65 20 77 72 61 70 70 65 72 20 68  nience wrapper h
4650: 6f 6c 64 69 6e 67 20 61 6c 6c 20 69 6e 66 6f 72  olding all infor
4660: 6d 61 74 69 6f 6e 20 6e 65 65 64 65 64 0a 2a 2a  mation needed.**
4670: 20 74 6f 20 63 6f 6e 73 74 72 75 63 74 20 57 68   to construct Wh
4680: 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 73 20  ereLoop objects 
4690: 66 6f 72 20 61 20 70 61 72 74 69 63 75 6c 61 72  for a particular
46a0: 20 71 75 65 72 79 2e 0a 2a 2f 0a 73 74 72 75 63   query..*/.struc
46b0: 74 20 57 68 65 72 65 4c 6f 6f 70 42 75 69 6c 64  t WhereLoopBuild
46c0: 65 72 20 7b 0a 20 20 57 68 65 72 65 49 6e 66 6f  er {.  WhereInfo
46d0: 20 2a 70 57 49 6e 66 6f 3b 20 20 20 20 20 20 20   *pWInfo;       
46e0: 20 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20   /* Information 
46f0: 61 62 6f 75 74 20 74 68 69 73 20 57 48 45 52 45  about this WHERE
4700: 20 2a 2f 0a 20 20 57 68 65 72 65 43 6c 61 75 73   */.  WhereClaus
4710: 65 20 2a 70 57 43 3b 20 20 20 20 20 20 20 20 20  e *pWC;         
4720: 2f 2a 20 57 48 45 52 45 20 63 6c 61 75 73 65 20  /* WHERE clause 
4730: 74 65 72 6d 73 20 2a 2f 0a 20 20 45 78 70 72 4c  terms */.  ExprL
4740: 69 73 74 20 2a 70 4f 72 64 65 72 42 79 3b 20 20  ist *pOrderBy;  
4750: 20 20 20 20 20 2f 2a 20 4f 52 44 45 52 20 42 59       /* ORDER BY
4760: 20 63 6c 61 75 73 65 20 2a 2f 0a 20 20 57 68 65   clause */.  Whe
4770: 72 65 4c 6f 6f 70 20 2a 70 4e 65 77 3b 20 20 20  reLoop *pNew;   
4780: 20 20 20 20 20 20 20 2f 2a 20 54 65 6d 70 6c 61         /* Templa
4790: 74 65 20 57 68 65 72 65 4c 6f 6f 70 20 2a 2f 0a  te WhereLoop */.
47a0: 20 20 57 68 65 72 65 4f 72 53 65 74 20 2a 70 4f    WhereOrSet *pO
47b0: 72 53 65 74 3b 20 20 20 20 20 20 20 2f 2a 20 52  rSet;       /* R
47c0: 65 63 6f 72 64 20 62 65 73 74 20 6c 6f 6f 70 73  ecord best loops
47d0: 20 68 65 72 65 2c 20 69 66 20 6e 6f 74 20 4e 55   here, if not NU
47e0: 4c 4c 20 2a 2f 0a 23 69 66 64 65 66 20 53 51 4c  LL */.#ifdef SQL
47f0: 49 54 45 5f 45 4e 41 42 4c 45 5f 53 54 41 54 33  ITE_ENABLE_STAT3
4800: 5f 4f 52 5f 53 54 41 54 34 0a 20 20 55 6e 70 61  _OR_STAT4.  Unpa
4810: 63 6b 65 64 52 65 63 6f 72 64 20 2a 70 52 65 63  ckedRecord *pRec
4820: 3b 20 20 20 20 20 2f 2a 20 50 72 6f 62 65 20 66  ;     /* Probe f
4830: 6f 72 20 73 74 61 74 34 20 28 69 66 20 72 65 71  or stat4 (if req
4840: 75 69 72 65 64 29 20 2a 2f 0a 20 20 69 6e 74 20  uired) */.  int 
4850: 6e 52 65 63 56 61 6c 69 64 3b 20 20 20 20 20 20  nRecValid;      
4860: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
4870: 6f 66 20 76 61 6c 69 64 20 66 69 65 6c 64 73 20  of valid fields 
4880: 63 75 72 72 65 6e 74 6c 79 20 69 6e 20 70 52 65  currently in pRe
4890: 63 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75 6e  c */.#endif.  un
48a0: 73 69 67 6e 65 64 20 69 6e 74 20 62 6c 64 46 6c  signed int bldFl
48b0: 61 67 73 3b 20 20 20 20 2f 2a 20 53 51 4c 49 54  ags;    /* SQLIT
48c0: 45 5f 42 4c 44 46 5f 2a 20 66 6c 61 67 73 20 2a  E_BLDF_* flags *
48d0: 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  /.  unsigned int
48e0: 20 69 50 6c 61 6e 4c 69 6d 69 74 3b 20 20 2f 2a   iPlanLimit;  /*
48f0: 20 53 65 61 72 63 68 20 6c 69 6d 69 74 65 72 20   Search limiter 
4900: 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 41 6c 6c 6f 77 65  */.};../* Allowe
4910: 64 20 76 61 6c 75 65 73 20 66 6f 72 20 57 68 65  d values for Whe
4920: 72 65 4c 6f 6f 70 42 75 69 64 65 72 2e 62 6c 64  reLoopBuider.bld
4930: 46 6c 61 67 73 20 2a 2f 0a 23 64 65 66 69 6e 65  Flags */.#define
4940: 20 53 51 4c 49 54 45 5f 42 4c 44 46 5f 49 4e 44   SQLITE_BLDF_IND
4950: 45 58 45 44 20 20 30 78 30 30 30 31 20 20 20 2f  EXED  0x0001   /
4960: 2a 20 41 6e 20 69 6e 64 65 78 20 69 73 20 75 73  * An index is us
4970: 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 51  ed */.#define SQ
4980: 4c 49 54 45 5f 42 4c 44 46 5f 55 4e 49 51 55 45  LITE_BLDF_UNIQUE
4990: 20 20 20 30 78 30 30 30 32 20 20 20 2f 2a 20 41     0x0002   /* A
49a0: 6c 6c 20 6b 65 79 73 20 6f 66 20 61 20 55 4e 49  ll keys of a UNI
49b0: 51 55 45 20 69 6e 64 65 78 20 75 73 65 64 20 2a  QUE index used *
49c0: 2f 0a 0a 2f 2a 20 54 68 65 20 57 68 65 72 65 4c  /../* The WhereL
49d0: 6f 6f 70 42 75 69 6c 64 65 72 2e 69 50 6c 61 6e  oopBuilder.iPlan
49e0: 4c 69 6d 69 74 20 69 73 20 75 73 65 64 20 74 6f  Limit is used to
49f0: 20 6c 69 6d 69 74 20 74 68 65 20 6e 75 6d 62 65   limit the numbe
4a00: 72 20 6f 66 0a 2a 2a 20 69 6e 64 65 78 2b 63 6f  r of.** index+co
4a10: 6e 73 74 72 61 69 6e 74 20 63 6f 6d 62 69 6e 61  nstraint combina
4a20: 74 69 6f 6e 73 20 74 68 65 20 71 75 65 72 79 20  tions the query 
4a30: 70 6c 61 6e 6e 65 72 20 77 69 6c 6c 20 63 6f 6e  planner will con
4a40: 73 69 64 65 72 20 66 6f 72 20 61 0a 2a 2a 20 70  sider for a.** p
4a50: 61 72 74 69 63 75 6c 61 72 20 71 75 65 72 79 2e  articular query.
4a60: 20 20 49 66 20 74 68 69 73 20 70 61 72 61 6d 65    If this parame
4a70: 74 65 72 20 69 73 20 75 6e 6c 69 6d 69 74 65 64  ter is unlimited
4a80: 2c 20 74 68 65 6e 20 63 65 72 74 61 69 6e 0a 2a  , then certain.*
4a90: 2a 20 70 61 74 68 6f 6c 6f 67 69 63 61 6c 20 71  * pathological q
4aa0: 75 65 72 69 65 73 20 63 61 6e 20 73 70 65 6e 64  ueries can spend
4ab0: 20 65 78 63 65 73 73 20 74 69 6d 65 20 69 6e 20   excess time in 
4ac0: 74 68 65 20 73 71 6c 69 74 65 33 57 68 65 72 65  the sqlite3Where
4ad0: 42 65 67 69 6e 28 29 0a 2a 2a 20 72 6f 75 74 69  Begin().** routi
4ae0: 6e 65 2e 20 20 54 68 65 20 6c 69 6d 69 74 20 69  ne.  The limit i
4af0: 73 20 68 69 67 68 20 65 6e 6f 75 67 68 20 74 68  s high enough th
4b00: 61 74 20 69 73 20 73 68 6f 75 6c 64 20 6e 6f 74  at is should not
4b10: 20 69 6d 70 61 63 74 20 72 65 61 6c 2d 77 6f 72   impact real-wor
4b20: 6c 64 0a 2a 2a 20 71 75 65 72 69 65 73 2e 0a 2a  ld.** queries..*
4b30: 2a 0a 2a 2a 20 53 51 4c 49 54 45 5f 51 55 45 52  *.** SQLITE_QUER
4b40: 59 5f 50 4c 41 4e 4e 45 52 5f 4c 49 4d 49 54 20  Y_PLANNER_LIMIT 
4b50: 69 73 20 74 68 65 20 62 61 73 65 6c 69 6e 65 20  is the baseline 
4b60: 6c 69 6d 69 74 2e 20 20 54 68 65 20 6c 69 6d 69  limit.  The limi
4b70: 74 20 69 73 0a 2a 2a 20 69 6e 63 72 65 61 73 65  t is.** increase
4b80: 64 20 62 79 20 53 51 4c 49 54 45 5f 51 55 45 52  d by SQLITE_QUER
4b90: 59 5f 50 4c 41 4e 4e 45 52 5f 4c 49 4d 49 54 5f  Y_PLANNER_LIMIT_
4ba0: 49 4e 43 52 20 62 65 66 6f 72 65 20 65 61 63 68  INCR before each
4bb0: 20 74 65 72 6d 20 6f 66 20 74 68 65 20 46 52 4f   term of the FRO
4bc0: 4d 0a 2a 2a 20 63 6c 61 75 73 65 20 69 73 20 70  M.** clause is p
4bd0: 72 6f 63 65 73 73 65 64 2c 20 73 6f 20 74 68 61  rocessed, so tha
4be0: 74 20 65 76 65 72 79 20 74 61 62 6c 65 20 69 6e  t every table in
4bf0: 20 61 20 6a 6f 69 6e 20 69 73 20 67 75 61 72 61   a join is guara
4c00: 6e 74 65 65 64 20 74 6f 20 62 65 0a 2a 2a 20 61  nteed to be.** a
4c10: 62 6c 65 20 74 6f 20 70 72 6f 70 6f 73 65 20 61  ble to propose a
4c20: 20 73 6f 6d 65 20 69 6e 64 65 78 2b 63 6f 6e 73   some index+cons
4c30: 74 72 61 69 6e 74 20 63 6f 6d 62 69 6e 61 74 69  traint combinati
4c40: 6f 6e 73 20 65 76 65 6e 20 69 66 20 74 68 65 20  ons even if the 
4c50: 69 6e 69 74 69 61 6c 0a 2a 2a 20 62 61 73 65 6c  initial.** basel
4c60: 69 6e 65 20 6c 69 6d 69 74 20 77 61 73 20 65 78  ine limit was ex
4c70: 68 61 75 73 74 65 64 20 62 79 20 70 72 69 6f 72  hausted by prior
4c80: 20 74 61 62 6c 65 73 20 6f 66 20 74 68 65 20 6a   tables of the j
4c90: 6f 69 6e 2e 0a 2a 2f 0a 23 69 66 6e 64 65 66 20  oin..*/.#ifndef 
4ca0: 53 51 4c 49 54 45 5f 51 55 45 52 59 5f 50 4c 41  SQLITE_QUERY_PLA
4cb0: 4e 4e 45 52 5f 4c 49 4d 49 54 0a 23 20 64 65 66  NNER_LIMIT.# def
4cc0: 69 6e 65 20 53 51 4c 49 54 45 5f 51 55 45 52 59  ine SQLITE_QUERY
4cd0: 5f 50 4c 41 4e 4e 45 52 5f 4c 49 4d 49 54 20 32  _PLANNER_LIMIT 2
4ce0: 30 30 30 30 0a 23 65 6e 64 69 66 0a 23 69 66 6e  0000.#endif.#ifn
4cf0: 64 65 66 20 53 51 4c 49 54 45 5f 51 55 45 52 59  def SQLITE_QUERY
4d00: 5f 50 4c 41 4e 4e 45 52 5f 4c 49 4d 49 54 5f 49  _PLANNER_LIMIT_I
4d10: 4e 43 52 0a 23 20 64 65 66 69 6e 65 20 53 51 4c  NCR.# define SQL
4d20: 49 54 45 5f 51 55 45 52 59 5f 50 4c 41 4e 4e 45  ITE_QUERY_PLANNE
4d30: 52 5f 4c 49 4d 49 54 5f 49 4e 43 52 20 31 30 30  R_LIMIT_INCR 100
4d40: 30 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20  0.#endif../*.** 
4d50: 54 68 65 20 57 48 45 52 45 20 63 6c 61 75 73 65  The WHERE clause
4d60: 20 70 72 6f 63 65 73 73 69 6e 67 20 72 6f 75 74   processing rout
4d70: 69 6e 65 20 68 61 73 20 74 77 6f 20 68 61 6c 76  ine has two halv
4d80: 65 73 2e 20 20 54 68 65 0a 2a 2a 20 66 69 72 73  es.  The.** firs
4d90: 74 20 70 61 72 74 20 64 6f 65 73 20 74 68 65 20  t part does the 
4da0: 73 74 61 72 74 20 6f 66 20 74 68 65 20 57 48 45  start of the WHE
4db0: 52 45 20 6c 6f 6f 70 20 61 6e 64 20 74 68 65 20  RE loop and the 
4dc0: 73 65 63 6f 6e 64 0a 2a 2a 20 68 61 6c 66 20 64  second.** half d
4dd0: 6f 65 73 20 74 68 65 20 74 61 69 6c 20 6f 66 20  oes the tail of 
4de0: 74 68 65 20 57 48 45 52 45 20 6c 6f 6f 70 2e 20  the WHERE loop. 
4df0: 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 0a   An instance of.
4e00: 2a 2a 20 74 68 69 73 20 73 74 72 75 63 74 75 72  ** this structur
4e10: 65 20 69 73 20 72 65 74 75 72 6e 65 64 20 62 79  e is returned by
4e20: 20 74 68 65 20 66 69 72 73 74 20 68 61 6c 66 20   the first half 
4e30: 61 6e 64 20 70 61 73 73 65 64 0a 2a 2a 20 69 6e  and passed.** in
4e40: 74 6f 20 74 68 65 20 73 65 63 6f 6e 64 20 68 61  to the second ha
4e50: 6c 66 20 74 6f 20 67 69 76 65 20 73 6f 6d 65 20  lf to give some 
4e60: 63 6f 6e 74 69 6e 75 69 74 79 2e 0a 2a 2a 0a 2a  continuity..**.*
4e70: 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66  * An instance of
4e80: 20 74 68 69 73 20 6f 62 6a 65 63 74 20 68 6f 6c   this object hol
4e90: 64 73 20 74 68 65 20 63 6f 6d 70 6c 65 74 65 20  ds the complete 
4ea0: 73 74 61 74 65 20 6f 66 20 74 68 65 20 71 75 65  state of the que
4eb0: 72 79 0a 2a 2a 20 70 6c 61 6e 6e 65 72 2e 0a 2a  ry.** planner..*
4ec0: 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 49 6e  /.struct WhereIn
4ed0: 66 6f 20 7b 0a 20 20 50 61 72 73 65 20 2a 70 50  fo {.  Parse *pP
4ee0: 61 72 73 65 3b 20 20 20 20 20 20 20 20 20 20 20  arse;           
4ef0: 20 2f 2a 20 50 61 72 73 69 6e 67 20 61 6e 64 20   /* Parsing and 
4f00: 63 6f 64 65 20 67 65 6e 65 72 61 74 69 6e 67 20  code generating 
4f10: 63 6f 6e 74 65 78 74 20 2a 2f 0a 20 20 53 72 63  context */.  Src
4f20: 4c 69 73 74 20 2a 70 54 61 62 4c 69 73 74 3b 20  List *pTabList; 
4f30: 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f         /* List o
4f40: 66 20 74 61 62 6c 65 73 20 69 6e 20 74 68 65 20  f tables in the 
4f50: 6a 6f 69 6e 20 2a 2f 0a 20 20 45 78 70 72 4c 69  join */.  ExprLi
4f60: 73 74 20 2a 70 4f 72 64 65 72 42 79 3b 20 20 20  st *pOrderBy;   
4f70: 20 20 20 20 2f 2a 20 54 68 65 20 4f 52 44 45 52      /* The ORDER
4f80: 20 42 59 20 63 6c 61 75 73 65 20 6f 72 20 4e 55   BY clause or NU
4f90: 4c 4c 20 2a 2f 0a 20 20 45 78 70 72 4c 69 73 74  LL */.  ExprList
4fa0: 20 2a 70 52 65 73 75 6c 74 53 65 74 3b 20 20 20   *pResultSet;   
4fb0: 20 20 2f 2a 20 52 65 73 75 6c 74 20 73 65 74 20    /* Result set 
4fc0: 6f 66 20 74 68 65 20 71 75 65 72 79 20 2a 2f 0a  of the query */.
4fd0: 20 20 45 78 70 72 20 2a 70 57 68 65 72 65 3b 20    Expr *pWhere; 
4fe0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
4ff0: 68 65 20 63 6f 6d 70 6c 65 74 65 20 57 48 45 52  he complete WHER
5000: 45 20 63 6c 61 75 73 65 20 2a 2f 0a 20 20 4c 6f  E clause */.  Lo
5010: 67 45 73 74 20 69 4c 69 6d 69 74 3b 20 20 20 20  gEst iLimit;    
5020: 20 20 20 20 20 20 20 20 2f 2a 20 4c 49 4d 49 54          /* LIMIT
5030: 20 69 66 20 77 63 74 72 6c 46 6c 61 67 73 20 68   if wctrlFlags h
5040: 61 73 20 57 48 45 52 45 5f 55 53 45 5f 4c 49 4d  as WHERE_USE_LIM
5050: 49 54 20 2a 2f 0a 20 20 69 6e 74 20 61 69 43 75  IT */.  int aiCu
5060: 72 4f 6e 65 50 61 73 73 5b 32 5d 3b 20 20 20 20  rOnePass[2];    
5070: 20 20 2f 2a 20 4f 50 5f 4f 70 65 6e 57 72 69 74    /* OP_OpenWrit
5080: 65 20 63 75 72 73 6f 72 73 20 66 6f 72 20 74 68  e cursors for th
5090: 65 20 4f 4e 45 50 41 53 53 20 6f 70 74 20 2a 2f  e ONEPASS opt */
50a0: 0a 20 20 69 6e 74 20 69 43 6f 6e 74 69 6e 75 65  .  int iContinue
50b0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
50c0: 4a 75 6d 70 20 68 65 72 65 20 74 6f 20 63 6f 6e  Jump here to con
50d0: 74 69 6e 75 65 20 77 69 74 68 20 6e 65 78 74 20  tinue with next 
50e0: 72 65 63 6f 72 64 20 2a 2f 0a 20 20 69 6e 74 20  record */.  int 
50f0: 69 42 72 65 61 6b 3b 20 20 20 20 20 20 20 20 20  iBreak;         
5100: 20 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65        /* Jump he
5110: 72 65 20 74 6f 20 62 72 65 61 6b 20 6f 75 74 20  re to break out 
5120: 6f 66 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20  of the loop */. 
5130: 20 69 6e 74 20 73 61 76 65 64 4e 51 75 65 72 79   int savedNQuery
5140: 4c 6f 6f 70 3b 20 20 20 20 20 20 2f 2a 20 70 50  Loop;      /* pP
5150: 61 72 73 65 2d 3e 6e 51 75 65 72 79 4c 6f 6f 70  arse->nQueryLoop
5160: 20 6f 75 74 73 69 64 65 20 74 68 65 20 57 48 45   outside the WHE
5170: 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 31 36  RE loop */.  u16
5180: 20 77 63 74 72 6c 46 6c 61 67 73 3b 20 20 20 20   wctrlFlags;    
5190: 20 20 20 20 20 20 20 2f 2a 20 46 6c 61 67 73 20         /* Flags 
51a0: 6f 72 69 67 69 6e 61 6c 6c 79 20 70 61 73 73 65  originally passe
51b0: 64 20 74 6f 20 73 71 6c 69 74 65 33 57 68 65 72  d to sqlite3Wher
51c0: 65 42 65 67 69 6e 28 29 20 2a 2f 0a 20 20 75 38  eBegin() */.  u8
51d0: 20 6e 4c 65 76 65 6c 3b 20 20 20 20 20 20 20 20   nLevel;        
51e0: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
51f0: 72 20 6f 66 20 6e 65 73 74 65 64 20 6c 6f 6f 70  r of nested loop
5200: 20 2a 2f 0a 20 20 69 38 20 6e 4f 42 53 61 74 3b   */.  i8 nOBSat;
5210: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5220: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 4f 52 44  /* Number of ORD
5230: 45 52 20 42 59 20 74 65 72 6d 73 20 73 61 74 69  ER BY terms sati
5240: 73 66 69 65 64 20 62 79 20 69 6e 64 69 63 65 73  sfied by indices
5250: 20 2a 2f 0a 20 20 75 38 20 73 6f 72 74 65 64 3b   */.  u8 sorted;
5260: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5270: 2f 2a 20 54 72 75 65 20 69 66 20 72 65 61 6c 6c  /* True if reall
5280: 79 20 73 6f 72 74 65 64 20 28 6e 6f 74 20 6a 75  y sorted (not ju
5290: 73 74 20 67 72 6f 75 70 65 64 29 20 2a 2f 0a 20  st grouped) */. 
52a0: 20 75 38 20 65 4f 6e 65 50 61 73 73 3b 20 20 20   u8 eOnePass;   
52b0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 4e             /* ON
52c0: 45 50 41 53 53 5f 4f 46 46 2c 20 6f 72 20 5f 53  EPASS_OFF, or _S
52d0: 49 4e 47 4c 45 2c 20 6f 72 20 5f 4d 55 4c 54 49  INGLE, or _MULTI
52e0: 20 2a 2f 0a 20 20 75 38 20 75 6e 74 65 73 74 65   */.  u8 unteste
52f0: 64 54 65 72 6d 73 3b 20 20 20 20 20 20 20 20 20  dTerms;         
5300: 2f 2a 20 4e 6f 74 20 61 6c 6c 20 57 48 45 52 45  /* Not all WHERE
5310: 20 74 65 72 6d 73 20 72 65 73 6f 6c 76 65 64 20   terms resolved 
5320: 62 79 20 6f 75 74 65 72 20 6c 6f 6f 70 20 2a 2f  by outer loop */
5330: 0a 20 20 75 38 20 65 44 69 73 74 69 6e 63 74 3b  .  u8 eDistinct;
5340: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5350: 4f 6e 65 20 6f 66 20 74 68 65 20 57 48 45 52 45  One of the WHERE
5360: 5f 44 49 53 54 49 4e 43 54 5f 2a 20 76 61 6c 75  _DISTINCT_* valu
5370: 65 73 20 2a 2f 0a 20 20 75 38 20 62 4f 72 64 65  es */.  u8 bOrde
5380: 72 65 64 49 6e 6e 65 72 4c 6f 6f 70 3b 20 20 20  redInnerLoop;   
5390: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 6f 6e 6c    /* True if onl
53a0: 79 20 74 68 65 20 69 6e 6e 65 72 2d 6d 6f 73 74  y the inner-most
53b0: 20 6c 6f 6f 70 20 69 73 20 6f 72 64 65 72 65 64   loop is ordered
53c0: 20 2a 2f 0a 20 20 69 6e 74 20 69 54 6f 70 3b 20   */.  int iTop; 
53d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
53e0: 2f 2a 20 54 68 65 20 76 65 72 79 20 62 65 67 69  /* The very begi
53f0: 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 57 48 45  nning of the WHE
5400: 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20 20 57 68 65  RE loop */.  Whe
5410: 72 65 4c 6f 6f 70 20 2a 70 4c 6f 6f 70 73 3b 20  reLoop *pLoops; 
5420: 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f         /* List o
5430: 66 20 61 6c 6c 20 57 68 65 72 65 4c 6f 6f 70 20  f all WhereLoop 
5440: 6f 62 6a 65 63 74 73 20 2a 2f 0a 20 20 42 69 74  objects */.  Bit
5450: 6d 61 73 6b 20 72 65 76 4d 61 73 6b 3b 20 20 20  mask revMask;   
5460: 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 6f         /* Mask o
5470: 66 20 4f 52 44 45 52 20 42 59 20 74 65 72 6d 73  f ORDER BY terms
5480: 20 74 68 61 74 20 6e 65 65 64 20 72 65 76 65 72   that need rever
5490: 73 69 6e 67 20 2a 2f 0a 20 20 4c 6f 67 45 73 74  sing */.  LogEst
54a0: 20 6e 52 6f 77 4f 75 74 3b 20 20 20 20 20 20 20   nRowOut;       
54b0: 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74 65 64      /* Estimated
54c0: 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74 70 75   number of outpu
54d0: 74 20 72 6f 77 73 20 2a 2f 0a 20 20 57 68 65 72  t rows */.  Wher
54e0: 65 43 6c 61 75 73 65 20 73 57 43 3b 20 20 20 20  eClause sWC;    
54f0: 20 20 20 20 20 20 2f 2a 20 44 65 63 6f 6d 70 6f        /* Decompo
5500: 73 69 74 69 6f 6e 20 6f 66 20 74 68 65 20 57 48  sition of the WH
5510: 45 52 45 20 63 6c 61 75 73 65 20 2a 2f 0a 20 20  ERE clause */.  
5520: 57 68 65 72 65 4d 61 73 6b 53 65 74 20 73 4d 61  WhereMaskSet sMa
5530: 73 6b 53 65 74 3b 20 20 20 20 2f 2a 20 4d 61 70  skSet;    /* Map
5540: 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20   cursor numbers 
5550: 74 6f 20 62 69 74 6d 61 73 6b 73 20 2a 2f 0a 20  to bitmasks */. 
5560: 20 57 68 65 72 65 4c 65 76 65 6c 20 61 5b 31 5d   WhereLevel a[1]
5570: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e  ;          /* In
5580: 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20  formation about 
5590: 65 61 63 68 20 6e 65 73 74 20 6c 6f 6f 70 20 69  each nest loop i
55a0: 6e 20 57 48 45 52 45 20 2a 2f 0a 7d 3b 0a 0a 2f  n WHERE */.};../
55b0: 2a 0a 2a 2a 20 50 72 69 76 61 74 65 20 69 6e 74  *.** Private int
55c0: 65 72 66 61 63 65 73 20 2d 20 63 61 6c 6c 61 62  erfaces - callab
55d0: 6c 65 20 6f 6e 6c 79 20 62 79 20 6f 74 68 65 72  le only by other
55e0: 20 77 68 65 72 65 2e 63 20 72 6f 75 74 69 6e 65   where.c routine
55f0: 73 2e 0a 2a 2a 0a 2a 2a 20 77 68 65 72 65 2e 63  s..**.** where.c
5600: 3a 0a 2a 2f 0a 42 69 74 6d 61 73 6b 20 73 71 6c  :.*/.Bitmask sql
5610: 69 74 65 33 57 68 65 72 65 47 65 74 4d 61 73 6b  ite3WhereGetMask
5620: 28 57 68 65 72 65 4d 61 73 6b 53 65 74 2a 2c 69  (WhereMaskSet*,i
5630: 6e 74 29 3b 0a 23 69 66 64 65 66 20 57 48 45 52  nt);.#ifdef WHER
5640: 45 54 52 41 43 45 5f 45 4e 41 42 4c 45 44 0a 76  ETRACE_ENABLED.v
5650: 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65 72 65  oid sqlite3Where
5660: 43 6c 61 75 73 65 50 72 69 6e 74 28 57 68 65 72  ClausePrint(Wher
5670: 65 43 6c 61 75 73 65 20 2a 70 57 43 29 3b 0a 23  eClause *pWC);.#
5680: 65 6e 64 69 66 0a 57 68 65 72 65 54 65 72 6d 20  endif.WhereTerm 
5690: 2a 73 71 6c 69 74 65 33 57 68 65 72 65 46 69 6e  *sqlite3WhereFin
56a0: 64 54 65 72 6d 28 0a 20 20 57 68 65 72 65 43 6c  dTerm(.  WhereCl
56b0: 61 75 73 65 20 2a 70 57 43 2c 20 20 20 20 20 2f  ause *pWC,     /
56c0: 2a 20 54 68 65 20 57 48 45 52 45 20 63 6c 61 75  * The WHERE clau
56d0: 73 65 20 74 6f 20 62 65 20 73 65 61 72 63 68 65  se to be searche
56e0: 64 20 2a 2f 0a 20 20 69 6e 74 20 69 43 75 72 2c  d */.  int iCur,
56f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5700: 43 75 72 73 6f 72 20 6e 75 6d 62 65 72 20 6f 66  Cursor number of
5710: 20 4c 48 53 20 2a 2f 0a 20 20 69 6e 74 20 69 43   LHS */.  int iC
5720: 6f 6c 75 6d 6e 2c 20 20 20 20 20 20 20 20 20 20  olumn,          
5730: 2f 2a 20 43 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72  /* Column number
5740: 20 6f 66 20 4c 48 53 20 2a 2f 0a 20 20 42 69 74   of LHS */.  Bit
5750: 6d 61 73 6b 20 6e 6f 74 52 65 61 64 79 2c 20 20  mask notReady,  
5760: 20 20 20 2f 2a 20 52 48 53 20 6d 75 73 74 20 6e     /* RHS must n
5770: 6f 74 20 6f 76 65 72 6c 61 70 20 77 69 74 68 20  ot overlap with 
5780: 74 68 69 73 20 6d 61 73 6b 20 2a 2f 0a 20 20 75  this mask */.  u
5790: 33 32 20 6f 70 2c 20 20 20 20 20 20 20 20 20 20  32 op,          
57a0: 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 6f 66 20       /* Mask of 
57b0: 57 4f 5f 78 78 20 76 61 6c 75 65 73 20 64 65 73  WO_xx values des
57c0: 63 72 69 62 69 6e 67 20 6f 70 65 72 61 74 6f 72  cribing operator
57d0: 20 2a 2f 0a 20 20 49 6e 64 65 78 20 2a 70 49 64   */.  Index *pId
57e0: 78 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d  x           /* M
57f0: 75 73 74 20 62 65 20 63 6f 6d 70 61 74 69 62 6c  ust be compatibl
5800: 65 20 77 69 74 68 20 74 68 69 73 20 69 6e 64 65  e with this inde
5810: 78 2c 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a  x, if not NULL *
5820: 2f 0a 29 3b 0a 0a 2f 2a 20 77 68 65 72 65 63 6f  /.);../* whereco
5830: 64 65 2e 63 3a 20 2a 2f 0a 23 69 66 6e 64 65 66  de.c: */.#ifndef
5840: 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 45 58 50   SQLITE_OMIT_EXP
5850: 4c 41 49 4e 0a 69 6e 74 20 73 71 6c 69 74 65 33  LAIN.int sqlite3
5860: 57 68 65 72 65 45 78 70 6c 61 69 6e 4f 6e 65 53  WhereExplainOneS
5870: 63 61 6e 28 0a 20 20 50 61 72 73 65 20 2a 70 50  can(.  Parse *pP
5880: 61 72 73 65 2c 20 20 20 20 20 20 20 20 20 20 20  arse,           
5890: 20 20 20 20 20 20 20 2f 2a 20 50 61 72 73 65 20         /* Parse 
58a0: 63 6f 6e 74 65 78 74 20 2a 2f 0a 20 20 53 72 63  context */.  Src
58b0: 4c 69 73 74 20 2a 70 54 61 62 4c 69 73 74 2c 20  List *pTabList, 
58c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
58d0: 54 61 62 6c 65 20 6c 69 73 74 20 74 68 69 73 20  Table list this 
58e0: 6c 6f 6f 70 20 72 65 66 65 72 73 20 74 6f 20 2a  loop refers to *
58f0: 2f 0a 20 20 57 68 65 72 65 4c 65 76 65 6c 20 2a  /.  WhereLevel *
5900: 70 4c 65 76 65 6c 2c 20 20 20 20 20 20 20 20 20  pLevel,         
5910: 20 20 20 20 2f 2a 20 53 63 61 6e 20 74 6f 20 77      /* Scan to w
5920: 72 69 74 65 20 4f 50 5f 45 78 70 6c 61 69 6e 20  rite OP_Explain 
5930: 6f 70 63 6f 64 65 20 66 6f 72 20 2a 2f 0a 20 20  opcode for */.  
5940: 75 31 36 20 77 63 74 72 6c 46 6c 61 67 73 20 20  u16 wctrlFlags  
5950: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5960: 2f 2a 20 46 6c 61 67 73 20 70 61 73 73 65 64 20  /* Flags passed 
5970: 74 6f 20 73 71 6c 69 74 65 33 57 68 65 72 65 42  to sqlite3WhereB
5980: 65 67 69 6e 28 29 20 2a 2f 0a 29 3b 0a 23 65 6c  egin() */.);.#el
5990: 73 65 0a 23 20 64 65 66 69 6e 65 20 73 71 6c 69  se.# define sqli
59a0: 74 65 33 57 68 65 72 65 45 78 70 6c 61 69 6e 4f  te3WhereExplainO
59b0: 6e 65 53 63 61 6e 28 75 2c 76 2c 77 2c 78 29 20  neScan(u,v,w,x) 
59c0: 30 0a 23 65 6e 64 69 66 20 2f 2a 20 53 51 4c 49  0.#endif /* SQLI
59d0: 54 45 5f 4f 4d 49 54 5f 45 58 50 4c 41 49 4e 20  TE_OMIT_EXPLAIN 
59e0: 2a 2f 0a 23 69 66 64 65 66 20 53 51 4c 49 54 45  */.#ifdef SQLITE
59f0: 5f 45 4e 41 42 4c 45 5f 53 54 4d 54 5f 53 43 41  _ENABLE_STMT_SCA
5a00: 4e 53 54 41 54 55 53 0a 76 6f 69 64 20 73 71 6c  NSTATUS.void sql
5a10: 69 74 65 33 57 68 65 72 65 41 64 64 53 63 61 6e  ite3WhereAddScan
5a20: 53 74 61 74 75 73 28 0a 20 20 56 64 62 65 20 2a  Status(.  Vdbe *
5a30: 76 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  v,              
5a40: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 56 64 62            /* Vdb
5a50: 65 20 74 6f 20 61 64 64 20 73 63 61 6e 73 74 61  e to add scansta
5a60: 74 75 73 20 65 6e 74 72 79 20 74 6f 20 2a 2f 0a  tus entry to */.
5a70: 20 20 53 72 63 4c 69 73 74 20 2a 70 53 72 63 6c    SrcList *pSrcl
5a80: 69 73 74 2c 20 20 20 20 20 20 20 20 20 20 20 20  ist,            
5a90: 20 20 2f 2a 20 46 52 4f 4d 20 63 6c 61 75 73 65    /* FROM clause
5aa0: 20 70 4c 76 6c 20 72 65 61 64 73 20 64 61 74 61   pLvl reads data
5ab0: 20 66 72 6f 6d 20 2a 2f 0a 20 20 57 68 65 72 65   from */.  Where
5ac0: 4c 65 76 65 6c 20 2a 70 4c 76 6c 2c 20 20 20 20  Level *pLvl,    
5ad0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 65             /* Le
5ae0: 76 65 6c 20 74 6f 20 61 64 64 20 73 63 61 6e 73  vel to add scans
5af0: 74 61 74 75 73 28 29 20 65 6e 74 72 79 20 66 6f  tatus() entry fo
5b00: 72 20 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72 45  r */.  int addrE
5b10: 78 70 6c 61 69 6e 20 20 20 20 20 20 20 20 20 20  xplain          
5b20: 20 20 20 20 20 20 20 2f 2a 20 41 64 64 72 65 73         /* Addres
5b30: 73 20 6f 66 20 4f 50 5f 45 78 70 6c 61 69 6e 20  s of OP_Explain 
5b40: 28 6f 72 20 30 29 20 2a 2f 0a 29 3b 0a 23 65 6c  (or 0) */.);.#el
5b50: 73 65 0a 23 20 64 65 66 69 6e 65 20 73 71 6c 69  se.# define sqli
5b60: 74 65 33 57 68 65 72 65 41 64 64 53 63 61 6e 53  te3WhereAddScanS
5b70: 74 61 74 75 73 28 61 2c 20 62 2c 20 63 2c 20 64  tatus(a, b, c, d
5b80: 29 20 28 28 76 6f 69 64 29 64 29 0a 23 65 6e 64  ) ((void)d).#end
5b90: 69 66 0a 42 69 74 6d 61 73 6b 20 73 71 6c 69 74  if.Bitmask sqlit
5ba0: 65 33 57 68 65 72 65 43 6f 64 65 4f 6e 65 4c 6f  e3WhereCodeOneLo
5bb0: 6f 70 53 74 61 72 74 28 0a 20 20 50 61 72 73 65  opStart(.  Parse
5bc0: 20 2a 70 50 61 72 73 65 2c 20 20 20 20 20 20 20   *pParse,       
5bd0: 2f 2a 20 50 61 72 73 69 6e 67 20 63 6f 6e 74 65  /* Parsing conte
5be0: 78 74 20 2a 2f 0a 20 20 56 64 62 65 20 2a 76 2c  xt */.  Vdbe *v,
5bf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5c00: 50 72 65 70 61 72 65 64 20 73 74 61 74 65 6d 65  Prepared stateme
5c10: 6e 74 20 75 6e 64 65 72 20 63 6f 6e 73 74 72 75  nt under constru
5c20: 63 74 69 6f 6e 20 2a 2f 0a 20 20 57 68 65 72 65  ction */.  Where
5c30: 49 6e 66 6f 20 2a 70 57 49 6e 66 6f 2c 20 20 20  Info *pWInfo,   
5c40: 2f 2a 20 43 6f 6d 70 6c 65 74 65 20 69 6e 66 6f  /* Complete info
5c50: 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 74 68  rmation about th
5c60: 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20 2a  e WHERE clause *
5c70: 2f 0a 20 20 69 6e 74 20 69 4c 65 76 65 6c 2c 20  /.  int iLevel, 
5c80: 20 20 20 20 20 20 20 20 20 2f 2a 20 57 68 69 63           /* Whic
5c90: 68 20 6c 65 76 65 6c 20 6f 66 20 70 57 49 6e 66  h level of pWInf
5ca0: 6f 2d 3e 61 5b 5d 20 73 68 6f 75 6c 64 20 62 65  o->a[] should be
5cb0: 20 63 6f 64 65 64 20 2a 2f 0a 20 20 57 68 65 72   coded */.  Wher
5cc0: 65 4c 65 76 65 6c 20 2a 70 4c 65 76 65 6c 2c 20  eLevel *pLevel, 
5cd0: 20 2f 2a 20 54 68 65 20 63 75 72 72 65 6e 74 20   /* The current 
5ce0: 6c 65 76 65 6c 20 70 6f 69 6e 74 65 72 20 2a 2f  level pointer */
5cf0: 0a 20 20 42 69 74 6d 61 73 6b 20 6e 6f 74 52 65  .  Bitmask notRe
5d00: 61 64 79 20 20 20 20 20 2f 2a 20 57 68 69 63 68  ady     /* Which
5d10: 20 74 61 62 6c 65 73 20 61 72 65 20 63 75 72 72   tables are curr
5d20: 65 6e 74 6c 79 20 61 76 61 69 6c 61 62 6c 65 20  ently available 
5d30: 2a 2f 0a 29 3b 0a 0a 2f 2a 20 77 68 65 72 65 65  */.);../* wheree
5d40: 78 70 72 2e 63 3a 20 2a 2f 0a 76 6f 69 64 20 73  xpr.c: */.void s
5d50: 71 6c 69 74 65 33 57 68 65 72 65 43 6c 61 75 73  qlite3WhereClaus
5d60: 65 49 6e 69 74 28 57 68 65 72 65 43 6c 61 75 73  eInit(WhereClaus
5d70: 65 2a 2c 57 68 65 72 65 49 6e 66 6f 2a 29 3b 0a  e*,WhereInfo*);.
5d80: 76 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65 72  void sqlite3Wher
5d90: 65 43 6c 61 75 73 65 43 6c 65 61 72 28 57 68 65  eClauseClear(Whe
5da0: 72 65 43 6c 61 75 73 65 2a 29 3b 0a 76 6f 69 64  reClause*);.void
5db0: 20 73 71 6c 69 74 65 33 57 68 65 72 65 53 70 6c   sqlite3WhereSpl
5dc0: 69 74 28 57 68 65 72 65 43 6c 61 75 73 65 2a 2c  it(WhereClause*,
5dd0: 45 78 70 72 2a 2c 75 38 29 3b 0a 42 69 74 6d 61  Expr*,u8);.Bitma
5de0: 73 6b 20 73 71 6c 69 74 65 33 57 68 65 72 65 45  sk sqlite3WhereE
5df0: 78 70 72 55 73 61 67 65 28 57 68 65 72 65 4d 61  xprUsage(WhereMa
5e00: 73 6b 53 65 74 2a 2c 20 45 78 70 72 2a 29 3b 0a  skSet*, Expr*);.
5e10: 42 69 74 6d 61 73 6b 20 73 71 6c 69 74 65 33 57  Bitmask sqlite3W
5e20: 68 65 72 65 45 78 70 72 55 73 61 67 65 4e 4e 28  hereExprUsageNN(
5e30: 57 68 65 72 65 4d 61 73 6b 53 65 74 2a 2c 20 45  WhereMaskSet*, E
5e40: 78 70 72 2a 29 3b 0a 42 69 74 6d 61 73 6b 20 73  xpr*);.Bitmask s
5e50: 71 6c 69 74 65 33 57 68 65 72 65 45 78 70 72 4c  qlite3WhereExprL
5e60: 69 73 74 55 73 61 67 65 28 57 68 65 72 65 4d 61  istUsage(WhereMa
5e70: 73 6b 53 65 74 2a 2c 20 45 78 70 72 4c 69 73 74  skSet*, ExprList
5e80: 2a 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  *);.void sqlite3
5e90: 57 68 65 72 65 45 78 70 72 41 6e 61 6c 79 7a 65  WhereExprAnalyze
5ea0: 28 53 72 63 4c 69 73 74 2a 2c 20 57 68 65 72 65  (SrcList*, Where
5eb0: 43 6c 61 75 73 65 2a 29 3b 0a 76 6f 69 64 20 73  Clause*);.void s
5ec0: 71 6c 69 74 65 33 57 68 65 72 65 54 61 62 46 75  qlite3WhereTabFu
5ed0: 6e 63 41 72 67 73 28 50 61 72 73 65 2a 2c 20 73  ncArgs(Parse*, s
5ee0: 74 72 75 63 74 20 53 72 63 4c 69 73 74 5f 69 74  truct SrcList_it
5ef0: 65 6d 2a 2c 20 57 68 65 72 65 43 6c 61 75 73 65  em*, WhereClause
5f00: 2a 29 3b 0a 0a 0a 0a 0a 0a 2f 2a 0a 2a 2a 20 42  *);....../*.** B
5f10: 69 74 6d 61 73 6b 73 20 66 6f 72 20 74 68 65 20  itmasks for the 
5f20: 6f 70 65 72 61 74 6f 72 73 20 6f 6e 20 57 68 65  operators on Whe
5f30: 72 65 54 65 72 6d 20 6f 62 6a 65 63 74 73 2e 20  reTerm objects. 
5f40: 20 54 68 65 73 65 20 61 72 65 20 61 6c 6c 0a 2a   These are all.*
5f50: 2a 20 6f 70 65 72 61 74 6f 72 73 20 74 68 61 74  * operators that
5f60: 20 61 72 65 20 6f 66 20 69 6e 74 65 72 65 73 74   are of interest
5f70: 20 74 6f 20 74 68 65 20 71 75 65 72 79 20 70 6c   to the query pl
5f80: 61 6e 6e 65 72 2e 20 20 41 6e 0a 2a 2a 20 4f 52  anner.  An.** OR
5f90: 2d 65 64 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20  -ed combination 
5fa0: 6f 66 20 74 68 65 73 65 20 76 61 6c 75 65 73 20  of these values 
5fb0: 63 61 6e 20 62 65 20 75 73 65 64 20 77 68 65 6e  can be used when
5fc0: 20 73 65 61 72 63 68 69 6e 67 20 66 6f 72 0a 2a   searching for.*
5fd0: 2a 20 70 61 72 74 69 63 75 6c 61 72 20 57 68 65  * particular Whe
5fe0: 72 65 54 65 72 6d 73 20 77 69 74 68 69 6e 20 61  reTerms within a
5ff0: 20 57 68 65 72 65 43 6c 61 75 73 65 2e 0a 2a 2a   WhereClause..**
6000: 0a 2a 2a 20 56 61 6c 75 65 20 63 6f 6e 73 74 72  .** Value constr
6010: 61 69 6e 74 73 3a 0a 2a 2a 20 20 20 20 20 57 4f  aints:.**     WO
6020: 5f 45 51 20 20 20 20 3d 3d 20 53 51 4c 49 54 45  _EQ    == SQLITE
6030: 5f 49 4e 44 45 58 5f 43 4f 4e 53 54 52 41 49 4e  _INDEX_CONSTRAIN
6040: 54 5f 45 51 0a 2a 2a 20 20 20 20 20 57 4f 5f 4c  T_EQ.**     WO_L
6050: 54 20 20 20 20 3d 3d 20 53 51 4c 49 54 45 5f 49  T    == SQLITE_I
6060: 4e 44 45 58 5f 43 4f 4e 53 54 52 41 49 4e 54 5f  NDEX_CONSTRAINT_
6070: 4c 54 0a 2a 2a 20 20 20 20 20 57 4f 5f 4c 45 20  LT.**     WO_LE 
6080: 20 20 20 3d 3d 20 53 51 4c 49 54 45 5f 49 4e 44     == SQLITE_IND
6090: 45 58 5f 43 4f 4e 53 54 52 41 49 4e 54 5f 4c 45  EX_CONSTRAINT_LE
60a0: 0a 2a 2a 20 20 20 20 20 57 4f 5f 47 54 20 20 20  .**     WO_GT   
60b0: 20 3d 3d 20 53 51 4c 49 54 45 5f 49 4e 44 45 58   == SQLITE_INDEX
60c0: 5f 43 4f 4e 53 54 52 41 49 4e 54 5f 47 54 0a 2a  _CONSTRAINT_GT.*
60d0: 2a 20 20 20 20 20 57 4f 5f 47 45 20 20 20 20 3d  *     WO_GE    =
60e0: 3d 20 53 51 4c 49 54 45 5f 49 4e 44 45 58 5f 43  = SQLITE_INDEX_C
60f0: 4f 4e 53 54 52 41 49 4e 54 5f 47 45 0a 2a 2f 0a  ONSTRAINT_GE.*/.
6100: 23 64 65 66 69 6e 65 20 57 4f 5f 49 4e 20 20 20  #define WO_IN   
6110: 20 20 30 78 30 30 30 31 0a 23 64 65 66 69 6e 65    0x0001.#define
6120: 20 57 4f 5f 45 51 20 20 20 20 20 30 78 30 30 30   WO_EQ     0x000
6130: 32 0a 23 64 65 66 69 6e 65 20 57 4f 5f 4c 54 20  2.#define WO_LT 
6140: 20 20 20 20 28 57 4f 5f 45 51 3c 3c 28 54 4b 5f      (WO_EQ<<(TK_
6150: 4c 54 2d 54 4b 5f 45 51 29 29 0a 23 64 65 66 69  LT-TK_EQ)).#defi
6160: 6e 65 20 57 4f 5f 4c 45 20 20 20 20 20 28 57 4f  ne WO_LE     (WO
6170: 5f 45 51 3c 3c 28 54 4b 5f 4c 45 2d 54 4b 5f 45  _EQ<<(TK_LE-TK_E
6180: 51 29 29 0a 23 64 65 66 69 6e 65 20 57 4f 5f 47  Q)).#define WO_G
6190: 54 20 20 20 20 20 28 57 4f 5f 45 51 3c 3c 28 54  T     (WO_EQ<<(T
61a0: 4b 5f 47 54 2d 54 4b 5f 45 51 29 29 0a 23 64 65  K_GT-TK_EQ)).#de
61b0: 66 69 6e 65 20 57 4f 5f 47 45 20 20 20 20 20 28  fine WO_GE     (
61c0: 57 4f 5f 45 51 3c 3c 28 54 4b 5f 47 45 2d 54 4b  WO_EQ<<(TK_GE-TK
61d0: 5f 45 51 29 29 0a 23 64 65 66 69 6e 65 20 57 4f  _EQ)).#define WO
61e0: 5f 41 55 58 20 20 20 20 30 78 30 30 34 30 20 20  _AUX    0x0040  
61f0: 20 20 20 20 20 2f 2a 20 4f 70 20 75 73 65 66 75       /* Op usefu
6200: 6c 20 74 6f 20 76 69 72 74 75 61 6c 20 74 61 62  l to virtual tab
6210: 6c 65 73 20 6f 6e 6c 79 20 2a 2f 0a 23 64 65 66  les only */.#def
6220: 69 6e 65 20 57 4f 5f 49 53 20 20 20 20 20 30 78  ine WO_IS     0x
6230: 30 30 38 30 0a 23 64 65 66 69 6e 65 20 57 4f 5f  0080.#define WO_
6240: 49 53 4e 55 4c 4c 20 30 78 30 31 30 30 0a 23 64  ISNULL 0x0100.#d
6250: 65 66 69 6e 65 20 57 4f 5f 4f 52 20 20 20 20 20  efine WO_OR     
6260: 30 78 30 32 30 30 20 20 20 20 20 20 20 2f 2a 20  0x0200       /* 
6270: 54 77 6f 20 6f 72 20 6d 6f 72 65 20 4f 52 2d 63  Two or more OR-c
6280: 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20 2a  onnected terms *
6290: 2f 0a 23 64 65 66 69 6e 65 20 57 4f 5f 41 4e 44  /.#define WO_AND
62a0: 20 20 20 20 30 78 30 34 30 30 20 20 20 20 20 20      0x0400      
62b0: 20 2f 2a 20 54 77 6f 20 6f 72 20 6d 6f 72 65 20   /* Two or more 
62c0: 41 4e 44 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65  AND-connected te
62d0: 72 6d 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  rms */.#define W
62e0: 4f 5f 45 51 55 49 56 20 20 30 78 30 38 30 30 20  O_EQUIV  0x0800 
62f0: 20 20 20 20 20 20 2f 2a 20 4f 66 20 74 68 65 20        /* Of the 
6300: 66 6f 72 6d 20 41 3d 3d 42 2c 20 62 6f 74 68 20  form A==B, both 
6310: 63 6f 6c 75 6d 6e 73 20 2a 2f 0a 23 64 65 66 69  columns */.#defi
6320: 6e 65 20 57 4f 5f 4e 4f 4f 50 20 20 20 30 78 31  ne WO_NOOP   0x1
6330: 30 30 30 20 20 20 20 20 20 20 2f 2a 20 54 68 69  000       /* Thi
6340: 73 20 74 65 72 6d 20 64 6f 65 73 20 6e 6f 74 20  s term does not 
6350: 72 65 73 74 72 69 63 74 20 73 65 61 72 63 68 20  restrict search 
6360: 73 70 61 63 65 20 2a 2f 0a 0a 23 64 65 66 69 6e  space */..#defin
6370: 65 20 57 4f 5f 41 4c 4c 20 20 20 20 30 78 31 66  e WO_ALL    0x1f
6380: 66 66 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b  ff       /* Mask
6390: 20 6f 66 20 61 6c 6c 20 70 6f 73 73 69 62 6c 65   of all possible
63a0: 20 57 4f 5f 2a 20 76 61 6c 75 65 73 20 2a 2f 0a   WO_* values */.
63b0: 23 64 65 66 69 6e 65 20 57 4f 5f 53 49 4e 47 4c  #define WO_SINGL
63c0: 45 20 30 78 30 31 66 66 20 20 20 20 20 20 20 2f  E 0x01ff       /
63d0: 2a 20 4d 61 73 6b 20 6f 66 20 61 6c 6c 20 6e 6f  * Mask of all no
63e0: 6e 2d 63 6f 6d 70 6f 75 6e 64 20 57 4f 5f 2a 20  n-compound WO_* 
63f0: 76 61 6c 75 65 73 20 2a 2f 0a 0a 2f 2a 0a 2a 2a  values */../*.**
6400: 20 54 68 65 73 65 20 61 72 65 20 64 65 66 69 6e   These are defin
6410: 69 74 69 6f 6e 73 20 6f 66 20 62 69 74 73 20 69  itions of bits i
6420: 6e 20 74 68 65 20 57 68 65 72 65 4c 6f 6f 70 2e  n the WhereLoop.
6430: 77 73 46 6c 61 67 73 20 66 69 65 6c 64 2e 0a 2a  wsFlags field..*
6440: 2a 20 54 68 65 20 70 61 72 74 69 63 75 6c 61 72  * The particular
6450: 20 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f 66 20   combination of 
6460: 62 69 74 73 20 69 6e 20 65 61 63 68 20 57 68 65  bits in each Whe
6470: 72 65 4c 6f 6f 70 20 68 65 6c 70 20 74 6f 0a 2a  reLoop help to.*
6480: 2a 20 64 65 74 65 72 6d 69 6e 65 20 74 68 65 20  * determine the 
6490: 61 6c 67 6f 72 69 74 68 6d 20 74 68 61 74 20 57  algorithm that W
64a0: 68 65 72 65 4c 6f 6f 70 20 72 65 70 72 65 73 65  hereLoop represe
64b0: 6e 74 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  nts..*/.#define 
64c0: 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 45 51 20  WHERE_COLUMN_EQ 
64d0: 20 20 20 30 78 30 30 30 30 30 30 30 31 20 20 2f     0x00000001  /
64e0: 2a 20 78 3d 45 58 50 52 20 2a 2f 0a 23 64 65 66  * x=EXPR */.#def
64f0: 69 6e 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e  ine WHERE_COLUMN
6500: 5f 52 41 4e 47 45 20 30 78 30 30 30 30 30 30 30  _RANGE 0x0000000
6510: 32 20 20 2f 2a 20 78 3c 45 58 50 52 20 61 6e 64  2  /* x<EXPR and
6520: 2f 6f 72 20 78 3e 45 58 50 52 20 2a 2f 0a 23 64  /or x>EXPR */.#d
6530: 65 66 69 6e 65 20 57 48 45 52 45 5f 43 4f 4c 55  efine WHERE_COLU
6540: 4d 4e 5f 49 4e 20 20 20 20 30 78 30 30 30 30 30  MN_IN    0x00000
6550: 30 30 34 20 20 2f 2a 20 78 20 49 4e 20 28 2e 2e  004  /* x IN (..
6560: 2e 29 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  .) */.#define WH
6570: 45 52 45 5f 43 4f 4c 55 4d 4e 5f 4e 55 4c 4c 20  ERE_COLUMN_NULL 
6580: 20 30 78 30 30 30 30 30 30 30 38 20 20 2f 2a 20   0x00000008  /* 
6590: 78 20 49 53 20 4e 55 4c 4c 20 2a 2f 0a 23 64 65  x IS NULL */.#de
65a0: 66 69 6e 65 20 57 48 45 52 45 5f 43 4f 4e 53 54  fine WHERE_CONST
65b0: 52 41 49 4e 54 20 20 20 30 78 30 30 30 30 30 30  RAINT   0x000000
65c0: 30 66 20 20 2f 2a 20 41 6e 79 20 6f 66 20 74 68  0f  /* Any of th
65d0: 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 78  e WHERE_COLUMN_x
65e0: 78 78 20 76 61 6c 75 65 73 20 2a 2f 0a 23 64 65  xx values */.#de
65f0: 66 69 6e 65 20 57 48 45 52 45 5f 54 4f 50 5f 4c  fine WHERE_TOP_L
6600: 49 4d 49 54 20 20 20 20 30 78 30 30 30 30 30 30  IMIT    0x000000
6610: 31 30 20 20 2f 2a 20 78 3c 45 58 50 52 20 6f 72  10  /* x<EXPR or
6620: 20 78 3c 3d 45 58 50 52 20 63 6f 6e 73 74 72 61   x<=EXPR constra
6630: 69 6e 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  int */.#define W
6640: 48 45 52 45 5f 42 54 4d 5f 4c 49 4d 49 54 20 20  HERE_BTM_LIMIT  
6650: 20 20 30 78 30 30 30 30 30 30 32 30 20 20 2f 2a    0x00000020  /*
6660: 20 78 3e 45 58 50 52 20 6f 72 20 78 3e 3d 45 58   x>EXPR or x>=EX
6670: 50 52 20 63 6f 6e 73 74 72 61 69 6e 74 20 2a 2f  PR constraint */
6680: 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f 42  .#define WHERE_B
6690: 4f 54 48 5f 4c 49 4d 49 54 20 20 20 30 78 30 30  OTH_LIMIT   0x00
66a0: 30 30 30 30 33 30 20 20 2f 2a 20 42 6f 74 68 20  000030  /* Both 
66b0: 78 3e 45 58 50 52 20 61 6e 64 20 78 3c 45 58 50  x>EXPR and x<EXP
66c0: 52 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45  R */.#define WHE
66d0: 52 45 5f 49 44 58 5f 4f 4e 4c 59 20 20 20 20 20  RE_IDX_ONLY     
66e0: 30 78 30 30 30 30 30 30 34 30 20 20 2f 2a 20 55  0x00000040  /* U
66f0: 73 65 20 69 6e 64 65 78 20 6f 6e 6c 79 20 2d 20  se index only - 
6700: 6f 6d 69 74 20 74 61 62 6c 65 20 2a 2f 0a 23 64  omit table */.#d
6710: 65 66 69 6e 65 20 57 48 45 52 45 5f 49 50 4b 20  efine WHERE_IPK 
6720: 20 20 20 20 20 20 20 20 20 30 78 30 30 30 30 30           0x00000
6730: 31 30 30 20 20 2f 2a 20 78 20 69 73 20 74 68 65  100  /* x is the
6740: 20 49 4e 54 45 47 45 52 20 50 52 49 4d 41 52 59   INTEGER PRIMARY
6750: 20 4b 45 59 20 2a 2f 0a 23 64 65 66 69 6e 65 20   KEY */.#define 
6760: 57 48 45 52 45 5f 49 4e 44 45 58 45 44 20 20 20  WHERE_INDEXED   
6770: 20 20 20 30 78 30 30 30 30 30 32 30 30 20 20 2f     0x00000200  /
6780: 2a 20 57 68 65 72 65 4c 6f 6f 70 2e 75 2e 62 74  * WhereLoop.u.bt
6790: 72 65 65 2e 70 49 6e 64 65 78 20 69 73 20 76 61  ree.pIndex is va
67a0: 6c 69 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  lid */.#define W
67b0: 48 45 52 45 5f 56 49 52 54 55 41 4c 54 41 42 4c  HERE_VIRTUALTABL
67c0: 45 20 30 78 30 30 30 30 30 34 30 30 20 20 2f 2a  E 0x00000400  /*
67d0: 20 57 68 65 72 65 4c 6f 6f 70 2e 75 2e 76 74 61   WhereLoop.u.vta
67e0: 62 20 69 73 20 76 61 6c 69 64 20 2a 2f 0a 23 64  b is valid */.#d
67f0: 65 66 69 6e 65 20 57 48 45 52 45 5f 49 4e 5f 41  efine WHERE_IN_A
6800: 42 4c 45 20 20 20 20 20 20 30 78 30 30 30 30 30  BLE      0x00000
6810: 38 30 30 20 20 2f 2a 20 41 62 6c 65 20 74 6f 20  800  /* Able to 
6820: 73 75 70 70 6f 72 74 20 61 6e 20 49 4e 20 6f 70  support an IN op
6830: 65 72 61 74 6f 72 20 2a 2f 0a 23 64 65 66 69 6e  erator */.#defin
6840: 65 20 57 48 45 52 45 5f 4f 4e 45 52 4f 57 20 20  e WHERE_ONEROW  
6850: 20 20 20 20 20 30 78 30 30 30 30 31 30 30 30 20       0x00001000 
6860: 20 2f 2a 20 53 65 6c 65 63 74 73 20 6e 6f 20 6d   /* Selects no m
6870: 6f 72 65 20 74 68 61 6e 20 6f 6e 65 20 72 6f 77  ore than one row
6880: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52   */.#define WHER
6890: 45 5f 4d 55 4c 54 49 5f 4f 52 20 20 20 20 20 30  E_MULTI_OR     0
68a0: 78 30 30 30 30 32 30 30 30 20 20 2f 2a 20 4f 52  x00002000  /* OR
68b0: 20 75 73 69 6e 67 20 6d 75 6c 74 69 70 6c 65 20   using multiple 
68c0: 69 6e 64 69 63 65 73 20 2a 2f 0a 23 64 65 66 69  indices */.#defi
68d0: 6e 65 20 57 48 45 52 45 5f 41 55 54 4f 5f 49 4e  ne WHERE_AUTO_IN
68e0: 44 45 58 20 20 20 30 78 30 30 30 30 34 30 30 30  DEX   0x00004000
68f0: 20 20 2f 2a 20 55 73 65 73 20 61 6e 20 65 70 68    /* Uses an eph
6900: 65 6d 65 72 61 6c 20 69 6e 64 65 78 20 2a 2f 0a  emeral index */.
6910: 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f 53 4b  #define WHERE_SK
6920: 49 50 53 43 41 4e 20 20 20 20 20 30 78 30 30 30  IPSCAN     0x000
6930: 30 38 30 30 30 20 20 2f 2a 20 55 73 65 73 20 74  08000  /* Uses t
6940: 68 65 20 73 6b 69 70 2d 73 63 61 6e 20 61 6c 67  he skip-scan alg
6950: 6f 72 69 74 68 6d 20 2a 2f 0a 23 64 65 66 69 6e  orithm */.#defin
6960: 65 20 57 48 45 52 45 5f 55 4e 51 5f 57 41 4e 54  e WHERE_UNQ_WANT
6970: 45 44 20 20 20 30 78 30 30 30 31 30 30 30 30 20  ED   0x00010000 
6980: 20 2f 2a 20 57 48 45 52 45 5f 4f 4e 45 52 4f 57   /* WHERE_ONEROW
6990: 20 77 6f 75 6c 64 20 68 61 76 65 20 62 65 65 6e   would have been
69a0: 20 68 65 6c 70 66 75 6c 2a 2f 0a 23 64 65 66 69   helpful*/.#defi
69b0: 6e 65 20 57 48 45 52 45 5f 50 41 52 54 49 41 4c  ne WHERE_PARTIAL
69c0: 49 44 58 20 20 20 30 78 30 30 30 32 30 30 30 30  IDX   0x00020000
69d0: 20 20 2f 2a 20 54 68 65 20 61 75 74 6f 6d 61 74    /* The automat
69e0: 69 63 20 69 6e 64 65 78 20 69 73 20 70 61 72 74  ic index is part
69f0: 69 61 6c 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  ial */.#define W
6a00: 48 45 52 45 5f 49 4e 5f 45 41 52 4c 59 4f 55 54  HERE_IN_EARLYOUT
6a10: 20 20 30 78 30 30 30 34 30 30 30 30 20 20 2f 2a    0x00040000  /*
6a20: 20 50 65 72 68 61 70 73 20 71 75 69 74 20 49 4e   Perhaps quit IN
6a30: 20 6c 6f 6f 70 73 20 65 61 72 6c 79 20 2a 2f 0a   loops early */.
6a40: 0a 23 65 6e 64 69 66 20 2f 2a 20 21 64 65 66 69  .#endif /* !defi
6a50: 6e 65 64 28 53 51 4c 49 54 45 5f 57 48 45 52 45  ned(SQLITE_WHERE
6a60: 49 4e 54 5f 48 29 20 2a 2f 0a                    INT_H) */.