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