src/whereInt.h

   1 /*
   2 ** 2013-11-12
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 **
  13 ** This file contains structure and macro definitions for the query
  14 ** planner logic in "where.c".  These definitions are broken out into
  15 ** a separate source file for easier editing.
  16 */
  17 #ifndef SQLITE_WHEREINT_H
  18 #define SQLITE_WHEREINT_H
  19
  20
  21 /* Forward references
  22 */
  23 typedef struct WhereClause WhereClause;
  24 typedef struct WhereMaskSet WhereMaskSet;
  25 typedef struct WhereOrInfo WhereOrInfo;
  26 typedef struct WhereAndInfo WhereAndInfo;
  27 typedef struct WhereLevel WhereLevel;
  28 typedef struct WhereLoop WhereLoop;
  29 typedef struct WherePath WherePath;
  30 typedef struct WhereTerm WhereTerm;
  31 typedef struct WhereLoopBuilder WhereLoopBuilder;
  32 typedef struct WhereScan WhereScan;
  33 typedef struct WhereOrCost WhereOrCost;
  34 typedef struct WhereOrSet WhereOrSet;
  35 typedef struct WhereMemBlock WhereMemBlock;
  36 typedef struct WhereRightJoin WhereRightJoin;
  37
  38 /*
  39 ** This object is a header on a block of allocated memory that will be
  40 ** automatically freed when its WInfo object is destructed.
  41 */
  42 struct WhereMemBlock {
  43   WhereMemBlock *pNext;      /* Next block in the chain */
  44   u64 sz;                    /* Bytes of space */
  45 };
  46
  47 /*
  48 ** Extra information attached to a WhereLevel that is a RIGHT JOIN.
  49 */
  50 struct WhereRightJoin {
  51   int iMatch;          /* Cursor used to determine prior matched rows */
  52   int regBloom;        /* Bloom filter for iRJMatch */
  53   int regReturn;       /* Return register for the interior subroutine */
  54   int addrSubrtn;      /* Starting address for the interior subroutine */
  55   int endSubrtn;       /* The last opcode in the interior subroutine */
  56 };
  57
  58 /*
  59 ** This object contains information needed to implement a single nested
  60 ** loop in WHERE clause.
  61 **
  62 ** Contrast this object with WhereLoop.  This object describes the
  63 ** implementation of the loop.  WhereLoop describes the algorithm.
  64 ** This object contains a pointer to the WhereLoop algorithm as one of
  65 ** its elements.
  66 **
  67 ** The WhereInfo object contains a single instance of this object for
  68 ** each term in the FROM clause (which is to say, for each of the
  69 ** nested loops as implemented).  The order of WhereLevel objects determines
  70 ** the loop nested order, with WhereInfo.a[0] being the outer loop and
  71 ** WhereInfo.a[WhereInfo.nLevel-1] being the inner loop.
  72 */
  73 struct WhereLevel {
  74   int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  75   int iTabCur;          /* The VDBE cursor used to access the table */
  76   int iIdxCur;          /* The VDBE cursor used to access pIdx */
  77   int addrBrk;          /* Jump here to break out of the loop */
  78   int addrNxt;          /* Jump here to start the next IN combination */
  79   int addrSkip;         /* Jump here for next iteration of skip-scan */
  80   int addrCont;         /* Jump here to continue with the next loop cycle */
  81   int addrFirst;        /* First instruction of interior of the loop */
  82   int addrBody;         /* Beginning of the body of this loop */
  83   int regBignull;       /* big-null flag reg. True if a NULL-scan is needed */
  84   int addrBignull;      /* Jump here for next part of big-null scan */
  85 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
  86   u32 iLikeRepCntr;     /* LIKE range processing counter register (times 2) */
  87   int addrLikeRep;      /* LIKE range processing address */
  88 #endif
  89   int regFilter;        /* Bloom filter */
  90   WhereRightJoin *pRJ;  /* Extra information for RIGHT JOIN */
  91   u8 iFrom;             /* Which entry in the FROM clause */
  92   u8 op, p3, p5;        /* Opcode, P3 & P5 of the opcode that ends the loop */
  93   int p1, p2;           /* Operands of the opcode used to end the loop */
  94   union {               /* Information that depends on pWLoop->wsFlags */
  95     struct {
  96       int nIn;              /* Number of entries in aInLoop[] */
  97       struct InLoop {
  98         int iCur;              /* The VDBE cursor used by this IN operator */
  99         int addrInTop;         /* Top of the IN loop */
 100         int iBase;             /* Base register of multi-key index record */
 101         int nPrefix;           /* Number of prior entries in the key */
 102         u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
 103       } *aInLoop;           /* Information about each nested IN operator */
 104     } in;                 /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */
 105     Index *pCoveringIdx;  /* Possible covering index for WHERE_MULTI_OR */
 106   } u;
 107   struct WhereLoop *pWLoop;  /* The selected WhereLoop object */
 108   Bitmask notReady;          /* FROM entries not usable at this level */
 109 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
 110   int addrVisit;        /* Address at which row is visited */
 111 #endif
 112 };
 113
 114 /*
 115 ** Each instance of this object represents an algorithm for evaluating one
 116 ** term of a join.  Every term of the FROM clause will have at least
 117 ** one corresponding WhereLoop object (unless INDEXED BY constraints
 118 ** prevent a query solution - which is an error) and many terms of the
 119 ** FROM clause will have multiple WhereLoop objects, each describing a
 120 ** potential way of implementing that FROM-clause term, together with
 121 ** dependencies and cost estimates for using the chosen algorithm.
 122 **
 123 ** Query planning consists of building up a collection of these WhereLoop
 124 ** objects, then computing a particular sequence of WhereLoop objects, with
 125 ** one WhereLoop object per FROM clause term, that satisfy all dependencies
 126 ** and that minimize the overall cost.
 127 */
 128 struct WhereLoop {
 129   Bitmask prereq;       /* Bitmask of other loops that must run first */
 130   Bitmask maskSelf;     /* Bitmask identifying table iTab */
 131 #ifdef SQLITE_DEBUG
 132   char cId;             /* Symbolic ID of this loop for debugging use */
 133 #endif
 134   u8 iTab;              /* Position in FROM clause of table for this loop */
 135   u8 iSortIdx;          /* Sorting index number.  0==None */
 136   LogEst rSetup;        /* One-time setup cost (ex: create transient index) */
 137   LogEst rRun;          /* Cost of running each loop */
 138   LogEst nOut;          /* Estimated number of output rows */
 139   union {
 140     struct {               /* Information for internal btree tables */
 141       u16 nEq;               /* Number of equality constraints */
 142       u16 nBtm;              /* Size of BTM vector */
 143       u16 nTop;              /* Size of TOP vector */
 144       u16 nDistinctCol;      /* Index columns used to sort for DISTINCT */
 145       Index *pIndex;         /* Index used, or NULL */
 146       ExprList *pOrderBy;    /* ORDER BY clause if this is really a subquery */
 147     } btree;
 148     struct {               /* Information for virtual tables */
 149       int idxNum;            /* Index number */
 150       u32 needFree : 1;      /* True if sqlite3_free(idxStr) is needed */
 151       u32 bOmitOffset : 1;   /* True to let virtual table handle offset */
 152       u32 bIdxNumHex : 1;    /* Show idxNum as hex in EXPLAIN QUERY PLAN */
 153       i8 isOrdered;          /* True if satisfies ORDER BY */
 154       u16 omitMask;          /* Terms that may be omitted */
 155       char *idxStr;          /* Index identifier string */
 156       u32 mHandleIn;         /* Terms to handle as IN(...) instead of == */
 157     } vtab;
 158   } u;
 159   u32 wsFlags;          /* WHERE_* flags describing the plan */
 160   u16 nLTerm;           /* Number of entries in aLTerm[] */
 161   u16 nSkip;            /* Number of NULL aLTerm[] entries */
 162   /**** whereLoopXfer() copies fields above ***********************/
 163 # define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot)
 164   u16 nLSlot;           /* Number of slots allocated for aLTerm[] */
 165   LogEst rStarDelta;    /* Cost delta due to star-schema heuristic.  Not
 166                         ** initialized unless pWInfo->nOutStarDelta>0 */
 167   WhereTerm **aLTerm;   /* WhereTerms used */
 168   WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
 169   WhereTerm *aLTermSpace[3];  /* Initial aLTerm[] space */
 170 };
 171
 172 /* This object holds the prerequisites and the cost of running a
 173 ** subquery on one operand of an OR operator in the WHERE clause.
 174 ** See WhereOrSet for additional information
 175 */
 176 struct WhereOrCost {
 177   Bitmask prereq;     /* Prerequisites */
 178   LogEst rRun;        /* Cost of running this subquery */
 179   LogEst nOut;        /* Number of outputs for this subquery */
 180 };
 181
 182 /* The WhereOrSet object holds a set of possible WhereOrCosts that
 183 ** correspond to the subquery(s) of OR-clause processing.  Only the
 184 ** best N_OR_COST elements are retained.
 185 */
 186 #define N_OR_COST 3
 187 struct WhereOrSet {
 188   u16 n;                      /* Number of valid a[] entries */
 189   WhereOrCost a[N_OR_COST];   /* Set of best costs */
 190 };
 191
 192 /*
 193 ** Each instance of this object holds a sequence of WhereLoop objects
 194 ** that implement some or all of a query plan.
 195 **
 196 ** Think of each WhereLoop object as a node in a graph with arcs
 197 ** showing dependencies and costs for travelling between nodes.  (That is
 198 ** not a completely accurate description because WhereLoop costs are a
 199 ** vector, not a scalar, and because dependencies are many-to-one, not
 200 ** one-to-one as are graph nodes.  But it is a useful visualization aid.)
 201 ** Then a WherePath object is a path through the graph that visits some
 202 ** or all of the WhereLoop objects once.
 203 **
 204 ** The "solver" works by creating the N best WherePath objects of length
 205 ** 1.  Then using those as a basis to compute the N best WherePath objects
 206 ** of length 2.  And so forth until the length of WherePaths equals the
 207 ** number of nodes in the FROM clause.  The best (lowest cost) WherePath
 208 ** at the end is the chosen query plan.
 209 */
 210 struct WherePath {
 211   Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
 212   Bitmask revLoop;      /* aLoop[]s that should be reversed for ORDER BY */
 213   LogEst nRow;          /* Estimated number of rows generated by this path */
 214   LogEst rCost;         /* Total cost of this path */
 215   LogEst rUnsorted;     /* Total cost of this path ignoring sorting costs */
 216   i8 isOrdered;         /* No. of ORDER BY terms satisfied. -1 for unknown */
 217   WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
 218 };
 219
 220 /*
 221 ** The query generator uses an array of instances of this structure to
 222 ** help it analyze the subexpressions of the WHERE clause.  Each WHERE
 223 ** clause subexpression is separated from the others by AND operators,
 224 ** usually, or sometimes subexpressions separated by OR.
 225 **
 226 ** All WhereTerms are collected into a single WhereClause structure.
 227 ** The following identity holds:
 228 **
 229 **        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
 230 **
 231 ** When a term is of the form:
 232 **
 233 **              X <op> <expr>
 234 **
 235 ** where X is a column name and <op> is one of certain operators,
 236 ** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
 237 ** cursor number and column number for X.  WhereTerm.eOperator records
 238 ** the <op> using a bitmask encoding defined by WO_xxx below.  The
 239 ** use of a bitmask encoding for the operator allows us to search
 240 ** quickly for terms that match any of several different operators.
 241 **
 242 ** A WhereTerm might also be two or more subterms connected by OR:
 243 **
 244 **         (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
 245 **
 246 ** In this second case, wtFlag has the TERM_ORINFO bit set and eOperator==WO_OR
 247 ** and the WhereTerm.u.pOrInfo field points to auxiliary information that
 248 ** is collected about the OR clause.
 249 **
 250 ** If a term in the WHERE clause does not match either of the two previous
 251 ** categories, then eOperator==0.  The WhereTerm.pExpr field is still set
 252 ** to the original subexpression content and wtFlags is set up appropriately
 253 ** but no other fields in the WhereTerm object are meaningful.
 254 **
 255 ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
 256 ** but they do so indirectly.  A single WhereMaskSet structure translates
 257 ** cursor number into bits and the translated bit is stored in the prereq
 258 ** fields.  The translation is used in order to maximize the number of
 259 ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be
 260 ** spread out over the non-negative integers.  For example, the cursor
 261 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The WhereMaskSet
 262 ** translates these sparse cursor numbers into consecutive integers
 263 ** beginning with 0 in order to make the best possible use of the available
 264 ** bits in the Bitmask.  So, in the example above, the cursor numbers
 265 ** would be mapped into integers 0 through 7.
 266 **
 267 ** The number of terms in a join is limited by the number of bits
 268 ** in prereqRight and prereqAll.  The default is 64 bits, hence SQLite
 269 ** is only able to process joins with 64 or fewer tables.
 270 */
 271 struct WhereTerm {
 272   Expr *pExpr;            /* Pointer to the subexpression that is this term */
 273   WhereClause *pWC;       /* The clause this term is part of */
 274   LogEst truthProb;       /* Probability of truth for this expression */
 275   u16 wtFlags;            /* TERM_xxx bit flags.  See below */
 276   u16 eOperator;          /* A WO_xx value describing <op> */
 277   u8 nChild;              /* Number of children that must disable us */
 278   u8 eMatchOp;            /* Op for vtab MATCH/LIKE/GLOB/REGEXP terms */
 279   int iParent;            /* Disable pWC->a[iParent] when this term disabled */
 280   int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
 281   union {
 282     struct {
 283       int leftColumn;         /* Column number of X in "X <op> <expr>" */
 284       int iField;             /* Field in (?,?,?) IN (SELECT...) vector */
 285     } x;                    /* Opcode other than OP_OR or OP_AND */
 286     WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
 287     WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
 288   } u;
 289   Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
 290   Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
 291 };
 292
 293 /*
 294 ** Allowed values of WhereTerm.wtFlags
 295 */
 296 #define TERM_DYNAMIC    0x0001 /* Need to call sqlite3ExprDelete(db, pExpr) */
 297 #define TERM_VIRTUAL    0x0002 /* Added by the optimizer.  Do not code */
 298 #define TERM_CODED      0x0004 /* This term is already coded */
 299 #define TERM_COPIED     0x0008 /* Has a child */
 300 #define TERM_ORINFO     0x0010 /* Need to free the WhereTerm.u.pOrInfo object */
 301 #define TERM_ANDINFO    0x0020 /* Need to free the WhereTerm.u.pAndInfo obj */
 302 #define TERM_OK         0x0040 /* Used during OR-clause processing */
 303 #define TERM_VNULL      0x0080 /* Manufactured x>NULL or x<=NULL term */
 304 #define TERM_LIKEOPT    0x0100 /* Virtual terms from the LIKE optimization */
 305 #define TERM_LIKECOND   0x0200 /* Conditionally this LIKE operator term */
 306 #define TERM_LIKE       0x0400 /* The original LIKE operator */
 307 #define TERM_IS         0x0800 /* Term.pExpr is an IS operator */
 308 #define TERM_VARSELECT  0x1000 /* Term.pExpr contains a correlated sub-query */
 309 #define TERM_HEURTRUTH  0x2000 /* Heuristic truthProb used */
 310 #ifdef SQLITE_ENABLE_STAT4
 311 #  define TERM_HIGHTRUTH  0x4000 /* Term excludes few rows */
 312 #else
 313 #  define TERM_HIGHTRUTH  0      /* Only used with STAT4 */
 314 #endif
 315 #define TERM_SLICE      0x8000 /* One slice of a row-value/vector comparison */
 316
 317 /*
 318 ** An instance of the WhereScan object is used as an iterator for locating
 319 ** terms in the WHERE clause that are useful to the query planner.
 320 */
 321 struct WhereScan {
 322   WhereClause *pOrigWC;      /* Original, innermost WhereClause */
 323   WhereClause *pWC;          /* WhereClause currently being scanned */
 324   const char *zCollName;     /* Required collating sequence, if not NULL */
 325   Expr *pIdxExpr;            /* Search for this index expression */
 326   int k;                     /* Resume scanning at this->pWC->a[this->k] */
 327   u32 opMask;                /* Acceptable operators */
 328   char idxaff;               /* Must match this affinity, if zCollName!=NULL */
 329   unsigned char iEquiv;      /* Current slot in aiCur[] and aiColumn[] */
 330   unsigned char nEquiv;      /* Number of entries in aiCur[] and aiColumn[] */
 331   int aiCur[11];             /* Cursors in the equivalence class */
 332   i16 aiColumn[11];          /* Corresponding column number in the eq-class */
 333 };
 334
 335 /*
 336 ** An instance of the following structure holds all information about a
 337 ** WHERE clause.  Mostly this is a container for one or more WhereTerms.
 338 **
 339 ** Explanation of pOuter:  For a WHERE clause of the form
 340 **
 341 **           a AND ((b AND c) OR (d AND e)) AND f
 342 **
 343 ** There are separate WhereClause objects for the whole clause and for
 344 ** the subclauses "(b AND c)" and "(d AND e)".  The pOuter field of the
 345 ** subclauses points to the WhereClause object for the whole clause.
 346 */
 347 struct WhereClause {
 348   WhereInfo *pWInfo;       /* WHERE clause processing context */
 349   WhereClause *pOuter;     /* Outer conjunction */
 350   u8 op;                   /* Split operator.  TK_AND or TK_OR */
 351   u8 hasOr;                /* True if any a[].eOperator is WO_OR */
 352   int nTerm;               /* Number of terms */
 353   int nSlot;               /* Number of entries in a[] */
 354   int nBase;               /* Number of terms through the last non-Virtual */
 355   WhereTerm *a;            /* Each a[] describes a term of the WHERE clause */
 356 #if defined(SQLITE_SMALL_STACK)
 357   WhereTerm aStatic[1];    /* Initial static space for a[] */
 358 #else
 359   WhereTerm aStatic[8];    /* Initial static space for a[] */
 360 #endif
 361 };
 362
 363 /*
 364 ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
 365 ** a dynamically allocated instance of the following structure.
 366 */
 367 struct WhereOrInfo {
 368   WhereClause wc;          /* Decomposition into subterms */
 369   Bitmask indexable;       /* Bitmask of all indexable tables in the clause */
 370 };
 371
 372 /*
 373 ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
 374 ** a dynamically allocated instance of the following structure.
 375 */
 376 struct WhereAndInfo {
 377   WhereClause wc;          /* The subexpression broken out */
 378 };
 379
 380 /*
 381 ** An instance of the following structure keeps track of a mapping
 382 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
 383 **
 384 ** The VDBE cursor numbers are small integers contained in
 385 ** SrcItem.iCursor and Expr.iTable fields.  For any given WHERE
 386 ** clause, the cursor numbers might not begin with 0 and they might
 387 ** contain gaps in the numbering sequence.  But we want to make maximum
 388 ** use of the bits in our bitmasks.  This structure provides a mapping
 389 ** from the sparse cursor numbers into consecutive integers beginning
 390 ** with 0.
 391 **
 392 ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
 393 ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.
 394 **
 395 ** For example, if the WHERE clause expression used these VDBE
 396 ** cursors:  4, 5, 8, 29, 57, 73.  Then the  WhereMaskSet structure
 397 ** would map those cursor numbers into bits 0 through 5.
 398 **
 399 ** Note that the mapping is not necessarily ordered.  In the example
 400 ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,
 401 ** 57->5, 73->4.  Or one of 719 other combinations might be used. It
 402 ** does not really matter.  What is important is that sparse cursor
 403 ** numbers all get mapped into bit numbers that begin with 0 and contain
 404 ** no gaps.
 405 */
 406 struct WhereMaskSet {
 407   int bVarSelect;               /* Used by sqlite3WhereExprUsage() */
 408   int n;                        /* Number of assigned cursor values */
 409   int ix[BMS];                  /* Cursor assigned to each bit */
 410 };
 411
 412 /*
 413 ** This object is a convenience wrapper holding all information needed
 414 ** to construct WhereLoop objects for a particular query.
 415 */
 416 struct WhereLoopBuilder {
 417   WhereInfo *pWInfo;        /* Information about this WHERE */
 418   WhereClause *pWC;         /* WHERE clause terms */
 419   WhereLoop *pNew;          /* Template WhereLoop */
 420   WhereOrSet *pOrSet;       /* Record best loops here, if not NULL */
 421 #ifdef SQLITE_ENABLE_STAT4
 422   UnpackedRecord *pRec;     /* Probe for stat4 (if required) */
 423   int nRecValid;            /* Number of valid fields currently in pRec */
 424 #endif
 425   unsigned char bldFlags1;  /* First set of SQLITE_BLDF_* flags */
 426   unsigned char bldFlags2;  /* Second set of SQLITE_BLDF_* flags */
 427   unsigned int iPlanLimit;  /* Search limiter */
 428 };
 429
 430 /* Allowed values for WhereLoopBuider.bldFlags */
 431 #define SQLITE_BLDF1_INDEXED  0x0001   /* An index is used */
 432 #define SQLITE_BLDF1_UNIQUE   0x0002   /* All keys of a UNIQUE index used */
 433
 434 #define SQLITE_BLDF2_2NDPASS  0x0004   /* Second builder pass needed */
 435
 436 /* The WhereLoopBuilder.iPlanLimit is used to limit the number of
 437 ** index+constraint combinations the query planner will consider for a
 438 ** particular query.  If this parameter is unlimited, then certain
 439 ** pathological queries can spend excess time in the sqlite3WhereBegin()
 440 ** routine.  The limit is high enough that is should not impact real-world
 441 ** queries.
 442 **
 443 ** SQLITE_QUERY_PLANNER_LIMIT is the baseline limit.  The limit is
 444 ** increased by SQLITE_QUERY_PLANNER_LIMIT_INCR before each term of the FROM
 445 ** clause is processed, so that every table in a join is guaranteed to be
 446 ** able to propose a some index+constraint combinations even if the initial
 447 ** baseline limit was exhausted by prior tables of the join.
 448 */
 449 #ifndef SQLITE_QUERY_PLANNER_LIMIT
 450 # define SQLITE_QUERY_PLANNER_LIMIT 20000
 451 #endif
 452 #ifndef SQLITE_QUERY_PLANNER_LIMIT_INCR
 453 # define SQLITE_QUERY_PLANNER_LIMIT_INCR 1000
 454 #endif
 455
 456 /*
 457 ** The WHERE clause processing routine has two halves.  The
 458 ** first part does the start of the WHERE loop and the second
 459 ** half does the tail of the WHERE loop.  An instance of
 460 ** this structure is returned by the first half and passed
 461 ** into the second half to give some continuity.
 462 **
 463 ** An instance of this object holds the complete state of the query
 464 ** planner.
 465 */
 466 struct WhereInfo {
 467   Parse *pParse;            /* Parsing and code generating context */
 468   SrcList *pTabList;        /* List of tables in the join */
 469   ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
 470   ExprList *pResultSet;     /* Result set of the query */
 471 #if WHERETRACE_ENABLED
 472   Expr *pWhere;             /* The complete WHERE clause */
 473 #endif
 474   Select *pSelect;          /* The entire SELECT statement containing WHERE */
 475   int aiCurOnePass[2];      /* OP_OpenWrite cursors for the ONEPASS opt */
 476   int iContinue;            /* Jump here to continue with next record */
 477   int iBreak;               /* Jump here to break out of the loop */
 478   int savedNQueryLoop;      /* pParse->nQueryLoop outside the WHERE loop */
 479   u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
 480   LogEst iLimit;            /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */
 481   u8 nLevel;                /* Number of nested loop */
 482   i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
 483   u8 eOnePass;              /* ONEPASS_OFF, or _SINGLE, or _MULTI */
 484   u8 eDistinct;             /* One of the WHERE_DISTINCT_* values */
 485   unsigned bDeferredSeek :1;   /* Uses OP_DeferredSeek */
 486   unsigned untestedTerms :1;   /* Not all WHERE terms resolved by outer loop */
 487   unsigned bOrderedInnerLoop:1;/* True if only the inner-most loop is ordered */
 488   unsigned sorted :1;          /* True if really sorted (not just grouped) */
 489   LogEst nOutStarDelta;     /* Artifical nOut reduction for star-query */
 490   LogEst nRowOut;           /* Estimated number of output rows */
 491   int iTop;                 /* The very beginning of the WHERE loop */
 492   int iEndWhere;            /* End of the WHERE clause itself */
 493   WhereLoop *pLoops;        /* List of all WhereLoop objects */
 494   WhereMemBlock *pMemToFree;/* Memory to free when this object destroyed */
 495   Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
 496   WhereClause sWC;          /* Decomposition of the WHERE clause */
 497   WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
 498   WhereLevel a[1];          /* Information about each nest loop in WHERE */
 499 };
 500
 501 /*
 502 ** Private interfaces - callable only by other where.c routines.
 503 **
 504 ** where.c:
 505 */
 506 Bitmask sqlite3WhereGetMask(WhereMaskSet*,int);
 507 #ifdef WHERETRACE_ENABLED
 508 void sqlite3WhereClausePrint(WhereClause *pWC);
 509 void sqlite3WhereTermPrint(WhereTerm *pTerm, int iTerm);
 510 void sqlite3WhereLoopPrint(const WhereLoop *p, const WhereClause *pWC);
 511 #endif
 512 WhereTerm *sqlite3WhereFindTerm(
 513   WhereClause *pWC,     /* The WHERE clause to be searched */
 514   int iCur,             /* Cursor number of LHS */
 515   int iColumn,          /* Column number of LHS */
 516   Bitmask notReady,     /* RHS must not overlap with this mask */
 517   u32 op,               /* Mask of WO_xx values describing operator */
 518   Index *pIdx           /* Must be compatible with this index, if not NULL */
 519 );
 520 void *sqlite3WhereMalloc(WhereInfo *pWInfo, u64 nByte);
 521 void *sqlite3WhereRealloc(WhereInfo *pWInfo, void *pOld, u64 nByte);
 522
 523 /* wherecode.c: */
 524 #ifndef SQLITE_OMIT_EXPLAIN
 525 int sqlite3WhereExplainOneScan(
 526   Parse *pParse,                  /* Parse context */
 527   SrcList *pTabList,              /* Table list this loop refers to */
 528   WhereLevel *pLevel,             /* Scan to write OP_Explain opcode for */
 529   u16 wctrlFlags                  /* Flags passed to sqlite3WhereBegin() */
 530 );
 531 int sqlite3WhereExplainBloomFilter(
 532   const Parse *pParse,            /* Parse context */
 533   const WhereInfo *pWInfo,        /* WHERE clause */
 534   const WhereLevel *pLevel        /* Bloom filter on this level */
 535 );
 536 #else
 537 # define sqlite3WhereExplainOneScan(u,v,w,x) 0
 538 # define sqlite3WhereExplainBloomFilter(u,v,w) 0
 539 #endif /* SQLITE_OMIT_EXPLAIN */
 540 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
 541 void sqlite3WhereAddScanStatus(
 542   Vdbe *v,                        /* Vdbe to add scanstatus entry to */
 543   SrcList *pSrclist,              /* FROM clause pLvl reads data from */
 544   WhereLevel *pLvl,               /* Level to add scanstatus() entry for */
 545   int addrExplain                 /* Address of OP_Explain (or 0) */
 546 );
 547 #else
 548 # define sqlite3WhereAddScanStatus(a, b, c, d) ((void)d)
 549 #endif
 550 Bitmask sqlite3WhereCodeOneLoopStart(
 551   Parse *pParse,       /* Parsing context */
 552   Vdbe *v,             /* Prepared statement under construction */
 553   WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
 554   int iLevel,          /* Which level of pWInfo->a[] should be coded */
 555   WhereLevel *pLevel,  /* The current level pointer */
 556   Bitmask notReady     /* Which tables are currently available */
 557 );
 558 SQLITE_NOINLINE void sqlite3WhereRightJoinLoop(
 559   WhereInfo *pWInfo,
 560   int iLevel,
 561   WhereLevel *pLevel
 562 );
 563
 564 /* whereexpr.c: */
 565 void sqlite3WhereClauseInit(WhereClause*,WhereInfo*);
 566 void sqlite3WhereClauseClear(WhereClause*);
 567 void sqlite3WhereSplit(WhereClause*,Expr*,u8);
 568 void sqlite3WhereAddLimit(WhereClause*, Select*);
 569 Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*);
 570 Bitmask sqlite3WhereExprUsageNN(WhereMaskSet*, Expr*);
 571 Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*);
 572 void sqlite3WhereExprAnalyze(SrcList*, WhereClause*);
 573 void sqlite3WhereTabFuncArgs(Parse*, SrcItem*, WhereClause*);
 574
 575
 576
 577
 578
 579 /*
 580 ** Bitmasks for the operators on WhereTerm objects.  These are all
 581 ** operators that are of interest to the query planner.  An
 582 ** OR-ed combination of these values can be used when searching for
 583 ** particular WhereTerms within a WhereClause.
 584 **
 585 ** Value constraints:
 586 **     WO_EQ    == SQLITE_INDEX_CONSTRAINT_EQ
 587 **     WO_LT    == SQLITE_INDEX_CONSTRAINT_LT
 588 **     WO_LE    == SQLITE_INDEX_CONSTRAINT_LE
 589 **     WO_GT    == SQLITE_INDEX_CONSTRAINT_GT
 590 **     WO_GE    == SQLITE_INDEX_CONSTRAINT_GE
 591 */
 592 #define WO_IN     0x0001
 593 #define WO_EQ     0x0002
 594 #define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))
 595 #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))
 596 #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))
 597 #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))
 598 #define WO_AUX    0x0040       /* Op useful to virtual tables only */
 599 #define WO_IS     0x0080
 600 #define WO_ISNULL 0x0100
 601 #define WO_OR     0x0200       /* Two or more OR-connected terms */
 602 #define WO_AND    0x0400       /* Two or more AND-connected terms */
 603 #define WO_EQUIV  0x0800       /* Of the form A==B, both columns */
 604 #define WO_NOOP   0x1000       /* This term does not restrict search space */
 605 #define WO_ROWVAL 0x2000       /* A row-value term */
 606
 607 #define WO_ALL    0x3fff       /* Mask of all possible WO_* values */
 608 #define WO_SINGLE 0x01ff       /* Mask of all non-compound WO_* values */
 609
 610 /*
 611 ** These are definitions of bits in the WhereLoop.wsFlags field.
 612 ** The particular combination of bits in each WhereLoop help to
 613 ** determine the algorithm that WhereLoop represents.
 614 */
 615 #define WHERE_COLUMN_EQ    0x00000001  /* x=EXPR */
 616 #define WHERE_COLUMN_RANGE 0x00000002  /* x<EXPR and/or x>EXPR */
 617 #define WHERE_COLUMN_IN    0x00000004  /* x IN (...) */
 618 #define WHERE_COLUMN_NULL  0x00000008  /* x IS NULL */
 619 #define WHERE_CONSTRAINT   0x0000000f  /* Any of the WHERE_COLUMN_xxx values */
 620 #define WHERE_TOP_LIMIT    0x00000010  /* x<EXPR or x<=EXPR constraint */
 621 #define WHERE_BTM_LIMIT    0x00000020  /* x>EXPR or x>=EXPR constraint */
 622 #define WHERE_BOTH_LIMIT   0x00000030  /* Both x>EXPR and x<EXPR */
 623 #define WHERE_IDX_ONLY     0x00000040  /* Use index only - omit table */
 624 #define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
 625 #define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
 626 #define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
 627 #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
 628 #define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
 629 #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
 630 #define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
 631 #define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */
 632 #define WHERE_UNQ_WANTED   0x00010000  /* WHERE_ONEROW would have been helpful*/
 633 #define WHERE_PARTIALIDX   0x00020000  /* The automatic index is partial */
 634 #define WHERE_IN_EARLYOUT  0x00040000  /* Perhaps quit IN loops early */
 635 #define WHERE_BIGNULL_SORT 0x00080000  /* Column nEq of index is BIGNULL */
 636 #define WHERE_IN_SEEKSCAN  0x00100000  /* Seek-scan optimization for IN */
 637 #define WHERE_TRANSCONS    0x00200000  /* Uses a transitive constraint */
 638 #define WHERE_BLOOMFILTER  0x00400000  /* Consider using a Bloom-filter */
 639 #define WHERE_SELFCULL     0x00800000  /* nOut reduced by extra WHERE terms */
 640 #define WHERE_OMIT_OFFSET  0x01000000  /* Set offset counter to zero */
 641 #define WHERE_COROUTINE    0x02000000  /* Implemented by co-routine.
 642                                        ** NB: False-negatives are possible */
 643 #define WHERE_EXPRIDX      0x04000000  /* Uses an index-on-expressions */
 644
 645 #endif /* !defined(SQLITE_WHEREINT_H) */