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