summaryrefslogtreecommitdiffstats
path: root/lib/libsqlite3/src/where.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libsqlite3/src/where.c')
-rw-r--r--lib/libsqlite3/src/where.c347
1 files changed, 202 insertions, 145 deletions
diff --git a/lib/libsqlite3/src/where.c b/lib/libsqlite3/src/where.c
index 9c30136e876..bc0110779ea 100644
--- a/lib/libsqlite3/src/where.c
+++ b/lib/libsqlite3/src/where.c
@@ -365,11 +365,6 @@ static int allowedOp(int op){
}
/*
-** Swap two objects of type TYPE.
-*/
-#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
-
-/*
** Commute a comparison operator. Expressions of the form "X op Y"
** are converted into "Y op X".
**
@@ -701,7 +696,7 @@ static int isLikeOrGlob(
** value of the variable means there is no need to invoke the LIKE
** function, then no OP_Variable will be added to the program.
** This causes problems for the sqlite3_bind_parameter_name()
- ** API. To workaround them, add a dummy OP_Variable here.
+ ** API. To work around them, add a dummy OP_Variable here.
*/
int r1 = sqlite3GetTempReg(pParse);
sqlite3ExprCodeTarget(pParse, pRight, r1);
@@ -821,7 +816,7 @@ static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
** appropriate for indexing exist.
**
** All examples A through E above satisfy case 2. But if a term
-** also statisfies case 1 (such as B) we know that the optimizer will
+** also satisfies case 1 (such as B) we know that the optimizer will
** always prefer case 1, so in that case we pretend that case 2 is not
** satisfied.
**
@@ -979,7 +974,7 @@ static void exprAnalyzeOrTerm(
}
if( (chngToIN & getMask(&pWInfo->sMaskSet, pOrTerm->leftCursor))==0 ){
/* This term must be of the form t1.a==t2.b where t2 is in the
- ** chngToIN set but t1 is not. This term will be either preceeded
+ ** chngToIN set but t1 is not. This term will be either preceded
** or follwed by an inverted copy (t2.b==t1.a). Skip this term
** and use its inversion. */
testcase( pOrTerm->wtFlags & TERM_COPIED );
@@ -1390,7 +1385,7 @@ static void exprAnalyze(
}
/*
-** This function searches pList for a entry that matches the iCol-th column
+** This function searches pList for an entry that matches the iCol-th column
** of index pIdx.
**
** If such an expression is found, its index in pList->a[] is returned. If
@@ -1913,7 +1908,7 @@ static void whereKeyStats(
assert( pRec->nField>0 && iCol<pIdx->nSampleCol );
do{
iTest = (iMin+i)/2;
- res = sqlite3VdbeRecordCompare(aSample[iTest].n, aSample[iTest].p, pRec, 0);
+ res = sqlite3VdbeRecordCompare(aSample[iTest].n, aSample[iTest].p, pRec);
if( res<0 ){
iMin = iTest+1;
}else{
@@ -1928,16 +1923,16 @@ static void whereKeyStats(
if( res==0 ){
/* If (res==0) is true, then sample $i must be equal to pRec */
assert( i<pIdx->nSample );
- assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec, 0)
+ assert( 0==sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)
|| pParse->db->mallocFailed );
}else{
/* Otherwise, pRec must be smaller than sample $i and larger than
** sample ($i-1). */
assert( i==pIdx->nSample
- || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec, 0)>0
+ || sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec)>0
|| pParse->db->mallocFailed );
assert( i==0
- || sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec, 0)<0
+ || sqlite3VdbeRecordCompare(aSample[i-1].n, aSample[i-1].p, pRec)<0
|| pParse->db->mallocFailed );
}
#endif /* ifdef SQLITE_DEBUG */
@@ -2140,7 +2135,7 @@ static int whereRangeSkipScanEst(
** number of rows that the index scan is expected to visit without
** considering the range constraints. If nEq is 0, this is the number of
** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced)
-** to account for the range contraints pLower and pUpper.
+** to account for the range constraints pLower and pUpper.
**
** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be
** used, a single range inequality reduces the search space by a factor of 4.
@@ -2191,6 +2186,10 @@ static int whereRangeScanEst(
tRowcnt iLower;
tRowcnt iUpper;
+ if( pRec ){
+ testcase( pRec->nField!=pBuilder->nRecValid );
+ pRec->nField = pBuilder->nRecValid;
+ }
if( nEq==p->nKeyCol ){
aff = SQLITE_AFF_INTEGER;
}else{
@@ -2208,18 +2207,26 @@ static int whereRangeScanEst(
iUpper = a[0] + a[1];
}
+ assert( pLower==0 || (pLower->eOperator & (WO_GT|WO_GE))!=0 );
+ assert( pUpper==0 || (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
+ assert( p->aSortOrder!=0 );
+ if( p->aSortOrder[nEq] ){
+ /* The roles of pLower and pUpper are swapped for a DESC index */
+ SWAP(WhereTerm*, pLower, pUpper);
+ }
+
/* If possible, improve on the iLower estimate using ($P:$L). */
if( pLower ){
int bOk; /* True if value is extracted from pExpr */
Expr *pExpr = pLower->pExpr->pRight;
- assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
if( rc==SQLITE_OK && bOk ){
tRowcnt iNew;
whereKeyStats(pParse, p, pRec, 0, a);
- iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0);
+ iNew = a[0] + ((pLower->eOperator & (WO_GT|WO_LE)) ? a[1] : 0);
if( iNew>iLower ) iLower = iNew;
nOut--;
+ pLower = 0;
}
}
@@ -2227,14 +2234,14 @@ static int whereRangeScanEst(
if( pUpper ){
int bOk; /* True if value is extracted from pExpr */
Expr *pExpr = pUpper->pExpr->pRight;
- assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
if( rc==SQLITE_OK && bOk ){
tRowcnt iNew;
whereKeyStats(pParse, p, pRec, 1, a);
- iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0);
+ iNew = a[0] + ((pUpper->eOperator & (WO_GT|WO_LE)) ? a[1] : 0);
if( iNew<iUpper ) iUpper = iNew;
nOut--;
+ pUpper = 0;
}
}
@@ -2248,10 +2255,8 @@ static int whereRangeScanEst(
if( nNew<nOut ){
nOut = nNew;
}
- pLoop->nOut = (LogEst)nOut;
- WHERETRACE(0x10, ("range scan regions: %u..%u est=%d\n",
+ WHERETRACE(0x10, ("STAT4 range scan: %u..%u est=%d\n",
(u32)iLower, (u32)iUpper, nOut));
- return SQLITE_OK;
}
}else{
int bDone = 0;
@@ -2262,8 +2267,8 @@ static int whereRangeScanEst(
#else
UNUSED_PARAMETER(pParse);
UNUSED_PARAMETER(pBuilder);
-#endif
assert( pLower || pUpper );
+#endif
assert( pUpper==0 || (pUpper->wtFlags & TERM_VNULL)==0 );
nNew = whereRangeAdjust(pLower, nOut);
nNew = whereRangeAdjust(pUpper, nNew);
@@ -2278,6 +2283,12 @@ static int whereRangeScanEst(
nOut -= (pLower!=0) + (pUpper!=0);
if( nNew<10 ) nNew = 10;
if( nNew<nOut ) nOut = nNew;
+#if defined(WHERETRACE_ENABLED)
+ if( pLoop->nOut>nOut ){
+ WHERETRACE(0x10,("Range scan lowers nOut from %d to %d\n",
+ pLoop->nOut, nOut));
+ }
+#endif
pLoop->nOut = (LogEst)nOut;
return rc;
}
@@ -2390,7 +2401,7 @@ static int whereInScanEst(
if( rc==SQLITE_OK ){
if( nRowEst > nRow0 ) nRowEst = nRow0;
*pnRow = nRowEst;
- WHERETRACE(0x10,("IN row estimate: est=%g\n", nRowEst));
+ WHERETRACE(0x10,("IN row estimate: est=%d\n", nRowEst));
}
assert( pBuilder->nRecValid==nRecValid );
return rc;
@@ -2726,9 +2737,8 @@ static void explainAppendTerm(
/*
** Argument pLevel describes a strategy for scanning table pTab. This
-** function returns a pointer to a string buffer containing a description
-** of the subset of table rows scanned by the strategy in the form of an
-** SQL expression. Or, if all rows are scanned, NULL is returned.
+** function appends text to pStr that describes the subset of table
+** rows scanned by the strategy in the form of an SQL expression.
**
** For example, if the query:
**
@@ -2738,49 +2748,37 @@ static void explainAppendTerm(
** string similar to:
**
** "a=? AND b>?"
-**
-** The returned pointer points to memory obtained from sqlite3DbMalloc().
-** It is the responsibility of the caller to free the buffer when it is
-** no longer required.
*/
-static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){
+static void explainIndexRange(StrAccum *pStr, WhereLoop *pLoop, Table *pTab){
Index *pIndex = pLoop->u.btree.pIndex;
u16 nEq = pLoop->u.btree.nEq;
u16 nSkip = pLoop->u.btree.nSkip;
int i, j;
Column *aCol = pTab->aCol;
i16 *aiColumn = pIndex->aiColumn;
- StrAccum txt;
- if( nEq==0 && (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
- return 0;
- }
- sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
- txt.db = db;
- sqlite3StrAccumAppend(&txt, " (", 2);
+ if( nEq==0 && (pLoop->wsFlags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ) return;
+ sqlite3StrAccumAppend(pStr, " (", 2);
for(i=0; i<nEq; i++){
char *z = aiColumn[i] < 0 ? "rowid" : aCol[aiColumn[i]].zName;
if( i>=nSkip ){
- explainAppendTerm(&txt, i, z, "=");
+ explainAppendTerm(pStr, i, z, "=");
}else{
- if( i ) sqlite3StrAccumAppend(&txt, " AND ", 5);
- sqlite3StrAccumAppend(&txt, "ANY(", 4);
- sqlite3StrAccumAppendAll(&txt, z);
- sqlite3StrAccumAppend(&txt, ")", 1);
+ if( i ) sqlite3StrAccumAppend(pStr, " AND ", 5);
+ sqlite3XPrintf(pStr, 0, "ANY(%s)", z);
}
}
j = i;
if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
char *z = aiColumn[j] < 0 ? "rowid" : aCol[aiColumn[j]].zName;
- explainAppendTerm(&txt, i++, z, ">");
+ explainAppendTerm(pStr, i++, z, ">");
}
if( pLoop->wsFlags&WHERE_TOP_LIMIT ){
char *z = aiColumn[j] < 0 ? "rowid" : aCol[aiColumn[j]].zName;
- explainAppendTerm(&txt, i, z, "<");
+ explainAppendTerm(pStr, i, z, "<");
}
- sqlite3StrAccumAppend(&txt, ")", 1);
- return sqlite3StrAccumFinish(&txt);
+ sqlite3StrAccumAppend(pStr, ")", 1);
}
/*
@@ -2804,11 +2802,13 @@ static void explainOneScan(
struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
Vdbe *v = pParse->pVdbe; /* VM being constructed */
sqlite3 *db = pParse->db; /* Database handle */
- char *zMsg; /* Text to add to EQP output */
int iId = pParse->iSelectId; /* Select id (left-most output column) */
int isSearch; /* True for a SEARCH. False for SCAN. */
WhereLoop *pLoop; /* The controlling WhereLoop object */
u32 flags; /* Flags that describe this loop */
+ char *zMsg; /* Text to add to EQP output */
+ StrAccum str; /* EQP output string */
+ char zBuf[100]; /* Initial space for EQP output string */
pLoop = pLevel->pWLoop;
flags = pLoop->wsFlags;
@@ -2818,54 +2818,70 @@ static void explainOneScan(
|| ((flags&WHERE_VIRTUALTABLE)==0 && (pLoop->u.btree.nEq>0))
|| (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX));
- zMsg = sqlite3MPrintf(db, "%s", isSearch?"SEARCH":"SCAN");
+ sqlite3StrAccumInit(&str, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH);
+ str.db = db;
+ sqlite3StrAccumAppendAll(&str, isSearch ? "SEARCH" : "SCAN");
if( pItem->pSelect ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s SUBQUERY %d", zMsg,pItem->iSelectId);
+ sqlite3XPrintf(&str, 0, " SUBQUERY %d", pItem->iSelectId);
}else{
- zMsg = sqlite3MAppendf(db, zMsg, "%s TABLE %s", zMsg, pItem->zName);
+ sqlite3XPrintf(&str, 0, " TABLE %s", pItem->zName);
}
if( pItem->zAlias ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
+ sqlite3XPrintf(&str, 0, " AS %s", pItem->zAlias);
}
- if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0
- && ALWAYS(pLoop->u.btree.pIndex!=0)
- ){
- const char *zFmt;
- Index *pIdx = pLoop->u.btree.pIndex;
- char *zWhere = explainIndexRange(db, pLoop, pItem->pTab);
+ if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){
+ const char *zFmt = 0;
+ Index *pIdx;
+
+ assert( pLoop->u.btree.pIndex!=0 );
+ pIdx = pLoop->u.btree.pIndex;
assert( !(flags&WHERE_AUTO_INDEX) || (flags&WHERE_IDX_ONLY) );
if( !HasRowid(pItem->pTab) && IsPrimaryKeyIndex(pIdx) ){
- zFmt = zWhere ? "%s USING PRIMARY KEY%.0s%s" : "%s%.0s%s";
+ if( isSearch ){
+ zFmt = "PRIMARY KEY";
+ }
}else if( flags & WHERE_AUTO_INDEX ){
- zFmt = "%s USING AUTOMATIC COVERING INDEX%.0s%s";
+ zFmt = "AUTOMATIC COVERING INDEX";
}else if( flags & WHERE_IDX_ONLY ){
- zFmt = "%s USING COVERING INDEX %s%s";
+ zFmt = "COVERING INDEX %s";
}else{
- zFmt = "%s USING INDEX %s%s";
+ zFmt = "INDEX %s";
+ }
+ if( zFmt ){
+ sqlite3StrAccumAppend(&str, " USING ", 7);
+ sqlite3XPrintf(&str, 0, zFmt, pIdx->zName);
+ explainIndexRange(&str, pLoop, pItem->pTab);
}
- zMsg = sqlite3MAppendf(db, zMsg, zFmt, zMsg, pIdx->zName, zWhere);
- sqlite3DbFree(db, zWhere);
}else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s USING INTEGER PRIMARY KEY", zMsg);
-
+ const char *zRange;
if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid=?)", zMsg);
+ zRange = "(rowid=?)";
}else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>? AND rowid<?)", zMsg);
+ zRange = "(rowid>? AND rowid<?)";
}else if( flags&WHERE_BTM_LIMIT ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>?)", zMsg);
- }else if( ALWAYS(flags&WHERE_TOP_LIMIT) ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid<?)", zMsg);
+ zRange = "(rowid>?)";
+ }else{
+ assert( flags&WHERE_TOP_LIMIT);
+ zRange = "(rowid<?)";
}
+ sqlite3StrAccumAppendAll(&str, " USING INTEGER PRIMARY KEY ");
+ sqlite3StrAccumAppendAll(&str, zRange);
}
#ifndef SQLITE_OMIT_VIRTUALTABLE
else if( (flags & WHERE_VIRTUALTABLE)!=0 ){
- zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
+ sqlite3XPrintf(&str, 0, " VIRTUAL TABLE INDEX %d:%s",
pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr);
}
#endif
- zMsg = sqlite3MAppendf(db, zMsg, "%s", zMsg);
+#ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
+ if( pLoop->nOut>=10 ){
+ sqlite3XPrintf(&str, 0, " (~%llu rows)", sqlite3LogEstToInt(pLoop->nOut));
+ }else{
+ sqlite3StrAccumAppend(&str, " (~1 row)", 9);
+ }
+#endif
+ zMsg = sqlite3StrAccumFinish(&str);
sqlite3VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC);
}
}
@@ -3407,7 +3423,7 @@ static Bitmask codeOneLoopStart(
** B: <after the loop>
**
** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
- ** use an ephermeral index instead of a RowSet to record the primary
+ ** use an ephemeral index instead of a RowSet to record the primary
** keys of the rows we have already seen.
**
*/
@@ -3458,7 +3474,7 @@ static Bitmask codeOneLoopStart(
}
/* Initialize the rowset register to contain NULL. An SQL NULL is
- ** equivalent to an empty rowset. Or, create an ephermeral index
+ ** equivalent to an empty rowset. Or, create an ephemeral index
** capable of holding primary keys in the case of a WITHOUT ROWID.
**
** Also initialize regReturn to contain the address of the instruction
@@ -3519,8 +3535,9 @@ static Bitmask codeOneLoopStart(
** eliminating duplicates from other WHERE clauses, the action for each
** sub-WHERE clause is to to invoke the main loop body as a subroutine.
*/
- wctrlFlags = WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY |
- WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY;
+ wctrlFlags = WHERE_OMIT_OPEN_CLOSE
+ | WHERE_FORCE_TABLE
+ | WHERE_ONETABLE_ONLY;
for(ii=0; ii<pOrWc->nTerm; ii++){
WhereTerm *pOrTerm = &pOrWc->a[ii];
if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
@@ -3532,6 +3549,7 @@ static Bitmask codeOneLoopStart(
pOrExpr = pAndExpr;
}
/* Loop through table entries that match term pOrTerm. */
+ WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
wctrlFlags, iCovCur);
assert( pSubWInfo || pParse->nErr || db->mallocFailed );
@@ -3751,21 +3769,26 @@ static Bitmask codeOneLoopStart(
return pLevel->notReady;
}
-#if defined(WHERETRACE_ENABLED) && defined(SQLITE_ENABLE_TREE_EXPLAIN)
+#ifdef WHERETRACE_ENABLED
/*
-** Generate "Explanation" text for a WhereTerm.
+** Print the content of a WhereTerm object
*/
-static void whereExplainTerm(Vdbe *v, WhereTerm *pTerm){
- char zType[4];
- memcpy(zType, "...", 4);
- if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V';
- if( pTerm->eOperator & WO_EQUIV ) zType[1] = 'E';
- if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L';
- sqlite3ExplainPrintf(v, "%s ", zType);
- sqlite3ExplainExpr(v, pTerm->pExpr);
+static void whereTermPrint(WhereTerm *pTerm, int iTerm){
+ if( pTerm==0 ){
+ sqlite3DebugPrintf("TERM-%-3d NULL\n", iTerm);
+ }else{
+ char zType[4];
+ memcpy(zType, "...", 4);
+ if( pTerm->wtFlags & TERM_VIRTUAL ) zType[0] = 'V';
+ if( pTerm->eOperator & WO_EQUIV ) zType[1] = 'E';
+ if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) zType[2] = 'L';
+ sqlite3DebugPrintf("TERM-%-3d %p %s cursor=%-3d prob=%-3d op=0x%03x\n",
+ iTerm, pTerm, zType, pTerm->leftCursor, pTerm->truthProb,
+ pTerm->eOperator);
+ sqlite3TreeViewExpr(0, pTerm->pExpr, 0);
+ }
}
-#endif /* WHERETRACE_ENABLED && SQLITE_ENABLE_TREE_EXPLAIN */
-
+#endif
#ifdef WHERETRACE_ENABLED
/*
@@ -3781,8 +3804,8 @@ static void whereLoopPrint(WhereLoop *p, WhereClause *pWC){
sqlite3DebugPrintf(" %12s",
pItem->zAlias ? pItem->zAlias : pTab->zName);
if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
- const char *zName;
- if( p->u.btree.pIndex && (zName = p->u.btree.pIndex->zName)!=0 ){
+ const char *zName;
+ if( p->u.btree.pIndex && (zName = p->u.btree.pIndex->zName)!=0 ){
if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){
int i = sqlite3Strlen30(zName) - 1;
while( zName[i]!='_' ) i--;
@@ -3803,29 +3826,18 @@ static void whereLoopPrint(WhereLoop *p, WhereClause *pWC){
sqlite3DebugPrintf(" %-19s", z);
sqlite3_free(z);
}
- sqlite3DebugPrintf(" f %05x N %d", p->wsFlags, p->nLTerm);
+ if( p->wsFlags & WHERE_SKIPSCAN ){
+ sqlite3DebugPrintf(" f %05x %d-%d", p->wsFlags, p->nLTerm,p->u.btree.nSkip);
+ }else{
+ sqlite3DebugPrintf(" f %05x N %d", p->wsFlags, p->nLTerm);
+ }
sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut);
-#ifdef SQLITE_ENABLE_TREE_EXPLAIN
- /* If the 0x100 bit of wheretracing is set, then show all of the constraint
- ** expressions in the WhereLoop.aLTerm[] array.
- */
- if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){ /* WHERETRACE 0x100 */
+ if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){
int i;
- Vdbe *v = pWInfo->pParse->pVdbe;
- 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);
- sqlite3ExplainPop(v);
- sqlite3ExplainNL(v);
+ whereTermPrint(p->aLTerm[i], i);
}
- sqlite3ExplainFinish(v);
- sqlite3DebugPrintf("%s", sqlite3VdbeExplanation(v));
}
-#endif
}
#endif
@@ -4138,7 +4150,7 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
** than pTemplate, so just ignore pTemplate */
#if WHERETRACE_ENABLED /* 0x8 */
if( sqlite3WhereTrace & 0x8 ){
- sqlite3DebugPrintf("ins-noop: ");
+ sqlite3DebugPrintf(" skip: ");
whereLoopPrint(pTemplate, pBuilder->pWC);
}
#endif
@@ -4154,10 +4166,10 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
#if WHERETRACE_ENABLED /* 0x8 */
if( sqlite3WhereTrace & 0x8 ){
if( p!=0 ){
- sqlite3DebugPrintf("ins-del: ");
+ sqlite3DebugPrintf("replace: ");
whereLoopPrint(p, pBuilder->pWC);
}
- sqlite3DebugPrintf("ins-new: ");
+ sqlite3DebugPrintf(" add: ");
whereLoopPrint(pTemplate, pBuilder->pWC);
}
#endif
@@ -4181,7 +4193,7 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
*ppTail = pToDel->pNextLoop;
#if WHERETRACE_ENABLED /* 0x8 */
if( sqlite3WhereTrace & 0x8 ){
- sqlite3DebugPrintf("ins-del: ");
+ sqlite3DebugPrintf(" delete: ");
whereLoopPrint(pToDel, pBuilder->pWC);
}
#endif
@@ -4207,14 +4219,16 @@ static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
** the number of output rows by a factor of 10 and each additional term
** reduces the number of output rows by sqrt(2).
*/
-static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop){
+static void whereLoopOutputAdjust(
+ WhereClause *pWC, /* The WHERE clause */
+ WhereLoop *pLoop, /* The loop to adjust downward */
+ LogEst nRow /* Number of rows in the entire table */
+){
WhereTerm *pTerm, *pX;
Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
int i, j;
+ int nEq = 0; /* Number of = constraints not within likely()/unlikely() */
- if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
- return;
- }
for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
@@ -4226,9 +4240,21 @@ static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop){
if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
}
if( j<0 ){
- pLoop->nOut += (pTerm->truthProb<=0 ? pTerm->truthProb : -1);
+ if( pTerm->truthProb<=0 ){
+ pLoop->nOut += pTerm->truthProb;
+ }else{
+ pLoop->nOut--;
+ if( pTerm->eOperator&WO_EQ ) nEq++;
+ }
}
}
+ /* TUNING: If there is at least one equality constraint in the WHERE
+ ** clause that does not have a likelihood() explicitly assigned to it
+ ** then do not let the estimated number of output rows exceed half
+ ** the number of rows in the table. */
+ if( nEq && pLoop->nOut>nRow-10 ){
+ pLoop->nOut = nRow - 10;
+ }
}
/*
@@ -4274,6 +4300,7 @@ static int whereLoopAddBtreeIndex(
LogEst saved_nOut; /* Original value of pNew->nOut */
int iCol; /* Index of the column in the table */
int rc = SQLITE_OK; /* Return code */
+ LogEst rSize; /* Number of rows in the table */
LogEst rLogSize; /* Logarithm of table size */
WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */
@@ -4303,7 +4330,8 @@ static int whereLoopAddBtreeIndex(
saved_prereq = pNew->prereq;
saved_nOut = pNew->nOut;
pNew->rSetup = 0;
- rLogSize = estLog(pProbe->aiRowLogEst[0]);
+ rSize = pProbe->aiRowLogEst[0];
+ rLogSize = estLog(rSize);
/* Consider using a skip-scan if there are no WHERE clause constraints
** available for the left-most terms of the index, and if the average
@@ -4316,8 +4344,7 @@ static int whereLoopAddBtreeIndex(
** On the other hand, the extra seeks could end up being significantly
** more expensive. */
assert( 42==sqlite3LogEst(18) );
- if( pTerm==0
- && saved_nEq==saved_nSkip
+ if( saved_nEq==saved_nSkip
&& saved_nEq+1<pProbe->nKeyCol
&& pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */
&& (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
@@ -4328,9 +4355,20 @@ static int whereLoopAddBtreeIndex(
pNew->aLTerm[pNew->nLTerm++] = 0;
pNew->wsFlags |= WHERE_SKIPSCAN;
nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1];
+ if( pTerm ){
+ /* TUNING: When estimating skip-scan for a term that is also indexable,
+ ** multiply the cost of the skip-scan by 2.0, to make it a little less
+ ** desirable than the regular index lookup. */
+ nIter += 10; assert( 10==sqlite3LogEst(2) );
+ }
pNew->nOut -= nIter;
+ /* TUNING: Because uncertainties in the estimates for skip-scan queries,
+ ** add a 1.375 fudge factor to make skip-scan slightly less likely. */
+ nIter += 5;
whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul);
pNew->nOut = saved_nOut;
+ pNew->u.btree.nEq = saved_nEq;
+ pNew->u.btree.nSkip = saved_nSkip;
}
for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
u16 eOp = pTerm->eOperator; /* Shorthand for pTerm->eOperator */
@@ -4473,7 +4511,7 @@ static int whereLoopAddBtreeIndex(
nOutUnadjusted = pNew->nOut;
pNew->rRun += nInMul + nIn;
pNew->nOut += nInMul + nIn;
- whereLoopOutputAdjust(pBuilder->pWC, pNew);
+ whereLoopOutputAdjust(pBuilder->pWC, pNew, rSize);
rc = whereLoopInsert(pBuilder, pNew);
if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
@@ -4523,6 +4561,7 @@ static int indexMightHelpWithOrderBy(
Expr *pExpr = sqlite3ExprSkipCollate(pOB->a[ii].pExpr);
if( pExpr->op!=TK_COLUMN ) return 0;
if( pExpr->iTable==iCursor ){
+ if( pExpr->iColumn<0 ) return 1;
for(jj=0; jj<pIndex->nKeyCol; jj++){
if( pExpr->iColumn==pIndex->aiColumn[jj] ) return 1;
}
@@ -4680,13 +4719,21 @@ static int whereLoopAddBtree(
pNew->nLTerm = 1;
pNew->aLTerm[0] = pTerm;
/* TUNING: One-time cost for computing the automatic index is
- ** approximately 7*N*log2(N) where N is the number of rows in
- ** the table being indexed. */
- pNew->rSetup = rLogSize + rSize + 28; assert( 28==sqlite3LogEst(7) );
+ ** estimated to be X*N*log2(N) where N is the number of rows in
+ ** the table being indexed and where X is 7 (LogEst=28) for normal
+ ** tables or 1.375 (LogEst=4) for views and subqueries. The value
+ ** of X is smaller for views and subqueries so that the query planner
+ ** will be more aggressive about generating automatic indexes for
+ ** those objects, since there is no opportunity to add schema
+ ** indexes on subqueries and views. */
+ pNew->rSetup = rLogSize + rSize + 4;
+ if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){
+ pNew->rSetup += 24;
+ }
ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
/* TUNING: Each index lookup yields 20 rows in the table. This
** is more than the usual guess of 10 rows, since we have no way
- ** of knowning how selective the index will ultimately be. It would
+ ** of knowing how selective the index will ultimately be. It would
** not be unreasonable to make this value much larger. */
pNew->nOut = 43; assert( 43==sqlite3LogEst(20) );
pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
@@ -4702,7 +4749,8 @@ static int whereLoopAddBtree(
*/
for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
if( pProbe->pPartIdxWhere!=0
- && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){
+ && !whereUsablePartialIndex(pSrc->iCursor, pWC, pProbe->pPartIdxWhere) ){
+ testcase( pNew->iTab!=pSrc->iCursor ); /* See ticket [98d973b8f5] */
continue; /* Partial index inappropriate for this query */
}
rSize = pProbe->aiRowLogEst[0];
@@ -4726,7 +4774,7 @@ static int whereLoopAddBtree(
/* TUNING: Cost of full table scan is (N*3.0). */
pNew->rRun = rSize + 16;
ApplyCostMultiplier(pNew->rRun, pTab->costMult);
- whereLoopOutputAdjust(pWC, pNew);
+ whereLoopOutputAdjust(pWC, pNew, rSize);
rc = whereLoopInsert(pBuilder, pNew);
pNew->nOut = rSize;
if( rc ) break;
@@ -4762,7 +4810,7 @@ static int whereLoopAddBtree(
pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rSize+16);
}
ApplyCostMultiplier(pNew->rRun, pTab->costMult);
- whereLoopOutputAdjust(pWC, pNew);
+ whereLoopOutputAdjust(pWC, pNew, rSize);
rc = whereLoopInsert(pBuilder, pNew);
pNew->nOut = rSize;
if( rc ) break;
@@ -4969,7 +5017,6 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
struct SrcList_item *pItem;
pWC = pBuilder->pWC;
- if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
pWCEnd = pWC->a + pWC->nTerm;
pNew = pBuilder->pNew;
memset(&sSum, 0, sizeof(sSum));
@@ -4990,6 +5037,7 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
sSubBuild.pOrderBy = 0;
sSubBuild.pOrSet = &sCur;
+ WHERETRACE(0x200, ("Begin processing OR-clause %p\n", pTerm));
for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
if( (pOrTerm->eOperator & WO_AND)!=0 ){
sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc;
@@ -5004,6 +5052,15 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
continue;
}
sCur.n = 0;
+#ifdef WHERETRACE_ENABLED
+ WHERETRACE(0x200, ("OR-term %d of %p has %d subterms:\n",
+ (int)(pOrTerm-pOrWC->a), pTerm, sSubBuild.pWC->nTerm));
+ if( sqlite3WhereTrace & 0x400 ){
+ for(i=0; i<sSubBuild.pWC->nTerm; i++){
+ whereTermPrint(&sSubBuild.pWC->a[i], i);
+ }
+ }
+#endif
#ifndef SQLITE_OMIT_VIRTUALTABLE
if( IsVirtual(pItem->pTab) ){
rc = whereLoopAddVirtual(&sSubBuild, mExtra);
@@ -5012,6 +5069,9 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
{
rc = whereLoopAddBtree(&sSubBuild, mExtra);
}
+ if( rc==SQLITE_OK ){
+ rc = whereLoopAddOr(&sSubBuild, mExtra);
+ }
assert( rc==SQLITE_OK || sCur.n==0 );
if( sCur.n==0 ){
sSum.n = 0;
@@ -5056,6 +5116,7 @@ static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
pNew->prereq = sSum.a[i].prereq;
rc = whereLoopInsert(pBuilder, pNew);
}
+ WHERETRACE(0x200, ("End processing OR-clause %p\n", pTerm));
}
}
return rc;
@@ -5115,7 +5176,7 @@ static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
** strict. With GROUP BY and DISTINCT the only requirement is that
** equivalent rows appear immediately adjacent to one another. GROUP BY
** and DISTINCT do not require rows to appear in any particular order as long
-** as equivelent rows are grouped together. Thus for GROUP BY and DISTINCT
+** as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT
** the pOrderBy terms can be matched in any order. With ORDER BY, the
** pOrderBy terms must be matched in strict left-to-right order.
*/
@@ -5299,7 +5360,7 @@ static i8 wherePathSatisfiesOrderBy(
isMatch = 1;
break;
}
- if( isMatch && (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){
+ if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){
/* Make sure the sort order is compatible in an ORDER BY clause.
** Sort order is irrelevant for a GROUP BY clause. */
if( revSet ){
@@ -5764,12 +5825,15 @@ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){
if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
&& pWInfo->nOBSat==pWInfo->pOrderBy->nExpr
){
- Bitmask notUsed = 0;
+ Bitmask revMask = 0;
int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy,
- pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed
+ pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &revMask
);
assert( pWInfo->sorted==0 );
- pWInfo->sorted = (nOrder==pWInfo->pOrderBy->nExpr);
+ if( nOrder==pWInfo->pOrderBy->nExpr ){
+ pWInfo->sorted = 1;
+ pWInfo->revMask = revMask;
+ }
}
}
@@ -6122,23 +6186,16 @@ WhereInfo *sqlite3WhereBegin(
/* Construct the WhereLoop objects */
WHERETRACE(0xffff,("*** Optimizer Start ***\n"));
+#if defined(WHERETRACE_ENABLED)
/* Display all terms of the WHERE clause */
-#if defined(WHERETRACE_ENABLED) && defined(SQLITE_ENABLE_TREE_EXPLAIN)
if( sqlite3WhereTrace & 0x100 ){
int i;
- Vdbe *v = pParse->pVdbe;
- sqlite3ExplainBegin(v);
for(i=0; i<sWLB.pWC->nTerm; i++){
- sqlite3ExplainPrintf(v, "#%-2d ", i);
- sqlite3ExplainPush(v);
- whereExplainTerm(v, &sWLB.pWC->a[i]);
- sqlite3ExplainPop(v);
- sqlite3ExplainNL(v);
+ whereTermPrint(&sWLB.pWC->a[i], i);
}
- sqlite3ExplainFinish(v);
- sqlite3DebugPrintf("%s", sqlite3VdbeExplanation(v));
}
#endif
+
if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
rc = whereLoopAddAll(&sWLB);
if( rc ) goto whereBeginError;
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.