AryaWu/sqlite
0
1/*2** 2013-11-123**4** The author disclaims copyright to this source code. In place of5** 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 query14** planner logic in "where.c". These definitions are broken out into15** a separate source file for easier editing.16*/17#ifndef SQLITE_WHEREINT_H18#define SQLITE_WHEREINT_H19 20 21/* Forward references22*/23typedef struct WhereClause WhereClause;24typedef struct WhereMaskSet WhereMaskSet;25typedef struct WhereOrInfo WhereOrInfo;26typedef struct WhereAndInfo WhereAndInfo;27typedef struct WhereLevel WhereLevel;28typedef struct WhereLoop WhereLoop;29typedef struct WherePath WherePath;30typedef struct WhereTerm WhereTerm;31typedef struct WhereLoopBuilder WhereLoopBuilder;32typedef struct WhereScan WhereScan;33typedef struct WhereOrCost WhereOrCost;34typedef struct WhereOrSet WhereOrSet;35typedef struct WhereMemBlock WhereMemBlock;36typedef struct WhereRightJoin WhereRightJoin;37 38/*39** This object is a header on a block of allocated memory that will be40** automatically freed when its WInfo object is destructed.41*/42struct 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*/50struct 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 nested60** loop in WHERE clause.61**62** Contrast this object with WhereLoop. This object describes the63** implementation of the loop. WhereLoop describes the algorithm.64** This object contains a pointer to the WhereLoop algorithm as one of65** its elements.66**67** The WhereInfo object contains a single instance of this object for68** each term in the FROM clause (which is to say, for each of the69** nested loops as implemented). The order of WhereLevel objects determines70** the loop nested order, with WhereInfo.a[0] being the outer loop and71** WhereInfo.a[WhereInfo.nLevel-1] being the inner loop.72*/73struct 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 addrHalt; /* Abort the query due to empty table or similar */79 int addrNxt; /* Jump here to start the next IN combination */80 int addrSkip; /* Jump here for next iteration of skip-scan */81 int addrCont; /* Jump here to continue with the next loop cycle */82 int addrFirst; /* First instruction of interior of the loop */83 int addrBody; /* Beginning of the body of this loop */84 int regBignull; /* big-null flag reg. True if a NULL-scan is needed */85 int addrBignull; /* Jump here for next part of big-null scan */86#ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS87 u32 iLikeRepCntr; /* LIKE range processing counter register (times 2) */88 int addrLikeRep; /* LIKE range processing address */89#endif90 int regFilter; /* Bloom filter */91 WhereRightJoin *pRJ; /* Extra information for RIGHT JOIN */92 u8 iFrom; /* Which entry in the FROM clause */93 u8 op, p3, p5; /* Opcode, P3 & P5 of the opcode that ends the loop */94 int p1, p2; /* Operands of the opcode used to end the loop */95 union { /* Information that depends on pWLoop->wsFlags */96 struct {97 int nIn; /* Number of entries in aInLoop[] */98 struct InLoop {99 int iCur; /* The VDBE cursor used by this IN operator */100 int addrInTop; /* Top of the IN loop */101 int iBase; /* Base register of multi-key index record */102 int nPrefix; /* Number of prior entries in the key */103 u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */104 } *aInLoop; /* Information about each nested IN operator */105 } in; /* Used when pWLoop->wsFlags&WHERE_IN_ABLE */106 Index *pCoveringIdx; /* Possible covering index for WHERE_MULTI_OR */107 } u;108 struct WhereLoop *pWLoop; /* The selected WhereLoop object */109 Bitmask notReady; /* FROM entries not usable at this level */110#ifdef SQLITE_ENABLE_STMT_SCANSTATUS111 int addrVisit; /* Address at which row is visited */112#endif113};114 115/*116** Each instance of this object represents an algorithm for evaluating one117** term of a join. Every term of the FROM clause will have at least118** one corresponding WhereLoop object (unless INDEXED BY constraints119** prevent a query solution - which is an error) and many terms of the120** FROM clause will have multiple WhereLoop objects, each describing a121** potential way of implementing that FROM-clause term, together with122** dependencies and cost estimates for using the chosen algorithm.123**124** Query planning consists of building up a collection of these WhereLoop125** objects, then computing a particular sequence of WhereLoop objects, with126** one WhereLoop object per FROM clause term, that satisfy all dependencies127** and that minimize the overall cost.128*/129struct WhereLoop {130 Bitmask prereq; /* Bitmask of other loops that must run first */131 Bitmask maskSelf; /* Bitmask identifying table iTab */132#ifdef SQLITE_DEBUG133 char cId; /* Symbolic ID of this loop for debugging use */134#endif135 u8 iTab; /* Position in FROM clause of table for this loop */136 u8 iSortIdx; /* Sorting index number. 0==None */137 LogEst rSetup; /* One-time setup cost (ex: create transient index) */138 LogEst rRun; /* Cost of running each loop */139 LogEst nOut; /* Estimated number of output rows */140 union {141 struct { /* Information for internal btree tables */142 u16 nEq; /* Number of equality constraints */143 u16 nBtm; /* Size of BTM vector */144 u16 nTop; /* Size of TOP vector */145 u16 nDistinctCol; /* Index columns used to sort for DISTINCT */146 Index *pIndex; /* Index used, or NULL */147 ExprList *pOrderBy; /* ORDER BY clause if this is really a subquery */148 } btree;149 struct { /* Information for virtual tables */150 int idxNum; /* Index number */151 u32 needFree : 1; /* True if sqlite3_free(idxStr) is needed */152 u32 bOmitOffset : 1; /* True to let virtual table handle offset */153 u32 bIdxNumHex : 1; /* Show idxNum as hex in EXPLAIN QUERY PLAN */154 i8 isOrdered; /* True if satisfies ORDER BY */155 u16 omitMask; /* Terms that may be omitted */156 char *idxStr; /* Index identifier string */157 u32 mHandleIn; /* Terms to handle as IN(...) instead of == */158 } vtab;159 } u;160 u32 wsFlags; /* WHERE_* flags describing the plan */161 u16 nLTerm; /* Number of entries in aLTerm[] */162 u16 nSkip; /* Number of NULL aLTerm[] entries */163 /**** whereLoopXfer() copies fields above ***********************/164# define WHERE_LOOP_XFER_SZ offsetof(WhereLoop,nLSlot)165 u16 nLSlot; /* Number of slots allocated for aLTerm[] */166#ifdef WHERETRACE_ENABLED167 LogEst rStarDelta; /* Cost delta due to star-schema heuristic. Not168 ** initialized unless pWInfo->bStarUsed */169#endif170 WhereTerm **aLTerm; /* WhereTerms used */171 WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */172 WhereTerm *aLTermSpace[3]; /* Initial aLTerm[] space */173};174 175/* This object holds the prerequisites and the cost of running a176** subquery on one operand of an OR operator in the WHERE clause.177** See WhereOrSet for additional information178*/179struct WhereOrCost {180 Bitmask prereq; /* Prerequisites */181 LogEst rRun; /* Cost of running this subquery */182 LogEst nOut; /* Number of outputs for this subquery */183};184 185/* The WhereOrSet object holds a set of possible WhereOrCosts that186** correspond to the subquery(s) of OR-clause processing. Only the187** best N_OR_COST elements are retained.188*/189#define N_OR_COST 3190struct WhereOrSet {191 u16 n; /* Number of valid a[] entries */192 WhereOrCost a[N_OR_COST]; /* Set of best costs */193};194 195/*196** Each instance of this object holds a sequence of WhereLoop objects197** that implement some or all of a query plan.198**199** Think of each WhereLoop object as a node in a graph with arcs200** showing dependencies and costs for travelling between nodes. (That is201** not a completely accurate description because WhereLoop costs are a202** vector, not a scalar, and because dependencies are many-to-one, not203** one-to-one as are graph nodes. But it is a useful visualization aid.)204** Then a WherePath object is a path through the graph that visits some205** or all of the WhereLoop objects once.206**207** The "solver" works by creating the N best WherePath objects of length208** 1. Then using those as a basis to compute the N best WherePath objects209** of length 2. And so forth until the length of WherePaths equals the210** number of nodes in the FROM clause. The best (lowest cost) WherePath211** at the end is the chosen query plan.212*/213struct WherePath {214 Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */215 Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */216 LogEst nRow; /* Estimated number of rows generated by this path */217 LogEst rCost; /* Total cost of this path */218 LogEst rUnsort; /* Total cost of this path ignoring sorting costs */219 i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */220 WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */221};222 223/*224** The query generator uses an array of instances of this structure to225** help it analyze the subexpressions of the WHERE clause. Each WHERE226** clause subexpression is separated from the others by AND operators,227** usually, or sometimes subexpressions separated by OR.228**229** All WhereTerms are collected into a single WhereClause structure. 230** The following identity holds:231**232** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm233**234** When a term is of the form:235**236** X <op> <expr>237**238** where X is a column name and <op> is one of certain operators,239** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the240** cursor number and column number for X. WhereTerm.eOperator records241** the <op> using a bitmask encoding defined by WO_xxx below. The242** use of a bitmask encoding for the operator allows us to search243** quickly for terms that match any of several different operators.244**245** A WhereTerm might also be two or more subterms connected by OR:246**247** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....248**249** In this second case, wtFlag has the TERM_ORINFO bit set and eOperator==WO_OR250** and the WhereTerm.u.pOrInfo field points to auxiliary information that251** is collected about the OR clause.252**253** If a term in the WHERE clause does not match either of the two previous254** categories, then eOperator==0. The WhereTerm.pExpr field is still set255** to the original subexpression content and wtFlags is set up appropriately256** but no other fields in the WhereTerm object are meaningful.257**258** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,259** but they do so indirectly. A single WhereMaskSet structure translates260** cursor number into bits and the translated bit is stored in the prereq261** fields. The translation is used in order to maximize the number of262** bits that will fit in a Bitmask. The VDBE cursor numbers might be263** spread out over the non-negative integers. For example, the cursor264** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet265** translates these sparse cursor numbers into consecutive integers266** beginning with 0 in order to make the best possible use of the available267** bits in the Bitmask. So, in the example above, the cursor numbers268** would be mapped into integers 0 through 7.269**270** The number of terms in a join is limited by the number of bits271** in prereqRight and prereqAll. The default is 64 bits, hence SQLite272** is only able to process joins with 64 or fewer tables.273*/274struct WhereTerm {275 Expr *pExpr; /* Pointer to the subexpression that is this term */276 WhereClause *pWC; /* The clause this term is part of */277 LogEst truthProb; /* Probability of truth for this expression */278 u16 wtFlags; /* TERM_xxx bit flags. See below */279 u16 eOperator; /* A WO_xx value describing <op> */280 u8 nChild; /* Number of children that must disable us */281 u8 eMatchOp; /* Op for vtab MATCH/LIKE/GLOB/REGEXP terms */282 int iParent; /* Disable pWC->a[iParent] when this term disabled */283 int leftCursor; /* Cursor number of X in "X <op> <expr>" */284#ifdef SQLITE_DEBUG285 int iTerm; /* Which WhereTerm is this, for debug purposes */286#endif287 union {288 struct {289 int leftColumn; /* Column number of X in "X <op> <expr>" */290 int iField; /* Field in (?,?,?) IN (SELECT...) vector */291 } x; /* Opcode other than OP_OR or OP_AND */292 WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */293 WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */294 } u;295 Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */296 Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */297};298 299/*300** Allowed values of WhereTerm.wtFlags301*/302#define TERM_DYNAMIC 0x0001 /* Need to call sqlite3ExprDelete(db, pExpr) */303#define TERM_VIRTUAL 0x0002 /* Added by the optimizer. Do not code */304#define TERM_CODED 0x0004 /* This term is already coded */305#define TERM_COPIED 0x0008 /* Has a child */306#define TERM_ORINFO 0x0010 /* Need to free the WhereTerm.u.pOrInfo object */307#define TERM_ANDINFO 0x0020 /* Need to free the WhereTerm.u.pAndInfo obj */308#define TERM_OK 0x0040 /* Used during OR-clause processing */309#define TERM_VNULL 0x0080 /* Manufactured x>NULL or x<=NULL term */310#define TERM_LIKEOPT 0x0100 /* Virtual terms from the LIKE optimization */311#define TERM_LIKECOND 0x0200 /* Conditionally this LIKE operator term */312#define TERM_LIKE 0x0400 /* The original LIKE operator */313#define TERM_IS 0x0800 /* Term.pExpr is an IS operator */314#define TERM_VARSELECT 0x1000 /* Term.pExpr contains a correlated sub-query */315#define TERM_HEURTRUTH 0x2000 /* Heuristic truthProb used */316#ifdef SQLITE_ENABLE_STAT4317# define TERM_HIGHTRUTH 0x4000 /* Term excludes few rows */318#else319# define TERM_HIGHTRUTH 0 /* Only used with STAT4 */320#endif321#define TERM_SLICE 0x8000 /* One slice of a row-value/vector comparison */322 323/*324** An instance of the WhereScan object is used as an iterator for locating325** terms in the WHERE clause that are useful to the query planner.326*/327struct WhereScan {328 WhereClause *pOrigWC; /* Original, innermost WhereClause */329 WhereClause *pWC; /* WhereClause currently being scanned */330 const char *zCollName; /* Required collating sequence, if not NULL */331 Expr *pIdxExpr; /* Search for this index expression */332 int k; /* Resume scanning at this->pWC->a[this->k] */333 u32 opMask; /* Acceptable operators */334 char idxaff; /* Must match this affinity, if zCollName!=NULL */335 unsigned char iEquiv; /* Current slot in aiCur[] and aiColumn[] */336 unsigned char nEquiv; /* Number of entries in aiCur[] and aiColumn[] */337 int aiCur[11]; /* Cursors in the equivalence class */338 i16 aiColumn[11]; /* Corresponding column number in the eq-class */339};340 341/*342** An instance of the following structure holds all information about a343** WHERE clause. Mostly this is a container for one or more WhereTerms.344**345** Explanation of pOuter: For a WHERE clause of the form346**347** a AND ((b AND c) OR (d AND e)) AND f348**349** There are separate WhereClause objects for the whole clause and for350** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the351** subclauses points to the WhereClause object for the whole clause.352*/353struct WhereClause {354 WhereInfo *pWInfo; /* WHERE clause processing context */355 WhereClause *pOuter; /* Outer conjunction */356 u8 op; /* Split operator. TK_AND or TK_OR */357 u8 hasOr; /* True if any a[].eOperator is WO_OR */358 int nTerm; /* Number of terms */359 int nSlot; /* Number of entries in a[] */360 int nBase; /* Number of terms through the last non-Virtual */361 WhereTerm *a; /* Each a[] describes a term of the WHERE clause */362#if defined(SQLITE_SMALL_STACK)363 WhereTerm aStatic[1]; /* Initial static space for a[] */364#else365 WhereTerm aStatic[8]; /* Initial static space for a[] */366#endif367};368 369/*370** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to371** a dynamically allocated instance of the following structure.372*/373struct WhereOrInfo {374 WhereClause wc; /* Decomposition into subterms */375 Bitmask indexable; /* Bitmask of all indexable tables in the clause */376};377 378/*379** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to380** a dynamically allocated instance of the following structure.381*/382struct WhereAndInfo {383 WhereClause wc; /* The subexpression broken out */384};385 386/*387** An instance of the following structure keeps track of a mapping388** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.389**390** The VDBE cursor numbers are small integers contained in391** SrcItem.iCursor and Expr.iTable fields. For any given WHERE392** clause, the cursor numbers might not begin with 0 and they might393** contain gaps in the numbering sequence. But we want to make maximum394** use of the bits in our bitmasks. This structure provides a mapping395** from the sparse cursor numbers into consecutive integers beginning396** with 0.397**398** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask399** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.400**401** For example, if the WHERE clause expression used these VDBE402** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure403** would map those cursor numbers into bits 0 through 5.404**405** Note that the mapping is not necessarily ordered. In the example406** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,407** 57->5, 73->4. Or one of 719 other combinations might be used. It408** does not really matter. What is important is that sparse cursor409** numbers all get mapped into bit numbers that begin with 0 and contain410** no gaps.411*/412struct WhereMaskSet {413 int bVarSelect; /* Used by sqlite3WhereExprUsage() */414 int n; /* Number of assigned cursor values */415 int ix[BMS]; /* Cursor assigned to each bit */416};417 418/*419** This object is a convenience wrapper holding all information needed420** to construct WhereLoop objects for a particular query.421*/422struct WhereLoopBuilder {423 WhereInfo *pWInfo; /* Information about this WHERE */424 WhereClause *pWC; /* WHERE clause terms */425 WhereLoop *pNew; /* Template WhereLoop */426 WhereOrSet *pOrSet; /* Record best loops here, if not NULL */427#ifdef SQLITE_ENABLE_STAT4428 UnpackedRecord *pRec; /* Probe for stat4 (if required) */429 int nRecValid; /* Number of valid fields currently in pRec */430#endif431 unsigned char bldFlags1; /* First set of SQLITE_BLDF_* flags */432 unsigned char bldFlags2; /* Second set of SQLITE_BLDF_* flags */433 unsigned int iPlanLimit; /* Search limiter */434};435 436/* Allowed values for WhereLoopBuider.bldFlags */437#define SQLITE_BLDF1_INDEXED 0x0001 /* An index is used */438#define SQLITE_BLDF1_UNIQUE 0x0002 /* All keys of a UNIQUE index used */439 440#define SQLITE_BLDF2_2NDPASS 0x0004 /* Second builder pass needed */441 442/* The WhereLoopBuilder.iPlanLimit is used to limit the number of443** index+constraint combinations the query planner will consider for a444** particular query. If this parameter is unlimited, then certain445** pathological queries can spend excess time in the sqlite3WhereBegin()446** routine. The limit is high enough that is should not impact real-world447** queries.448**449** SQLITE_QUERY_PLANNER_LIMIT is the baseline limit. The limit is450** increased by SQLITE_QUERY_PLANNER_LIMIT_INCR before each term of the FROM451** clause is processed, so that every table in a join is guaranteed to be452** able to propose a some index+constraint combinations even if the initial453** baseline limit was exhausted by prior tables of the join.454*/455#ifndef SQLITE_QUERY_PLANNER_LIMIT456# define SQLITE_QUERY_PLANNER_LIMIT 20000457#endif458#ifndef SQLITE_QUERY_PLANNER_LIMIT_INCR459# define SQLITE_QUERY_PLANNER_LIMIT_INCR 1000460#endif461 462/*463** The WHERE clause processing routine has two halves. The464** first part does the start of the WHERE loop and the second465** half does the tail of the WHERE loop. An instance of466** this structure is returned by the first half and passed467** into the second half to give some continuity.468**469** An instance of this object holds the complete state of the query470** planner.471*/472struct WhereInfo {473 Parse *pParse; /* Parsing and code generating context */474 SrcList *pTabList; /* List of tables in the join */475 ExprList *pOrderBy; /* The ORDER BY clause or NULL */476 ExprList *pResultSet; /* Result set of the query */477#if WHERETRACE_ENABLED478 Expr *pWhere; /* The complete WHERE clause */479#endif480 Select *pSelect; /* The entire SELECT statement containing WHERE */481 int aiCurOnePass[2]; /* OP_OpenWrite cursors for the ONEPASS opt */482 int iContinue; /* Jump here to continue with next record */483 int iBreak; /* Jump here to break out of the loop */484 int savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */485 u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */486 LogEst iLimit; /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */487 u8 nLevel; /* Number of nested loop */488 i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */489 u8 eOnePass; /* ONEPASS_OFF, or _SINGLE, or _MULTI */490 u8 eDistinct; /* One of the WHERE_DISTINCT_* values */491 unsigned bDeferredSeek :1; /* Uses OP_DeferredSeek */492 unsigned untestedTerms :1; /* Not all WHERE terms resolved by outer loop */493 unsigned bOrderedInnerLoop:1;/* True if only the inner-most loop is ordered */494 unsigned sorted :1; /* True if really sorted (not just grouped) */495 unsigned bStarDone :1; /* True if check for star-query is complete */496 unsigned bStarUsed :1; /* True if star-query heuristic is used */497 LogEst nRowOut; /* Estimated number of output rows */498#ifdef WHERETRACE_ENABLED499 LogEst rTotalCost; /* Total cost of the solution */500#endif501 int iTop; /* The very beginning of the WHERE loop */502 int iEndWhere; /* End of the WHERE clause itself */503 WhereLoop *pLoops; /* List of all WhereLoop objects */504 WhereMemBlock *pMemToFree;/* Memory to free when this object destroyed */505 Bitmask revMask; /* Mask of ORDER BY terms that need reversing */506 WhereClause sWC; /* Decomposition of the WHERE clause */507 WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */508 WhereLevel a[FLEXARRAY]; /* Information about each nest loop in WHERE */509};510 511/*512** The size (in bytes) of a WhereInfo object that holds N WhereLevels.513*/514#define SZ_WHEREINFO(N) ROUND8(offsetof(WhereInfo,a)+(N)*sizeof(WhereLevel))515 516/*517** Private interfaces - callable only by other where.c routines.518**519** where.c:520*/521Bitmask sqlite3WhereGetMask(WhereMaskSet*,int);522#ifdef WHERETRACE_ENABLED523void sqlite3WhereClausePrint(WhereClause *pWC);524void sqlite3WhereTermPrint(WhereTerm *pTerm, int iTerm);525void sqlite3WhereLoopPrint(const WhereLoop *p, const WhereClause *pWC);526#endif527WhereTerm *sqlite3WhereFindTerm(528 WhereClause *pWC, /* The WHERE clause to be searched */529 int iCur, /* Cursor number of LHS */530 int iColumn, /* Column number of LHS */531 Bitmask notReady, /* RHS must not overlap with this mask */532 u32 op, /* Mask of WO_xx values describing operator */533 Index *pIdx /* Must be compatible with this index, if not NULL */534);535void *sqlite3WhereMalloc(WhereInfo *pWInfo, u64 nByte);536void *sqlite3WhereRealloc(WhereInfo *pWInfo, void *pOld, u64 nByte);537 538/* wherecode.c: */539#ifndef SQLITE_OMIT_EXPLAIN540int sqlite3WhereExplainOneScan(541 Parse *pParse, /* Parse context */542 SrcList *pTabList, /* Table list this loop refers to */543 WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */544 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */545);546int sqlite3WhereExplainBloomFilter(547 const Parse *pParse, /* Parse context */548 const WhereInfo *pWInfo, /* WHERE clause */549 const WhereLevel *pLevel /* Bloom filter on this level */550);551void sqlite3WhereAddExplainText(552 Parse *pParse, /* Parse context */553 int addr, 554 SrcList *pTabList, /* Table list this loop refers to */555 WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */556 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */557);558#else559# define sqlite3WhereExplainOneScan(u,v,w,x) 0560# define sqlite3WhereExplainBloomFilter(u,v,w) 0561# define sqlite3WhereAddExplainText(u,v,w,x,y)562#endif /* SQLITE_OMIT_EXPLAIN */563#ifdef SQLITE_ENABLE_STMT_SCANSTATUS564void sqlite3WhereAddScanStatus(565 Vdbe *v, /* Vdbe to add scanstatus entry to */566 SrcList *pSrclist, /* FROM clause pLvl reads data from */567 WhereLevel *pLvl, /* Level to add scanstatus() entry for */568 int addrExplain /* Address of OP_Explain (or 0) */569);570#else571# define sqlite3WhereAddScanStatus(a, b, c, d) ((void)d)572#endif573Bitmask sqlite3WhereCodeOneLoopStart(574 Parse *pParse, /* Parsing context */575 Vdbe *v, /* Prepared statement under construction */576 WhereInfo *pWInfo, /* Complete information about the WHERE clause */577 int iLevel, /* Which level of pWInfo->a[] should be coded */578 WhereLevel *pLevel, /* The current level pointer */579 Bitmask notReady /* Which tables are currently available */580);581SQLITE_NOINLINE void sqlite3WhereRightJoinLoop(582 WhereInfo *pWInfo,583 int iLevel,584 WhereLevel *pLevel585);586 587/* whereexpr.c: */588void sqlite3WhereClauseInit(WhereClause*,WhereInfo*);589void sqlite3WhereClauseClear(WhereClause*);590void sqlite3WhereSplit(WhereClause*,Expr*,u8);591void sqlite3WhereAddLimit(WhereClause*, Select*);592Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*);593Bitmask sqlite3WhereExprUsageNN(WhereMaskSet*, Expr*);594Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*);595void sqlite3WhereExprAnalyze(SrcList*, WhereClause*);596void sqlite3WhereTabFuncArgs(Parse*, SrcItem*, WhereClause*);597 598 599 600 601 602/*603** Bitmasks for the operators on WhereTerm objects. These are all604** operators that are of interest to the query planner. An605** OR-ed combination of these values can be used when searching for606** particular WhereTerms within a WhereClause.607**608** Value constraints:609** WO_EQ == SQLITE_INDEX_CONSTRAINT_EQ610** WO_LT == SQLITE_INDEX_CONSTRAINT_LT611** WO_LE == SQLITE_INDEX_CONSTRAINT_LE612** WO_GT == SQLITE_INDEX_CONSTRAINT_GT613** WO_GE == SQLITE_INDEX_CONSTRAINT_GE614*/615#define WO_IN 0x0001616#define WO_EQ 0x0002617#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))618#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))619#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))620#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))621#define WO_AUX 0x0040 /* Op useful to virtual tables only */622#define WO_IS 0x0080623#define WO_ISNULL 0x0100624#define WO_OR 0x0200 /* Two or more OR-connected terms */625#define WO_AND 0x0400 /* Two or more AND-connected terms */626#define WO_EQUIV 0x0800 /* Of the form A==B, both columns */627#define WO_NOOP 0x1000 /* This term does not restrict search space */628#define WO_ROWVAL 0x2000 /* A row-value term */629 630#define WO_ALL 0x3fff /* Mask of all possible WO_* values */631#define WO_SINGLE 0x01ff /* Mask of all non-compound WO_* values */632 633/*634** These are definitions of bits in the WhereLoop.wsFlags field.635** The particular combination of bits in each WhereLoop help to636** determine the algorithm that WhereLoop represents.637*/638#define WHERE_COLUMN_EQ 0x00000001 /* x=EXPR */639#define WHERE_COLUMN_RANGE 0x00000002 /* x<EXPR and/or x>EXPR */640#define WHERE_COLUMN_IN 0x00000004 /* x IN (...) */641#define WHERE_COLUMN_NULL 0x00000008 /* x IS NULL */642#define WHERE_CONSTRAINT 0x0000000f /* Any of the WHERE_COLUMN_xxx values */643#define WHERE_TOP_LIMIT 0x00000010 /* x<EXPR or x<=EXPR constraint */644#define WHERE_BTM_LIMIT 0x00000020 /* x>EXPR or x>=EXPR constraint */645#define WHERE_BOTH_LIMIT 0x00000030 /* Both x>EXPR and x<EXPR */646#define WHERE_IDX_ONLY 0x00000040 /* Use index only - omit table */647#define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */648#define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */649#define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */650#define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */651#define WHERE_ONEROW 0x00001000 /* Selects no more than one row */652#define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */653#define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */654#define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */655#define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/656#define WHERE_PARTIALIDX 0x00020000 /* The automatic index is partial */657#define WHERE_IN_EARLYOUT 0x00040000 /* Perhaps quit IN loops early */658#define WHERE_BIGNULL_SORT 0x00080000 /* Column nEq of index is BIGNULL */659#define WHERE_IN_SEEKSCAN 0x00100000 /* Seek-scan optimization for IN */660#define WHERE_TRANSCONS 0x00200000 /* Uses a transitive constraint */661#define WHERE_BLOOMFILTER 0x00400000 /* Consider using a Bloom-filter */662#define WHERE_SELFCULL 0x00800000 /* nOut reduced by extra WHERE terms */663#define WHERE_OMIT_OFFSET 0x01000000 /* Set offset counter to zero */664#define WHERE_COROUTINE 0x02000000 /* Implemented by co-routine.665 ** NB: False-negatives are possible */666#define WHERE_EXPRIDX 0x04000000 /* Uses an index-on-expressions */667 668#endif /* !defined(SQLITE_WHEREINT_H) */669