| /* |
| ** 2013-11-12 |
| ** |
| ** The author disclaims copyright to this source code. In place of |
| ** a legal notice, here is a blessing: |
| ** |
| ** May you do good and not evil. |
| ** May you find forgiveness for yourself and forgive others. |
| ** May you share freely, never taking more than you give. |
| ** |
| ************************************************************************* |
| ** |
| ** This file contains structure and macro definitions for the query |
| ** planner logic in "where.c". These definitions are broken out into |
| ** a separate source file for easier editing. |
| */ |
| |
| /* |
| ** Trace output macros |
| */ |
| #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) |
| /***/ extern int sqlite3WhereTrace; |
| #endif |
| #if defined(SQLITE_DEBUG) \ |
| && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE)) |
| # define WHERETRACE(K,X) if(sqlite3WhereTrace&(K)) sqlite3DebugPrintf X |
| # define WHERETRACE_ENABLED 1 |
| #else |
| # define WHERETRACE(K,X) |
| #endif |
| |
| /* Forward references |
| */ |
| typedef struct WhereClause WhereClause; |
| typedef struct WhereMaskSet WhereMaskSet; |
| typedef struct WhereOrInfo WhereOrInfo; |
| typedef struct WhereAndInfo WhereAndInfo; |
| typedef struct WhereLevel WhereLevel; |
| typedef struct WhereLoop WhereLoop; |
| typedef struct WherePath WherePath; |
| typedef struct WhereTerm WhereTerm; |
| typedef struct WhereLoopBuilder WhereLoopBuilder; |
| typedef struct WhereScan WhereScan; |
| typedef struct WhereOrCost WhereOrCost; |
| typedef struct WhereOrSet WhereOrSet; |
| |
| /* |
| ** This object contains information needed to implement a single nested |
| ** loop in WHERE clause. |
| ** |
| ** Contrast this object with WhereLoop. This object describes the |
| ** implementation of the loop. WhereLoop describes the algorithm. |
| ** This object contains a pointer to the WhereLoop algorithm as one of |
| ** its elements. |
| ** |
| ** The WhereInfo object contains a single instance of this object for |
| ** each term in the FROM clause (which is to say, for each of the |
| ** nested loops as implemented). The order of WhereLevel objects determines |
| ** the loop nested order, with WhereInfo.a[0] being the outer loop and |
| ** WhereInfo.a[WhereInfo.nLevel-1] being the inner loop. |
| */ |
| struct WhereLevel { |
| int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ |
| int iTabCur; /* The VDBE cursor used to access the table */ |
| int iIdxCur; /* The VDBE cursor used to access pIdx */ |
| int addrBrk; /* Jump here to break out of the loop */ |
| int addrNxt; /* Jump here to start the next IN combination */ |
| int addrSkip; /* Jump here for next iteration of skip-scan */ |
| int addrCont; /* Jump here to continue with the next loop cycle */ |
| int addrFirst; /* First instruction of interior of the loop */ |
| int addrBody; /* Beginning of the body of this loop */ |
| #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS |
| u32 iLikeRepCntr; /* LIKE range processing counter register (times 2) */ |
| int addrLikeRep; /* LIKE range processing address */ |
| #endif |
| u8 iFrom; /* Which entry in the FROM clause */ |
| u8 op, p3, p5; /* Opcode, P3 & P5 of the opcode that ends the loop */ |
| int p1, p2; /* Operands of the opcode used to ends the loop */ |
| union { /* Information that depends on pWLoop->wsFlags */ |
| struct { |
| int nIn; /* Number of entries in aInLoop[] */ |
| struct InLoop { |
| int iCur; /* The VDBE cursor used by this IN operator */ |
| int addrInTop; /* Top of the IN loop */ |
| int iBase; /* Base register of multi-key index record */ |
| int nPrefix; /* Number of prior entires in the key */ |
| u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */ |
| } *aInLoop; /* Information about each nested IN operator */ |
| } in; /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */ |
| Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ |
| } u; |
| struct WhereLoop *pWLoop; /* The selected WhereLoop object */ |
| Bitmask notReady; /* FROM entries not usable at this level */ |
| #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
| int addrVisit; /* Address at which row is visited */ |
| #endif |
| }; |
| |
| /* |
| ** Each instance of this object represents an algorithm for evaluating one |
| ** term of a join. Every term of the FROM clause will have at least |
| ** one corresponding WhereLoop object (unless INDEXED BY constraints |
| ** prevent a query solution - which is an error) and many terms of the |
| ** FROM clause will have multiple WhereLoop objects, each describing a |
| ** potential way of implementing that FROM-clause term, together with |
| ** dependencies and cost estimates for using the chosen algorithm. |
| ** |
| ** Query planning consists of building up a collection of these WhereLoop |
| ** objects, then computing a particular sequence of WhereLoop objects, with |
| ** one WhereLoop object per FROM clause term, that satisfy all dependencies |
| ** and that minimize the overall cost. |
| */ |
| struct WhereLoop { |
| Bitmask prereq; /* Bitmask of other loops that must run first */ |
| Bitmask maskSelf; /* Bitmask identifying table iTab */ |
| #ifdef SQLITE_DEBUG |
| char cId; /* Symbolic ID of this loop for debugging use */ |
| #endif |
| u8 iTab; /* Position in FROM clause of table for this loop */ |
| u8 iSortIdx; /* Sorting index number. 0==None */ |
| LogEst rSetup; /* One-time setup cost (ex: create transient index) */ |
| LogEst rRun; /* Cost of running each loop */ |
| LogEst nOut; /* Estimated number of output rows */ |
| union { |
| struct { /* Information for internal btree tables */ |
| u16 nEq; /* Number of equality constraints */ |
| u16 nBtm; /* Size of BTM vector */ |
| u16 nTop; /* Size of TOP vector */ |
| u16 nIdxCol; /* Index column used for ORDER BY */ |
| Index *pIndex; /* Index used, or NULL */ |
| } btree; |
| struct { /* Information for virtual tables */ |
| int idxNum; /* Index number */ |
| u8 needFree; /* True if sqlite3_free(idxStr) is needed */ |
| i8 isOrdered; /* True if satisfies ORDER BY */ |
| u16 omitMask; /* Terms that may be omitted */ |
| char *idxStr; /* Index identifier string */ |
| } vtab; |
| } u; |
| u32 wsFlags; /* WHERE_* flags describing the plan */ |
| u16 nLTerm; /* Number of entries in aLTerm[] */ |
| u16 nSkip; /* Number of NULL aLTerm[] entries */ |
| /**** whereLoopXfer() copies fields above ***********************/ |
| # define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot) |
| u16 nLSlot; /* Number of slots allocated for aLTerm[] */ |
| WhereTerm **aLTerm; /* WhereTerms used */ |
| WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */ |
| WhereTerm *aLTermSpace[3]; /* Initial aLTerm[] space */ |
| }; |
| |
| /* This object holds the prerequisites and the cost of running a |
| ** subquery on one operand of an OR operator in the WHERE clause. |
| ** See WhereOrSet for additional information |
| */ |
| struct WhereOrCost { |
| Bitmask prereq; /* Prerequisites */ |
| LogEst rRun; /* Cost of running this subquery */ |
| LogEst nOut; /* Number of outputs for this subquery */ |
| }; |
| |
| /* The WhereOrSet object holds a set of possible WhereOrCosts that |
| ** correspond to the subquery(s) of OR-clause processing. Only the |
| ** best N_OR_COST elements are retained. |
| */ |
| #define N_OR_COST 3 |
| struct WhereOrSet { |
| u16 n; /* Number of valid a[] entries */ |
| WhereOrCost a[N_OR_COST]; /* Set of best costs */ |
| }; |
| |
| /* |
| ** Each instance of this object holds a sequence of WhereLoop objects |
| ** that implement some or all of a query plan. |
| ** |
| ** Think of each WhereLoop object as a node in a graph with arcs |
| ** showing dependencies and costs for travelling between nodes. (That is |
| ** not a completely accurate description because WhereLoop costs are a |
| ** vector, not a scalar, and because dependencies are many-to-one, not |
| ** one-to-one as are graph nodes. But it is a useful visualization aid.) |
| ** Then a WherePath object is a path through the graph that visits some |
| ** or all of the WhereLoop objects once. |
| ** |
| ** The "solver" works by creating the N best WherePath objects of length |
| ** 1. Then using those as a basis to compute the N best WherePath objects |
| ** of length 2. And so forth until the length of WherePaths equals the |
| ** number of nodes in the FROM clause. The best (lowest cost) WherePath |
| ** at the end is the chosen query plan. |
| */ |
| struct WherePath { |
| Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ |
| Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ |
| LogEst nRow; /* Estimated number of rows generated by this path */ |
| LogEst rCost; /* Total cost of this path */ |
| LogEst rUnsorted; /* Total cost of this path ignoring sorting costs */ |
| i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */ |
| WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */ |
| }; |
| |
| /* |
| ** The query generator uses an array of instances of this structure to |
| ** help it analyze the subexpressions of the WHERE clause. Each WHERE |
| ** clause subexpression is separated from the others by AND operators, |
| ** usually, or sometimes subexpressions separated by OR. |
| ** |
| ** All WhereTerms are collected into a single WhereClause structure. |
| ** The following identity holds: |
| ** |
| ** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm |
| ** |
| ** When a term is of the form: |
| ** |
| ** X <op> <expr> |
| ** |
| ** where X is a column name and <op> is one of certain operators, |
| ** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the |
| ** cursor number and column number for X. WhereTerm.eOperator records |
| ** the <op> using a bitmask encoding defined by WO_xxx below. The |
| ** use of a bitmask encoding for the operator allows us to search |
| ** quickly for terms that match any of several different operators. |
| ** |
| ** A WhereTerm might also be two or more subterms connected by OR: |
| ** |
| ** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR .... |
| ** |
| ** In this second case, wtFlag has the TERM_ORINFO bit set and eOperator==WO_OR |
| ** and the WhereTerm.u.pOrInfo field points to auxiliary information that |
| ** is collected about the OR clause. |
| ** |
| ** If a term in the WHERE clause does not match either of the two previous |
| ** categories, then eOperator==0. The WhereTerm.pExpr field is still set |
| ** to the original subexpression content and wtFlags is set up appropriately |
| ** but no other fields in the WhereTerm object are meaningful. |
| ** |
| ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers, |
| ** but they do so indirectly. A single WhereMaskSet structure translates |
| ** cursor number into bits and the translated bit is stored in the prereq |
| ** fields. The translation is used in order to maximize the number of |
| ** bits that will fit in a Bitmask. The VDBE cursor numbers might be |
| ** spread out over the non-negative integers. For example, the cursor |
| ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet |
| ** translates these sparse cursor numbers into consecutive integers |
| ** beginning with 0 in order to make the best possible use of the available |
| ** bits in the Bitmask. So, in the example above, the cursor numbers |
| ** would be mapped into integers 0 through 7. |
| ** |
| ** The number of terms in a join is limited by the number of bits |
| ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite |
| ** is only able to process joins with 64 or fewer tables. |
| */ |
| struct WhereTerm { |
| Expr *pExpr; /* Pointer to the subexpression that is this term */ |
| WhereClause *pWC; /* The clause this term is part of */ |
| LogEst truthProb; /* Probability of truth for this expression */ |
| u16 wtFlags; /* TERM_xxx bit flags. See below */ |
| u16 eOperator; /* A WO_xx value describing <op> */ |
| u8 nChild; /* Number of children that must disable us */ |
| u8 eMatchOp; /* Op for vtab MATCH/LIKE/GLOB/REGEXP terms */ |
| int iParent; /* Disable pWC->a[iParent] when this term disabled */ |
| int leftCursor; /* Cursor number of X in "X <op> <expr>" */ |
| int iField; /* Field in (?,?,?) IN (SELECT...) vector */ |
| union { |
| int leftColumn; /* Column number of X in "X <op> <expr>" */ |
| WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ |
| WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ |
| } u; |
| Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ |
| Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ |
| }; |
| |
| /* |
| ** Allowed values of WhereTerm.wtFlags |
| */ |
| #define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */ |
| #define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */ |
| #define TERM_CODED 0x04 /* This term is already coded */ |
| #define TERM_COPIED 0x08 /* Has a child */ |
| #define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */ |
| #define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */ |
| #define TERM_OR_OK 0x40 /* Used during OR-clause processing */ |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| # define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */ |
| #else |
| # define TERM_VNULL 0x00 /* Disabled if not using stat3 */ |
| #endif |
| #define TERM_LIKEOPT 0x100 /* Virtual terms from the LIKE optimization */ |
| #define TERM_LIKECOND 0x200 /* Conditionally this LIKE operator term */ |
| #define TERM_LIKE 0x400 /* The original LIKE operator */ |
| #define TERM_IS 0x800 /* Term.pExpr is an IS operator */ |
| #define TERM_VARSELECT 0x1000 /* Term.pExpr contains a correlated sub-query */ |
| |
| /* |
| ** An instance of the WhereScan object is used as an iterator for locating |
| ** terms in the WHERE clause that are useful to the query planner. |
| */ |
| struct WhereScan { |
| WhereClause *pOrigWC; /* Original, innermost WhereClause */ |
| WhereClause *pWC; /* WhereClause currently being scanned */ |
| const char *zCollName; /* Required collating sequence, if not NULL */ |
| Expr *pIdxExpr; /* Search for this index expression */ |
| char idxaff; /* Must match this affinity, if zCollName!=NULL */ |
| unsigned char nEquiv; /* Number of entries in aEquiv[] */ |
| unsigned char iEquiv; /* Next unused slot in aEquiv[] */ |
| u32 opMask; /* Acceptable operators */ |
| int k; /* Resume scanning at this->pWC->a[this->k] */ |
| int aiCur[11]; /* Cursors in the equivalence class */ |
| i16 aiColumn[11]; /* Corresponding column number in the eq-class */ |
| }; |
| |
| /* |
| ** An instance of the following structure holds all information about a |
| ** WHERE clause. Mostly this is a container for one or more WhereTerms. |
| ** |
| ** Explanation of pOuter: For a WHERE clause of the form |
| ** |
| ** a AND ((b AND c) OR (d AND e)) AND f |
| ** |
| ** There are separate WhereClause objects for the whole clause and for |
| ** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the |
| ** subclauses points to the WhereClause object for the whole clause. |
| */ |
| struct WhereClause { |
| WhereInfo *pWInfo; /* WHERE clause processing context */ |
| WhereClause *pOuter; /* Outer conjunction */ |
| u8 op; /* Split operator. TK_AND or TK_OR */ |
| u8 hasOr; /* True if any a[].eOperator is WO_OR */ |
| int nTerm; /* Number of terms */ |
| int nSlot; /* Number of entries in a[] */ |
| WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */ |
| #if defined(SQLITE_SMALL_STACK) |
| WhereTerm aStatic[1]; /* Initial static space for a[] */ |
| #else |
| WhereTerm aStatic[8]; /* Initial static space for a[] */ |
| #endif |
| }; |
| |
| /* |
| ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to |
| ** a dynamically allocated instance of the following structure. |
| */ |
| struct WhereOrInfo { |
| WhereClause wc; /* Decomposition into subterms */ |
| Bitmask indexable; /* Bitmask of all indexable tables in the clause */ |
| }; |
| |
| /* |
| ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to |
| ** a dynamically allocated instance of the following structure. |
| */ |
| struct WhereAndInfo { |
| WhereClause wc; /* The subexpression broken out */ |
| }; |
| |
| /* |
| ** An instance of the following structure keeps track of a mapping |
| ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm. |
| ** |
| ** The VDBE cursor numbers are small integers contained in |
| ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE |
| ** clause, the cursor numbers might not begin with 0 and they might |
| ** contain gaps in the numbering sequence. But we want to make maximum |
| ** use of the bits in our bitmasks. This structure provides a mapping |
| ** from the sparse cursor numbers into consecutive integers beginning |
| ** with 0. |
| ** |
| ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask |
| ** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A. |
| ** |
| ** For example, if the WHERE clause expression used these VDBE |
| ** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure |
| ** would map those cursor numbers into bits 0 through 5. |
| ** |
| ** Note that the mapping is not necessarily ordered. In the example |
| ** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0, |
| ** 57->5, 73->4. Or one of 719 other combinations might be used. It |
| ** does not really matter. What is important is that sparse cursor |
| ** numbers all get mapped into bit numbers that begin with 0 and contain |
| ** no gaps. |
| */ |
| struct WhereMaskSet { |
| int bVarSelect; /* Used by sqlite3WhereExprUsage() */ |
| int n; /* Number of assigned cursor values */ |
| int ix[BMS]; /* Cursor assigned to each bit */ |
| }; |
| |
| /* |
| ** Initialize a WhereMaskSet object |
| */ |
| #define initMaskSet(P) (P)->n=0 |
| |
| /* |
| ** This object is a convenience wrapper holding all information needed |
| ** to construct WhereLoop objects for a particular query. |
| */ |
| struct WhereLoopBuilder { |
| WhereInfo *pWInfo; /* Information about this WHERE */ |
| WhereClause *pWC; /* WHERE clause terms */ |
| ExprList *pOrderBy; /* ORDER BY clause */ |
| WhereLoop *pNew; /* Template WhereLoop */ |
| WhereOrSet *pOrSet; /* Record best loops here, if not NULL */ |
| #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
| UnpackedRecord *pRec; /* Probe for stat4 (if required) */ |
| int nRecValid; /* Number of valid fields currently in pRec */ |
| #endif |
| unsigned int bldFlags; /* SQLITE_BLDF_* flags */ |
| unsigned int iPlanLimit; /* Search limiter */ |
| }; |
| |
| /* Allowed values for WhereLoopBuider.bldFlags */ |
| #define SQLITE_BLDF_INDEXED 0x0001 /* An index is used */ |
| #define SQLITE_BLDF_UNIQUE 0x0002 /* All keys of a UNIQUE index used */ |
| |
| /* The WhereLoopBuilder.iPlanLimit is used to limit the number of |
| ** index+constraint combinations the query planner will consider for a |
| ** particular query. If this parameter is unlimited, then certain |
| ** pathological queries can spend excess time in the sqlite3WhereBegin() |
| ** routine. The limit is high enough that is should not impact real-world |
| ** queries. |
| ** |
| ** SQLITE_QUERY_PLANNER_LIMIT is the baseline limit. The limit is |
| ** increased by SQLITE_QUERY_PLANNER_LIMIT_INCR before each term of the FROM |
| ** clause is processed, so that every table in a join is guaranteed to be |
| ** able to propose a some index+constraint combinations even if the initial |
| ** baseline limit was exhausted by prior tables of the join. |
| */ |
| #ifndef SQLITE_QUERY_PLANNER_LIMIT |
| # define SQLITE_QUERY_PLANNER_LIMIT 20000 |
| #endif |
| #ifndef SQLITE_QUERY_PLANNER_LIMIT_INCR |
| # define SQLITE_QUERY_PLANNER_LIMIT_INCR 1000 |
| #endif |
| |
| /* |
| ** The WHERE clause processing routine has two halves. The |
| ** first part does the start of the WHERE loop and the second |
| ** half does the tail of the WHERE loop. An instance of |
| ** this structure is returned by the first half and passed |
| ** into the second half to give some continuity. |
| ** |
| ** An instance of this object holds the complete state of the query |
| ** planner. |
| */ |
| struct WhereInfo { |
| Parse *pParse; /* Parsing and code generating context */ |
| SrcList *pTabList; /* List of tables in the join */ |
| ExprList *pOrderBy; /* The ORDER BY clause or NULL */ |
| ExprList *pResultSet; /* Result set of the query */ |
| Expr *pWhere; /* The complete WHERE clause */ |
| LogEst iLimit; /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */ |
| int aiCurOnePass[2]; /* OP_OpenWrite cursors for the ONEPASS opt */ |
| int iContinue; /* Jump here to continue with next record */ |
| int iBreak; /* Jump here to break out of the loop */ |
| int savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ |
| u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ |
| u8 nLevel; /* Number of nested loop */ |
| i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */ |
| u8 sorted; /* True if really sorted (not just grouped) */ |
| u8 eOnePass; /* ONEPASS_OFF, or _SINGLE, or _MULTI */ |
| u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ |
| u8 eDistinct; /* One of the WHERE_DISTINCT_* values */ |
| u8 bOrderedInnerLoop; /* True if only the inner-most loop is ordered */ |
| int iTop; /* The very beginning of the WHERE loop */ |
| WhereLoop *pLoops; /* List of all WhereLoop objects */ |
| Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ |
| LogEst nRowOut; /* Estimated number of output rows */ |
| WhereClause sWC; /* Decomposition of the WHERE clause */ |
| WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */ |
| WhereLevel a[1]; /* Information about each nest loop in WHERE */ |
| }; |
| |
| /* |
| ** Private interfaces - callable only by other where.c routines. |
| ** |
| ** where.c: |
| */ |
| Bitmask sqlite3WhereGetMask(WhereMaskSet*,int); |
| #ifdef WHERETRACE_ENABLED |
| void sqlite3WhereClausePrint(WhereClause *pWC); |
| #endif |
| WhereTerm *sqlite3WhereFindTerm( |
| WhereClause *pWC, /* The WHERE clause to be searched */ |
| int iCur, /* Cursor number of LHS */ |
| int iColumn, /* Column number of LHS */ |
| Bitmask notReady, /* RHS must not overlap with this mask */ |
| u32 op, /* Mask of WO_xx values describing operator */ |
| Index *pIdx /* Must be compatible with this index, if not NULL */ |
| ); |
| |
| /* wherecode.c: */ |
| #ifndef SQLITE_OMIT_EXPLAIN |
| int sqlite3WhereExplainOneScan( |
| Parse *pParse, /* Parse context */ |
| SrcList *pTabList, /* Table list this loop refers to */ |
| WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */ |
| u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ |
| ); |
| #else |
| # define sqlite3WhereExplainOneScan(u,v,w,x) 0 |
| #endif /* SQLITE_OMIT_EXPLAIN */ |
| #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
| void sqlite3WhereAddScanStatus( |
| Vdbe *v, /* Vdbe to add scanstatus entry to */ |
| SrcList *pSrclist, /* FROM clause pLvl reads data from */ |
| WhereLevel *pLvl, /* Level to add scanstatus() entry for */ |
| int addrExplain /* Address of OP_Explain (or 0) */ |
| ); |
| #else |
| # define sqlite3WhereAddScanStatus(a, b, c, d) ((void)d) |
| #endif |
| Bitmask sqlite3WhereCodeOneLoopStart( |
| Parse *pParse, /* Parsing context */ |
| Vdbe *v, /* Prepared statement under construction */ |
| WhereInfo *pWInfo, /* Complete information about the WHERE clause */ |
| int iLevel, /* Which level of pWInfo->a[] should be coded */ |
| WhereLevel *pLevel, /* The current level pointer */ |
| Bitmask notReady /* Which tables are currently available */ |
| ); |
| |
| /* whereexpr.c: */ |
| void sqlite3WhereClauseInit(WhereClause*,WhereInfo*); |
| void sqlite3WhereClauseClear(WhereClause*); |
| void sqlite3WhereSplit(WhereClause*,Expr*,u8); |
| Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*); |
| Bitmask sqlite3WhereExprUsageNN(WhereMaskSet*, Expr*); |
| Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*); |
| void sqlite3WhereExprAnalyze(SrcList*, WhereClause*); |
| void sqlite3WhereTabFuncArgs(Parse*, struct SrcList_item*, WhereClause*); |
| |
| |
| |
| |
| |
| /* |
| ** Bitmasks for the operators on WhereTerm objects. These are all |
| ** operators that are of interest to the query planner. An |
| ** OR-ed combination of these values can be used when searching for |
| ** particular WhereTerms within a WhereClause. |
| ** |
| ** Value constraints: |
| ** WO_EQ == SQLITE_INDEX_CONSTRAINT_EQ |
| ** WO_LT == SQLITE_INDEX_CONSTRAINT_LT |
| ** WO_LE == SQLITE_INDEX_CONSTRAINT_LE |
| ** WO_GT == SQLITE_INDEX_CONSTRAINT_GT |
| ** WO_GE == SQLITE_INDEX_CONSTRAINT_GE |
| */ |
| #define WO_IN 0x0001 |
| #define WO_EQ 0x0002 |
| #define WO_LT (WO_EQ<<(TK_LT-TK_EQ)) |
| #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) |
| #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) |
| #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) |
| #define WO_AUX 0x0040 /* Op useful to virtual tables only */ |
| #define WO_IS 0x0080 |
| #define WO_ISNULL 0x0100 |
| #define WO_OR 0x0200 /* Two or more OR-connected terms */ |
| #define WO_AND 0x0400 /* Two or more AND-connected terms */ |
| #define WO_EQUIV 0x0800 /* Of the form A==B, both columns */ |
| #define WO_NOOP 0x1000 /* This term does not restrict search space */ |
| |
| #define WO_ALL 0x1fff /* Mask of all possible WO_* values */ |
| #define WO_SINGLE 0x01ff /* Mask of all non-compound WO_* values */ |
| |
| /* |
| ** These are definitions of bits in the WhereLoop.wsFlags field. |
| ** The particular combination of bits in each WhereLoop help to |
| ** determine the algorithm that WhereLoop represents. |
| */ |
| #define WHERE_COLUMN_EQ 0x00000001 /* x=EXPR */ |
| #define WHERE_COLUMN_RANGE 0x00000002 /* x<EXPR and/or x>EXPR */ |
| #define WHERE_COLUMN_IN 0x00000004 /* x IN (...) */ |
| #define WHERE_COLUMN_NULL 0x00000008 /* x IS NULL */ |
| #define WHERE_CONSTRAINT 0x0000000f /* Any of the WHERE_COLUMN_xxx values */ |
| #define WHERE_TOP_LIMIT 0x00000010 /* x<EXPR or x<=EXPR constraint */ |
| #define WHERE_BTM_LIMIT 0x00000020 /* x>EXPR or x>=EXPR constraint */ |
| #define WHERE_BOTH_LIMIT 0x00000030 /* Both x>EXPR and x<EXPR */ |
| #define WHERE_IDX_ONLY 0x00000040 /* Use index only - omit table */ |
| #define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */ |
| #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ |
| #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ |
| #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ |
| #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ |
| #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ |
| #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ |
| #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ |
| #define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/ |
| #define WHERE_PARTIALIDX 0x00020000 /* The automatic index is partial */ |
| #define WHERE_IN_EARLYOUT 0x00040000 /* Perhaps quit IN loops early */ |