diff options
Diffstat (limited to 'src/where.c')
| -rw-r--r-- | src/where.c | 555 |
1 files changed, 93 insertions, 462 deletions
diff --git a/src/where.c b/src/where.c index 60a9471da..c4f25675c 100644 --- a/src/where.c +++ b/src/where.c @@ -17,447 +17,7 @@ ** indices, you might also think of this module as the "query optimizer". */ #include "sqliteInt.h" - - -/* -** Trace output macros -*/ -#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) -/***/ int sqlite3WhereTrace = 0; -#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 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 */ - u8 iFrom; /* Which entry in the FROM clause */ - u8 op, p5; /* Opcode and 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 */ - 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 */ -}; - -/* -** 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 */ - int nEq; /* Number of equality constraints */ - 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 */ - u8 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[] */ - /**** 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[4]; /* 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 */ -}; - - -/* Forward declaration of methods */ -static int whereLoopResize(sqlite3*, WhereLoop*, int); - -/* -** 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 choosen 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 */ - u8 isOrdered; /* True if this path satisfies ORDER BY */ - u8 isOrderedValid; /* True if the isOrdered field is valid */ - 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 */ - int iParent; /* Disable pWC->a[iParent] when this term disabled */ - int leftCursor; /* Cursor number of X in "X <op> <expr>" */ - 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; - LogEst truthProb; /* Probability of truth for this expression */ - u16 eOperator; /* A WO_xx value describing <op> */ - u8 wtFlags; /* TERM_xxx bit flags. See below */ - u8 nChild; /* Number of children that must disable us */ - WhereClause *pWC; /* The clause this term is part of */ - 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 - -/* -** 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 */ - char *zCollName; /* Required collating sequence, if not NULL */ - 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 aEquiv[22]; /* Cursor,Column pairs for equivalence classes */ -}; - -/* -** 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 */ - 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 n; /* Number of assigned cursor values */ - int ix[BMS]; /* Cursor assigned to each bit */ -}; - -/* -** 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 -}; - -/* -** 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. DISTINCT operates on these */ - WhereLoop *pLoops; /* List of all WhereLoop objects */ - Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ - LogEst nRowOut; /* Estimated number of output rows */ - u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ - u8 bOBSat; /* ORDER BY satisfied by indices */ - u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */ - u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ - u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ - u8 nLevel; /* Number of nested loop */ - int iTop; /* The very beginning of the WHERE loop */ - 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 */ - int aiCurOnePass[2]; /* OP_OpenWrite cursors for the ONEPASS opt */ - WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */ - WhereClause sWC; /* Decomposition of the WHERE clause */ - WhereLevel a[1]; /* Information about each nest loop in WHERE */ -}; - -/* -** 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. -*/ -#define WO_IN 0x001 -#define WO_EQ 0x002 -#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_MATCH 0x040 -#define WO_ISNULL 0x080 -#define WO_OR 0x100 /* Two or more OR-connected terms */ -#define WO_AND 0x200 /* Two or more AND-connected terms */ -#define WO_EQUIV 0x400 /* Of the form A==B, both columns */ -#define WO_NOOP 0x800 /* This term does not restrict search space */ - -#define WO_ALL 0xfff /* Mask of all possible WO_* values */ -#define WO_SINGLE 0x0ff /* 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 */ +#include "whereInt.h" /* ** Return the estimated number of output rows from a WHERE clause @@ -2862,7 +2422,7 @@ static int codeEqualityTerm( /* ** Generate code that will evaluate all == and IN constraints for an -** index. +** index scan. ** ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c). ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10 @@ -2877,9 +2437,15 @@ static int codeEqualityTerm( ** The only thing it does is allocate the pLevel->iMem memory cell and ** compute the affinity string. ** -** This routine always allocates at least one memory cell and returns -** the index of that memory cell. The code that -** calls this routine will use that memory cell to store the termination +** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints +** are == or IN and are covered by the nEq. nExtraReg is 1 if there is +** an inequality constraint (such as the "c>=5 AND c<10" in the example) that +** occurs after the nEq quality constraints. +** +** This routine allocates a range of nEq+nExtraReg memory cells and returns +** the index of the first memory cell in that range. The code that +** calls this routine will use that memory range to store keys for +** start and termination conditions of the loop. ** key value of the loop. If one or more IN operators appear, then ** this routine allocates an additional nEq memory cells for internal ** use. @@ -2906,7 +2472,8 @@ static int codeAllEqualityTerms( int nExtraReg, /* Number of extra registers to allocate */ char **pzAff /* OUT: Set to point to affinity string */ ){ - int nEq; /* The number of == or IN constraints to code */ + u16 nEq; /* The number of == or IN constraints to code */ + u16 nSkip; /* Number of left-most columns to skip */ Vdbe *v = pParse->pVdbe; /* The vm under construction */ Index *pIdx; /* The index being used for this loop */ WhereTerm *pTerm; /* A single constraint term */ @@ -2920,6 +2487,7 @@ static int codeAllEqualityTerms( pLoop = pLevel->pWLoop; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); nEq = pLoop->u.btree.nEq; + nSkip = pLoop->u.btree.nSkip; pIdx = pLoop->u.btree.pIndex; assert( pIdx!=0 ); @@ -2934,14 +2502,29 @@ static int codeAllEqualityTerms( pParse->db->mallocFailed = 1; } + if( nSkip ){ + int iIdxCur = pLevel->iIdxCur; + sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur); + VdbeComment((v, "begin skip-scan on %s", pIdx->zName)); + j = sqlite3VdbeAddOp0(v, OP_Goto); + pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLt:OP_SeekGt), + iIdxCur, 0, regBase, nSkip); + sqlite3VdbeJumpHere(v, j); + for(j=0; j<nSkip; j++){ + sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j); + assert( pIdx->aiColumn[j]>=0 ); + VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName)); + } + } + /* Evaluate the equality constraints */ assert( zAff==0 || (int)strlen(zAff)>=nEq ); - for(j=0; j<nEq; j++){ + for(j=nSkip; j<nEq; j++){ int r1; pTerm = pLoop->aLTerm[j]; assert( pTerm!=0 ); - /* The following true for indices with redundant columns. + /* The following testcase is true for indices with redundant columns. ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */ testcase( (pTerm->wtFlags & TERM_CODED)!=0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); @@ -3015,7 +2598,8 @@ static void explainAppendTerm( */ static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){ Index *pIndex = pLoop->u.btree.pIndex; - int nEq = pLoop->u.btree.nEq; + u16 nEq = pLoop->u.btree.nEq; + u16 nSkip = pLoop->u.btree.nSkip; int i, j; Column *aCol = pTab->aCol; i16 *aiColumn = pIndex->aiColumn; @@ -3029,7 +2613,14 @@ static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){ sqlite3StrAccumAppend(&txt, " (", 2); for(i=0; i<nEq; i++){ char *z = (i==pIndex->nKeyCol ) ? "rowid" : aCol[aiColumn[i]].zName; - explainAppendTerm(&txt, i, z, "="); + if( i>=nSkip ){ + explainAppendTerm(&txt, i, z, "="); + }else{ + if( i ) sqlite3StrAccumAppend(&txt, " AND ", 5); + sqlite3StrAccumAppend(&txt, "ANY(", 4); + sqlite3StrAccumAppend(&txt, z, -1); + sqlite3StrAccumAppend(&txt, ")", 1); + } } j = i; @@ -3059,7 +2650,10 @@ static void explainOneScan( int iFrom, /* Value for "from" column of output */ u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ ){ - if( pParse->explain==2 ){ +#ifndef SQLITE_DEBUG + if( pParse->explain==2 ) +#endif + { struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom]; Vdbe *v = pParse->pVdbe; /* VM being constructed */ sqlite3 *db = pParse->db; /* Database handle */ @@ -3165,7 +2759,7 @@ static Bitmask codeOneLoopStart( bRev = (pWInfo->revMask>>iLevel)&1; omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 && (pWInfo->wctrlFlags & WHERE_FORCE_TABLE)==0; - VdbeNoopComment((v, "Begin WHERE-Loop %d: %s", iLevel,pTabItem->pTab->zName)); + VdbeNoopComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName)); /* Create labels for the "break" and "continue" instructions ** for the current loop. Jump to addrBrk to break out of a loop. @@ -3392,8 +2986,9 @@ static Bitmask codeOneLoopStart( OP_IdxGE, /* 1: (end_constraints && !bRev) */ OP_IdxLT /* 2: (end_constraints && bRev) */ }; - int nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ - int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */ + u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ + u16 nSkip = pLoop->u.btree.nSkip; /* Number of left index terms to skip */ + int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */ int regBase; /* Base register holding constraint values */ int r1; /* Temp register */ WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ @@ -3411,6 +3006,7 @@ static Bitmask codeOneLoopStart( pIdx = pLoop->u.btree.pIndex; iIdxCur = pLevel->iIdxCur; + assert( nEq>=nSkip ); /* If this loop satisfies a sort order (pOrderBy) request that ** was passed to this function to implement a "SELECT min(x) ..." @@ -3424,8 +3020,7 @@ static Bitmask codeOneLoopStart( && (pWInfo->bOBSat!=0) && (pIdx->nKeyCol>nEq) ){ - /* assert( pOrderBy->nExpr==1 ); */ - /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */ + assert( nSkip==0 ); isMinQuery = 1; nExtraReg = 1; } @@ -3556,8 +3151,12 @@ static Bitmask codeOneLoopStart( r1 = sqlite3GetTempReg(pParse); testcase( pLoop->wsFlags & WHERE_BTM_LIMIT ); testcase( pLoop->wsFlags & WHERE_TOP_LIMIT ); - if( (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){ + if( (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 + && (j = pIdx->aiColumn[nEq])>=0 + && pIdx->pTable->aCol[j].notNull==0 + ){ sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1); + VdbeComment((v, "%s", pIdx->pTable->aCol[j].zName)); sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont); } sqlite3ReleaseTempReg(pParse, r1); @@ -3972,6 +3571,7 @@ static void whereLoopPrint(WhereLoop *p, WhereClause *pWC){ sqlite3ExplainBegin(v); for(i=0; i<p->nLTerm; i++){ WhereTerm *pTerm = p->aLTerm[i]; + if( pTerm==0 ) continue; sqlite3ExplainPrintf(v, " (%d) #%-2d ", i+1, (int)(pTerm-pWC->a)); sqlite3ExplainPush(v); whereExplainTerm(v, pTerm); @@ -4255,6 +3855,7 @@ static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop){ if( (pTerm->prereqAll & notAllowed)!=0 ) continue; for(j=pLoop->nLTerm-1; j>=0; j--){ pX = pLoop->aLTerm[j]; + if( pX==0 ) continue; if( pX==pTerm ) break; if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; } @@ -4284,7 +3885,8 @@ static int whereLoopAddBtreeIndex( WhereScan scan; /* Iterator for WHERE terms */ Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ - int saved_nEq; /* Original value of pNew->u.btree.nEq */ + u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ + u16 saved_nSkip; /* Original value of pNew->u.btree.nSkip */ u32 saved_wsFlags; /* Original value of pNew->wsFlags */ LogEst saved_nOut; /* Original value of pNew->nOut */ int iCol; /* Index of the column in the table */ @@ -4319,12 +3921,26 @@ static int whereLoopAddBtreeIndex( pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, pProbe); saved_nEq = pNew->u.btree.nEq; + saved_nSkip = pNew->u.btree.nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0])); + if( pTerm==0 + && saved_nEq==saved_nSkip + && saved_nEq+1<pProbe->nKeyCol + && pProbe->aiRowEst[saved_nEq+1]>50 + ){ + LogEst nIter; + pNew->u.btree.nEq++; + pNew->u.btree.nSkip++; + pNew->aLTerm[pNew->nLTerm++] = 0; + pNew->wsFlags |= WHERE_SKIPSCAN; + nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]); + whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter); + } for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 @@ -4360,8 +3976,10 @@ static int whereLoopAddBtreeIndex( pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ - assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0 - || nInMul==0 ); + assert( + (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0 + || nInMul==0 + ); pNew->wsFlags |= WHERE_COLUMN_EQ; if( iCol<0 || (pProbe->onError!=OE_None && nInMul==0 @@ -4442,6 +4060,7 @@ static int whereLoopAddBtreeIndex( } pNew->prereq = saved_prereq; pNew->u.btree.nEq = saved_nEq; + pNew->u.btree.nSkip = saved_nSkip; pNew->wsFlags = saved_wsFlags; pNew->nOut = saved_nOut; pNew->nLTerm = saved_nLTerm; @@ -4588,6 +4207,7 @@ static int whereLoopAddBtree( if( pTerm->prereqRight & pNew->maskSelf ) continue; if( termCanDriveIndex(pTerm, pSrc, 0) ){ pNew->u.btree.nEq = 1; + pNew->u.btree.nSkip = 0; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; @@ -4617,6 +4237,7 @@ static int whereLoopAddBtree( continue; /* Partial index inappropriate for this query */ } pNew->u.btree.nEq = 0; + pNew->u.btree.nSkip = 0; pNew->nLTerm = 0; pNew->iSortIdx = 0; pNew->rSetup = 0; @@ -5151,6 +4772,7 @@ static int wherePathSatisfiesOrderBy( /* Skip over == and IS NULL terms */ if( j<pLoop->u.btree.nEq + && pLoop->u.btree.nSkip==0 && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0 ){ if( i & WO_ISNULL ){ @@ -5576,6 +5198,7 @@ static int whereShortCut(WhereLoopBuilder *pBuilder){ pWC = &pWInfo->sWC; pLoop = pBuilder->pNew; pLoop->wsFlags = 0; + pLoop->u.btree.nSkip = 0; pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; @@ -6119,6 +5742,7 @@ WhereInfo *sqlite3WhereBegin( } /* Done. */ + VdbeNoopComment((v, "Begin WHERE-core")); return pWInfo; /* Jump here if malloc fails */ @@ -6145,8 +5769,10 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ /* Generate loop termination code. */ + VdbeNoopComment((v, "End WHERE-core")); sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ + int addr; pLevel = &pWInfo->a[i]; pLoop = pLevel->pWLoop; sqlite3VdbeResolveLabel(v, pLevel->addrCont); @@ -6166,8 +5792,13 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ sqlite3DbFree(db, pLevel->u.in.aInLoop); } sqlite3VdbeResolveLabel(v, pLevel->addrBrk); + if( pLevel->addrSkip ){ + sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip); + VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName)); + sqlite3VdbeJumpHere(v, pLevel->addrSkip); + sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); + } if( pLevel->iLeftJoin ){ - int addr; addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin); assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 || (pLoop->wsFlags & WHERE_INDEXED)!=0 ); @@ -6184,7 +5815,7 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ } sqlite3VdbeJumpHere(v, addr); } - VdbeNoopComment((v, "End WHERE-Loop %d: %s", i, + VdbeNoopComment((v, "End WHERE-loop%d: %s", i, pWInfo->pTabList->a[pLevel->iFrom].pTab->zName)); } |