Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -4259,19 +4259,20 @@ sDistinct.eTnctType = WHERE_DISTINCT_NOOP; } if( !isAgg && pGroupBy==0 ){ /* No aggregate functions and no GROUP BY clause */ - ExprList *pDist = (sDistinct.isTnct ? p->pEList : 0); + u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0); /* Begin the database scan. */ - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, pDist, 0,0); + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, p->pEList, + wctrlFlags, 0); if( pWInfo==0 ) goto select_end; if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){ p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo); } - if( sqlite3WhereIsDistinct(pWInfo) ){ + if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){ sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); } if( pOrderBy && sqlite3WhereIsOrdered(pWInfo) ) pOrderBy = 0; /* If sorting index that was created by a prior OP_OpenEphemeral Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1022,10 +1022,11 @@ #define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */ #define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */ #define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */ #define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */ #define SQLITE_Transitive 0x0200 /* Transitive constraints */ +#define SQLITE_OmitNoopJoin 0x0400 /* Omit unused tables in joins */ #define SQLITE_AllOpts 0xffff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ @@ -1972,10 +1973,11 @@ #define WHERE_FORCE_TABLE 0x0020 /* Do not use an index-only search */ #define WHERE_ONETABLE_ONLY 0x0040 /* Only code the 1st table in pTabList */ #define WHERE_AND_ONLY 0x0080 /* Don't use indices for OR terms */ #define WHERE_GROUPBY 0x0100 /* pOrderBy is really a GROUP BY */ #define WHERE_DISTINCTBY 0x0200 /* pOrderby is really a DISTINCT clause */ +#define WHERE_WANT_DISTINCT 0x0400 /* All output needs to be distinct */ /* Allowed return values from sqlite3WhereIsDistinct() */ #define WHERE_DISTINCT_NOOP 0 /* DISTINCT keyword not used */ #define WHERE_DISTINCT_UNIQUE 1 /* No duplicates */ Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -381,23 +381,23 @@ */ 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 *pDistinct; /* DISTINCT ON values, 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 */ WhereCost 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 nLevel; /* Number of nested loop */ int savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */ WhereClause sWC; /* Decomposition of the WHERE clause */ WhereLevel a[1]; /* Information about each nest loop in WHERE */ }; @@ -3926,13 +3926,13 @@ */ static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){ int nb = 1+(pTabList->nSrc+7)/8; struct SrcList_item *pItem = pTabList->a + p->iTab; Table *pTab = pItem->pTab; - sqlite3DebugPrintf("%c %2d.%0*llx.%0*llx", p->cId, + sqlite3DebugPrintf("%c%2d.%0*llx.%0*llx", p->cId, p->iTab, nb, p->maskSelf, nb, p->prereq); - sqlite3DebugPrintf(" %8s", + sqlite3DebugPrintf(" %12s", pItem->zAlias ? pItem->zAlias : pTab->zName); if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){ if( p->u.btree.pIndex ){ const char *zName = p->u.btree.pIndex->zName; if( zName==0 ) zName = "ipk"; @@ -3939,26 +3939,26 @@ if( strncmp(zName, "sqlite_autoindex_", 17)==0 ){ int i = sqlite3Strlen30(zName) - 1; while( zName[i]!='_' ) i--; zName += i; } - sqlite3DebugPrintf(".%-12s %2d", zName, p->u.btree.nEq); + sqlite3DebugPrintf(".%-16s %2d", zName, p->u.btree.nEq); }else{ - sqlite3DebugPrintf("%16s",""); + sqlite3DebugPrintf("%20s",""); } }else{ char *z; if( p->u.vtab.idxStr ){ z = sqlite3_mprintf("(%d,\"%s\",%x)", p->u.vtab.idxNum, p->u.vtab.idxStr, p->u.vtab.omitMask); }else{ z = sqlite3_mprintf("(%d,%x)", p->u.vtab.idxNum, p->u.vtab.omitMask); } - sqlite3DebugPrintf(" %-15s", z); + sqlite3DebugPrintf(" %-19s", z); sqlite3_free(z); } - sqlite3DebugPrintf(" fg %05x N %d", p->wsFlags, p->nLTerm); + sqlite3DebugPrintf(" f %04x N %d", p->wsFlags, p->nLTerm); sqlite3DebugPrintf(" cost %d,%d,%d\n", p->rSetup, p->rRun, p->nOut); } #endif /* @@ -5368,16 +5368,17 @@ WhereLevel *pLevel = pWInfo->a + iLoop; pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop]; pLevel->iFrom = pWLoop->iTab; pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor; } - if( (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0 - && pWInfo->pDistinct + if( (pWInfo->wctrlFlags & WHERE_WANT_DISTINCT)!=0 + && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0 + && pWInfo->eDistinct==WHERE_DISTINCT_NOOP && nRowEst ){ Bitmask notUsed; - int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pDistinct, pFrom, + int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom, WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], ¬Used); if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } if( pFrom->isOrdered ){ if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){ @@ -5462,11 +5463,13 @@ pWInfo->a[0].pWLoop = pLoop; pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur); pWInfo->a[0].iTabCur = iCur; pWInfo->nRowOut = 1; if( pWInfo->pOrderBy ) pWInfo->bOBSat = 1; - if( pWInfo->pDistinct ) pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; + if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ + pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; + } #ifdef SQLITE_DEBUG pLoop->cId = '0'; #endif return 1; } @@ -5552,14 +5555,14 @@ ** if there is one. If there is no ORDER BY clause or if this routine ** is called from an UPDATE or DELETE statement, then pOrderBy is NULL. */ WhereInfo *sqlite3WhereBegin( Parse *pParse, /* The parser context */ - SrcList *pTabList, /* A list of all tables to be scanned */ + SrcList *pTabList, /* FROM clause: A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList *pOrderBy, /* An ORDER BY clause, or NULL */ - ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */ + ExprList *pResultSet, /* Result set of the query */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ int nTabList; /* Number of elements in pTabList */ @@ -5567,18 +5570,26 @@ Vdbe *v = pParse->pVdbe; /* The virtual database engine */ Bitmask notReady; /* Cursors that are not yet positioned */ WhereLoopBuilder sWLB; /* The WhereLoop builder */ WhereMaskSet *pMaskSet; /* The expression mask set */ WhereLevel *pLevel; /* A single level in pWInfo->a[] */ + WhereLoop *pLoop; /* Pointer to a single WhereLoop object */ int ii; /* Loop counter */ sqlite3 *db; /* Database connection */ int rc; /* Return code */ /* Variable initialization */ + db = pParse->db; memset(&sWLB, 0, sizeof(sWLB)); sWLB.pOrderBy = pOrderBy; + + /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via + ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ + if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){ + wctrlFlags &= ~WHERE_WANT_DISTINCT; + } /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ testcase( pTabList->nSrc==BMS ); @@ -5599,11 +5610,10 @@ ** struct, the contents of WhereInfo.a[], the WhereClause structure ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte ** field (type Bitmask) it must be aligned on an 8-byte boundary on ** some architectures. Hence the ROUND8() below. */ - db = pParse->db; nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel)); pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereLoop)); if( db->mallocFailed ){ sqlite3DbFree(db, pWInfo); pWInfo = 0; @@ -5611,11 +5621,11 @@ } pWInfo->nLevel = nTabList; pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->pOrderBy = pOrderBy; - pWInfo->pDistinct = pDistinct; + pWInfo->pResultSet = pResultSet; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = &pWInfo->sMaskSet; sWLB.pWInfo = pWInfo; @@ -5624,14 +5634,10 @@ whereLoopInit(sWLB.pNew); #ifdef SQLITE_DEBUG sWLB.pNew->cId = '*'; #endif - /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via - ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ - if( OptimizationDisabled(db, SQLITE_DistinctOpt) ) pDistinct = 0; - /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. */ initMaskSet(pMaskSet); whereClauseInit(&pWInfo->sWC, pWInfo); @@ -5648,11 +5654,13 @@ /* Special case: No FROM clause */ if( nTabList==0 ){ if( pOrderBy ) pWInfo->bOBSat = 1; - if( pDistinct ) pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; + if( wctrlFlags & WHERE_WANT_DISTINCT ){ + pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; + } } /* Assign a bit from the bitmask to every term in the FROM clause. ** ** When assigning bitmask values to FROM clause cursors, it must be @@ -5695,11 +5703,11 @@ /* If the ORDER BY (or GROUP BY) clause contains references to general ** expressions, then we won't be able to satisfy it using indices, so ** go ahead and disable it now. */ - if( pOrderBy && pDistinct ){ + if( pOrderBy && (wctrlFlags & WHERE_WANT_DISTINCT)!=0 ){ for(ii=0; iinExpr; ii++){ Expr *pExpr = sqlite3ExprSkipCollate(pOrderBy->a[ii].pExpr); if( pExpr->op!=TK_COLUMN ){ pWInfo->pOrderBy = pOrderBy = 0; break; @@ -5707,21 +5715,18 @@ break; } } } - /* Check if the DISTINCT qualifier, if there is one, is redundant. - ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to - ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT. - */ - if( pDistinct ){ - if( isDistinctRedundant(pParse,pTabList,&pWInfo->sWC,pDistinct) ){ - pDistinct = 0; + if( wctrlFlags & WHERE_WANT_DISTINCT ){ + if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){ + /* The DISTINCT marking is pointless. Ignore it. */ pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; }else if( pOrderBy==0 ){ + /* Try to ORDER BY the result set to make distinct processing easier */ pWInfo->wctrlFlags |= WHERE_DISTINCTBY; - pWInfo->pOrderBy = pDistinct; + pWInfo->pOrderBy = pResultSet; } } /* Construct the WhereLoop objects */ WHERETRACE(0xffff,("*** Optimizer Start ***\n")); @@ -5731,15 +5736,15 @@ /* Display all of the WhereLoop objects if wheretrace is enabled */ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace ){ WhereLoop *p; - int i = 0; + int i; static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz" "ABCDEFGHIJKLMNOPQRSTUVWYXZ"; - for(p=pWInfo->pLoops; p; p=p->pNextLoop){ - p->cId = zLabel[(i++)%sizeof(zLabel)]; + for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){ + p->cId = zLabel[i%sizeof(zLabel)]; whereLoopPrint(p, pTabList); } } #endif @@ -5776,15 +5781,36 @@ sqlite3DebugPrintf(" DISTINCT=unordered"); break; } } sqlite3DebugPrintf("\n"); - for(ii=0; iinLevel; ii++){ whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList); } } #endif + /* Attempt to omit tables from the join that do not effect the result */ + if( pWInfo->nLevel>=2 + && pResultSet!=0 + && OptimizationEnabled(db, SQLITE_OmitNoopJoin) + ){ + Bitmask tabUsed = exprListTableUsage(pMaskSet, pResultSet); + if( pOrderBy ) tabUsed |= exprListTableUsage(pMaskSet, pOrderBy); + while( pWInfo->nLevel>=2 ){ + pLoop = pWInfo->a[pWInfo->nLevel-1].pWLoop; + if( (pWInfo->pTabList->a[pLoop->iTab].jointype & JT_LEFT)==0 ) break; + if( (wctrlFlags & WHERE_WANT_DISTINCT)==0 + && (pLoop->wsFlags & WHERE_ONEROW)==0 + ){ + break; + } + if( (tabUsed & pLoop->maskSelf)!=0 ) break; + WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId)); + pWInfo->nLevel--; + nTabList--; + } + } WHERETRACE(0xffff,("*** Optimizer Finished ***\n")); pWInfo->pParse->nQueryLoop += pWInfo->nRowOut; /* If the caller is an UPDATE or DELETE statement that is requesting ** to use a one-pass algorithm, determine if this is appropriate. @@ -5949,11 +5975,11 @@ */ sqlite3VdbeResolveLabel(v, pWInfo->iBreak); /* Close all of the cursors that were opened by sqlite3WhereBegin. */ - assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc ); + assert( pWInfo->nLevel<=pTabList->nSrc ); for(i=0, pLevel=pWInfo->a; inLevel; i++, pLevel++){ Index *pIdx = 0; struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; Table *pTab = pTabItem->pTab; assert( pTab!=0 );