/ Hex Artifact Content
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Artifact 2d50c2b74a33be44cb68fdecee30b4d93552f1f4:


0000: 2f 2a 0a 2a 2a 20 32 30 31 33 2d 31 31 2d 31 32  /*.** 2013-11-12
0010: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 68 6f  .**.** The autho
0020: 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70 79  r disclaims copy
0030: 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73 6f  right to this so
0040: 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20 70  urce code.  In p
0050: 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c 65 67  lace of.** a leg
0060: 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65 20  al notice, here 
0070: 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a 2a  is a blessing:.*
0080: 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f 75 20  *.**    May you 
0090: 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74 20  do good and not 
00a0: 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 79 20  evil..**    May 
00b0: 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 76 65  you find forgive
00c0: 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 65 6c  ness for yoursel
00d0: 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 6f 74  f and forgive ot
00e0: 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 79 20  hers..**    May 
00f0: 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 6c 79  you share freely
0100: 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 20 6d  , never taking m
0110: 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 69 76  ore than you giv
0120: 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  e..**.**********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a  ***************.
0170: 2a 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20  **.** This file 
0180: 63 6f 6e 74 61 69 6e 73 20 73 74 72 75 63 74 75  contains structu
0190: 72 65 20 61 6e 64 20 6d 61 63 72 6f 20 64 65 66  re and macro def
01a0: 69 6e 69 74 69 6f 6e 73 20 66 6f 72 20 74 68 65  initions for the
01b0: 20 71 75 65 72 79 0a 2a 2a 20 70 6c 61 6e 6e 65   query.** planne
01c0: 72 20 6c 6f 67 69 63 20 69 6e 20 22 77 68 65 72  r logic in "wher
01d0: 65 2e 63 22 2e 20 20 54 68 65 73 65 20 64 65 66  e.c".  These def
01e0: 69 6e 69 74 69 6f 6e 73 20 61 72 65 20 62 72 6f  initions are bro
01f0: 6b 65 6e 20 6f 75 74 20 69 6e 74 6f 0a 2a 2a 20  ken out into.** 
0200: 61 20 73 65 70 61 72 61 74 65 20 73 6f 75 72 63  a separate sourc
0210: 65 20 66 69 6c 65 20 66 6f 72 20 65 61 73 69 65  e file for easie
0220: 72 20 65 64 69 74 69 6e 67 2e 0a 2a 2f 0a 0a 2f  r editing..*/../
0230: 2a 0a 2a 2a 20 54 72 61 63 65 20 6f 75 74 70 75  *.** Trace outpu
0240: 74 20 6d 61 63 72 6f 73 0a 2a 2f 0a 23 69 66 20  t macros.*/.#if 
0250: 64 65 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 54  defined(SQLITE_T
0260: 45 53 54 29 20 7c 7c 20 64 65 66 69 6e 65 64 28  EST) || defined(
0270: 53 51 4c 49 54 45 5f 44 45 42 55 47 29 0a 2f 2a  SQLITE_DEBUG)./*
0280: 2a 2a 2f 20 69 6e 74 20 73 71 6c 69 74 65 33 57  **/ int sqlite3W
0290: 68 65 72 65 54 72 61 63 65 3b 0a 23 65 6e 64 69  hereTrace;.#endi
02a0: 66 0a 23 69 66 20 64 65 66 69 6e 65 64 28 53 51  f.#if defined(SQ
02b0: 4c 49 54 45 5f 44 45 42 55 47 29 20 5c 0a 20 20  LITE_DEBUG) \.  
02c0: 20 20 26 26 20 28 64 65 66 69 6e 65 64 28 53 51    && (defined(SQ
02d0: 4c 49 54 45 5f 54 45 53 54 29 20 7c 7c 20 64 65  LITE_TEST) || de
02e0: 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 45 4e 41  fined(SQLITE_ENA
02f0: 42 4c 45 5f 57 48 45 52 45 54 52 41 43 45 29 29  BLE_WHERETRACE))
0300: 0a 23 20 64 65 66 69 6e 65 20 57 48 45 52 45 54  .# define WHERET
0310: 52 41 43 45 28 4b 2c 58 29 20 20 69 66 28 73 71  RACE(K,X)  if(sq
0320: 6c 69 74 65 33 57 68 65 72 65 54 72 61 63 65 26  lite3WhereTrace&
0330: 28 4b 29 29 20 73 71 6c 69 74 65 33 44 65 62 75  (K)) sqlite3Debu
0340: 67 50 72 69 6e 74 66 20 58 0a 23 20 64 65 66 69  gPrintf X.# defi
0350: 6e 65 20 57 48 45 52 45 54 52 41 43 45 5f 45 4e  ne WHERETRACE_EN
0360: 41 42 4c 45 44 20 31 0a 23 65 6c 73 65 0a 23 20  ABLED 1.#else.# 
0370: 64 65 66 69 6e 65 20 57 48 45 52 45 54 52 41 43  define WHERETRAC
0380: 45 28 4b 2c 58 29 0a 23 65 6e 64 69 66 0a 0a 2f  E(K,X).#endif../
0390: 2a 20 46 6f 72 77 61 72 64 20 72 65 66 65 72 65  * Forward refere
03a0: 6e 63 65 73 0a 2a 2f 0a 74 79 70 65 64 65 66 20  nces.*/.typedef 
03b0: 73 74 72 75 63 74 20 57 68 65 72 65 43 6c 61 75  struct WhereClau
03c0: 73 65 20 57 68 65 72 65 43 6c 61 75 73 65 3b 0a  se WhereClause;.
03d0: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 57  typedef struct W
03e0: 68 65 72 65 4d 61 73 6b 53 65 74 20 57 68 65 72  hereMaskSet Wher
03f0: 65 4d 61 73 6b 53 65 74 3b 0a 74 79 70 65 64 65  eMaskSet;.typede
0400: 66 20 73 74 72 75 63 74 20 57 68 65 72 65 4f 72  f struct WhereOr
0410: 49 6e 66 6f 20 57 68 65 72 65 4f 72 49 6e 66 6f  Info WhereOrInfo
0420: 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  ;.typedef struct
0430: 20 57 68 65 72 65 41 6e 64 49 6e 66 6f 20 57 68   WhereAndInfo Wh
0440: 65 72 65 41 6e 64 49 6e 66 6f 3b 0a 74 79 70 65  ereAndInfo;.type
0450: 64 65 66 20 73 74 72 75 63 74 20 57 68 65 72 65  def struct Where
0460: 4c 65 76 65 6c 20 57 68 65 72 65 4c 65 76 65 6c  Level WhereLevel
0470: 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  ;.typedef struct
0480: 20 57 68 65 72 65 4c 6f 6f 70 20 57 68 65 72 65   WhereLoop Where
0490: 4c 6f 6f 70 3b 0a 74 79 70 65 64 65 66 20 73 74  Loop;.typedef st
04a0: 72 75 63 74 20 57 68 65 72 65 50 61 74 68 20 57  ruct WherePath W
04b0: 68 65 72 65 50 61 74 68 3b 0a 74 79 70 65 64 65  herePath;.typede
04c0: 66 20 73 74 72 75 63 74 20 57 68 65 72 65 54 65  f struct WhereTe
04d0: 72 6d 20 57 68 65 72 65 54 65 72 6d 3b 0a 74 79  rm WhereTerm;.ty
04e0: 70 65 64 65 66 20 73 74 72 75 63 74 20 57 68 65  pedef struct Whe
04f0: 72 65 4c 6f 6f 70 42 75 69 6c 64 65 72 20 57 68  reLoopBuilder Wh
0500: 65 72 65 4c 6f 6f 70 42 75 69 6c 64 65 72 3b 0a  ereLoopBuilder;.
0510: 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20 57  typedef struct W
0520: 68 65 72 65 53 63 61 6e 20 57 68 65 72 65 53 63  hereScan WhereSc
0530: 61 6e 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75  an;.typedef stru
0540: 63 74 20 57 68 65 72 65 4f 72 43 6f 73 74 20 57  ct WhereOrCost W
0550: 68 65 72 65 4f 72 43 6f 73 74 3b 0a 74 79 70 65  hereOrCost;.type
0560: 64 65 66 20 73 74 72 75 63 74 20 57 68 65 72 65  def struct Where
0570: 4f 72 53 65 74 20 57 68 65 72 65 4f 72 53 65 74  OrSet WhereOrSet
0580: 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 6f 62  ;../*.** This ob
0590: 6a 65 63 74 20 63 6f 6e 74 61 69 6e 73 20 69 6e  ject contains in
05a0: 66 6f 72 6d 61 74 69 6f 6e 20 6e 65 65 64 65 64  formation needed
05b0: 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20 61 20   to implement a 
05c0: 73 69 6e 67 6c 65 20 6e 65 73 74 65 64 0a 2a 2a  single nested.**
05d0: 20 6c 6f 6f 70 20 69 6e 20 57 48 45 52 45 20 63   loop in WHERE c
05e0: 6c 61 75 73 65 2e 0a 2a 2a 0a 2a 2a 20 43 6f 6e  lause..**.** Con
05f0: 74 72 61 73 74 20 74 68 69 73 20 6f 62 6a 65 63  trast this objec
0600: 74 20 77 69 74 68 20 57 68 65 72 65 4c 6f 6f 70  t with WhereLoop
0610: 2e 20 20 54 68 69 73 20 6f 62 6a 65 63 74 20 64  .  This object d
0620: 65 73 63 72 69 62 65 73 20 74 68 65 0a 2a 2a 20  escribes the.** 
0630: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f  implementation o
0640: 66 20 74 68 65 20 6c 6f 6f 70 2e 20 20 57 68 65  f the loop.  Whe
0650: 72 65 4c 6f 6f 70 20 64 65 73 63 72 69 62 65 73  reLoop describes
0660: 20 74 68 65 20 61 6c 67 6f 72 69 74 68 6d 2e 0a   the algorithm..
0670: 2a 2a 20 54 68 69 73 20 6f 62 6a 65 63 74 20 63  ** This object c
0680: 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74 65  ontains a pointe
0690: 72 20 74 6f 20 74 68 65 20 57 68 65 72 65 4c 6f  r to the WhereLo
06a0: 6f 70 20 61 6c 67 6f 72 69 74 68 6d 20 61 73 20  op algorithm as 
06b0: 6f 6e 65 20 6f 66 0a 2a 2a 20 69 74 73 20 65 6c  one of.** its el
06c0: 65 6d 65 6e 74 73 2e 0a 2a 2a 0a 2a 2a 20 54 68  ements..**.** Th
06d0: 65 20 57 68 65 72 65 49 6e 66 6f 20 6f 62 6a 65  e WhereInfo obje
06e0: 63 74 20 63 6f 6e 74 61 69 6e 73 20 61 20 73 69  ct contains a si
06f0: 6e 67 6c 65 20 69 6e 73 74 61 6e 63 65 20 6f 66  ngle instance of
0700: 20 74 68 69 73 20 6f 62 6a 65 63 74 20 66 6f 72   this object for
0710: 0a 2a 2a 20 65 61 63 68 20 74 65 72 6d 20 69 6e  .** each term in
0720: 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73 65   the FROM clause
0730: 20 28 77 68 69 63 68 20 69 73 20 74 6f 20 73 61   (which is to sa
0740: 79 2c 20 66 6f 72 20 65 61 63 68 20 6f 66 20 74  y, for each of t
0750: 68 65 0a 2a 2a 20 6e 65 73 74 65 64 20 6c 6f 6f  he.** nested loo
0760: 70 73 20 61 73 20 69 6d 70 6c 65 6d 65 6e 74 65  ps as implemente
0770: 64 29 2e 20 20 54 68 65 20 6f 72 64 65 72 20 6f  d).  The order o
0780: 66 20 57 68 65 72 65 4c 65 76 65 6c 20 6f 62 6a  f WhereLevel obj
0790: 65 63 74 73 20 64 65 74 65 72 6d 69 6e 65 73 0a  ects determines.
07a0: 2a 2a 20 74 68 65 20 6c 6f 6f 70 20 6e 65 73 74  ** the loop nest
07b0: 65 64 20 6f 72 64 65 72 2c 20 77 69 74 68 20 57  ed order, with W
07c0: 68 65 72 65 49 6e 66 6f 2e 61 5b 30 5d 20 62 65  hereInfo.a[0] be
07d0: 69 6e 67 20 74 68 65 20 6f 75 74 65 72 20 6c 6f  ing the outer lo
07e0: 6f 70 20 61 6e 64 0a 2a 2a 20 57 68 65 72 65 49  op and.** WhereI
07f0: 6e 66 6f 2e 61 5b 57 68 65 72 65 49 6e 66 6f 2e  nfo.a[WhereInfo.
0800: 6e 4c 65 76 65 6c 2d 31 5d 20 62 65 69 6e 67 20  nLevel-1] being 
0810: 74 68 65 20 69 6e 6e 65 72 20 6c 6f 6f 70 2e 0a  the inner loop..
0820: 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72 65 4c  */.struct WhereL
0830: 65 76 65 6c 20 7b 0a 20 20 69 6e 74 20 69 4c 65  evel {.  int iLe
0840: 66 74 4a 6f 69 6e 3b 20 20 20 20 20 20 20 20 2f  ftJoin;        /
0850: 2a 20 4d 65 6d 6f 72 79 20 63 65 6c 6c 20 75 73  * Memory cell us
0860: 65 64 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20  ed to implement 
0870: 4c 45 46 54 20 4f 55 54 45 52 20 4a 4f 49 4e 20  LEFT OUTER JOIN 
0880: 2a 2f 0a 20 20 69 6e 74 20 69 54 61 62 43 75 72  */.  int iTabCur
0890: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68  ;          /* Th
08a0: 65 20 56 44 42 45 20 63 75 72 73 6f 72 20 75 73  e VDBE cursor us
08b0: 65 64 20 74 6f 20 61 63 63 65 73 73 20 74 68 65  ed to access the
08c0: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74 20   table */.  int 
08d0: 69 49 64 78 43 75 72 3b 20 20 20 20 20 20 20 20  iIdxCur;        
08e0: 20 20 2f 2a 20 54 68 65 20 56 44 42 45 20 63 75    /* The VDBE cu
08f0: 72 73 6f 72 20 75 73 65 64 20 74 6f 20 61 63 63  rsor used to acc
0900: 65 73 73 20 70 49 64 78 20 2a 2f 0a 20 20 69 6e  ess pIdx */.  in
0910: 74 20 61 64 64 72 42 72 6b 3b 20 20 20 20 20 20  t addrBrk;      
0920: 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65 72 65      /* Jump here
0930: 20 74 6f 20 62 72 65 61 6b 20 6f 75 74 20 6f 66   to break out of
0940: 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20 20 69   the loop */.  i
0950: 6e 74 20 61 64 64 72 4e 78 74 3b 20 20 20 20 20  nt addrNxt;     
0960: 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65 72       /* Jump her
0970: 65 20 74 6f 20 73 74 61 72 74 20 74 68 65 20 6e  e to start the n
0980: 65 78 74 20 49 4e 20 63 6f 6d 62 69 6e 61 74 69  ext IN combinati
0990: 6f 6e 20 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72  on */.  int addr
09a0: 53 6b 69 70 3b 20 20 20 20 20 20 20 20 20 2f 2a  Skip;         /*
09b0: 20 4a 75 6d 70 20 68 65 72 65 20 66 6f 72 20 6e   Jump here for n
09c0: 65 78 74 20 69 74 65 72 61 74 69 6f 6e 20 6f 66  ext iteration of
09d0: 20 73 6b 69 70 2d 73 63 61 6e 20 2a 2f 0a 20 20   skip-scan */.  
09e0: 69 6e 74 20 61 64 64 72 43 6f 6e 74 3b 20 20 20  int addrCont;   
09f0: 20 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65        /* Jump he
0a00: 72 65 20 74 6f 20 63 6f 6e 74 69 6e 75 65 20 77  re to continue w
0a10: 69 74 68 20 74 68 65 20 6e 65 78 74 20 6c 6f 6f  ith the next loo
0a20: 70 20 63 79 63 6c 65 20 2a 2f 0a 20 20 69 6e 74  p cycle */.  int
0a30: 20 61 64 64 72 46 69 72 73 74 3b 20 20 20 20 20   addrFirst;     
0a40: 20 20 20 2f 2a 20 46 69 72 73 74 20 69 6e 73 74     /* First inst
0a50: 72 75 63 74 69 6f 6e 20 6f 66 20 69 6e 74 65 72  ruction of inter
0a60: 69 6f 72 20 6f 66 20 74 68 65 20 6c 6f 6f 70 20  ior of the loop 
0a70: 2a 2f 0a 20 20 69 6e 74 20 61 64 64 72 42 6f 64  */.  int addrBod
0a80: 79 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 42 65  y;         /* Be
0a90: 67 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 62  ginning of the b
0aa0: 6f 64 79 20 6f 66 20 74 68 69 73 20 6c 6f 6f 70  ody of this loop
0ab0: 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49   */.#ifndef SQLI
0ac0: 54 45 5f 4c 49 4b 45 5f 44 4f 45 53 4e 54 5f 4d  TE_LIKE_DOESNT_M
0ad0: 41 54 43 48 5f 42 4c 4f 42 53 0a 20 20 75 33 32  ATCH_BLOBS.  u32
0ae0: 20 69 4c 69 6b 65 52 65 70 43 6e 74 72 3b 20 20   iLikeRepCntr;  
0af0: 20 20 20 2f 2a 20 4c 49 4b 45 20 72 61 6e 67 65     /* LIKE range
0b00: 20 70 72 6f 63 65 73 73 69 6e 67 20 63 6f 75 6e   processing coun
0b10: 74 65 72 20 72 65 67 69 73 74 65 72 20 28 74 69  ter register (ti
0b20: 6d 65 73 20 32 29 20 2a 2f 0a 20 20 69 6e 74 20  mes 2) */.  int 
0b30: 61 64 64 72 4c 69 6b 65 52 65 70 3b 20 20 20 20  addrLikeRep;    
0b40: 20 20 2f 2a 20 4c 49 4b 45 20 72 61 6e 67 65 20    /* LIKE range 
0b50: 70 72 6f 63 65 73 73 69 6e 67 20 61 64 64 72 65  processing addre
0b60: 73 73 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  ss */.#endif.  u
0b70: 38 20 69 46 72 6f 6d 3b 20 20 20 20 20 20 20 20  8 iFrom;        
0b80: 20 20 20 20 20 2f 2a 20 57 68 69 63 68 20 65 6e       /* Which en
0b90: 74 72 79 20 69 6e 20 74 68 65 20 46 52 4f 4d 20  try in the FROM 
0ba0: 63 6c 61 75 73 65 20 2a 2f 0a 20 20 75 38 20 6f  clause */.  u8 o
0bb0: 70 2c 20 70 33 2c 20 70 35 3b 20 20 20 20 20 20  p, p3, p5;      
0bc0: 20 20 2f 2a 20 4f 70 63 6f 64 65 2c 20 50 33 20    /* Opcode, P3 
0bd0: 26 20 50 35 20 6f 66 20 74 68 65 20 6f 70 63 6f  & P5 of the opco
0be0: 64 65 20 74 68 61 74 20 65 6e 64 73 20 74 68 65  de that ends the
0bf0: 20 6c 6f 6f 70 20 2a 2f 0a 20 20 69 6e 74 20 70   loop */.  int p
0c00: 31 2c 20 70 32 3b 20 20 20 20 20 20 20 20 20 20  1, p2;          
0c10: 20 2f 2a 20 4f 70 65 72 61 6e 64 73 20 6f 66 20   /* Operands of 
0c20: 74 68 65 20 6f 70 63 6f 64 65 20 75 73 65 64 20  the opcode used 
0c30: 74 6f 20 65 6e 64 73 20 74 68 65 20 6c 6f 6f 70  to ends the loop
0c40: 20 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b 20 20 20   */.  union {   
0c50: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
0c60: 6e 66 6f 72 6d 61 74 69 6f 6e 20 74 68 61 74 20  nformation that 
0c70: 64 65 70 65 6e 64 73 20 6f 6e 20 70 57 4c 6f 6f  depends on pWLoo
0c80: 70 2d 3e 77 73 46 6c 61 67 73 20 2a 2f 0a 20 20  p->wsFlags */.  
0c90: 20 20 73 74 72 75 63 74 20 7b 0a 20 20 20 20 20    struct {.     
0ca0: 20 69 6e 74 20 6e 49 6e 3b 20 20 20 20 20 20 20   int nIn;       
0cb0: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
0cc0: 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 61   of entries in a
0cd0: 49 6e 4c 6f 6f 70 5b 5d 20 2a 2f 0a 20 20 20 20  InLoop[] */.    
0ce0: 20 20 73 74 72 75 63 74 20 49 6e 4c 6f 6f 70 20    struct InLoop 
0cf0: 7b 0a 20 20 20 20 20 20 20 20 69 6e 74 20 69 43  {.        int iC
0d00: 75 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ur;             
0d10: 20 2f 2a 20 54 68 65 20 56 44 42 45 20 63 75 72   /* The VDBE cur
0d20: 73 6f 72 20 75 73 65 64 20 62 79 20 74 68 69 73  sor used by this
0d30: 20 49 4e 20 6f 70 65 72 61 74 6f 72 20 2a 2f 0a   IN operator */.
0d40: 20 20 20 20 20 20 20 20 69 6e 74 20 61 64 64 72          int addr
0d50: 49 6e 54 6f 70 3b 20 20 20 20 20 20 20 20 20 2f  InTop;         /
0d60: 2a 20 54 6f 70 20 6f 66 20 74 68 65 20 49 4e 20  * Top of the IN 
0d70: 6c 6f 6f 70 20 2a 2f 0a 20 20 20 20 20 20 20 20  loop */.        
0d80: 75 38 20 65 45 6e 64 4c 6f 6f 70 4f 70 3b 20 20  u8 eEndLoopOp;  
0d90: 20 20 20 20 20 20 20 2f 2a 20 49 4e 20 4c 6f 6f         /* IN Loo
0da0: 70 20 74 65 72 6d 69 6e 61 74 6f 72 2e 20 4f 50  p terminator. OP
0db0: 5f 4e 65 78 74 20 6f 72 20 4f 50 5f 50 72 65 76  _Next or OP_Prev
0dc0: 20 2a 2f 0a 20 20 20 20 20 20 7d 20 2a 61 49 6e   */.      } *aIn
0dd0: 4c 6f 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20  Loop;           
0de0: 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20 61  /* Information a
0df0: 62 6f 75 74 20 65 61 63 68 20 6e 65 73 74 65 64  bout each nested
0e00: 20 49 4e 20 6f 70 65 72 61 74 6f 72 20 2a 2f 0a   IN operator */.
0e10: 20 20 20 20 7d 20 69 6e 3b 20 20 20 20 20 20 20      } in;       
0e20: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65            /* Use
0e30: 64 20 77 68 65 6e 20 70 57 4c 6f 6f 70 2d 3e 77  d when pWLoop->w
0e40: 73 46 6c 61 67 73 26 57 48 45 52 45 5f 49 4e 5f  sFlags&WHERE_IN_
0e50: 41 42 4c 45 20 2a 2f 0a 20 20 20 20 49 6e 64 65  ABLE */.    Inde
0e60: 78 20 2a 70 43 6f 76 69 64 78 3b 20 20 20 20 20  x *pCovidx;     
0e70: 20 20 2f 2a 20 50 6f 73 73 69 62 6c 65 20 63 6f    /* Possible co
0e80: 76 65 72 69 6e 67 20 69 6e 64 65 78 20 66 6f 72  vering index for
0e90: 20 57 48 45 52 45 5f 4d 55 4c 54 49 5f 4f 52 20   WHERE_MULTI_OR 
0ea0: 2a 2f 0a 20 20 7d 20 75 3b 0a 20 20 73 74 72 75  */.  } u;.  stru
0eb0: 63 74 20 57 68 65 72 65 4c 6f 6f 70 20 2a 70 57  ct WhereLoop *pW
0ec0: 4c 6f 6f 70 3b 20 20 2f 2a 20 54 68 65 20 73 65  Loop;  /* The se
0ed0: 6c 65 63 74 65 64 20 57 68 65 72 65 4c 6f 6f 70  lected WhereLoop
0ee0: 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 42 69 74   object */.  Bit
0ef0: 6d 61 73 6b 20 6e 6f 74 52 65 61 64 79 3b 20 20  mask notReady;  
0f00: 20 20 20 20 20 20 20 20 2f 2a 20 46 52 4f 4d 20          /* FROM 
0f10: 65 6e 74 72 69 65 73 20 6e 6f 74 20 75 73 61 62  entries not usab
0f20: 6c 65 20 61 74 20 74 68 69 73 20 6c 65 76 65 6c  le at this level
0f30: 20 2a 2f 0a 23 69 66 64 65 66 20 53 51 4c 49 54   */.#ifdef SQLIT
0f40: 45 5f 45 4e 41 42 4c 45 5f 53 54 4d 54 5f 53 43  E_ENABLE_STMT_SC
0f50: 41 4e 53 54 41 54 55 53 0a 20 20 69 6e 74 20 61  ANSTATUS.  int a
0f60: 64 64 72 56 69 73 69 74 3b 20 20 20 20 20 20 20  ddrVisit;       
0f70: 20 2f 2a 20 41 64 64 72 65 73 73 20 61 74 20 77   /* Address at w
0f80: 68 69 63 68 20 72 6f 77 20 69 73 20 76 69 73 69  hich row is visi
0f90: 74 65 64 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d 3b  ted */.#endif.};
0fa0: 0a 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 69 6e 73  ../*.** Each ins
0fb0: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
0fc0: 6a 65 63 74 20 72 65 70 72 65 73 65 6e 74 73 20  ject represents 
0fd0: 61 6e 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f 72  an algorithm for
0fe0: 20 65 76 61 6c 75 61 74 69 6e 67 20 6f 6e 65 0a   evaluating one.
0ff0: 2a 2a 20 74 65 72 6d 20 6f 66 20 61 20 6a 6f 69  ** term of a joi
1000: 6e 2e 20 20 45 76 65 72 79 20 74 65 72 6d 20 6f  n.  Every term o
1010: 66 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73  f the FROM claus
1020: 65 20 77 69 6c 6c 20 68 61 76 65 20 61 74 20 6c  e will have at l
1030: 65 61 73 74 0a 2a 2a 20 6f 6e 65 20 63 6f 72 72  east.** one corr
1040: 65 73 70 6f 6e 64 69 6e 67 20 57 68 65 72 65 4c  esponding WhereL
1050: 6f 6f 70 20 6f 62 6a 65 63 74 20 28 75 6e 6c 65  oop object (unle
1060: 73 73 20 49 4e 44 45 58 45 44 20 42 59 20 63 6f  ss INDEXED BY co
1070: 6e 73 74 72 61 69 6e 74 73 0a 2a 2a 20 70 72 65  nstraints.** pre
1080: 76 65 6e 74 20 61 20 71 75 65 72 79 20 73 6f 6c  vent a query sol
1090: 75 74 69 6f 6e 20 2d 20 77 68 69 63 68 20 69 73  ution - which is
10a0: 20 61 6e 20 65 72 72 6f 72 29 20 61 6e 64 20 6d   an error) and m
10b0: 61 6e 79 20 74 65 72 6d 73 20 6f 66 20 74 68 65  any terms of the
10c0: 0a 2a 2a 20 46 52 4f 4d 20 63 6c 61 75 73 65 20  .** FROM clause 
10d0: 77 69 6c 6c 20 68 61 76 65 20 6d 75 6c 74 69 70  will have multip
10e0: 6c 65 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a  le WhereLoop obj
10f0: 65 63 74 73 2c 20 65 61 63 68 20 64 65 73 63 72  ects, each descr
1100: 69 62 69 6e 67 20 61 0a 2a 2a 20 70 6f 74 65 6e  ibing a.** poten
1110: 74 69 61 6c 20 77 61 79 20 6f 66 20 69 6d 70 6c  tial way of impl
1120: 65 6d 65 6e 74 69 6e 67 20 74 68 61 74 20 46 52  ementing that FR
1130: 4f 4d 2d 63 6c 61 75 73 65 20 74 65 72 6d 2c 20  OM-clause term, 
1140: 74 6f 67 65 74 68 65 72 20 77 69 74 68 0a 2a 2a  together with.**
1150: 20 64 65 70 65 6e 64 65 6e 63 69 65 73 20 61 6e   dependencies an
1160: 64 20 63 6f 73 74 20 65 73 74 69 6d 61 74 65 73  d cost estimates
1170: 20 66 6f 72 20 75 73 69 6e 67 20 74 68 65 20 63   for using the c
1180: 68 6f 73 65 6e 20 61 6c 67 6f 72 69 74 68 6d 2e  hosen algorithm.
1190: 0a 2a 2a 0a 2a 2a 20 51 75 65 72 79 20 70 6c 61  .**.** Query pla
11a0: 6e 6e 69 6e 67 20 63 6f 6e 73 69 73 74 73 20 6f  nning consists o
11b0: 66 20 62 75 69 6c 64 69 6e 67 20 75 70 20 61 20  f building up a 
11c0: 63 6f 6c 6c 65 63 74 69 6f 6e 20 6f 66 20 74 68  collection of th
11d0: 65 73 65 20 57 68 65 72 65 4c 6f 6f 70 0a 2a 2a  ese WhereLoop.**
11e0: 20 6f 62 6a 65 63 74 73 2c 20 74 68 65 6e 20 63   objects, then c
11f0: 6f 6d 70 75 74 69 6e 67 20 61 20 70 61 72 74 69  omputing a parti
1200: 63 75 6c 61 72 20 73 65 71 75 65 6e 63 65 20 6f  cular sequence o
1210: 66 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65  f WhereLoop obje
1220: 63 74 73 2c 20 77 69 74 68 0a 2a 2a 20 6f 6e 65  cts, with.** one
1230: 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63   WhereLoop objec
1240: 74 20 70 65 72 20 46 52 4f 4d 20 63 6c 61 75 73  t per FROM claus
1250: 65 20 74 65 72 6d 2c 20 74 68 61 74 20 73 61 74  e term, that sat
1260: 69 73 66 79 20 61 6c 6c 20 64 65 70 65 6e 64 65  isfy all depende
1270: 6e 63 69 65 73 0a 2a 2a 20 61 6e 64 20 74 68 61  ncies.** and tha
1280: 74 20 6d 69 6e 69 6d 69 7a 65 20 74 68 65 20 6f  t minimize the o
1290: 76 65 72 61 6c 6c 20 63 6f 73 74 2e 0a 2a 2f 0a  verall cost..*/.
12a0: 73 74 72 75 63 74 20 57 68 65 72 65 4c 6f 6f 70  struct WhereLoop
12b0: 20 7b 0a 20 20 42 69 74 6d 61 73 6b 20 70 72 65   {.  Bitmask pre
12c0: 72 65 71 3b 20 20 20 20 20 20 20 2f 2a 20 42 69  req;       /* Bi
12d0: 74 6d 61 73 6b 20 6f 66 20 6f 74 68 65 72 20 6c  tmask of other l
12e0: 6f 6f 70 73 20 74 68 61 74 20 6d 75 73 74 20 72  oops that must r
12f0: 75 6e 20 66 69 72 73 74 20 2a 2f 0a 20 20 42 69  un first */.  Bi
1300: 74 6d 61 73 6b 20 6d 61 73 6b 53 65 6c 66 3b 20  tmask maskSelf; 
1310: 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b 20 69      /* Bitmask i
1320: 64 65 6e 74 69 66 79 69 6e 67 20 74 61 62 6c 65  dentifying table
1330: 20 69 54 61 62 20 2a 2f 0a 23 69 66 64 65 66 20   iTab */.#ifdef 
1340: 53 51 4c 49 54 45 5f 44 45 42 55 47 0a 20 20 63  SQLITE_DEBUG.  c
1350: 68 61 72 20 63 49 64 3b 20 20 20 20 20 20 20 20  har cId;        
1360: 20 20 20 20 20 2f 2a 20 53 79 6d 62 6f 6c 69 63       /* Symbolic
1370: 20 49 44 20 6f 66 20 74 68 69 73 20 6c 6f 6f 70   ID of this loop
1380: 20 66 6f 72 20 64 65 62 75 67 67 69 6e 67 20 75   for debugging u
1390: 73 65 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  se */.#endif.  u
13a0: 38 20 69 54 61 62 3b 20 20 20 20 20 20 20 20 20  8 iTab;         
13b0: 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e       /* Position
13c0: 20 69 6e 20 46 52 4f 4d 20 63 6c 61 75 73 65 20   in FROM clause 
13d0: 6f 66 20 74 61 62 6c 65 20 66 6f 72 20 74 68 69  of table for thi
13e0: 73 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 38 20 69  s loop */.  u8 i
13f0: 53 6f 72 74 49 64 78 3b 20 20 20 20 20 20 20 20  SortIdx;        
1400: 20 20 2f 2a 20 53 6f 72 74 69 6e 67 20 69 6e 64    /* Sorting ind
1410: 65 78 20 6e 75 6d 62 65 72 2e 20 20 30 3d 3d 4e  ex number.  0==N
1420: 6f 6e 65 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20  one */.  LogEst 
1430: 72 53 65 74 75 70 3b 20 20 20 20 20 20 20 20 2f  rSetup;        /
1440: 2a 20 4f 6e 65 2d 74 69 6d 65 20 73 65 74 75 70  * One-time setup
1450: 20 63 6f 73 74 20 28 65 78 3a 20 63 72 65 61 74   cost (ex: creat
1460: 65 20 74 72 61 6e 73 69 65 6e 74 20 69 6e 64 65  e transient inde
1470: 78 29 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72  x) */.  LogEst r
1480: 52 75 6e 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  Run;          /*
1490: 20 43 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e 67   Cost of running
14a0: 20 65 61 63 68 20 6c 6f 6f 70 20 2a 2f 0a 20 20   each loop */.  
14b0: 4c 6f 67 45 73 74 20 6e 4f 75 74 3b 20 20 20 20  LogEst nOut;    
14c0: 20 20 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74        /* Estimat
14d0: 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74  ed number of out
14e0: 70 75 74 20 72 6f 77 73 20 2a 2f 0a 20 20 75 6e  put rows */.  un
14f0: 69 6f 6e 20 7b 0a 20 20 20 20 73 74 72 75 63 74  ion {.    struct
1500: 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 20 20   {              
1510: 20 2f 2a 20 49 6e 66 6f 72 6d 61 74 69 6f 6e 20   /* Information 
1520: 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 62 74 72  for internal btr
1530: 65 65 20 74 61 62 6c 65 73 20 2a 2f 0a 20 20 20  ee tables */.   
1540: 20 20 20 75 31 36 20 6e 45 71 3b 20 20 20 20 20     u16 nEq;     
1550: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1560: 62 65 72 20 6f 66 20 65 71 75 61 6c 69 74 79 20  ber of equality 
1570: 63 6f 6e 73 74 72 61 69 6e 74 73 20 2a 2f 0a 20  constraints */. 
1580: 20 20 20 20 20 75 31 36 20 6e 42 74 6d 3b 20 20       u16 nBtm;  
1590: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53              /* S
15a0: 69 7a 65 20 6f 66 20 42 54 4d 20 76 65 63 74 6f  ize of BTM vecto
15b0: 72 20 2a 2f 0a 20 20 20 20 20 20 75 31 36 20 6e  r */.      u16 n
15c0: 54 6f 70 3b 20 20 20 20 20 20 20 20 20 20 20 20  Top;            
15d0: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 54 4f 50    /* Size of TOP
15e0: 20 76 65 63 74 6f 72 20 2a 2f 0a 20 20 20 20 20   vector */.     
15f0: 20 49 6e 64 65 78 20 2a 70 49 6e 64 65 78 3b 20   Index *pIndex; 
1600: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78          /* Index
1610: 20 75 73 65 64 2c 20 6f 72 20 4e 55 4c 4c 20 2a   used, or NULL *
1620: 2f 0a 20 20 20 20 7d 20 62 74 72 65 65 3b 0a 20  /.    } btree;. 
1630: 20 20 20 73 74 72 75 63 74 20 7b 20 20 20 20 20     struct {     
1640: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 66            /* Inf
1650: 6f 72 6d 61 74 69 6f 6e 20 66 6f 72 20 76 69 72  ormation for vir
1660: 74 75 61 6c 20 74 61 62 6c 65 73 20 2a 2f 0a 20  tual tables */. 
1670: 20 20 20 20 20 69 6e 74 20 69 64 78 4e 75 6d 3b       int idxNum;
1680: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
1690: 6e 64 65 78 20 6e 75 6d 62 65 72 20 2a 2f 0a 20  ndex number */. 
16a0: 20 20 20 20 20 75 38 20 6e 65 65 64 46 72 65 65       u8 needFree
16b0: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54  ;           /* T
16c0: 72 75 65 20 69 66 20 73 71 6c 69 74 65 33 5f 66  rue if sqlite3_f
16d0: 72 65 65 28 69 64 78 53 74 72 29 20 69 73 20 6e  ree(idxStr) is n
16e0: 65 65 64 65 64 20 2a 2f 0a 20 20 20 20 20 20 69  eeded */.      i
16f0: 38 20 69 73 4f 72 64 65 72 65 64 3b 20 20 20 20  8 isOrdered;    
1700: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66        /* True if
1710: 20 73 61 74 69 73 66 69 65 73 20 4f 52 44 45 52   satisfies ORDER
1720: 20 42 59 20 2a 2f 0a 20 20 20 20 20 20 75 31 36   BY */.      u16
1730: 20 6f 6d 69 74 4d 61 73 6b 3b 20 20 20 20 20 20   omitMask;      
1740: 20 20 20 20 2f 2a 20 54 65 72 6d 73 20 74 68 61      /* Terms tha
1750: 74 20 6d 61 79 20 62 65 20 6f 6d 69 74 74 65 64  t may be omitted
1760: 20 2a 2f 0a 20 20 20 20 20 20 63 68 61 72 20 2a   */.      char *
1770: 69 64 78 53 74 72 3b 20 20 20 20 20 20 20 20 20  idxStr;         
1780: 20 2f 2a 20 49 6e 64 65 78 20 69 64 65 6e 74 69   /* Index identi
1790: 66 69 65 72 20 73 74 72 69 6e 67 20 2a 2f 0a 20  fier string */. 
17a0: 20 20 20 7d 20 76 74 61 62 3b 0a 20 20 7d 20 75     } vtab;.  } u
17b0: 3b 0a 20 20 75 33 32 20 77 73 46 6c 61 67 73 3b  ;.  u32 wsFlags;
17c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57 48 45            /* WHE
17d0: 52 45 5f 2a 20 66 6c 61 67 73 20 64 65 73 63 72  RE_* flags descr
17e0: 69 62 69 6e 67 20 74 68 65 20 70 6c 61 6e 20 2a  ibing the plan *
17f0: 2f 0a 20 20 75 31 36 20 6e 4c 54 65 72 6d 3b 20  /.  u16 nLTerm; 
1800: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1810: 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69  ber of entries i
1820: 6e 20 61 4c 54 65 72 6d 5b 5d 20 2a 2f 0a 20 20  n aLTerm[] */.  
1830: 75 31 36 20 6e 53 6b 69 70 3b 20 20 20 20 20 20  u16 nSkip;      
1840: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
1850: 6f 66 20 4e 55 4c 4c 20 61 4c 54 65 72 6d 5b 5d  of NULL aLTerm[]
1860: 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20 2f 2a   entries */.  /*
1870: 2a 2a 2a 20 77 68 65 72 65 4c 6f 6f 70 58 66 65  *** whereLoopXfe
1880: 72 28 29 20 63 6f 70 69 65 73 20 66 69 65 6c 64  r() copies field
1890: 73 20 61 62 6f 76 65 20 2a 2a 2a 2a 2a 2a 2a 2a  s above ********
18a0: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f  ***************/
18b0: 0a 23 20 64 65 66 69 6e 65 20 57 48 45 52 45 5f  .# define WHERE_
18c0: 4c 4f 4f 50 5f 58 46 45 52 5f 53 5a 20 6f 66 66  LOOP_XFER_SZ off
18d0: 73 65 74 6f 66 28 57 68 65 72 65 4c 6f 6f 70 2c  setof(WhereLoop,
18e0: 6e 4c 53 6c 6f 74 29 0a 20 20 75 31 36 20 6e 4c  nLSlot).  u16 nL
18f0: 53 6c 6f 74 3b 20 20 20 20 20 20 20 20 20 20 20  Slot;           
1900: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 73 6c 6f  /* Number of slo
1910: 74 73 20 61 6c 6c 6f 63 61 74 65 64 20 66 6f 72  ts allocated for
1920: 20 61 4c 54 65 72 6d 5b 5d 20 2a 2f 0a 20 20 57   aLTerm[] */.  W
1930: 68 65 72 65 54 65 72 6d 20 2a 2a 61 4c 54 65 72  hereTerm **aLTer
1940: 6d 3b 20 20 20 2f 2a 20 57 68 65 72 65 54 65 72  m;   /* WhereTer
1950: 6d 73 20 75 73 65 64 20 2a 2f 0a 20 20 57 68 65  ms used */.  Whe
1960: 72 65 4c 6f 6f 70 20 2a 70 4e 65 78 74 4c 6f 6f  reLoop *pNextLoo
1970: 70 3b 20 2f 2a 20 4e 65 78 74 20 57 68 65 72 65  p; /* Next Where
1980: 4c 6f 6f 70 20 6f 62 6a 65 63 74 20 69 6e 20 74  Loop object in t
1990: 68 65 20 57 68 65 72 65 43 6c 61 75 73 65 20 2a  he WhereClause *
19a0: 2f 0a 20 20 57 68 65 72 65 54 65 72 6d 20 2a 61  /.  WhereTerm *a
19b0: 4c 54 65 72 6d 53 70 61 63 65 5b 33 5d 3b 20 20  LTermSpace[3];  
19c0: 2f 2a 20 49 6e 69 74 69 61 6c 20 61 4c 54 65 72  /* Initial aLTer
19d0: 6d 5b 5d 20 73 70 61 63 65 20 2a 2f 0a 7d 3b 0a  m[] space */.};.
19e0: 0a 2f 2a 20 54 68 69 73 20 6f 62 6a 65 63 74 20  ./* This object 
19f0: 68 6f 6c 64 73 20 74 68 65 20 70 72 65 72 65 71  holds the prereq
1a00: 75 69 73 69 74 65 73 20 61 6e 64 20 74 68 65 20  uisites and the 
1a10: 63 6f 73 74 20 6f 66 20 72 75 6e 6e 69 6e 67 20  cost of running 
1a20: 61 0a 2a 2a 20 73 75 62 71 75 65 72 79 20 6f 6e  a.** subquery on
1a30: 20 6f 6e 65 20 6f 70 65 72 61 6e 64 20 6f 66 20   one operand of 
1a40: 61 6e 20 4f 52 20 6f 70 65 72 61 74 6f 72 20 69  an OR operator i
1a50: 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75  n the WHERE clau
1a60: 73 65 2e 0a 2a 2a 20 53 65 65 20 57 68 65 72 65  se..** See Where
1a70: 4f 72 53 65 74 20 66 6f 72 20 61 64 64 69 74 69  OrSet for additi
1a80: 6f 6e 61 6c 20 69 6e 66 6f 72 6d 61 74 69 6f 6e  onal information
1a90: 20 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68 65 72   .*/.struct Wher
1aa0: 65 4f 72 43 6f 73 74 20 7b 0a 20 20 42 69 74 6d  eOrCost {.  Bitm
1ab0: 61 73 6b 20 70 72 65 72 65 71 3b 20 20 20 20 20  ask prereq;     
1ac0: 2f 2a 20 50 72 65 72 65 71 75 69 73 69 74 65 73  /* Prerequisites
1ad0: 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 72 52 75   */.  LogEst rRu
1ae0: 6e 3b 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 73  n;        /* Cos
1af0: 74 20 6f 66 20 72 75 6e 6e 69 6e 67 20 74 68 69  t of running thi
1b00: 73 20 73 75 62 71 75 65 72 79 20 2a 2f 0a 20 20  s subquery */.  
1b10: 4c 6f 67 45 73 74 20 6e 4f 75 74 3b 20 20 20 20  LogEst nOut;    
1b20: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
1b30: 20 6f 75 74 70 75 74 73 20 66 6f 72 20 74 68 69   outputs for thi
1b40: 73 20 73 75 62 71 75 65 72 79 20 2a 2f 0a 7d 3b  s subquery */.};
1b50: 0a 0a 2f 2a 20 54 68 65 20 57 68 65 72 65 4f 72  ../* The WhereOr
1b60: 53 65 74 20 6f 62 6a 65 63 74 20 68 6f 6c 64 73  Set object holds
1b70: 20 61 20 73 65 74 20 6f 66 20 70 6f 73 73 69 62   a set of possib
1b80: 6c 65 20 57 68 65 72 65 4f 72 43 6f 73 74 73 20  le WhereOrCosts 
1b90: 74 68 61 74 0a 2a 2a 20 63 6f 72 72 65 73 70 6f  that.** correspo
1ba0: 6e 64 20 74 6f 20 74 68 65 20 73 75 62 71 75 65  nd to the subque
1bb0: 72 79 28 73 29 20 6f 66 20 4f 52 2d 63 6c 61 75  ry(s) of OR-clau
1bc0: 73 65 20 70 72 6f 63 65 73 73 69 6e 67 2e 20 20  se processing.  
1bd0: 4f 6e 6c 79 20 74 68 65 0a 2a 2a 20 62 65 73 74  Only the.** best
1be0: 20 4e 5f 4f 52 5f 43 4f 53 54 20 65 6c 65 6d 65   N_OR_COST eleme
1bf0: 6e 74 73 20 61 72 65 20 72 65 74 61 69 6e 65 64  nts are retained
1c00: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4e 5f 4f  ..*/.#define N_O
1c10: 52 5f 43 4f 53 54 20 33 0a 73 74 72 75 63 74 20  R_COST 3.struct 
1c20: 57 68 65 72 65 4f 72 53 65 74 20 7b 0a 20 20 75  WhereOrSet {.  u
1c30: 31 36 20 6e 3b 20 20 20 20 20 20 20 20 20 20 20  16 n;           
1c40: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
1c50: 6d 62 65 72 20 6f 66 20 76 61 6c 69 64 20 61 5b  mber of valid a[
1c60: 5d 20 65 6e 74 72 69 65 73 20 2a 2f 0a 20 20 57  ] entries */.  W
1c70: 68 65 72 65 4f 72 43 6f 73 74 20 61 5b 4e 5f 4f  hereOrCost a[N_O
1c80: 52 5f 43 4f 53 54 5d 3b 20 20 20 2f 2a 20 53 65  R_COST];   /* Se
1c90: 74 20 6f 66 20 62 65 73 74 20 63 6f 73 74 73 20  t of best costs 
1ca0: 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 45 61 63  */.};../*.** Eac
1cb0: 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68  h instance of th
1cc0: 69 73 20 6f 62 6a 65 63 74 20 68 6f 6c 64 73 20  is object holds 
1cd0: 61 20 73 65 71 75 65 6e 63 65 20 6f 66 20 57 68  a sequence of Wh
1ce0: 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 73 0a  ereLoop objects.
1cf0: 2a 2a 20 74 68 61 74 20 69 6d 70 6c 65 6d 65 6e  ** that implemen
1d00: 74 20 73 6f 6d 65 20 6f 72 20 61 6c 6c 20 6f 66  t some or all of
1d10: 20 61 20 71 75 65 72 79 20 70 6c 61 6e 2e 0a 2a   a query plan..*
1d20: 2a 0a 2a 2a 20 54 68 69 6e 6b 20 6f 66 20 65 61  *.** Think of ea
1d30: 63 68 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a  ch WhereLoop obj
1d40: 65 63 74 20 61 73 20 61 20 6e 6f 64 65 20 69 6e  ect as a node in
1d50: 20 61 20 67 72 61 70 68 20 77 69 74 68 20 61 72   a graph with ar
1d60: 63 73 0a 2a 2a 20 73 68 6f 77 69 6e 67 20 64 65  cs.** showing de
1d70: 70 65 6e 64 65 6e 63 69 65 73 20 61 6e 64 20 63  pendencies and c
1d80: 6f 73 74 73 20 66 6f 72 20 74 72 61 76 65 6c 6c  osts for travell
1d90: 69 6e 67 20 62 65 74 77 65 65 6e 20 6e 6f 64 65  ing between node
1da0: 73 2e 20 20 28 54 68 61 74 20 69 73 0a 2a 2a 20  s.  (That is.** 
1db0: 6e 6f 74 20 61 20 63 6f 6d 70 6c 65 74 65 6c 79  not a completely
1dc0: 20 61 63 63 75 72 61 74 65 20 64 65 73 63 72 69   accurate descri
1dd0: 70 74 69 6f 6e 20 62 65 63 61 75 73 65 20 57 68  ption because Wh
1de0: 65 72 65 4c 6f 6f 70 20 63 6f 73 74 73 20 61 72  ereLoop costs ar
1df0: 65 20 61 0a 2a 2a 20 76 65 63 74 6f 72 2c 20 6e  e a.** vector, n
1e00: 6f 74 20 61 20 73 63 61 6c 61 72 2c 20 61 6e 64  ot a scalar, and
1e10: 20 62 65 63 61 75 73 65 20 64 65 70 65 6e 64 65   because depende
1e20: 6e 63 69 65 73 20 61 72 65 20 6d 61 6e 79 2d 74  ncies are many-t
1e30: 6f 2d 6f 6e 65 2c 20 6e 6f 74 0a 2a 2a 20 6f 6e  o-one, not.** on
1e40: 65 2d 74 6f 2d 6f 6e 65 20 61 73 20 61 72 65 20  e-to-one as are 
1e50: 67 72 61 70 68 20 6e 6f 64 65 73 2e 20 20 42 75  graph nodes.  Bu
1e60: 74 20 69 74 20 69 73 20 61 20 75 73 65 66 75 6c  t it is a useful
1e70: 20 76 69 73 75 61 6c 69 7a 61 74 69 6f 6e 20 61   visualization a
1e80: 69 64 2e 29 0a 2a 2a 20 54 68 65 6e 20 61 20 57  id.).** Then a W
1e90: 68 65 72 65 50 61 74 68 20 6f 62 6a 65 63 74 20  herePath object 
1ea0: 69 73 20 61 20 70 61 74 68 20 74 68 72 6f 75 67  is a path throug
1eb0: 68 20 74 68 65 20 67 72 61 70 68 20 74 68 61 74  h the graph that
1ec0: 20 76 69 73 69 74 73 20 73 6f 6d 65 0a 2a 2a 20   visits some.** 
1ed0: 6f 72 20 61 6c 6c 20 6f 66 20 74 68 65 20 57 68  or all of the Wh
1ee0: 65 72 65 4c 6f 6f 70 20 6f 62 6a 65 63 74 73 20  ereLoop objects 
1ef0: 6f 6e 63 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  once..**.** The 
1f00: 22 73 6f 6c 76 65 72 22 20 77 6f 72 6b 73 20 62  "solver" works b
1f10: 79 20 63 72 65 61 74 69 6e 67 20 74 68 65 20 4e  y creating the N
1f20: 20 62 65 73 74 20 57 68 65 72 65 50 61 74 68 20   best WherePath 
1f30: 6f 62 6a 65 63 74 73 20 6f 66 20 6c 65 6e 67 74  objects of lengt
1f40: 68 0a 2a 2a 20 31 2e 20 20 54 68 65 6e 20 75 73  h.** 1.  Then us
1f50: 69 6e 67 20 74 68 6f 73 65 20 61 73 20 61 20 62  ing those as a b
1f60: 61 73 69 73 20 74 6f 20 63 6f 6d 70 75 74 65 20  asis to compute 
1f70: 74 68 65 20 4e 20 62 65 73 74 20 57 68 65 72 65  the N best Where
1f80: 50 61 74 68 20 6f 62 6a 65 63 74 73 0a 2a 2a 20  Path objects.** 
1f90: 6f 66 20 6c 65 6e 67 74 68 20 32 2e 20 20 41 6e  of length 2.  An
1fa0: 64 20 73 6f 20 66 6f 72 74 68 20 75 6e 74 69 6c  d so forth until
1fb0: 20 74 68 65 20 6c 65 6e 67 74 68 20 6f 66 20 57   the length of W
1fc0: 68 65 72 65 50 61 74 68 73 20 65 71 75 61 6c 73  herePaths equals
1fd0: 20 74 68 65 0a 2a 2a 20 6e 75 6d 62 65 72 20 6f   the.** number o
1fe0: 66 20 6e 6f 64 65 73 20 69 6e 20 74 68 65 20 46  f nodes in the F
1ff0: 52 4f 4d 20 63 6c 61 75 73 65 2e 20 20 54 68 65  ROM clause.  The
2000: 20 62 65 73 74 20 28 6c 6f 77 65 73 74 20 63 6f   best (lowest co
2010: 73 74 29 20 57 68 65 72 65 50 61 74 68 0a 2a 2a  st) WherePath.**
2020: 20 61 74 20 74 68 65 20 65 6e 64 20 69 73 20 74   at the end is t
2030: 68 65 20 63 68 6f 73 65 6e 20 71 75 65 72 79 20  he chosen query 
2040: 70 6c 61 6e 2e 0a 2a 2f 0a 73 74 72 75 63 74 20  plan..*/.struct 
2050: 57 68 65 72 65 50 61 74 68 20 7b 0a 20 20 42 69  WherePath {.  Bi
2060: 74 6d 61 73 6b 20 6d 61 73 6b 4c 6f 6f 70 3b 20  tmask maskLoop; 
2070: 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b 20 6f      /* Bitmask o
2080: 66 20 61 6c 6c 20 57 68 65 72 65 4c 6f 6f 70 20  f all WhereLoop 
2090: 6f 62 6a 65 63 74 73 20 69 6e 20 74 68 69 73 20  objects in this 
20a0: 70 61 74 68 20 2a 2f 0a 20 20 42 69 74 6d 61 73  path */.  Bitmas
20b0: 6b 20 72 65 76 4c 6f 6f 70 3b 20 20 20 20 20 20  k revLoop;      
20c0: 2f 2a 20 61 4c 6f 6f 70 5b 5d 73 20 74 68 61 74  /* aLoop[]s that
20d0: 20 73 68 6f 75 6c 64 20 62 65 20 72 65 76 65 72   should be rever
20e0: 73 65 64 20 66 6f 72 20 4f 52 44 45 52 20 42 59  sed for ORDER BY
20f0: 20 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 6e 52 6f   */.  LogEst nRo
2100: 77 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 45  w;          /* E
2110: 73 74 69 6d 61 74 65 64 20 6e 75 6d 62 65 72 20  stimated number 
2120: 6f 66 20 72 6f 77 73 20 67 65 6e 65 72 61 74 65  of rows generate
2130: 64 20 62 79 20 74 68 69 73 20 70 61 74 68 20 2a  d by this path *
2140: 2f 0a 20 20 4c 6f 67 45 73 74 20 72 43 6f 73 74  /.  LogEst rCost
2150: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f 74  ;         /* Tot
2160: 61 6c 20 63 6f 73 74 20 6f 66 20 74 68 69 73 20  al cost of this 
2170: 70 61 74 68 20 2a 2f 0a 20 20 4c 6f 67 45 73 74  path */.  LogEst
2180: 20 72 55 6e 73 6f 72 74 65 64 3b 20 20 20 20 20   rUnsorted;     
2190: 2f 2a 20 54 6f 74 61 6c 20 63 6f 73 74 20 6f 66  /* Total cost of
21a0: 20 74 68 69 73 20 70 61 74 68 20 69 67 6e 6f 72   this path ignor
21b0: 69 6e 67 20 73 6f 72 74 69 6e 67 20 63 6f 73 74  ing sorting cost
21c0: 73 20 2a 2f 0a 20 20 69 38 20 69 73 4f 72 64 65  s */.  i8 isOrde
21d0: 72 65 64 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  red;         /* 
21e0: 4e 6f 2e 20 6f 66 20 4f 52 44 45 52 20 42 59 20  No. of ORDER BY 
21f0: 74 65 72 6d 73 20 73 61 74 69 73 66 69 65 64 2e  terms satisfied.
2200: 20 2d 31 20 66 6f 72 20 75 6e 6b 6e 6f 77 6e 20   -1 for unknown 
2210: 2a 2f 0a 20 20 57 68 65 72 65 4c 6f 6f 70 20 2a  */.  WhereLoop *
2220: 2a 61 4c 6f 6f 70 3b 20 20 20 20 2f 2a 20 41 72  *aLoop;    /* Ar
2230: 72 61 79 20 6f 66 20 57 68 65 72 65 4c 6f 6f 70  ray of WhereLoop
2240: 20 6f 62 6a 65 63 74 73 20 69 6d 70 6c 65 6d 65   objects impleme
2250: 6e 74 69 6e 67 20 74 68 69 73 20 70 61 74 68 20  nting this path 
2260: 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  */.};../*.** The
2270: 20 71 75 65 72 79 20 67 65 6e 65 72 61 74 6f 72   query generator
2280: 20 75 73 65 73 20 61 6e 20 61 72 72 61 79 20 6f   uses an array o
2290: 66 20 69 6e 73 74 61 6e 63 65 73 20 6f 66 20 74  f instances of t
22a0: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 74 6f  his structure to
22b0: 0a 2a 2a 20 68 65 6c 70 20 69 74 20 61 6e 61 6c  .** help it anal
22c0: 79 7a 65 20 74 68 65 20 73 75 62 65 78 70 72 65  yze the subexpre
22d0: 73 73 69 6f 6e 73 20 6f 66 20 74 68 65 20 57 48  ssions of the WH
22e0: 45 52 45 20 63 6c 61 75 73 65 2e 20 20 45 61 63  ERE clause.  Eac
22f0: 68 20 57 48 45 52 45 0a 2a 2a 20 63 6c 61 75 73  h WHERE.** claus
2300: 65 20 73 75 62 65 78 70 72 65 73 73 69 6f 6e 20  e subexpression 
2310: 69 73 20 73 65 70 61 72 61 74 65 64 20 66 72 6f  is separated fro
2320: 6d 20 74 68 65 20 6f 74 68 65 72 73 20 62 79 20  m the others by 
2330: 41 4e 44 20 6f 70 65 72 61 74 6f 72 73 2c 0a 2a  AND operators,.*
2340: 2a 20 75 73 75 61 6c 6c 79 2c 20 6f 72 20 73 6f  * usually, or so
2350: 6d 65 74 69 6d 65 73 20 73 75 62 65 78 70 72 65  metimes subexpre
2360: 73 73 69 6f 6e 73 20 73 65 70 61 72 61 74 65 64  ssions separated
2370: 20 62 79 20 4f 52 2e 0a 2a 2a 0a 2a 2a 20 41 6c   by OR..**.** Al
2380: 6c 20 57 68 65 72 65 54 65 72 6d 73 20 61 72 65  l WhereTerms are
2390: 20 63 6f 6c 6c 65 63 74 65 64 20 69 6e 74 6f 20   collected into 
23a0: 61 20 73 69 6e 67 6c 65 20 57 68 65 72 65 43 6c  a single WhereCl
23b0: 61 75 73 65 20 73 74 72 75 63 74 75 72 65 2e 20  ause structure. 
23c0: 20 0a 2a 2a 20 54 68 65 20 66 6f 6c 6c 6f 77 69   .** The followi
23d0: 6e 67 20 69 64 65 6e 74 69 74 79 20 68 6f 6c 64  ng identity hold
23e0: 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20  s:.**.**        
23f0: 57 68 65 72 65 54 65 72 6d 2e 70 57 43 2d 3e 61  WhereTerm.pWC->a
2400: 5b 57 68 65 72 65 54 65 72 6d 2e 69 64 78 5d 20  [WhereTerm.idx] 
2410: 3d 3d 20 57 68 65 72 65 54 65 72 6d 0a 2a 2a 0a  == WhereTerm.**.
2420: 2a 2a 20 57 68 65 6e 20 61 20 74 65 72 6d 20 69  ** When a term i
2430: 73 20 6f 66 20 74 68 65 20 66 6f 72 6d 3a 0a 2a  s of the form:.*
2440: 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  *.**            
2450: 20 20 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 0a    X <op> <expr>.
2460: 2a 2a 0a 2a 2a 20 77 68 65 72 65 20 58 20 69 73  **.** where X is
2470: 20 61 20 63 6f 6c 75 6d 6e 20 6e 61 6d 65 20 61   a column name a
2480: 6e 64 20 3c 6f 70 3e 20 69 73 20 6f 6e 65 20 6f  nd <op> is one o
2490: 66 20 63 65 72 74 61 69 6e 20 6f 70 65 72 61 74  f certain operat
24a0: 6f 72 73 2c 0a 2a 2a 20 74 68 65 6e 20 57 68 65  ors,.** then Whe
24b0: 72 65 54 65 72 6d 2e 6c 65 66 74 43 75 72 73 6f  reTerm.leftCurso
24c0: 72 20 61 6e 64 20 57 68 65 72 65 54 65 72 6d 2e  r and WhereTerm.
24d0: 75 2e 6c 65 66 74 43 6f 6c 75 6d 6e 20 72 65 63  u.leftColumn rec
24e0: 6f 72 64 20 74 68 65 0a 2a 2a 20 63 75 72 73 6f  ord the.** curso
24f0: 72 20 6e 75 6d 62 65 72 20 61 6e 64 20 63 6f 6c  r number and col
2500: 75 6d 6e 20 6e 75 6d 62 65 72 20 66 6f 72 20 58  umn number for X
2510: 2e 20 20 57 68 65 72 65 54 65 72 6d 2e 65 4f 70  .  WhereTerm.eOp
2520: 65 72 61 74 6f 72 20 72 65 63 6f 72 64 73 0a 2a  erator records.*
2530: 2a 20 74 68 65 20 3c 6f 70 3e 20 75 73 69 6e 67  * the <op> using
2540: 20 61 20 62 69 74 6d 61 73 6b 20 65 6e 63 6f 64   a bitmask encod
2550: 69 6e 67 20 64 65 66 69 6e 65 64 20 62 79 20 57  ing defined by W
2560: 4f 5f 78 78 78 20 62 65 6c 6f 77 2e 20 20 54 68  O_xxx below.  Th
2570: 65 0a 2a 2a 20 75 73 65 20 6f 66 20 61 20 62 69  e.** use of a bi
2580: 74 6d 61 73 6b 20 65 6e 63 6f 64 69 6e 67 20 66  tmask encoding f
2590: 6f 72 20 74 68 65 20 6f 70 65 72 61 74 6f 72 20  or the operator 
25a0: 61 6c 6c 6f 77 73 20 75 73 20 74 6f 20 73 65 61  allows us to sea
25b0: 72 63 68 0a 2a 2a 20 71 75 69 63 6b 6c 79 20 66  rch.** quickly f
25c0: 6f 72 20 74 65 72 6d 73 20 74 68 61 74 20 6d 61  or terms that ma
25d0: 74 63 68 20 61 6e 79 20 6f 66 20 73 65 76 65 72  tch any of sever
25e0: 61 6c 20 64 69 66 66 65 72 65 6e 74 20 6f 70 65  al different ope
25f0: 72 61 74 6f 72 73 2e 0a 2a 2a 0a 2a 2a 20 41 20  rators..**.** A 
2600: 57 68 65 72 65 54 65 72 6d 20 6d 69 67 68 74 20  WhereTerm might 
2610: 61 6c 73 6f 20 62 65 20 74 77 6f 20 6f 72 20 6d  also be two or m
2620: 6f 72 65 20 73 75 62 74 65 72 6d 73 20 63 6f 6e  ore subterms con
2630: 6e 65 63 74 65 64 20 62 79 20 4f 52 3a 0a 2a 2a  nected by OR:.**
2640: 0a 2a 2a 20 20 20 20 20 20 20 20 20 28 74 31 2e  .**         (t1.
2650: 58 20 3c 6f 70 3e 20 3c 65 78 70 72 3e 29 20 4f  X <op> <expr>) O
2660: 52 20 28 74 31 2e 59 20 3c 6f 70 3e 20 3c 65 78  R (t1.Y <op> <ex
2670: 70 72 3e 29 20 4f 52 20 2e 2e 2e 2e 0a 2a 2a 0a  pr>) OR .....**.
2680: 2a 2a 20 49 6e 20 74 68 69 73 20 73 65 63 6f 6e  ** In this secon
2690: 64 20 63 61 73 65 2c 20 77 74 46 6c 61 67 20 68  d case, wtFlag h
26a0: 61 73 20 74 68 65 20 54 45 52 4d 5f 4f 52 49 4e  as the TERM_ORIN
26b0: 46 4f 20 62 69 74 20 73 65 74 20 61 6e 64 20 65  FO bit set and e
26c0: 4f 70 65 72 61 74 6f 72 3d 3d 57 4f 5f 4f 52 0a  Operator==WO_OR.
26d0: 2a 2a 20 61 6e 64 20 74 68 65 20 57 68 65 72 65  ** and the Where
26e0: 54 65 72 6d 2e 75 2e 70 4f 72 49 6e 66 6f 20 66  Term.u.pOrInfo f
26f0: 69 65 6c 64 20 70 6f 69 6e 74 73 20 74 6f 20 61  ield points to a
2700: 75 78 69 6c 69 61 72 79 20 69 6e 66 6f 72 6d 61  uxiliary informa
2710: 74 69 6f 6e 20 74 68 61 74 0a 2a 2a 20 69 73 20  tion that.** is 
2720: 63 6f 6c 6c 65 63 74 65 64 20 61 62 6f 75 74 20  collected about 
2730: 74 68 65 20 4f 52 20 63 6c 61 75 73 65 2e 0a 2a  the OR clause..*
2740: 2a 0a 2a 2a 20 49 66 20 61 20 74 65 72 6d 20 69  *.** If a term i
2750: 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75  n the WHERE clau
2760: 73 65 20 64 6f 65 73 20 6e 6f 74 20 6d 61 74 63  se does not matc
2770: 68 20 65 69 74 68 65 72 20 6f 66 20 74 68 65 20  h either of the 
2780: 74 77 6f 20 70 72 65 76 69 6f 75 73 0a 2a 2a 20  two previous.** 
2790: 63 61 74 65 67 6f 72 69 65 73 2c 20 74 68 65 6e  categories, then
27a0: 20 65 4f 70 65 72 61 74 6f 72 3d 3d 30 2e 20 20   eOperator==0.  
27b0: 54 68 65 20 57 68 65 72 65 54 65 72 6d 2e 70 45  The WhereTerm.pE
27c0: 78 70 72 20 66 69 65 6c 64 20 69 73 20 73 74 69  xpr field is sti
27d0: 6c 6c 20 73 65 74 0a 2a 2a 20 74 6f 20 74 68 65  ll set.** to the
27e0: 20 6f 72 69 67 69 6e 61 6c 20 73 75 62 65 78 70   original subexp
27f0: 72 65 73 73 69 6f 6e 20 63 6f 6e 74 65 6e 74 20  ression content 
2800: 61 6e 64 20 77 74 46 6c 61 67 73 20 69 73 20 73  and wtFlags is s
2810: 65 74 20 75 70 20 61 70 70 72 6f 70 72 69 61 74  et up appropriat
2820: 65 6c 79 0a 2a 2a 20 62 75 74 20 6e 6f 20 6f 74  ely.** but no ot
2830: 68 65 72 20 66 69 65 6c 64 73 20 69 6e 20 74 68  her fields in th
2840: 65 20 57 68 65 72 65 54 65 72 6d 20 6f 62 6a 65  e WhereTerm obje
2850: 63 74 20 61 72 65 20 6d 65 61 6e 69 6e 67 66 75  ct are meaningfu
2860: 6c 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20 65 4f  l..**.** When eO
2870: 70 65 72 61 74 6f 72 21 3d 30 2c 20 70 72 65 72  perator!=0, prer
2880: 65 71 52 69 67 68 74 20 61 6e 64 20 70 72 65 72  eqRight and prer
2890: 65 71 41 6c 6c 20 72 65 63 6f 72 64 20 73 65 74  eqAll record set
28a0: 73 20 6f 66 20 63 75 72 73 6f 72 20 6e 75 6d 62  s of cursor numb
28b0: 65 72 73 2c 0a 2a 2a 20 62 75 74 20 74 68 65 79  ers,.** but they
28c0: 20 64 6f 20 73 6f 20 69 6e 64 69 72 65 63 74 6c   do so indirectl
28d0: 79 2e 20 20 41 20 73 69 6e 67 6c 65 20 57 68 65  y.  A single Whe
28e0: 72 65 4d 61 73 6b 53 65 74 20 73 74 72 75 63 74  reMaskSet struct
28f0: 75 72 65 20 74 72 61 6e 73 6c 61 74 65 73 0a 2a  ure translates.*
2900: 2a 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 20  * cursor number 
2910: 69 6e 74 6f 20 62 69 74 73 20 61 6e 64 20 74 68  into bits and th
2920: 65 20 74 72 61 6e 73 6c 61 74 65 64 20 62 69 74  e translated bit
2930: 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20 74 68   is stored in th
2940: 65 20 70 72 65 72 65 71 0a 2a 2a 20 66 69 65 6c  e prereq.** fiel
2950: 64 73 2e 20 20 54 68 65 20 74 72 61 6e 73 6c 61  ds.  The transla
2960: 74 69 6f 6e 20 69 73 20 75 73 65 64 20 69 6e 20  tion is used in 
2970: 6f 72 64 65 72 20 74 6f 20 6d 61 78 69 6d 69 7a  order to maximiz
2980: 65 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a  e the number of.
2990: 2a 2a 20 62 69 74 73 20 74 68 61 74 20 77 69 6c  ** bits that wil
29a0: 6c 20 66 69 74 20 69 6e 20 61 20 42 69 74 6d 61  l fit in a Bitma
29b0: 73 6b 2e 20 20 54 68 65 20 56 44 42 45 20 63 75  sk.  The VDBE cu
29c0: 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 6d 69 67  rsor numbers mig
29d0: 68 74 20 62 65 0a 2a 2a 20 73 70 72 65 61 64 20  ht be.** spread 
29e0: 6f 75 74 20 6f 76 65 72 20 74 68 65 20 6e 6f 6e  out over the non
29f0: 2d 6e 65 67 61 74 69 76 65 20 69 6e 74 65 67 65  -negative intege
2a00: 72 73 2e 20 20 46 6f 72 20 65 78 61 6d 70 6c 65  rs.  For example
2a10: 2c 20 74 68 65 20 63 75 72 73 6f 72 0a 2a 2a 20  , the cursor.** 
2a20: 6e 75 6d 62 65 72 73 20 6d 69 67 68 74 20 62 65  numbers might be
2a30: 20 33 2c 20 38 2c 20 39 2c 20 31 30 2c 20 32 30   3, 8, 9, 10, 20
2a40: 2c 20 32 33 2c 20 34 31 2c 20 61 6e 64 20 34 35  , 23, 41, and 45
2a50: 2e 20 20 54 68 65 20 57 68 65 72 65 4d 61 73 6b  .  The WhereMask
2a60: 53 65 74 0a 2a 2a 20 74 72 61 6e 73 6c 61 74 65  Set.** translate
2a70: 73 20 74 68 65 73 65 20 73 70 61 72 73 65 20 63  s these sparse c
2a80: 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 69 6e  ursor numbers in
2a90: 74 6f 20 63 6f 6e 73 65 63 75 74 69 76 65 20 69  to consecutive i
2aa0: 6e 74 65 67 65 72 73 0a 2a 2a 20 62 65 67 69 6e  ntegers.** begin
2ab0: 6e 69 6e 67 20 77 69 74 68 20 30 20 69 6e 20 6f  ning with 0 in o
2ac0: 72 64 65 72 20 74 6f 20 6d 61 6b 65 20 74 68 65  rder to make the
2ad0: 20 62 65 73 74 20 70 6f 73 73 69 62 6c 65 20 75   best possible u
2ae0: 73 65 20 6f 66 20 74 68 65 20 61 76 61 69 6c 61  se of the availa
2af0: 62 6c 65 0a 2a 2a 20 62 69 74 73 20 69 6e 20 74  ble.** bits in t
2b00: 68 65 20 42 69 74 6d 61 73 6b 2e 20 20 53 6f 2c  he Bitmask.  So,
2b10: 20 69 6e 20 74 68 65 20 65 78 61 6d 70 6c 65 20   in the example 
2b20: 61 62 6f 76 65 2c 20 74 68 65 20 63 75 72 73 6f  above, the curso
2b30: 72 20 6e 75 6d 62 65 72 73 0a 2a 2a 20 77 6f 75  r numbers.** wou
2b40: 6c 64 20 62 65 20 6d 61 70 70 65 64 20 69 6e 74  ld be mapped int
2b50: 6f 20 69 6e 74 65 67 65 72 73 20 30 20 74 68 72  o integers 0 thr
2b60: 6f 75 67 68 20 37 2e 0a 2a 2a 0a 2a 2a 20 54 68  ough 7..**.** Th
2b70: 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 65 72 6d  e number of term
2b80: 73 20 69 6e 20 61 20 6a 6f 69 6e 20 69 73 20 6c  s in a join is l
2b90: 69 6d 69 74 65 64 20 62 79 20 74 68 65 20 6e 75  imited by the nu
2ba0: 6d 62 65 72 20 6f 66 20 62 69 74 73 0a 2a 2a 20  mber of bits.** 
2bb0: 69 6e 20 70 72 65 72 65 71 52 69 67 68 74 20 61  in prereqRight a
2bc0: 6e 64 20 70 72 65 72 65 71 41 6c 6c 2e 20 20 54  nd prereqAll.  T
2bd0: 68 65 20 64 65 66 61 75 6c 74 20 69 73 20 36 34  he default is 64
2be0: 20 62 69 74 73 2c 20 68 65 6e 63 65 20 53 51 4c   bits, hence SQL
2bf0: 69 74 65 0a 2a 2a 20 69 73 20 6f 6e 6c 79 20 61  ite.** is only a
2c00: 62 6c 65 20 74 6f 20 70 72 6f 63 65 73 73 20 6a  ble to process j
2c10: 6f 69 6e 73 20 77 69 74 68 20 36 34 20 6f 72 20  oins with 64 or 
2c20: 66 65 77 65 72 20 74 61 62 6c 65 73 2e 0a 2a 2f  fewer tables..*/
2c30: 0a 73 74 72 75 63 74 20 57 68 65 72 65 54 65 72  .struct WhereTer
2c40: 6d 20 7b 0a 20 20 45 78 70 72 20 2a 70 45 78 70  m {.  Expr *pExp
2c50: 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  r;            /*
2c60: 20 50 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   Pointer to the 
2c70: 73 75 62 65 78 70 72 65 73 73 69 6f 6e 20 74 68  subexpression th
2c80: 61 74 20 69 73 20 74 68 69 73 20 74 65 72 6d 20  at is this term 
2c90: 2a 2f 0a 20 20 57 68 65 72 65 43 6c 61 75 73 65  */.  WhereClause
2ca0: 20 2a 70 57 43 3b 20 20 20 20 20 20 20 2f 2a 20   *pWC;       /* 
2cb0: 54 68 65 20 63 6c 61 75 73 65 20 74 68 69 73 20  The clause this 
2cc0: 74 65 72 6d 20 69 73 20 70 61 72 74 20 6f 66 20  term is part of 
2cd0: 2a 2f 0a 20 20 4c 6f 67 45 73 74 20 74 72 75 74  */.  LogEst trut
2ce0: 68 50 72 6f 62 3b 20 20 20 20 20 20 20 2f 2a 20  hProb;       /* 
2cf0: 50 72 6f 62 61 62 69 6c 69 74 79 20 6f 66 20 74  Probability of t
2d00: 72 75 74 68 20 66 6f 72 20 74 68 69 73 20 65 78  ruth for this ex
2d10: 70 72 65 73 73 69 6f 6e 20 2a 2f 0a 20 20 75 31  pression */.  u1
2d20: 36 20 77 74 46 6c 61 67 73 3b 20 20 20 20 20 20  6 wtFlags;      
2d30: 20 20 20 20 20 20 2f 2a 20 54 45 52 4d 5f 78 78        /* TERM_xx
2d40: 78 20 62 69 74 20 66 6c 61 67 73 2e 20 20 53 65  x bit flags.  Se
2d50: 65 20 62 65 6c 6f 77 20 2a 2f 0a 20 20 75 31 36  e below */.  u16
2d60: 20 65 4f 70 65 72 61 74 6f 72 3b 20 20 20 20 20   eOperator;     
2d70: 20 20 20 20 20 2f 2a 20 41 20 57 4f 5f 78 78 20       /* A WO_xx 
2d80: 76 61 6c 75 65 20 64 65 73 63 72 69 62 69 6e 67  value describing
2d90: 20 3c 6f 70 3e 20 2a 2f 0a 20 20 75 38 20 6e 43   <op> */.  u8 nC
2da0: 68 69 6c 64 3b 20 20 20 20 20 20 20 20 20 20 20  hild;           
2db0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
2dc0: 63 68 69 6c 64 72 65 6e 20 74 68 61 74 20 6d 75  children that mu
2dd0: 73 74 20 64 69 73 61 62 6c 65 20 75 73 20 2a 2f  st disable us */
2de0: 0a 20 20 75 38 20 65 4d 61 74 63 68 4f 70 3b 20  .  u8 eMatchOp; 
2df0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 70             /* Op
2e00: 20 66 6f 72 20 76 74 61 62 20 4d 41 54 43 48 2f   for vtab MATCH/
2e10: 4c 49 4b 45 2f 47 4c 4f 42 2f 52 45 47 45 58 50  LIKE/GLOB/REGEXP
2e20: 20 74 65 72 6d 73 20 2a 2f 0a 20 20 69 6e 74 20   terms */.  int 
2e30: 69 50 61 72 65 6e 74 3b 20 20 20 20 20 20 20 20  iParent;        
2e40: 20 20 20 20 2f 2a 20 44 69 73 61 62 6c 65 20 70      /* Disable p
2e50: 57 43 2d 3e 61 5b 69 50 61 72 65 6e 74 5d 20 77  WC->a[iParent] w
2e60: 68 65 6e 20 74 68 69 73 20 74 65 72 6d 20 64 69  hen this term di
2e70: 73 61 62 6c 65 64 20 2a 2f 0a 20 20 69 6e 74 20  sabled */.  int 
2e80: 6c 65 66 74 43 75 72 73 6f 72 3b 20 20 20 20 20  leftCursor;     
2e90: 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 20 6e 75      /* Cursor nu
2ea0: 6d 62 65 72 20 6f 66 20 58 20 69 6e 20 22 58 20  mber of X in "X 
2eb0: 3c 6f 70 3e 20 3c 65 78 70 72 3e 22 20 2a 2f 0a  <op> <expr>" */.
2ec0: 20 20 69 6e 74 20 69 46 69 65 6c 64 3b 20 20 20    int iField;   
2ed0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 69 65            /* Fie
2ee0: 6c 64 20 69 6e 20 28 3f 2c 3f 2c 3f 29 20 49 4e  ld in (?,?,?) IN
2ef0: 20 28 53 45 4c 45 43 54 2e 2e 2e 29 20 76 65 63   (SELECT...) vec
2f00: 74 6f 72 20 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b  tor */.  union {
2f10: 0a 20 20 20 20 69 6e 74 20 6c 65 66 74 43 6f 6c  .    int leftCol
2f20: 75 6d 6e 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  umn;         /* 
2f30: 43 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20 6f 66  Column number of
2f40: 20 58 20 69 6e 20 22 58 20 3c 6f 70 3e 20 3c 65   X in "X <op> <e
2f50: 78 70 72 3e 22 20 2a 2f 0a 20 20 20 20 57 68 65  xpr>" */.    Whe
2f60: 72 65 4f 72 49 6e 66 6f 20 2a 70 4f 72 49 6e 66  reOrInfo *pOrInf
2f70: 6f 3b 20 20 20 2f 2a 20 45 78 74 72 61 20 69 6e  o;   /* Extra in
2f80: 66 6f 72 6d 61 74 69 6f 6e 20 69 66 20 28 65 4f  formation if (eO
2f90: 70 65 72 61 74 6f 72 20 26 20 57 4f 5f 4f 52 29  perator & WO_OR)
2fa0: 21 3d 30 20 2a 2f 0a 20 20 20 20 57 68 65 72 65  !=0 */.    Where
2fb0: 41 6e 64 49 6e 66 6f 20 2a 70 41 6e 64 49 6e 66  AndInfo *pAndInf
2fc0: 6f 3b 20 2f 2a 20 45 78 74 72 61 20 69 6e 66 6f  o; /* Extra info
2fd0: 72 6d 61 74 69 6f 6e 20 69 66 20 28 65 4f 70 65  rmation if (eOpe
2fe0: 72 61 74 6f 72 26 20 57 4f 5f 41 4e 44 29 21 3d  rator& WO_AND)!=
2ff0: 30 20 2a 2f 0a 20 20 7d 20 75 3b 0a 20 20 42 69  0 */.  } u;.  Bi
3000: 74 6d 61 73 6b 20 70 72 65 72 65 71 52 69 67 68  tmask prereqRigh
3010: 74 3b 20 20 20 20 2f 2a 20 42 69 74 6d 61 73 6b  t;    /* Bitmask
3020: 20 6f 66 20 74 61 62 6c 65 73 20 75 73 65 64 20   of tables used 
3030: 62 79 20 70 45 78 70 72 2d 3e 70 52 69 67 68 74  by pExpr->pRight
3040: 20 2a 2f 0a 20 20 42 69 74 6d 61 73 6b 20 70 72   */.  Bitmask pr
3050: 65 72 65 71 41 6c 6c 3b 20 20 20 20 20 20 2f 2a  ereqAll;      /*
3060: 20 42 69 74 6d 61 73 6b 20 6f 66 20 74 61 62 6c   Bitmask of tabl
3070: 65 73 20 72 65 66 65 72 65 6e 63 65 64 20 62 79  es referenced by
3080: 20 70 45 78 70 72 20 2a 2f 0a 7d 3b 0a 0a 2f 2a   pExpr */.};../*
3090: 0a 2a 2a 20 41 6c 6c 6f 77 65 64 20 76 61 6c 75  .** Allowed valu
30a0: 65 73 20 6f 66 20 57 68 65 72 65 54 65 72 6d 2e  es of WhereTerm.
30b0: 77 74 46 6c 61 67 73 0a 2a 2f 0a 23 64 65 66 69  wtFlags.*/.#defi
30c0: 6e 65 20 54 45 52 4d 5f 44 59 4e 41 4d 49 43 20  ne TERM_DYNAMIC 
30d0: 20 20 20 30 78 30 31 20 20 20 2f 2a 20 4e 65 65     0x01   /* Nee
30e0: 64 20 74 6f 20 63 61 6c 6c 20 73 71 6c 69 74 65  d to call sqlite
30f0: 33 45 78 70 72 44 65 6c 65 74 65 28 64 62 2c 20  3ExprDelete(db, 
3100: 70 45 78 70 72 29 20 2a 2f 0a 23 64 65 66 69 6e  pExpr) */.#defin
3110: 65 20 54 45 52 4d 5f 56 49 52 54 55 41 4c 20 20  e TERM_VIRTUAL  
3120: 20 20 30 78 30 32 20 20 20 2f 2a 20 41 64 64 65    0x02   /* Adde
3130: 64 20 62 79 20 74 68 65 20 6f 70 74 69 6d 69 7a  d by the optimiz
3140: 65 72 2e 20 20 44 6f 20 6e 6f 74 20 63 6f 64 65  er.  Do not code
3150: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d   */.#define TERM
3160: 5f 43 4f 44 45 44 20 20 20 20 20 20 30 78 30 34  _CODED      0x04
3170: 20 20 20 2f 2a 20 54 68 69 73 20 74 65 72 6d 20     /* This term 
3180: 69 73 20 61 6c 72 65 61 64 79 20 63 6f 64 65 64  is already coded
3190: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d   */.#define TERM
31a0: 5f 43 4f 50 49 45 44 20 20 20 20 20 30 78 30 38  _COPIED     0x08
31b0: 20 20 20 2f 2a 20 48 61 73 20 61 20 63 68 69 6c     /* Has a chil
31c0: 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52  d */.#define TER
31d0: 4d 5f 4f 52 49 4e 46 4f 20 20 20 20 20 30 78 31  M_ORINFO     0x1
31e0: 30 20 20 20 2f 2a 20 4e 65 65 64 20 74 6f 20 66  0   /* Need to f
31f0: 72 65 65 20 74 68 65 20 57 68 65 72 65 54 65 72  ree the WhereTer
3200: 6d 2e 75 2e 70 4f 72 49 6e 66 6f 20 6f 62 6a 65  m.u.pOrInfo obje
3210: 63 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45  ct */.#define TE
3220: 52 4d 5f 41 4e 44 49 4e 46 4f 20 20 20 20 30 78  RM_ANDINFO    0x
3230: 32 30 20 20 20 2f 2a 20 4e 65 65 64 20 74 6f 20  20   /* Need to 
3240: 66 72 65 65 20 74 68 65 20 57 68 65 72 65 54 65  free the WhereTe
3250: 72 6d 2e 75 2e 70 41 6e 64 49 6e 66 6f 20 6f 62  rm.u.pAndInfo ob
3260: 6a 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52  j */.#define TER
3270: 4d 5f 4f 52 5f 4f 4b 20 20 20 20 20 20 30 78 34  M_OR_OK      0x4
3280: 30 20 20 20 2f 2a 20 55 73 65 64 20 64 75 72 69  0   /* Used duri
3290: 6e 67 20 4f 52 2d 63 6c 61 75 73 65 20 70 72 6f  ng OR-clause pro
32a0: 63 65 73 73 69 6e 67 20 2a 2f 0a 23 69 66 64 65  cessing */.#ifde
32b0: 66 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f  f SQLITE_ENABLE_
32c0: 53 54 41 54 33 5f 4f 52 5f 53 54 41 54 34 0a 23  STAT3_OR_STAT4.#
32d0: 20 20 64 65 66 69 6e 65 20 54 45 52 4d 5f 56 4e    define TERM_VN
32e0: 55 4c 4c 20 20 20 20 30 78 38 30 20 20 20 2f 2a  ULL    0x80   /*
32f0: 20 4d 61 6e 75 66 61 63 74 75 72 65 64 20 78 3e   Manufactured x>
3300: 4e 55 4c 4c 20 6f 72 20 78 3c 3d 4e 55 4c 4c 20  NULL or x<=NULL 
3310: 74 65 72 6d 20 2a 2f 0a 23 65 6c 73 65 0a 23 20  term */.#else.# 
3320: 20 64 65 66 69 6e 65 20 54 45 52 4d 5f 56 4e 55   define TERM_VNU
3330: 4c 4c 20 20 20 20 30 78 30 30 20 20 20 2f 2a 20  LL    0x00   /* 
3340: 44 69 73 61 62 6c 65 64 20 69 66 20 6e 6f 74 20  Disabled if not 
3350: 75 73 69 6e 67 20 73 74 61 74 33 20 2a 2f 0a 23  using stat3 */.#
3360: 65 6e 64 69 66 0a 23 64 65 66 69 6e 65 20 54 45  endif.#define TE
3370: 52 4d 5f 4c 49 4b 45 4f 50 54 20 20 20 20 30 78  RM_LIKEOPT    0x
3380: 31 30 30 20 20 2f 2a 20 56 69 72 74 75 61 6c 20  100  /* Virtual 
3390: 74 65 72 6d 73 20 66 72 6f 6d 20 74 68 65 20 4c  terms from the L
33a0: 49 4b 45 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e  IKE optimization
33b0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 54 45 52 4d   */.#define TERM
33c0: 5f 4c 49 4b 45 43 4f 4e 44 20 20 20 30 78 32 30  _LIKECOND   0x20
33d0: 30 20 20 2f 2a 20 43 6f 6e 64 69 74 69 6f 6e 61  0  /* Conditiona
33e0: 6c 6c 79 20 74 68 69 73 20 4c 49 4b 45 20 6f 70  lly this LIKE op
33f0: 65 72 61 74 6f 72 20 74 65 72 6d 20 2a 2f 0a 23  erator term */.#
3400: 64 65 66 69 6e 65 20 54 45 52 4d 5f 4c 49 4b 45  define TERM_LIKE
3410: 20 20 20 20 20 20 20 30 78 34 30 30 20 20 2f 2a         0x400  /*
3420: 20 54 68 65 20 6f 72 69 67 69 6e 61 6c 20 4c 49   The original LI
3430: 4b 45 20 6f 70 65 72 61 74 6f 72 20 2a 2f 0a 23  KE operator */.#
3440: 64 65 66 69 6e 65 20 54 45 52 4d 5f 49 53 20 20  define TERM_IS  
3450: 20 20 20 20 20 20 20 30 78 38 30 30 20 20 2f 2a         0x800  /*
3460: 20 54 65 72 6d 2e 70 45 78 70 72 20 69 73 20 61   Term.pExpr is a
3470: 6e 20 49 53 20 6f 70 65 72 61 74 6f 72 20 2a 2f  n IS operator */
3480: 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61  ../*.** An insta
3490: 6e 63 65 20 6f 66 20 74 68 65 20 57 68 65 72 65  nce of the Where
34a0: 53 63 61 6e 20 6f 62 6a 65 63 74 20 69 73 20 75  Scan object is u
34b0: 73 65 64 20 61 73 20 61 6e 20 69 74 65 72 61 74  sed as an iterat
34c0: 6f 72 20 66 6f 72 20 6c 6f 63 61 74 69 6e 67 0a  or for locating.
34d0: 2a 2a 20 74 65 72 6d 73 20 69 6e 20 74 68 65 20  ** terms in the 
34e0: 57 48 45 52 45 20 63 6c 61 75 73 65 20 74 68 61  WHERE clause tha
34f0: 74 20 61 72 65 20 75 73 65 66 75 6c 20 74 6f 20  t are useful to 
3500: 74 68 65 20 71 75 65 72 79 20 70 6c 61 6e 6e 65  the query planne
3510: 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 57 68 65  r..*/.struct Whe
3520: 72 65 53 63 61 6e 20 7b 0a 20 20 57 68 65 72 65  reScan {.  Where
3530: 43 6c 61 75 73 65 20 2a 70 4f 72 69 67 57 43 3b  Clause *pOrigWC;
3540: 20 20 20 20 20 20 2f 2a 20 4f 72 69 67 69 6e 61        /* Origina
3550: 6c 2c 20 69 6e 6e 65 72 6d 6f 73 74 20 57 68 65  l, innermost Whe
3560: 72 65 43 6c 61 75 73 65 20 2a 2f 0a 20 20 57 68  reClause */.  Wh
3570: 65 72 65 43 6c 61 75 73 65 20 2a 70 57 43 3b 20  ereClause *pWC; 
3580: 20 20 20 20 20 20 20 20 20 2f 2a 20 57 68 65 72           /* Wher
3590: 65 43 6c 61 75 73 65 20 63 75 72 72 65 6e 74 6c  eClause currentl
35a0: 79 20 62 65 69 6e 67 20 73 63 61 6e 6e 65 64 20  y being scanned 
35b0: 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20  */.  const char 
35c0: 2a 7a 43 6f 6c 6c 4e 61 6d 65 3b 20 20 20 20 20  *zCollName;     
35d0: 2f 2a 20 52 65 71 75 69 72 65 64 20 63 6f 6c 6c  /* Required coll
35e0: 61 74 69 6e 67 20 73 65 71 75 65 6e 63 65 2c 20  ating sequence, 
35f0: 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a 2f 0a 20  if not NULL */. 
3600: 20 45 78 70 72 20 2a 70 49 64 78 45 78 70 72 3b   Expr *pIdxExpr;
3610: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53              /* S
3620: 65 61 72 63 68 20 66 6f 72 20 74 68 69 73 20 69  earch for this i
3630: 6e 64 65 78 20 65 78 70 72 65 73 73 69 6f 6e 20  ndex expression 
3640: 2a 2f 0a 20 20 63 68 61 72 20 69 64 78 61 66 66  */.  char idxaff
3650: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
3660: 2f 2a 20 4d 75 73 74 20 6d 61 74 63 68 20 74 68  /* Must match th
3670: 69 73 20 61 66 66 69 6e 69 74 79 2c 20 69 66 20  is affinity, if 
3680: 7a 43 6f 6c 6c 4e 61 6d 65 21 3d 4e 55 4c 4c 20  zCollName!=NULL 
3690: 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 63 68  */.  unsigned ch
36a0: 61 72 20 6e 45 71 75 69 76 3b 20 20 20 20 20 20  ar nEquiv;      
36b0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6e 74  /* Number of ent
36c0: 72 69 65 73 20 69 6e 20 61 45 71 75 69 76 5b 5d  ries in aEquiv[]
36d0: 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 63   */.  unsigned c
36e0: 68 61 72 20 69 45 71 75 69 76 3b 20 20 20 20 20  har iEquiv;     
36f0: 20 2f 2a 20 4e 65 78 74 20 75 6e 75 73 65 64 20   /* Next unused 
3700: 73 6c 6f 74 20 69 6e 20 61 45 71 75 69 76 5b 5d  slot in aEquiv[]
3710: 20 2a 2f 0a 20 20 75 33 32 20 6f 70 4d 61 73 6b   */.  u32 opMask
3720: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
3730: 20 2f 2a 20 41 63 63 65 70 74 61 62 6c 65 20 6f   /* Acceptable o
3740: 70 65 72 61 74 6f 72 73 20 2a 2f 0a 20 20 69 6e  perators */.  in
3750: 74 20 6b 3b 20 20 20 20 20 20 20 20 20 20 20 20  t k;            
3760: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 65 73 75           /* Resu
3770: 6d 65 20 73 63 61 6e 6e 69 6e 67 20 61 74 20 74  me scanning at t
3780: 68 69 73 2d 3e 70 57 43 2d 3e 61 5b 74 68 69 73  his->pWC->a[this
3790: 2d 3e 6b 5d 20 2a 2f 0a 20 20 69 6e 74 20 61 69  ->k] */.  int ai
37a0: 43 75 72 5b 31 31 5d 3b 20 20 20 20 20 20 20 20  Cur[11];        
37b0: 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 73 20       /* Cursors 
37c0: 69 6e 20 74 68 65 20 65 71 75 69 76 61 6c 65 6e  in the equivalen
37d0: 63 65 20 63 6c 61 73 73 20 2a 2f 0a 20 20 69 31  ce class */.  i1
37e0: 36 20 61 69 43 6f 6c 75 6d 6e 5b 31 31 5d 3b 20  6 aiColumn[11]; 
37f0: 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 72 72           /* Corr
3800: 65 73 70 6f 6e 64 69 6e 67 20 63 6f 6c 75 6d 6e  esponding column
3810: 20 6e 75 6d 62 65 72 20 69 6e 20 74 68 65 20 65   number in the e
3820: 71 2d 63 6c 61 73 73 20 2a 2f 0a 7d 3b 0a 0a 2f  q-class */.};../
3830: 2a 0a 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65  *.** An instance
3840: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
3850: 67 20 73 74 72 75 63 74 75 72 65 20 68 6f 6c 64  g structure hold
3860: 73 20 61 6c 6c 20 69 6e 66 6f 72 6d 61 74 69 6f  s all informatio
3870: 6e 20 61 62 6f 75 74 20 61 0a 2a 2a 20 57 48 45  n about a.** WHE
3880: 52 45 20 63 6c 61 75 73 65 2e 20 20 4d 6f 73 74  RE clause.  Most
3890: 6c 79 20 74 68 69 73 20 69 73 20 61 20 63 6f 6e  ly this is a con
38a0: 74 61 69 6e 65 72 20 66 6f 72 20 6f 6e 65 20 6f  tainer for one o
38b0: 72 20 6d 6f 72 65 20 57 68 65 72 65 54 65 72 6d  r more WhereTerm
38c0: 73 2e 0a 2a 2a 0a 2a 2a 20 45 78 70 6c 61 6e 61  s..**.** Explana
38d0: 74 69 6f 6e 20 6f 66 20 70 4f 75 74 65 72 3a 20  tion of pOuter: 
38e0: 20 46 6f 72 20 61 20 57 48 45 52 45 20 63 6c 61   For a WHERE cla
38f0: 75 73 65 20 6f 66 20 74 68 65 20 66 6f 72 6d 0a  use of the form.
3900: 2a 2a 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20  **.**           
3910: 61 20 41 4e 44 20 28 28 62 20 41 4e 44 20 63 29  a AND ((b AND c)
3920: 20 4f 52 20 28 64 20 41 4e 44 20 65 29 29 20 41   OR (d AND e)) A
3930: 4e 44 20 66 0a 2a 2a 0a 2a 2a 20 54 68 65 72 65  ND f.**.** There
3940: 20 61 72 65 20 73 65 70 61 72 61 74 65 20 57 68   are separate Wh
3950: 65 72 65 43 6c 61 75 73 65 20 6f 62 6a 65 63 74  ereClause object
3960: 73 20 66 6f 72 20 74 68 65 20 77 68 6f 6c 65 20  s for the whole 
3970: 63 6c 61 75 73 65 20 61 6e 64 20 66 6f 72 0a 2a  clause and for.*
3980: 2a 20 74 68 65 20 73 75 62 63 6c 61 75 73 65 73  * the subclauses
3990: 20 22 28 62 20 41 4e 44 20 63 29 22 20 61 6e 64   "(b AND c)" and
39a0: 20 22 28 64 20 41 4e 44 20 65 29 22 2e 20 20 54   "(d AND e)".  T
39b0: 68 65 20 70 4f 75 74 65 72 20 66 69 65 6c 64 20  he pOuter field 
39c0: 6f 66 20 74 68 65 0a 2a 2a 20 73 75 62 63 6c 61  of the.** subcla
39d0: 75 73 65 73 20 70 6f 69 6e 74 73 20 74 6f 20 74  uses points to t
39e0: 68 65 20 57 68 65 72 65 43 6c 61 75 73 65 20 6f  he WhereClause o
39f0: 62 6a 65 63 74 20 66 6f 72 20 74 68 65 20 77 68  bject for the wh
3a00: 6f 6c 65 20 63 6c 61 75 73 65 2e 0a 2a 2f 0a 73  ole clause..*/.s
3a10: 74 72 75 63 74 20 57 68 65 72 65 43 6c 61 75 73  truct WhereClaus
3a20: 65 20 7b 0a 20 20 57 68 65 72 65 49 6e 66 6f 20  e {.  WhereInfo 
3a30: 2a 70 57 49 6e 66 6f 3b 20 20 20 20 20 20 20 2f  *pWInfo;       /
3a40: 2a 20 57 48 45 52 45 20 63 6c 61 75 73 65 20 70  * WHERE clause p
3a50: 72 6f 63 65 73 73 69 6e 67 20 63 6f 6e 74 65 78  rocessing contex
3a60: 74 20 2a 2f 0a 20 20 57 68 65 72 65 43 6c 61 75  t */.  WhereClau
3a70: 73 65 20 2a 70 4f 75 74 65 72 3b 20 20 20 20 20  se *pOuter;     
3a80: 2f 2a 20 4f 75 74 65 72 20 63 6f 6e 6a 75 6e 63  /* Outer conjunc
3a90: 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20 6f 70 3b  tion */.  u8 op;
3aa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3ab0: 20 20 20 2f 2a 20 53 70 6c 69 74 20 6f 70 65 72     /* Split oper
3ac0: 61 74 6f 72 2e 20 20 54 4b 5f 41 4e 44 20 6f 72  ator.  TK_AND or
3ad0: 20 54 4b 5f 4f 52 20 2a 2f 0a 20 20 69 6e 74 20   TK_OR */.  int 
3ae0: 6e 54 65 72 6d 3b 20 20 20 20 20 20 20 20 20 20  nTerm;          
3af0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
3b00: 66 20 74 65 72 6d 73 20 2a 2f 0a 20 20 69 6e 74  f terms */.  int
3b10: 20 6e 53 6c 6f 74 3b 20 20 20 20 20 20 20 20 20   nSlot;         
3b20: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
3b30: 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 61 5b  of entries in a[
3b40: 5d 20 2a 2f 0a 20 20 57 68 65 72 65 54 65 72 6d  ] */.  WhereTerm
3b50: 20 2a 61 3b 20 20 20 20 20 20 20 20 20 20 20 20   *a;            
3b60: 2f 2a 20 45 61 63 68 20 61 5b 5d 20 64 65 73 63  /* Each a[] desc
3b70: 72 69 62 65 73 20 61 20 74 65 72 6d 20 6f 66 20  ribes a term of 
3b80: 74 68 65 20 57 48 45 52 45 20 63 6c 75 61 73 65  the WHERE cluase
3b90: 20 2a 2f 0a 23 69 66 20 64 65 66 69 6e 65 64 28   */.#if defined(
3ba0: 53 51 4c 49 54 45 5f 53 4d 41 4c 4c 5f 53 54 41  SQLITE_SMALL_STA
3bb0: 43 4b 29 0a 20 20 57 68 65 72 65 54 65 72 6d 20  CK).  WhereTerm 
3bc0: 61 53 74 61 74 69 63 5b 31 5d 3b 20 20 20 20 2f  aStatic[1];    /
3bd0: 2a 20 49 6e 69 74 69 61 6c 20 73 74 61 74 69 63  * Initial static
3be0: 20 73 70 61 63 65 20 66 6f 72 20 61 5b 5d 20 2a   space for a[] *
3bf0: 2f 0a 23 65 6c 73 65 0a 20 20 57 68 65 72 65 54  /.#else.  WhereT
3c00: 65 72 6d 20 61 53 74 61 74 69 63 5b 38 5d 3b 20  erm aStatic[8]; 
3c10: 20 20 20 2f 2a 20 49 6e 69 74 69 61 6c 20 73 74     /* Initial st
3c20: 61 74 69 63 20 73 70 61 63 65 20 66 6f 72 20 61  atic space for a
3c30: 5b 5d 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d 3b 0a  [] */.#endif.};.
3c40: 0a 2f 2a 0a 2a 2a 20 41 20 57 68 65 72 65 54 65  ./*.** A WhereTe
3c50: 72 6d 20 77 69 74 68 20 65 4f 70 65 72 61 74 6f  rm with eOperato
3c60: 72 3d 3d 57 4f 5f 4f 52 20 68 61 73 20 69 74 73  r==WO_OR has its
3c70: 20 75 2e 70 4f 72 49 6e 66 6f 20 70 6f 69 6e 74   u.pOrInfo point
3c80: 65 72 20 73 65 74 20 74 6f 0a 2a 2a 20 61 20 64  er set to.** a d
3c90: 79 6e 61 6d 69 63 61 6c 6c 79 20 61 6c 6c 6f 63  ynamically alloc
3ca0: 61 74 65 64 20 69 6e 73 74 61 6e 63 65 20 6f 66  ated instance of
3cb0: 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73   the following s
3cc0: 74 72 75 63 74 75 72 65 2e 0a 2a 2f 0a 73 74 72  tructure..*/.str
3cd0: 75 63 74 20 57 68 65 72 65 4f 72 49 6e 66 6f 20  uct WhereOrInfo 
3ce0: 7b 0a 20 20 57 68 65 72 65 43 6c 61 75 73 65 20  {.  WhereClause 
3cf0: 77 63 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  wc;          /* 
3d00: 44 65 63 6f 6d 70 6f 73 69 74 69 6f 6e 20 69 6e  Decomposition in
3d10: 74 6f 20 73 75 62 74 65 72 6d 73 20 2a 2f 0a 20  to subterms */. 
3d20: 20 42 69 74 6d 61 73 6b 20 69 6e 64 65 78 61 62   Bitmask indexab
3d30: 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20 42 69 74  le;       /* Bit
3d40: 6d 61 73 6b 20 6f 66 20 61 6c 6c 20 69 6e 64 65  mask of all inde
3d50: 78 61 62 6c 65 20 74 61 62 6c 65 73 20 69 6e 20  xable tables in 
3d60: 74 68 65 20 63 6c 61 75 73 65 20 2a 2f 0a 7d 3b  the clause */.};
3d70: 0a 0a 2f 2a 0a 2a 2a 20 41 20 57 68 65 72 65 54  ../*.** A WhereT
3d80: 65 72 6d 20 77 69 74 68 20 65 4f 70 65 72 61 74  erm with eOperat
3d90: 6f 72 3d 3d 57 4f 5f 41 4e 44 20 68 61 73 20 69  or==WO_AND has i
3da0: 74 73 20 75 2e 70 41 6e 64 49 6e 66 6f 20 70 6f  ts u.pAndInfo po
3db0: 69 6e 74 65 72 20 73 65 74 20 74 6f 0a 2a 2a 20  inter set to.** 
3dc0: 61 20 64 79 6e 61 6d 69 63 61 6c 6c 79 20 61 6c  a dynamically al
3dd0: 6c 6f 63 61 74 65 64 20 69 6e 73 74 61 6e 63 65  located instance
3de0: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
3df0: 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2f 0a  g structure..*/.
3e00: 73 74 72 75 63 74 20 57 68 65 72 65 41 6e 64 49  struct WhereAndI
3e10: 6e 66 6f 20 7b 0a 20 20 57 68 65 72 65 43 6c 61  nfo {.  WhereCla
3e20: 75 73 65 20 77 63 3b 20 20 20 20 20 20 20 20 20  use wc;         
3e30: 20 2f 2a 20 54 68 65 20 73 75 62 65 78 70 72 65   /* The subexpre
3e40: 73 73 69 6f 6e 20 62 72 6f 6b 65 6e 20 6f 75 74  ssion broken out
3e50: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 6e   */.};../*.** An
3e60: 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65   instance of the
3e70: 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63   following struc
3e80: 74 75 72 65 20 6b 65 65 70 73 20 74 72 61 63 6b  ture keeps track
3e90: 20 6f 66 20 61 20 6d 61 70 70 69 6e 67 0a 2a 2a   of a mapping.**
3ea0: 20 62 65 74 77 65 65 6e 20 56 44 42 45 20 63 75   between VDBE cu
3eb0: 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 61 6e 64  rsor numbers and
3ec0: 20 62 69 74 73 20 6f 66 20 74 68 65 20 62 69 74   bits of the bit
3ed0: 6d 61 73 6b 73 20 69 6e 20 57 68 65 72 65 54 65  masks in WhereTe
3ee0: 72 6d 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 56 44  rm..**.** The VD
3ef0: 42 45 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72  BE cursor number
3f00: 73 20 61 72 65 20 73 6d 61 6c 6c 20 69 6e 74 65  s are small inte
3f10: 67 65 72 73 20 63 6f 6e 74 61 69 6e 65 64 20 69  gers contained i
3f20: 6e 20 0a 2a 2a 20 53 72 63 4c 69 73 74 5f 69 74  n .** SrcList_it
3f30: 65 6d 2e 69 43 75 72 73 6f 72 20 61 6e 64 20 45  em.iCursor and E
3f40: 78 70 72 2e 69 54 61 62 6c 65 20 66 69 65 6c 64  xpr.iTable field
3f50: 73 2e 20 20 46 6f 72 20 61 6e 79 20 67 69 76 65  s.  For any give
3f60: 6e 20 57 48 45 52 45 20 0a 2a 2a 20 63 6c 61 75  n WHERE .** clau
3f70: 73 65 2c 20 74 68 65 20 63 75 72 73 6f 72 20 6e  se, the cursor n
3f80: 75 6d 62 65 72 73 20 6d 69 67 68 74 20 6e 6f 74  umbers might not
3f90: 20 62 65 67 69 6e 20 77 69 74 68 20 30 20 61 6e   begin with 0 an
3fa0: 64 20 74 68 65 79 20 6d 69 67 68 74 0a 2a 2a 20  d they might.** 
3fb0: 63 6f 6e 74 61 69 6e 20 67 61 70 73 20 69 6e 20  contain gaps in 
3fc0: 74 68 65 20 6e 75 6d 62 65 72 69 6e 67 20 73 65  the numbering se
3fd0: 71 75 65 6e 63 65 2e 20 20 42 75 74 20 77 65 20  quence.  But we 
3fe0: 77 61 6e 74 20 74 6f 20 6d 61 6b 65 20 6d 61 78  want to make max
3ff0: 69 6d 75 6d 0a 2a 2a 20 75 73 65 20 6f 66 20 74  imum.** use of t
4000: 68 65 20 62 69 74 73 20 69 6e 20 6f 75 72 20 62  he bits in our b
4010: 69 74 6d 61 73 6b 73 2e 20 20 54 68 69 73 20 73  itmasks.  This s
4020: 74 72 75 63 74 75 72 65 20 70 72 6f 76 69 64 65  tructure provide
4030: 73 20 61 20 6d 61 70 70 69 6e 67 0a 2a 2a 20 66  s a mapping.** f
4040: 72 6f 6d 20 74 68 65 20 73 70 61 72 73 65 20 63  rom the sparse c
4050: 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20 69 6e  ursor numbers in
4060: 74 6f 20 63 6f 6e 73 65 63 75 74 69 76 65 20 69  to consecutive i
4070: 6e 74 65 67 65 72 73 20 62 65 67 69 6e 6e 69 6e  ntegers beginnin
4080: 67 0a 2a 2a 20 77 69 74 68 20 30 2e 0a 2a 2a 0a  g.** with 0..**.
4090: 2a 2a 20 49 66 20 57 68 65 72 65 4d 61 73 6b 53  ** If WhereMaskS
40a0: 65 74 2e 69 78 5b 41 5d 3d 3d 42 20 69 74 20 6d  et.ix[A]==B it m
40b0: 65 61 6e 73 20 74 68 61 74 20 54 68 65 20 41 2d  eans that The A-
40c0: 74 68 20 62 69 74 20 6f 66 20 61 20 42 69 74 6d  th bit of a Bitm
40d0: 61 73 6b 0a 2a 2a 20 63 6f 72 72 65 73 70 6f 6e  ask.** correspon
40e0: 64 73 20 56 44 42 45 20 63 75 72 73 6f 72 20 6e  ds VDBE cursor n
40f0: 75 6d 62 65 72 20 42 2e 20 20 54 68 65 20 41 2d  umber B.  The A-
4100: 74 68 20 62 69 74 20 6f 66 20 61 20 62 69 74 6d  th bit of a bitm
4110: 61 73 6b 20 69 73 20 31 3c 3c 41 2e 0a 2a 2a 0a  ask is 1<<A..**.
4120: 2a 2a 20 46 6f 72 20 65 78 61 6d 70 6c 65 2c 20  ** For example, 
4130: 69 66 20 74 68 65 20 57 48 45 52 45 20 63 6c 61  if the WHERE cla
4140: 75 73 65 20 65 78 70 72 65 73 73 69 6f 6e 20 75  use expression u
4150: 73 65 64 20 74 68 65 73 65 20 56 44 42 45 0a 2a  sed these VDBE.*
4160: 2a 20 63 75 72 73 6f 72 73 3a 20 20 34 2c 20 35  * cursors:  4, 5
4170: 2c 20 38 2c 20 32 39 2c 20 35 37 2c 20 37 33 2e  , 8, 29, 57, 73.
4180: 20 20 54 68 65 6e 20 74 68 65 20 20 57 68 65 72    Then the  Wher
4190: 65 4d 61 73 6b 53 65 74 20 73 74 72 75 63 74 75  eMaskSet structu
41a0: 72 65 0a 2a 2a 20 77 6f 75 6c 64 20 6d 61 70 20  re.** would map 
41b0: 74 68 6f 73 65 20 63 75 72 73 6f 72 20 6e 75 6d  those cursor num
41c0: 62 65 72 73 20 69 6e 74 6f 20 62 69 74 73 20 30  bers into bits 0
41d0: 20 74 68 72 6f 75 67 68 20 35 2e 0a 2a 2a 0a 2a   through 5..**.*
41e0: 2a 20 4e 6f 74 65 20 74 68 61 74 20 74 68 65 20  * Note that the 
41f0: 6d 61 70 70 69 6e 67 20 69 73 20 6e 6f 74 20 6e  mapping is not n
4200: 65 63 65 73 73 61 72 69 6c 79 20 6f 72 64 65 72  ecessarily order
4210: 65 64 2e 20 20 49 6e 20 74 68 65 20 65 78 61 6d  ed.  In the exam
4220: 70 6c 65 0a 2a 2a 20 61 62 6f 76 65 2c 20 74 68  ple.** above, th
4230: 65 20 6d 61 70 70 69 6e 67 20 6d 69 67 68 74 20  e mapping might 
4240: 67 6f 20 6c 69 6b 65 20 74 68 69 73 3a 20 20 34  go like this:  4
4250: 2d 3e 33 2c 20 35 2d 3e 31 2c 20 38 2d 3e 32 2c  ->3, 5->1, 8->2,
4260: 20 32 39 2d 3e 30 2c 0a 2a 2a 20 35 37 2d 3e 35   29->0,.** 57->5
4270: 2c 20 37 33 2d 3e 34 2e 20 20 4f 72 20 6f 6e 65  , 73->4.  Or one
4280: 20 6f 66 20 37 31 39 20 6f 74 68 65 72 20 63 6f   of 719 other co
4290: 6d 62 69 6e 61 74 69 6f 6e 73 20 6d 69 67 68 74  mbinations might
42a0: 20 62 65 20 75 73 65 64 2e 20 49 74 0a 2a 2a 20   be used. It.** 
42b0: 64 6f 65 73 20 6e 6f 74 20 72 65 61 6c 6c 79 20  does not really 
42c0: 6d 61 74 74 65 72 2e 20 20 57 68 61 74 20 69 73  matter.  What is
42d0: 20 69 6d 70 6f 72 74 61 6e 74 20 69 73 20 74 68   important is th
42e0: 61 74 20 73 70 61 72 73 65 20 63 75 72 73 6f 72  at sparse cursor
42f0: 0a 2a 2a 20 6e 75 6d 62 65 72 73 20 61 6c 6c 20  .** numbers all 
4300: 67 65 74 20 6d 61 70 70 65 64 20 69 6e 74 6f 20  get mapped into 
4310: 62 69 74 20 6e 75 6d 62 65 72 73 20 74 68 61 74  bit numbers that
4320: 20 62 65 67 69 6e 20 77 69 74 68 20 30 20 61 6e   begin with 0 an
4330: 64 20 63 6f 6e 74 61 69 6e 0a 2a 2a 20 6e 6f 20  d contain.** no 
4340: 67 61 70 73 2e 0a 2a 2f 0a 73 74 72 75 63 74 20  gaps..*/.struct 
4350: 57 68 65 72 65 4d 61 73 6b 53 65 74 20 7b 0a 20  WhereMaskSet {. 
4360: 20 69 6e 74 20 6e 3b 20 20 20 20 20 20 20 20 20   int n;         
4370: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
4380: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 61 73 73 69  * Number of assi
4390: 67 6e 65 64 20 63 75 72 73 6f 72 20 76 61 6c 75  gned cursor valu
43a0: 65 73 20 2a 2f 0a 20 20 69 6e 74 20 69 78 5b 42  es */.  int ix[B
43b0: 4d 53 5d 3b 20 20 20 20 20 20 20 20 20 20 20 20  MS];            
43c0: 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 20        /* Cursor 
43d0: 61 73 73 69 67 6e 65 64 20 74 6f 20 65 61 63 68  assigned to each
43e0: 20 62 69 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a   bit */.};../*.*
43f0: 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 61 20 57  * Initialize a W
4400: 68 65 72 65 4d 61 73 6b 53 65 74 20 6f 62 6a 65  hereMaskSet obje
4410: 63 74 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 69 6e  ct.*/.#define in
4420: 69 74 4d 61 73 6b 53 65 74 28 50 29 20 20 28 50  itMaskSet(P)  (P
4430: 29 2d 3e 6e 3d 30 0a 0a 2f 2a 0a 2a 2a 20 54 68  )->n=0../*.** Th
4440: 69 73 20 6f 62 6a 65 63 74 20 69 73 20 61 20 63  is object is a c
4450: 6f 6e 76 65 6e 69 65 6e 63 65 20 77 72 61 70 70  onvenience wrapp
4460: 65 72 20 68 6f 6c 64 69 6e 67 20 61 6c 6c 20 69  er holding all i
4470: 6e 66 6f 72 6d 61 74 69 6f 6e 20 6e 65 65 64 65  nformation neede
4480: 64 0a 2a 2a 20 74 6f 20 63 6f 6e 73 74 72 75 63  d.** to construc
4490: 74 20 57 68 65 72 65 4c 6f 6f 70 20 6f 62 6a 65  t WhereLoop obje
44a0: 63 74 73 20 66 6f 72 20 61 20 70 61 72 74 69 63  cts for a partic
44b0: 75 6c 61 72 20 71 75 65 72 79 2e 0a 2a 2f 0a 73  ular query..*/.s
44c0: 74 72 75 63 74 20 57 68 65 72 65 4c 6f 6f 70 42  truct WhereLoopB
44d0: 75 69 6c 64 65 72 20 7b 0a 20 20 57 68 65 72 65  uilder {.  Where
44e0: 49 6e 66 6f 20 2a 70 57 49 6e 66 6f 3b 20 20 20  Info *pWInfo;   
44f0: 20 20 20 20 20 2f 2a 20 49 6e 66 6f 72 6d 61 74       /* Informat
4500: 69 6f 6e 20 61 62 6f 75 74 20 74 68 69 73 20 57  ion about this W
4510: 48 45 52 45 20 2a 2f 0a 20 20 57 68 65 72 65 43  HERE */.  WhereC
4520: 6c 61 75 73 65 20 2a 70 57 43 3b 20 20 20 20 20  lause *pWC;     
4530: 20 20 20 20 2f 2a 20 57 48 45 52 45 20 63 6c 61      /* WHERE cla
4540: 75 73 65 20 74 65 72 6d 73 20 2a 2f 0a 20 20 45  use terms */.  E
4550: 78 70 72 4c 69 73 74 20 2a 70 4f 72 64 65 72 42  xprList *pOrderB
4560: 79 3b 20 20 20 20 20 20 20 2f 2a 20 4f 52 44 45  y;       /* ORDE
4570: 52 20 42 59 20 63 6c 61 75 73 65 20 2a 2f 0a 20  R BY clause */. 
4580: 20 57 68 65 72 65 4c 6f 6f 70 20 2a 70 4e 65 77   WhereLoop *pNew
4590: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 65  ;          /* Te
45a0: 6d 70 6c 61 74 65 20 57 68 65 72 65 4c 6f 6f 70  mplate WhereLoop
45b0: 20 2a 2f 0a 20 20 57 68 65 72 65 4f 72 53 65 74   */.  WhereOrSet
45c0: 20 2a 70 4f 72 53 65 74 3b 20 20 20 20 20 20 20   *pOrSet;       
45d0: 2f 2a 20 52 65 63 6f 72 64 20 62 65 73 74 20 6c  /* Record best l
45e0: 6f 6f 70 73 20 68 65 72 65 2c 20 69 66 20 6e 6f  oops here, if no
45f0: 74 20 4e 55 4c 4c 20 2a 2f 0a 23 69 66 64 65 66  t NULL */.#ifdef
4600: 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 53   SQLITE_ENABLE_S
4610: 54 41 54 33 5f 4f 52 5f 53 54 41 54 34 0a 20 20  TAT3_OR_STAT4.  
4620: 55 6e 70 61 63 6b 65 64 52 65 63 6f 72 64 20 2a  UnpackedRecord *
4630: 70 52 65 63 3b 20 20 20 20 20 2f 2a 20 50 72 6f  pRec;     /* Pro
4640: 62 65 20 66 6f 72 20 73 74 61 74 34 20 28 69 66  be for stat4 (if
4650: 20 72 65 71 75 69 72 65 64 29 20 2a 2f 0a 20 20   required) */.  
4660: 69 6e 74 20 6e 52 65 63 56 61 6c 69 64 3b 20 20  int nRecValid;  
4670: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
4680: 62 65 72 20 6f 66 20 76 61 6c 69 64 20 66 69 65  ber of valid fie
4690: 6c 64 73 20 63 75 72 72 65 6e 74 6c 79 20 69 6e  lds currently in
46a0: 20 70 52 65 63 20 2a 2f 0a 23 65 6e 64 69 66 0a   pRec */.#endif.
46b0: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 62    unsigned int b
46c0: 6c 64 46 6c 61 67 73 3b 20 20 20 20 2f 2a 20 53  ldFlags;    /* S
46d0: 51 4c 49 54 45 5f 42 4c 44 46 5f 2a 20 66 6c 61  QLITE_BLDF_* fla
46e0: 67 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 41 6c 6c  gs */.};../* All
46f0: 6f 77 65 64 20 76 61 6c 75 65 73 20 66 6f 72 20  owed values for 
4700: 57 68 65 72 65 4c 6f 6f 70 42 75 69 64 65 72 2e  WhereLoopBuider.
4710: 62 6c 64 46 6c 61 67 73 20 2a 2f 0a 23 64 65 66  bldFlags */.#def
4720: 69 6e 65 20 53 51 4c 49 54 45 5f 42 4c 44 46 5f  ine SQLITE_BLDF_
4730: 49 4e 44 45 58 45 44 20 20 30 78 30 30 30 31 20  INDEXED  0x0001 
4740: 20 20 2f 2a 20 41 6e 20 69 6e 64 65 78 20 69 73    /* An index is
4750: 20 75 73 65 64 20 2a 2f 0a 23 64 65 66 69 6e 65   used */.#define
4760: 20 53 51 4c 49 54 45 5f 42 4c 44 46 5f 55 4e 49   SQLITE_BLDF_UNI
4770: 51 55 45 20 20 20 30 78 30 30 30 32 20 20 20 2f  QUE   0x0002   /
4780: 2a 20 41 6c 6c 20 6b 65 79 73 20 6f 66 20 61 20  * All keys of a 
4790: 55 4e 49 51 55 45 20 69 6e 64 65 78 20 75 73 65  UNIQUE index use
47a0: 64 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  d */../*.** The 
47b0: 57 48 45 52 45 20 63 6c 61 75 73 65 20 70 72 6f  WHERE clause pro
47c0: 63 65 73 73 69 6e 67 20 72 6f 75 74 69 6e 65 20  cessing routine 
47d0: 68 61 73 20 74 77 6f 20 68 61 6c 76 65 73 2e 20  has two halves. 
47e0: 20 54 68 65 0a 2a 2a 20 66 69 72 73 74 20 70 61   The.** first pa
47f0: 72 74 20 64 6f 65 73 20 74 68 65 20 73 74 61 72  rt does the star
4800: 74 20 6f 66 20 74 68 65 20 57 48 45 52 45 20 6c  t of the WHERE l
4810: 6f 6f 70 20 61 6e 64 20 74 68 65 20 73 65 63 6f  oop and the seco
4820: 6e 64 0a 2a 2a 20 68 61 6c 66 20 64 6f 65 73 20  nd.** half does 
4830: 74 68 65 20 74 61 69 6c 20 6f 66 20 74 68 65 20  the tail of the 
4840: 57 48 45 52 45 20 6c 6f 6f 70 2e 20 20 41 6e 20  WHERE loop.  An 
4850: 69 6e 73 74 61 6e 63 65 20 6f 66 0a 2a 2a 20 74  instance of.** t
4860: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 69 73  his structure is
4870: 20 72 65 74 75 72 6e 65 64 20 62 79 20 74 68 65   returned by the
4880: 20 66 69 72 73 74 20 68 61 6c 66 20 61 6e 64 20   first half and 
4890: 70 61 73 73 65 64 0a 2a 2a 20 69 6e 74 6f 20 74  passed.** into t
48a0: 68 65 20 73 65 63 6f 6e 64 20 68 61 6c 66 20 74  he second half t
48b0: 6f 20 67 69 76 65 20 73 6f 6d 65 20 63 6f 6e 74  o give some cont
48c0: 69 6e 75 69 74 79 2e 0a 2a 2a 0a 2a 2a 20 41 6e  inuity..**.** An
48d0: 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 69   instance of thi
48e0: 73 20 6f 62 6a 65 63 74 20 68 6f 6c 64 73 20 74  s object holds t
48f0: 68 65 20 63 6f 6d 70 6c 65 74 65 20 73 74 61 74  he complete stat
4900: 65 20 6f 66 20 74 68 65 20 71 75 65 72 79 0a 2a  e of the query.*
4910: 2a 20 70 6c 61 6e 6e 65 72 2e 0a 2a 2f 0a 73 74  * planner..*/.st
4920: 72 75 63 74 20 57 68 65 72 65 49 6e 66 6f 20 7b  ruct WhereInfo {
4930: 0a 20 20 50 61 72 73 65 20 2a 70 50 61 72 73 65  .  Parse *pParse
4940: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
4950: 50 61 72 73 69 6e 67 20 61 6e 64 20 63 6f 64 65  Parsing and code
4960: 20 67 65 6e 65 72 61 74 69 6e 67 20 63 6f 6e 74   generating cont
4970: 65 78 74 20 2a 2f 0a 20 20 53 72 63 4c 69 73 74  ext */.  SrcList
4980: 20 2a 70 54 61 62 4c 69 73 74 3b 20 20 20 20 20   *pTabList;     
4990: 20 20 20 2f 2a 20 4c 69 73 74 20 6f 66 20 74 61     /* List of ta
49a0: 62 6c 65 73 20 69 6e 20 74 68 65 20 6a 6f 69 6e  bles in the join
49b0: 20 2a 2f 0a 20 20 45 78 70 72 4c 69 73 74 20 2a   */.  ExprList *
49c0: 70 4f 72 64 65 72 42 79 3b 20 20 20 20 20 20 20  pOrderBy;       
49d0: 2f 2a 20 54 68 65 20 4f 52 44 45 52 20 42 59 20  /* The ORDER BY 
49e0: 63 6c 61 75 73 65 20 6f 72 20 4e 55 4c 4c 20 2a  clause or NULL *
49f0: 2f 0a 20 20 45 78 70 72 4c 69 73 74 20 2a 70 52  /.  ExprList *pR
4a00: 65 73 75 6c 74 53 65 74 3b 20 20 20 20 20 2f 2a  esultSet;     /*
4a10: 20 52 65 73 75 6c 74 20 73 65 74 20 6f 66 20 74   Result set of t
4a20: 68 65 20 71 75 65 72 79 20 2a 2f 0a 20 20 4c 6f  he query */.  Lo
4a30: 67 45 73 74 20 69 4c 69 6d 69 74 3b 20 20 20 20  gEst iLimit;    
4a40: 20 20 20 20 20 20 20 20 2f 2a 20 4c 49 4d 49 54          /* LIMIT
4a50: 20 69 66 20 77 63 74 72 6c 46 6c 61 67 73 20 68   if wctrlFlags h
4a60: 61 73 20 57 48 45 52 45 5f 55 53 45 5f 4c 49 4d  as WHERE_USE_LIM
4a70: 49 54 20 2a 2f 0a 20 20 69 6e 74 20 61 69 43 75  IT */.  int aiCu
4a80: 72 4f 6e 65 50 61 73 73 5b 32 5d 3b 20 20 20 20  rOnePass[2];    
4a90: 20 20 2f 2a 20 4f 50 5f 4f 70 65 6e 57 72 69 74    /* OP_OpenWrit
4aa0: 65 20 63 75 72 73 6f 72 73 20 66 6f 72 20 74 68  e cursors for th
4ab0: 65 20 4f 4e 45 50 41 53 53 20 6f 70 74 20 2a 2f  e ONEPASS opt */
4ac0: 0a 20 20 69 6e 74 20 69 43 6f 6e 74 69 6e 75 65  .  int iContinue
4ad0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
4ae0: 4a 75 6d 70 20 68 65 72 65 20 74 6f 20 63 6f 6e  Jump here to con
4af0: 74 69 6e 75 65 20 77 69 74 68 20 6e 65 78 74 20  tinue with next 
4b00: 72 65 63 6f 72 64 20 2a 2f 0a 20 20 69 6e 74 20  record */.  int 
4b10: 69 42 72 65 61 6b 3b 20 20 20 20 20 20 20 20 20  iBreak;         
4b20: 20 20 20 20 20 20 2f 2a 20 4a 75 6d 70 20 68 65        /* Jump he
4b30: 72 65 20 74 6f 20 62 72 65 61 6b 20 6f 75 74 20  re to break out 
4b40: 6f 66 20 74 68 65 20 6c 6f 6f 70 20 2a 2f 0a 20  of the loop */. 
4b50: 20 69 6e 74 20 73 61 76 65 64 4e 51 75 65 72 79   int savedNQuery
4b60: 4c 6f 6f 70 3b 20 20 20 20 20 20 2f 2a 20 70 50  Loop;      /* pP
4b70: 61 72 73 65 2d 3e 6e 51 75 65 72 79 4c 6f 6f 70  arse->nQueryLoop
4b80: 20 6f 75 74 73 69 64 65 20 74 68 65 20 57 48 45   outside the WHE
4b90: 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20 20 75 31 36  RE loop */.  u16
4ba0: 20 77 63 74 72 6c 46 6c 61 67 73 3b 20 20 20 20   wctrlFlags;    
4bb0: 20 20 20 20 20 20 20 2f 2a 20 46 6c 61 67 73 20         /* Flags 
4bc0: 6f 72 69 67 69 6e 61 6c 6c 79 20 70 61 73 73 65  originally passe
4bd0: 64 20 74 6f 20 73 71 6c 69 74 65 33 57 68 65 72  d to sqlite3Wher
4be0: 65 42 65 67 69 6e 28 29 20 2a 2f 0a 20 20 75 38  eBegin() */.  u8
4bf0: 20 6e 4c 65 76 65 6c 3b 20 20 20 20 20 20 20 20   nLevel;        
4c00: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
4c10: 72 20 6f 66 20 6e 65 73 74 65 64 20 6c 6f 6f 70  r of nested loop
4c20: 20 2a 2f 0a 20 20 69 38 20 6e 4f 42 53 61 74 3b   */.  i8 nOBSat;
4c30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4c40: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 4f 52 44  /* Number of ORD
4c50: 45 52 20 42 59 20 74 65 72 6d 73 20 73 61 74 69  ER BY terms sati
4c60: 73 66 69 65 64 20 62 79 20 69 6e 64 69 63 65 73  sfied by indices
4c70: 20 2a 2f 0a 20 20 75 38 20 73 6f 72 74 65 64 3b   */.  u8 sorted;
4c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4c90: 2f 2a 20 54 72 75 65 20 69 66 20 72 65 61 6c 6c  /* True if reall
4ca0: 79 20 73 6f 72 74 65 64 20 28 6e 6f 74 20 6a 75  y sorted (not ju
4cb0: 73 74 20 67 72 6f 75 70 65 64 29 20 2a 2f 0a 20  st grouped) */. 
4cc0: 20 75 38 20 65 4f 6e 65 50 61 73 73 3b 20 20 20   u8 eOnePass;   
4cd0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 4e             /* ON
4ce0: 45 50 41 53 53 5f 4f 46 46 2c 20 6f 72 20 5f 53  EPASS_OFF, or _S
4cf0: 49 4e 47 4c 45 2c 20 6f 72 20 5f 4d 55 4c 54 49  INGLE, or _MULTI
4d00: 20 2a 2f 0a 20 20 75 38 20 75 6e 74 65 73 74 65   */.  u8 unteste
4d10: 64 54 65 72 6d 73 3b 20 20 20 20 20 20 20 20 20  dTerms;         
4d20: 2f 2a 20 4e 6f 74 20 61 6c 6c 20 57 48 45 52 45  /* Not all WHERE
4d30: 20 74 65 72 6d 73 20 72 65 73 6f 6c 76 65 64 20   terms resolved 
4d40: 62 79 20 6f 75 74 65 72 20 6c 6f 6f 70 20 2a 2f  by outer loop */
4d50: 0a 20 20 75 38 20 65 44 69 73 74 69 6e 63 74 3b  .  u8 eDistinct;
4d60: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
4d70: 4f 6e 65 20 6f 66 20 74 68 65 20 57 48 45 52 45  One of the WHERE
4d80: 5f 44 49 53 54 49 4e 43 54 5f 2a 20 76 61 6c 75  _DISTINCT_* valu
4d90: 65 73 20 2a 2f 0a 20 20 75 38 20 62 4f 72 64 65  es */.  u8 bOrde
4da0: 72 65 64 49 6e 6e 65 72 4c 6f 6f 70 3b 20 20 20  redInnerLoop;   
4db0: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 6f 6e 6c    /* True if onl
4dc0: 79 20 74 68 65 20 69 6e 6e 65 72 2d 6d 6f 73 74  y the inner-most
4dd0: 20 6c 6f 6f 70 20 69 73 20 6f 72 64 65 72 65 64   loop is ordered
4de0: 20 2a 2f 0a 20 20 69 6e 74 20 69 54 6f 70 3b 20   */.  int iTop; 
4df0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4e00: 2f 2a 20 54 68 65 20 76 65 72 79 20 62 65 67 69  /* The very begi
4e10: 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 57 48 45  nning of the WHE
4e20: 52 45 20 6c 6f 6f 70 20 2a 2f 0a 20 20 57 68 65  RE loop */.  Whe
4e30: 72 65 4c 6f 6f 70 20 2a 70 4c 6f 6f 70 73 3b 20  reLoop *pLoops; 
4e40: 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f         /* List o
4e50: 66 20 61 6c 6c 20 57 68 65 72 65 4c 6f 6f 70 20  f all WhereLoop 
4e60: 6f 62 6a 65 63 74 73 20 2a 2f 0a 20 20 42 69 74  objects */.  Bit
4e70: 6d 61 73 6b 20 72 65 76 4d 61 73 6b 3b 20 20 20  mask revMask;   
4e80: 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 6f         /* Mask o
4e90: 66 20 4f 52 44 45 52 20 42 59 20 74 65 72 6d 73  f ORDER BY terms
4ea0: 20 74 68 61 74 20 6e 65 65 64 20 72 65 76 65 72   that need rever
4eb0: 73 69 6e 67 20 2a 2f 0a 20 20 4c 6f 67 45 73 74  sing */.  LogEst
4ec0: 20 6e 52 6f 77 4f 75 74 3b 20 20 20 20 20 20 20   nRowOut;       
4ed0: 20 20 20 20 2f 2a 20 45 73 74 69 6d 61 74 65 64      /* Estimated
4ee0: 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74 70 75   number of outpu
4ef0: 74 20 72 6f 77 73 20 2a 2f 0a 20 20 57 68 65 72  t rows */.  Wher
4f00: 65 43 6c 61 75 73 65 20 73 57 43 3b 20 20 20 20  eClause sWC;    
4f10: 20 20 20 20 20 20 2f 2a 20 44 65 63 6f 6d 70 6f        /* Decompo
4f20: 73 69 74 69 6f 6e 20 6f 66 20 74 68 65 20 57 48  sition of the WH
4f30: 45 52 45 20 63 6c 61 75 73 65 20 2a 2f 0a 20 20  ERE clause */.  
4f40: 57 68 65 72 65 4d 61 73 6b 53 65 74 20 73 4d 61  WhereMaskSet sMa
4f50: 73 6b 53 65 74 3b 20 20 20 20 2f 2a 20 4d 61 70  skSet;    /* Map
4f60: 20 63 75 72 73 6f 72 20 6e 75 6d 62 65 72 73 20   cursor numbers 
4f70: 74 6f 20 62 69 74 6d 61 73 6b 73 20 2a 2f 0a 20  to bitmasks */. 
4f80: 20 57 68 65 72 65 4c 65 76 65 6c 20 61 5b 31 5d   WhereLevel a[1]
4f90: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e  ;          /* In
4fa0: 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20  formation about 
4fb0: 65 61 63 68 20 6e 65 73 74 20 6c 6f 6f 70 20 69  each nest loop i
4fc0: 6e 20 57 48 45 52 45 20 2a 2f 0a 7d 3b 0a 0a 2f  n WHERE */.};../
4fd0: 2a 0a 2a 2a 20 50 72 69 76 61 74 65 20 69 6e 74  *.** Private int
4fe0: 65 72 66 61 63 65 73 20 2d 20 63 61 6c 6c 61 62  erfaces - callab
4ff0: 6c 65 20 6f 6e 6c 79 20 62 79 20 6f 74 68 65 72  le only by other
5000: 20 77 68 65 72 65 2e 63 20 72 6f 75 74 69 6e 65   where.c routine
5010: 73 2e 0a 2a 2a 0a 2a 2a 20 77 68 65 72 65 2e 63  s..**.** where.c
5020: 3a 0a 2a 2f 0a 42 69 74 6d 61 73 6b 20 73 71 6c  :.*/.Bitmask sql
5030: 69 74 65 33 57 68 65 72 65 47 65 74 4d 61 73 6b  ite3WhereGetMask
5040: 28 57 68 65 72 65 4d 61 73 6b 53 65 74 2a 2c 69  (WhereMaskSet*,i
5050: 6e 74 29 3b 0a 23 69 66 64 65 66 20 57 48 45 52  nt);.#ifdef WHER
5060: 45 54 52 41 43 45 5f 45 4e 41 42 4c 45 44 0a 76  ETRACE_ENABLED.v
5070: 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65 72 65  oid sqlite3Where
5080: 43 6c 61 75 73 65 50 72 69 6e 74 28 57 68 65 72  ClausePrint(Wher
5090: 65 43 6c 61 75 73 65 20 2a 70 57 43 29 3b 0a 23  eClause *pWC);.#
50a0: 65 6e 64 69 66 0a 57 68 65 72 65 54 65 72 6d 20  endif.WhereTerm 
50b0: 2a 73 71 6c 69 74 65 33 57 68 65 72 65 46 69 6e  *sqlite3WhereFin
50c0: 64 54 65 72 6d 28 0a 20 20 57 68 65 72 65 43 6c  dTerm(.  WhereCl
50d0: 61 75 73 65 20 2a 70 57 43 2c 20 20 20 20 20 2f  ause *pWC,     /
50e0: 2a 20 54 68 65 20 57 48 45 52 45 20 63 6c 61 75  * The WHERE clau
50f0: 73 65 20 74 6f 20 62 65 20 73 65 61 72 63 68 65  se to be searche
5100: 64 20 2a 2f 0a 20 20 69 6e 74 20 69 43 75 72 2c  d */.  int iCur,
5110: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
5120: 43 75 72 73 6f 72 20 6e 75 6d 62 65 72 20 6f 66  Cursor number of
5130: 20 4c 48 53 20 2a 2f 0a 20 20 69 6e 74 20 69 43   LHS */.  int iC
5140: 6f 6c 75 6d 6e 2c 20 20 20 20 20 20 20 20 20 20  olumn,          
5150: 2f 2a 20 43 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72  /* Column number
5160: 20 6f 66 20 4c 48 53 20 2a 2f 0a 20 20 42 69 74   of LHS */.  Bit
5170: 6d 61 73 6b 20 6e 6f 74 52 65 61 64 79 2c 20 20  mask notReady,  
5180: 20 20 20 2f 2a 20 52 48 53 20 6d 75 73 74 20 6e     /* RHS must n
5190: 6f 74 20 6f 76 65 72 6c 61 70 20 77 69 74 68 20  ot overlap with 
51a0: 74 68 69 73 20 6d 61 73 6b 20 2a 2f 0a 20 20 75  this mask */.  u
51b0: 33 32 20 6f 70 2c 20 20 20 20 20 20 20 20 20 20  32 op,          
51c0: 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20 6f 66 20       /* Mask of 
51d0: 57 4f 5f 78 78 20 76 61 6c 75 65 73 20 64 65 73  WO_xx values des
51e0: 63 72 69 62 69 6e 67 20 6f 70 65 72 61 74 6f 72  cribing operator
51f0: 20 2a 2f 0a 20 20 49 6e 64 65 78 20 2a 70 49 64   */.  Index *pId
5200: 78 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d  x           /* M
5210: 75 73 74 20 62 65 20 63 6f 6d 70 61 74 69 62 6c  ust be compatibl
5220: 65 20 77 69 74 68 20 74 68 69 73 20 69 6e 64 65  e with this inde
5230: 78 2c 20 69 66 20 6e 6f 74 20 4e 55 4c 4c 20 2a  x, if not NULL *
5240: 2f 0a 29 3b 0a 0a 2f 2a 20 77 68 65 72 65 63 6f  /.);../* whereco
5250: 64 65 2e 63 3a 20 2a 2f 0a 23 69 66 6e 64 65 66  de.c: */.#ifndef
5260: 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 45 58 50   SQLITE_OMIT_EXP
5270: 4c 41 49 4e 0a 69 6e 74 20 73 71 6c 69 74 65 33  LAIN.int sqlite3
5280: 57 68 65 72 65 45 78 70 6c 61 69 6e 4f 6e 65 53  WhereExplainOneS
5290: 63 61 6e 28 0a 20 20 50 61 72 73 65 20 2a 70 50  can(.  Parse *pP
52a0: 61 72 73 65 2c 20 20 20 20 20 20 20 20 20 20 20  arse,           
52b0: 20 20 20 20 20 20 20 2f 2a 20 50 61 72 73 65 20         /* Parse 
52c0: 63 6f 6e 74 65 78 74 20 2a 2f 0a 20 20 53 72 63  context */.  Src
52d0: 4c 69 73 74 20 2a 70 54 61 62 4c 69 73 74 2c 20  List *pTabList, 
52e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
52f0: 54 61 62 6c 65 20 6c 69 73 74 20 74 68 69 73 20  Table list this 
5300: 6c 6f 6f 70 20 72 65 66 65 72 73 20 74 6f 20 2a  loop refers to *
5310: 2f 0a 20 20 57 68 65 72 65 4c 65 76 65 6c 20 2a  /.  WhereLevel *
5320: 70 4c 65 76 65 6c 2c 20 20 20 20 20 20 20 20 20  pLevel,         
5330: 20 20 20 20 2f 2a 20 53 63 61 6e 20 74 6f 20 77      /* Scan to w
5340: 72 69 74 65 20 4f 50 5f 45 78 70 6c 61 69 6e 20  rite OP_Explain 
5350: 6f 70 63 6f 64 65 20 66 6f 72 20 2a 2f 0a 20 20  opcode for */.  
5360: 69 6e 74 20 69 4c 65 76 65 6c 2c 20 20 20 20 20  int iLevel,     
5370: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5380: 2f 2a 20 56 61 6c 75 65 20 66 6f 72 20 22 6c 65  /* Value for "le
5390: 76 65 6c 22 20 63 6f 6c 75 6d 6e 20 6f 66 20 6f  vel" column of o
53a0: 75 74 70 75 74 20 2a 2f 0a 20 20 69 6e 74 20 69  utput */.  int i
53b0: 46 72 6f 6d 2c 20 20 20 20 20 20 20 20 20 20 20  From,           
53c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 56 61             /* Va
53d0: 6c 75 65 20 66 6f 72 20 22 66 72 6f 6d 22 20 63  lue for "from" c
53e0: 6f 6c 75 6d 6e 20 6f 66 20 6f 75 74 70 75 74 20  olumn of output 
53f0: 2a 2f 0a 20 20 75 31 36 20 77 63 74 72 6c 46 6c  */.  u16 wctrlFl
5400: 61 67 73 20 20 20 20 20 20 20 20 20 20 20 20 20  ags             
5410: 20 20 20 20 20 2f 2a 20 46 6c 61 67 73 20 70 61       /* Flags pa
5420: 73 73 65 64 20 74 6f 20 73 71 6c 69 74 65 33 57  ssed to sqlite3W
5430: 68 65 72 65 42 65 67 69 6e 28 29 20 2a 2f 0a 29  hereBegin() */.)
5440: 3b 0a 23 65 6c 73 65 0a 23 20 64 65 66 69 6e 65  ;.#else.# define
5450: 20 73 71 6c 69 74 65 33 57 68 65 72 65 45 78 70   sqlite3WhereExp
5460: 6c 61 69 6e 4f 6e 65 53 63 61 6e 28 75 2c 76 2c  lainOneScan(u,v,
5470: 77 2c 78 2c 79 2c 7a 29 20 30 0a 23 65 6e 64 69  w,x,y,z) 0.#endi
5480: 66 20 2f 2a 20 53 51 4c 49 54 45 5f 4f 4d 49 54  f /* SQLITE_OMIT
5490: 5f 45 58 50 4c 41 49 4e 20 2a 2f 0a 23 69 66 64  _EXPLAIN */.#ifd
54a0: 65 66 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45  ef SQLITE_ENABLE
54b0: 5f 53 54 4d 54 5f 53 43 41 4e 53 54 41 54 55 53  _STMT_SCANSTATUS
54c0: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65  .void sqlite3Whe
54d0: 72 65 41 64 64 53 63 61 6e 53 74 61 74 75 73 28  reAddScanStatus(
54e0: 0a 20 20 56 64 62 65 20 2a 76 2c 20 20 20 20 20  .  Vdbe *v,     
54f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5500: 20 20 20 2f 2a 20 56 64 62 65 20 74 6f 20 61 64     /* Vdbe to ad
5510: 64 20 73 63 61 6e 73 74 61 74 75 73 20 65 6e 74  d scanstatus ent
5520: 72 79 20 74 6f 20 2a 2f 0a 20 20 53 72 63 4c 69  ry to */.  SrcLi
5530: 73 74 20 2a 70 53 72 63 6c 69 73 74 2c 20 20 20  st *pSrclist,   
5540: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 52             /* FR
5550: 4f 4d 20 63 6c 61 75 73 65 20 70 4c 76 6c 20 72  OM clause pLvl r
5560: 65 61 64 73 20 64 61 74 61 20 66 72 6f 6d 20 2a  eads data from *
5570: 2f 0a 20 20 57 68 65 72 65 4c 65 76 65 6c 20 2a  /.  WhereLevel *
5580: 70 4c 76 6c 2c 20 20 20 20 20 20 20 20 20 20 20  pLvl,           
5590: 20 20 20 20 2f 2a 20 4c 65 76 65 6c 20 74 6f 20      /* Level to 
55a0: 61 64 64 20 73 63 61 6e 73 74 61 74 75 73 28 29  add scanstatus()
55b0: 20 65 6e 74 72 79 20 66 6f 72 20 2a 2f 0a 20 20   entry for */.  
55c0: 69 6e 74 20 61 64 64 72 45 78 70 6c 61 69 6e 20  int addrExplain 
55d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
55e0: 2f 2a 20 41 64 64 72 65 73 73 20 6f 66 20 4f 50  /* Address of OP
55f0: 5f 45 78 70 6c 61 69 6e 20 28 6f 72 20 30 29 20  _Explain (or 0) 
5600: 2a 2f 0a 29 3b 0a 23 65 6c 73 65 0a 23 20 64 65  */.);.#else.# de
5610: 66 69 6e 65 20 73 71 6c 69 74 65 33 57 68 65 72  fine sqlite3Wher
5620: 65 41 64 64 53 63 61 6e 53 74 61 74 75 73 28 61  eAddScanStatus(a
5630: 2c 20 62 2c 20 63 2c 20 64 29 20 28 28 76 6f 69  , b, c, d) ((voi
5640: 64 29 64 29 0a 23 65 6e 64 69 66 0a 42 69 74 6d  d)d).#endif.Bitm
5650: 61 73 6b 20 73 71 6c 69 74 65 33 57 68 65 72 65  ask sqlite3Where
5660: 43 6f 64 65 4f 6e 65 4c 6f 6f 70 53 74 61 72 74  CodeOneLoopStart
5670: 28 0a 20 20 57 68 65 72 65 49 6e 66 6f 20 2a 70  (.  WhereInfo *p
5680: 57 49 6e 66 6f 2c 20 20 20 2f 2a 20 43 6f 6d 70  WInfo,   /* Comp
5690: 6c 65 74 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e  lete information
56a0: 20 61 62 6f 75 74 20 74 68 65 20 57 48 45 52 45   about the WHERE
56b0: 20 63 6c 61 75 73 65 20 2a 2f 0a 20 20 69 6e 74   clause */.  int
56c0: 20 69 4c 65 76 65 6c 2c 20 20 20 20 20 20 20 20   iLevel,        
56d0: 20 20 2f 2a 20 57 68 69 63 68 20 6c 65 76 65 6c    /* Which level
56e0: 20 6f 66 20 70 57 49 6e 66 6f 2d 3e 61 5b 5d 20   of pWInfo->a[] 
56f0: 73 68 6f 75 6c 64 20 62 65 20 63 6f 64 65 64 20  should be coded 
5700: 2a 2f 0a 20 20 42 69 74 6d 61 73 6b 20 6e 6f 74  */.  Bitmask not
5710: 52 65 61 64 79 20 20 20 20 20 2f 2a 20 57 68 69  Ready     /* Whi
5720: 63 68 20 74 61 62 6c 65 73 20 61 72 65 20 63 75  ch tables are cu
5730: 72 72 65 6e 74 6c 79 20 61 76 61 69 6c 61 62 6c  rrently availabl
5740: 65 20 2a 2f 0a 29 3b 0a 0a 2f 2a 20 77 68 65 72  e */.);../* wher
5750: 65 65 78 70 72 2e 63 3a 20 2a 2f 0a 76 6f 69 64  eexpr.c: */.void
5760: 20 73 71 6c 69 74 65 33 57 68 65 72 65 43 6c 61   sqlite3WhereCla
5770: 75 73 65 49 6e 69 74 28 57 68 65 72 65 43 6c 61  useInit(WhereCla
5780: 75 73 65 2a 2c 57 68 65 72 65 49 6e 66 6f 2a 29  use*,WhereInfo*)
5790: 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 57 68  ;.void sqlite3Wh
57a0: 65 72 65 43 6c 61 75 73 65 43 6c 65 61 72 28 57  ereClauseClear(W
57b0: 68 65 72 65 43 6c 61 75 73 65 2a 29 3b 0a 76 6f  hereClause*);.vo
57c0: 69 64 20 73 71 6c 69 74 65 33 57 68 65 72 65 53  id sqlite3WhereS
57d0: 70 6c 69 74 28 57 68 65 72 65 43 6c 61 75 73 65  plit(WhereClause
57e0: 2a 2c 45 78 70 72 2a 2c 75 38 29 3b 0a 42 69 74  *,Expr*,u8);.Bit
57f0: 6d 61 73 6b 20 73 71 6c 69 74 65 33 57 68 65 72  mask sqlite3Wher
5800: 65 45 78 70 72 55 73 61 67 65 28 57 68 65 72 65  eExprUsage(Where
5810: 4d 61 73 6b 53 65 74 2a 2c 20 45 78 70 72 2a 29  MaskSet*, Expr*)
5820: 3b 0a 42 69 74 6d 61 73 6b 20 73 71 6c 69 74 65  ;.Bitmask sqlite
5830: 33 57 68 65 72 65 45 78 70 72 4c 69 73 74 55 73  3WhereExprListUs
5840: 61 67 65 28 57 68 65 72 65 4d 61 73 6b 53 65 74  age(WhereMaskSet
5850: 2a 2c 20 45 78 70 72 4c 69 73 74 2a 29 3b 0a 76  *, ExprList*);.v
5860: 6f 69 64 20 73 71 6c 69 74 65 33 57 68 65 72 65  oid sqlite3Where
5870: 45 78 70 72 41 6e 61 6c 79 7a 65 28 53 72 63 4c  ExprAnalyze(SrcL
5880: 69 73 74 2a 2c 20 57 68 65 72 65 43 6c 61 75 73  ist*, WhereClaus
5890: 65 2a 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65  e*);.void sqlite
58a0: 33 57 68 65 72 65 54 61 62 46 75 6e 63 41 72 67  3WhereTabFuncArg
58b0: 73 28 50 61 72 73 65 2a 2c 20 73 74 72 75 63 74  s(Parse*, struct
58c0: 20 53 72 63 4c 69 73 74 5f 69 74 65 6d 2a 2c 20   SrcList_item*, 
58d0: 57 68 65 72 65 43 6c 61 75 73 65 2a 29 3b 0a 0a  WhereClause*);..
58e0: 0a 0a 0a 0a 2f 2a 0a 2a 2a 20 42 69 74 6d 61 73  ..../*.** Bitmas
58f0: 6b 73 20 66 6f 72 20 74 68 65 20 6f 70 65 72 61  ks for the opera
5900: 74 6f 72 73 20 6f 6e 20 57 68 65 72 65 54 65 72  tors on WhereTer
5910: 6d 20 6f 62 6a 65 63 74 73 2e 20 20 54 68 65 73  m objects.  Thes
5920: 65 20 61 72 65 20 61 6c 6c 0a 2a 2a 20 6f 70 65  e are all.** ope
5930: 72 61 74 6f 72 73 20 74 68 61 74 20 61 72 65 20  rators that are 
5940: 6f 66 20 69 6e 74 65 72 65 73 74 20 74 6f 20 74  of interest to t
5950: 68 65 20 71 75 65 72 79 20 70 6c 61 6e 6e 65 72  he query planner
5960: 2e 20 20 41 6e 0a 2a 2a 20 4f 52 2d 65 64 20 63  .  An.** OR-ed c
5970: 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f 66 20 74 68  ombination of th
5980: 65 73 65 20 76 61 6c 75 65 73 20 63 61 6e 20 62  ese values can b
5990: 65 20 75 73 65 64 20 77 68 65 6e 20 73 65 61 72  e used when sear
59a0: 63 68 69 6e 67 20 66 6f 72 0a 2a 2a 20 70 61 72  ching for.** par
59b0: 74 69 63 75 6c 61 72 20 57 68 65 72 65 54 65 72  ticular WhereTer
59c0: 6d 73 20 77 69 74 68 69 6e 20 61 20 57 68 65 72  ms within a Wher
59d0: 65 43 6c 61 75 73 65 2e 0a 2a 2a 0a 2a 2a 20 56  eClause..**.** V
59e0: 61 6c 75 65 20 63 6f 6e 73 74 72 61 69 6e 74 73  alue constraints
59f0: 3a 0a 2a 2a 20 20 20 20 20 57 4f 5f 45 51 20 20  :.**     WO_EQ  
5a00: 20 20 3d 3d 20 53 51 4c 49 54 45 5f 49 4e 44 45    == SQLITE_INDE
5a10: 58 5f 43 4f 4e 53 54 52 41 49 4e 54 5f 45 51 0a  X_CONSTRAINT_EQ.
5a20: 2a 2a 20 20 20 20 20 57 4f 5f 4c 54 20 20 20 20  **     WO_LT    
5a30: 3d 3d 20 53 51 4c 49 54 45 5f 49 4e 44 45 58 5f  == SQLITE_INDEX_
5a40: 43 4f 4e 53 54 52 41 49 4e 54 5f 4c 54 0a 2a 2a  CONSTRAINT_LT.**
5a50: 20 20 20 20 20 57 4f 5f 4c 45 20 20 20 20 3d 3d       WO_LE    ==
5a60: 20 53 51 4c 49 54 45 5f 49 4e 44 45 58 5f 43 4f   SQLITE_INDEX_CO
5a70: 4e 53 54 52 41 49 4e 54 5f 4c 45 0a 2a 2a 20 20  NSTRAINT_LE.**  
5a80: 20 20 20 57 4f 5f 47 54 20 20 20 20 3d 3d 20 53     WO_GT    == S
5a90: 51 4c 49 54 45 5f 49 4e 44 45 58 5f 43 4f 4e 53  QLITE_INDEX_CONS
5aa0: 54 52 41 49 4e 54 5f 47 54 0a 2a 2a 20 20 20 20  TRAINT_GT.**    
5ab0: 20 57 4f 5f 47 45 20 20 20 20 3d 3d 20 53 51 4c   WO_GE    == SQL
5ac0: 49 54 45 5f 49 4e 44 45 58 5f 43 4f 4e 53 54 52  ITE_INDEX_CONSTR
5ad0: 41 49 4e 54 5f 47 45 0a 2a 2a 20 20 20 20 20 57  AINT_GE.**     W
5ae0: 4f 5f 4d 41 54 43 48 20 3d 3d 20 53 51 4c 49 54  O_MATCH == SQLIT
5af0: 45 5f 49 4e 44 45 58 5f 43 4f 4e 53 54 52 41 49  E_INDEX_CONSTRAI
5b00: 4e 54 5f 4d 41 54 43 48 0a 2a 2f 0a 23 64 65 66  NT_MATCH.*/.#def
5b10: 69 6e 65 20 57 4f 5f 49 4e 20 20 20 20 20 30 78  ine WO_IN     0x
5b20: 30 30 30 31 0a 23 64 65 66 69 6e 65 20 57 4f 5f  0001.#define WO_
5b30: 45 51 20 20 20 20 20 30 78 30 30 30 32 0a 23 64  EQ     0x0002.#d
5b40: 65 66 69 6e 65 20 57 4f 5f 4c 54 20 20 20 20 20  efine WO_LT     
5b50: 28 57 4f 5f 45 51 3c 3c 28 54 4b 5f 4c 54 2d 54  (WO_EQ<<(TK_LT-T
5b60: 4b 5f 45 51 29 29 0a 23 64 65 66 69 6e 65 20 57  K_EQ)).#define W
5b70: 4f 5f 4c 45 20 20 20 20 20 28 57 4f 5f 45 51 3c  O_LE     (WO_EQ<
5b80: 3c 28 54 4b 5f 4c 45 2d 54 4b 5f 45 51 29 29 0a  <(TK_LE-TK_EQ)).
5b90: 23 64 65 66 69 6e 65 20 57 4f 5f 47 54 20 20 20  #define WO_GT   
5ba0: 20 20 28 57 4f 5f 45 51 3c 3c 28 54 4b 5f 47 54    (WO_EQ<<(TK_GT
5bb0: 2d 54 4b 5f 45 51 29 29 0a 23 64 65 66 69 6e 65  -TK_EQ)).#define
5bc0: 20 57 4f 5f 47 45 20 20 20 20 20 28 57 4f 5f 45   WO_GE     (WO_E
5bd0: 51 3c 3c 28 54 4b 5f 47 45 2d 54 4b 5f 45 51 29  Q<<(TK_GE-TK_EQ)
5be0: 29 0a 23 64 65 66 69 6e 65 20 57 4f 5f 4d 41 54  ).#define WO_MAT
5bf0: 43 48 20 20 30 78 30 30 34 30 0a 23 64 65 66 69  CH  0x0040.#defi
5c00: 6e 65 20 57 4f 5f 49 53 20 20 20 20 20 30 78 30  ne WO_IS     0x0
5c10: 30 38 30 0a 23 64 65 66 69 6e 65 20 57 4f 5f 49  080.#define WO_I
5c20: 53 4e 55 4c 4c 20 30 78 30 31 30 30 0a 23 64 65  SNULL 0x0100.#de
5c30: 66 69 6e 65 20 57 4f 5f 4f 52 20 20 20 20 20 30  fine WO_OR     0
5c40: 78 30 32 30 30 20 20 20 20 20 20 20 2f 2a 20 54  x0200       /* T
5c50: 77 6f 20 6f 72 20 6d 6f 72 65 20 4f 52 2d 63 6f  wo or more OR-co
5c60: 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20 2a 2f  nnected terms */
5c70: 0a 23 64 65 66 69 6e 65 20 57 4f 5f 41 4e 44 20  .#define WO_AND 
5c80: 20 20 20 30 78 30 34 30 30 20 20 20 20 20 20 20     0x0400       
5c90: 2f 2a 20 54 77 6f 20 6f 72 20 6d 6f 72 65 20 41  /* Two or more A
5ca0: 4e 44 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72  ND-connected ter
5cb0: 6d 73 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 4f  ms */.#define WO
5cc0: 5f 45 51 55 49 56 20 20 30 78 30 38 30 30 20 20  _EQUIV  0x0800  
5cd0: 20 20 20 20 20 2f 2a 20 4f 66 20 74 68 65 20 66       /* Of the f
5ce0: 6f 72 6d 20 41 3d 3d 42 2c 20 62 6f 74 68 20 63  orm A==B, both c
5cf0: 6f 6c 75 6d 6e 73 20 2a 2f 0a 23 64 65 66 69 6e  olumns */.#defin
5d00: 65 20 57 4f 5f 4e 4f 4f 50 20 20 20 30 78 31 30  e WO_NOOP   0x10
5d10: 30 30 20 20 20 20 20 20 20 2f 2a 20 54 68 69 73  00       /* This
5d20: 20 74 65 72 6d 20 64 6f 65 73 20 6e 6f 74 20 72   term does not r
5d30: 65 73 74 72 69 63 74 20 73 65 61 72 63 68 20 73  estrict search s
5d40: 70 61 63 65 20 2a 2f 0a 0a 23 64 65 66 69 6e 65  pace */..#define
5d50: 20 57 4f 5f 41 4c 4c 20 20 20 20 30 78 31 66 66   WO_ALL    0x1ff
5d60: 66 20 20 20 20 20 20 20 2f 2a 20 4d 61 73 6b 20  f       /* Mask 
5d70: 6f 66 20 61 6c 6c 20 70 6f 73 73 69 62 6c 65 20  of all possible 
5d80: 57 4f 5f 2a 20 76 61 6c 75 65 73 20 2a 2f 0a 23  WO_* values */.#
5d90: 64 65 66 69 6e 65 20 57 4f 5f 53 49 4e 47 4c 45  define WO_SINGLE
5da0: 20 30 78 30 31 66 66 20 20 20 20 20 20 20 2f 2a   0x01ff       /*
5db0: 20 4d 61 73 6b 20 6f 66 20 61 6c 6c 20 6e 6f 6e   Mask of all non
5dc0: 2d 63 6f 6d 70 6f 75 6e 64 20 57 4f 5f 2a 20 76  -compound WO_* v
5dd0: 61 6c 75 65 73 20 2a 2f 0a 0a 2f 2a 0a 2a 2a 20  alues */../*.** 
5de0: 54 68 65 73 65 20 61 72 65 20 64 65 66 69 6e 69  These are defini
5df0: 74 69 6f 6e 73 20 6f 66 20 62 69 74 73 20 69 6e  tions of bits in
5e00: 20 74 68 65 20 57 68 65 72 65 4c 6f 6f 70 2e 77   the WhereLoop.w
5e10: 73 46 6c 61 67 73 20 66 69 65 6c 64 2e 0a 2a 2a  sFlags field..**
5e20: 20 54 68 65 20 70 61 72 74 69 63 75 6c 61 72 20   The particular 
5e30: 63 6f 6d 62 69 6e 61 74 69 6f 6e 20 6f 66 20 62  combination of b
5e40: 69 74 73 20 69 6e 20 65 61 63 68 20 57 68 65 72  its in each Wher
5e50: 65 4c 6f 6f 70 20 68 65 6c 70 20 74 6f 0a 2a 2a  eLoop help to.**
5e60: 20 64 65 74 65 72 6d 69 6e 65 20 74 68 65 20 61   determine the a
5e70: 6c 67 6f 72 69 74 68 6d 20 74 68 61 74 20 57 68  lgorithm that Wh
5e80: 65 72 65 4c 6f 6f 70 20 72 65 70 72 65 73 65 6e  ereLoop represen
5e90: 74 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 57  ts..*/.#define W
5ea0: 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 45 51 20 20  HERE_COLUMN_EQ  
5eb0: 20 20 30 78 30 30 30 30 30 30 30 31 20 20 2f 2a    0x00000001  /*
5ec0: 20 78 3d 45 58 50 52 20 2a 2f 0a 23 64 65 66 69   x=EXPR */.#defi
5ed0: 6e 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f  ne WHERE_COLUMN_
5ee0: 52 41 4e 47 45 20 30 78 30 30 30 30 30 30 30 32  RANGE 0x00000002
5ef0: 20 20 2f 2a 20 78 3c 45 58 50 52 20 61 6e 64 2f    /* x<EXPR and/
5f00: 6f 72 20 78 3e 45 58 50 52 20 2a 2f 0a 23 64 65  or x>EXPR */.#de
5f10: 66 69 6e 65 20 57 48 45 52 45 5f 43 4f 4c 55 4d  fine WHERE_COLUM
5f20: 4e 5f 49 4e 20 20 20 20 30 78 30 30 30 30 30 30  N_IN    0x000000
5f30: 30 34 20 20 2f 2a 20 78 20 49 4e 20 28 2e 2e 2e  04  /* x IN (...
5f40: 29 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45  ) */.#define WHE
5f50: 52 45 5f 43 4f 4c 55 4d 4e 5f 4e 55 4c 4c 20 20  RE_COLUMN_NULL  
5f60: 30 78 30 30 30 30 30 30 30 38 20 20 2f 2a 20 78  0x00000008  /* x
5f70: 20 49 53 20 4e 55 4c 4c 20 2a 2f 0a 23 64 65 66   IS NULL */.#def
5f80: 69 6e 65 20 57 48 45 52 45 5f 43 4f 4e 53 54 52  ine WHERE_CONSTR
5f90: 41 49 4e 54 20 20 20 30 78 30 30 30 30 30 30 30  AINT   0x0000000
5fa0: 66 20 20 2f 2a 20 41 6e 79 20 6f 66 20 74 68 65  f  /* Any of the
5fb0: 20 57 48 45 52 45 5f 43 4f 4c 55 4d 4e 5f 78 78   WHERE_COLUMN_xx
5fc0: 78 20 76 61 6c 75 65 73 20 2a 2f 0a 23 64 65 66  x values */.#def
5fd0: 69 6e 65 20 57 48 45 52 45 5f 54 4f 50 5f 4c 49  ine WHERE_TOP_LI
5fe0: 4d 49 54 20 20 20 20 30 78 30 30 30 30 30 30 31  MIT    0x0000001
5ff0: 30 20 20 2f 2a 20 78 3c 45 58 50 52 20 6f 72 20  0  /* x<EXPR or 
6000: 78 3c 3d 45 58 50 52 20 63 6f 6e 73 74 72 61 69  x<=EXPR constrai
6010: 6e 74 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  nt */.#define WH
6020: 45 52 45 5f 42 54 4d 5f 4c 49 4d 49 54 20 20 20  ERE_BTM_LIMIT   
6030: 20 30 78 30 30 30 30 30 30 32 30 20 20 2f 2a 20   0x00000020  /* 
6040: 78 3e 45 58 50 52 20 6f 72 20 78 3e 3d 45 58 50  x>EXPR or x>=EXP
6050: 52 20 63 6f 6e 73 74 72 61 69 6e 74 20 2a 2f 0a  R constraint */.
6060: 23 64 65 66 69 6e 65 20 57 48 45 52 45 5f 42 4f  #define WHERE_BO
6070: 54 48 5f 4c 49 4d 49 54 20 20 20 30 78 30 30 30  TH_LIMIT   0x000
6080: 30 30 30 33 30 20 20 2f 2a 20 42 6f 74 68 20 78  00030  /* Both x
6090: 3e 45 58 50 52 20 61 6e 64 20 78 3c 45 58 50 52  >EXPR and x<EXPR
60a0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52   */.#define WHER
60b0: 45 5f 49 44 58 5f 4f 4e 4c 59 20 20 20 20 20 30  E_IDX_ONLY     0
60c0: 78 30 30 30 30 30 30 34 30 20 20 2f 2a 20 55 73  x00000040  /* Us
60d0: 65 20 69 6e 64 65 78 20 6f 6e 6c 79 20 2d 20 6f  e index only - o
60e0: 6d 69 74 20 74 61 62 6c 65 20 2a 2f 0a 23 64 65  mit table */.#de
60f0: 66 69 6e 65 20 57 48 45 52 45 5f 49 50 4b 20 20  fine WHERE_IPK  
6100: 20 20 20 20 20 20 20 20 30 78 30 30 30 30 30 31          0x000001
6110: 30 30 20 20 2f 2a 20 78 20 69 73 20 74 68 65 20  00  /* x is the 
6120: 49 4e 54 45 47 45 52 20 50 52 49 4d 41 52 59 20  INTEGER PRIMARY 
6130: 4b 45 59 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57  KEY */.#define W
6140: 48 45 52 45 5f 49 4e 44 45 58 45 44 20 20 20 20  HERE_INDEXED    
6150: 20 20 30 78 30 30 30 30 30 32 30 30 20 20 2f 2a    0x00000200  /*
6160: 20 57 68 65 72 65 4c 6f 6f 70 2e 75 2e 62 74 72   WhereLoop.u.btr
6170: 65 65 2e 70 49 6e 64 65 78 20 69 73 20 76 61 6c  ee.pIndex is val
6180: 69 64 20 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48  id */.#define WH
6190: 45 52 45 5f 56 49 52 54 55 41 4c 54 41 42 4c 45  ERE_VIRTUALTABLE
61a0: 20 30 78 30 30 30 30 30 34 30 30 20 20 2f 2a 20   0x00000400  /* 
61b0: 57 68 65 72 65 4c 6f 6f 70 2e 75 2e 76 74 61 62  WhereLoop.u.vtab
61c0: 20 69 73 20 76 61 6c 69 64 20 2a 2f 0a 23 64 65   is valid */.#de
61d0: 66 69 6e 65 20 57 48 45 52 45 5f 49 4e 5f 41 42  fine WHERE_IN_AB
61e0: 4c 45 20 20 20 20 20 20 30 78 30 30 30 30 30 38  LE      0x000008
61f0: 30 30 20 20 2f 2a 20 41 62 6c 65 20 74 6f 20 73  00  /* Able to s
6200: 75 70 70 6f 72 74 20 61 6e 20 49 4e 20 6f 70 65  upport an IN ope
6210: 72 61 74 6f 72 20 2a 2f 0a 23 64 65 66 69 6e 65  rator */.#define
6220: 20 57 48 45 52 45 5f 4f 4e 45 52 4f 57 20 20 20   WHERE_ONEROW   
6230: 20 20 20 20 30 78 30 30 30 30 31 30 30 30 20 20      0x00001000  
6240: 2f 2a 20 53 65 6c 65 63 74 73 20 6e 6f 20 6d 6f  /* Selects no mo
6250: 72 65 20 74 68 61 6e 20 6f 6e 65 20 72 6f 77 20  re than one row 
6260: 2a 2f 0a 23 64 65 66 69 6e 65 20 57 48 45 52 45  */.#define WHERE
6270: 5f 4d 55 4c 54 49 5f 4f 52 20 20 20 20 20 30 78  _MULTI_OR     0x
6280: 30 30 30 30 32 30 30 30 20 20 2f 2a 20 4f 52 20  00002000  /* OR 
6290: 75 73 69 6e 67 20 6d 75 6c 74 69 70 6c 65 20 69  using multiple i
62a0: 6e 64 69 63 65 73 20 2a 2f 0a 23 64 65 66 69 6e  ndices */.#defin
62b0: 65 20 57 48 45 52 45 5f 41 55 54 4f 5f 49 4e 44  e WHERE_AUTO_IND
62c0: 45 58 20 20 20 30 78 30 30 30 30 34 30 30 30 20  EX   0x00004000 
62d0: 20 2f 2a 20 55 73 65 73 20 61 6e 20 65 70 68 65   /* Uses an ephe
62e0: 6d 65 72 61 6c 20 69 6e 64 65 78 20 2a 2f 0a 23  meral index */.#
62f0: 64 65 66 69 6e 65 20 57 48 45 52 45 5f 53 4b 49  define WHERE_SKI
6300: 50 53 43 41 4e 20 20 20 20 20 30 78 30 30 30 30  PSCAN     0x0000
6310: 38 30 30 30 20 20 2f 2a 20 55 73 65 73 20 74 68  8000  /* Uses th
6320: 65 20 73 6b 69 70 2d 73 63 61 6e 20 61 6c 67 6f  e skip-scan algo
6330: 72 69 74 68 6d 20 2a 2f 0a 23 64 65 66 69 6e 65  rithm */.#define
6340: 20 57 48 45 52 45 5f 55 4e 51 5f 57 41 4e 54 45   WHERE_UNQ_WANTE
6350: 44 20 20 20 30 78 30 30 30 31 30 30 30 30 20 20  D   0x00010000  
6360: 2f 2a 20 57 48 45 52 45 5f 4f 4e 45 52 4f 57 20  /* WHERE_ONEROW 
6370: 77 6f 75 6c 64 20 68 61 76 65 20 62 65 65 6e 20  would have been 
6380: 68 65 6c 70 66 75 6c 2a 2f 0a 23 64 65 66 69 6e  helpful*/.#defin
6390: 65 20 57 48 45 52 45 5f 50 41 52 54 49 41 4c 49  e WHERE_PARTIALI
63a0: 44 58 20 20 20 30 78 30 30 30 32 30 30 30 30 20  DX   0x00020000 
63b0: 20 2f 2a 20 54 68 65 20 61 75 74 6f 6d 61 74 69   /* The automati
63c0: 63 20 69 6e 64 65 78 20 69 73 20 70 61 72 74 69  c index is parti
63d0: 61 6c 20 2a 2f 0a                                al */.