Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhanced "wheretrace" output in the NGQP solver routine. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
04dfb85a2a7025d4b5056b73fa847769 |
User & Date: | drh 2013-05-21 19:23:10.944 |
Context
2013-05-22
| ||
02:06 | Improvements to ORDER BY handling in the NGQP. Fix an "exit" mistakenly left in a test script during the previous check-in. (check-in: 12c709b436 user: drh tags: nextgen-query-plan-exp) | |
2013-05-21
| ||
19:23 | Enhanced "wheretrace" output in the NGQP solver routine. (check-in: 04dfb85a2a user: drh tags: nextgen-query-plan-exp) | |
15:52 | Work toward improving the NGQP's ability to optimize out ORDER BY clauses. (check-in: 67367f1e1f user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
24 25 26 27 28 29 30 31 32 33 34 35 36 37 | */ #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) /***/ int sqlite3WhereTrace = 0; #endif #if defined(SQLITE_DEBUG) \ && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE)) # define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X #else # define WHERETRACE(X) #endif /* Forward reference */ typedef struct WhereClause WhereClause; | > | 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | */ #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) /***/ int sqlite3WhereTrace = 0; #endif #if defined(SQLITE_DEBUG) \ && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE)) # define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X # define WHERETRACE_ENABLED 1 #else # define WHERETRACE(X) #endif /* Forward reference */ typedef struct WhereClause WhereClause; |
︙ | ︙ | |||
52 53 54 55 56 57 58 59 60 61 62 63 64 65 | ** term of a join. The WhereClause object holds a table of these ** objects using (maskSelf,prereq,) as the primary key. Note that the ** same join term might have multiple associated WhereLoop objects. */ struct WhereLoop { Bitmask prereq; /* Bitmask of other loops that must run first */ Bitmask maskSelf; /* Bitmask identifying table iTab */ u8 iTab; /* Position in FROM clause of table coded by this loop */ u8 iSortIdx; /* Sorting index number. 0==None */ u16 nTerm; /* Number of entries in aTerm[] */ u32 wsFlags; /* WHERE_* flags describing the plan */ double rSetup; /* One-time setup cost (ex: create transient index) */ double rRun; /* Cost of running each loop */ double nOut; /* Estimated number of output rows */ | > > > | 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | ** term of a join. The WhereClause object holds a table of these ** objects using (maskSelf,prereq,) as the primary key. Note that the ** same join term might have multiple associated WhereLoop objects. */ 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 coded by this loop */ u8 iSortIdx; /* Sorting index number. 0==None */ u16 nTerm; /* Number of entries in aTerm[] */ u32 wsFlags; /* WHERE_* flags describing the plan */ double rSetup; /* One-time setup cost (ex: create transient index) */ double rRun; /* Cost of running each loop */ double nOut; /* Estimated number of output rows */ |
︙ | ︙ | |||
1831 1832 1833 1834 1835 1836 1837 | /* ** Two routines for printing the content of an sqlite3_index_info ** structure. Used for testing and debugging only. If neither ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines ** are no-ops. */ | | | 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 | /* ** Two routines for printing the content of an sqlite3_index_info ** structure. Used for testing and debugging only. If neither ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines ** are no-ops. */ #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(WHERETRACE_ENABLED) static void TRACE_IDX_INPUTS(sqlite3_index_info *p){ int i; if( !sqlite3WhereTrace ) return; for(i=0; i<p->nConstraint; i++){ sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n", i, p->aConstraint[i].iColumn, |
︙ | ︙ | |||
5062 5063 5064 5065 5066 5067 5068 | ** analysis only. */ char sqlite3_query_plan[BMS*2*40]; /* Text of the join */ static int nQPlan = 0; /* Next free slow in _query_plan[] */ #endif /* SQLITE_TEST */ | < | | | 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 | ** analysis only. */ char sqlite3_query_plan[BMS*2*40]; /* Text of the join */ static int nQPlan = 0; /* Next free slow in _query_plan[] */ #endif /* SQLITE_TEST */ #ifdef WHERETRACE_ENABLED /* ** Print a WhereLoop object for debugging purposes */ static void whereLoopPrint(WhereLoop *p, SrcList *pTabList){ int nb = 2*((pTabList->nSrc+15)/16); struct SrcList_item *pItem = pTabList->a + p->iTab; Table *pTab = pItem->pTab; sqlite3DebugPrintf("%c %2d.%0*llx.%0*llx", p->cId, p->iTab, nb, p->maskSelf, nb, p->prereq); sqlite3DebugPrintf(" %8s", 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( strncmp(zName, "sqlite_autoindex_", 17)==0 ){ |
︙ | ︙ | |||
5098 5099 5100 5101 5102 5103 5104 | }else{ z = sqlite3_mprintf("(%d)", p->u.vtab.idxNum); } sqlite3DebugPrintf(" %-15s", z); sqlite3_free(z); } sqlite3DebugPrintf(" fg %08x N %2d", p->wsFlags, p->nTerm); | | | 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 | }else{ z = sqlite3_mprintf("(%d)", p->u.vtab.idxNum); } sqlite3DebugPrintf(" %-15s", z); sqlite3_free(z); } sqlite3DebugPrintf(" fg %08x N %2d", p->wsFlags, p->nTerm); sqlite3DebugPrintf(" cost %.2g,%.2g,%.2g\n", p->prereq, p->rSetup, p->rRun, p->nOut); } #endif /* ** Deallocate internal memory used by a WhereLoop object */ |
︙ | ︙ | |||
5873 5874 5875 5876 5877 5878 5879 | } for(i=0; i<=nLoop && nUsed<nOrderBy; i++){ pLoop = i<nLoop ? pPath->aLoop[i] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); isUnique = 1; if( pLoop->wsFlags & WHERE_IPK ){ | | > | 5876 5877 5878 5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891 | } for(i=0; i<=nLoop && nUsed<nOrderBy; i++){ pLoop = i<nLoop ? pPath->aLoop[i] : pLast; assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); isUnique = 1; if( pLoop->wsFlags & WHERE_IPK ){ if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isUnique = 0; if( pLoop->u.btree.nEq!=1 ) isUnique = 0; pIndex = 0; nColumn = 1; }else if( pLoop->u.btree.pIndex==0 ){ return 0; }else{ pIndex = pLoop->u.btree.pIndex; nColumn = pIndex->nColumn; |
︙ | ︙ | |||
5931 5932 5933 5934 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 | } if( nUsed==nOrderBy ){ *pRevMask = revMask; return 1; } return -1; } /* ** Given the list of WhereLoop objects on pWInfo->pLoops, this routine ** attempts to find the lowest cost path that visits each WhereLoop ** once. This path is then loaded into the pWInfo->a[].pWLoop fields. ** | > > > > > > > > > > > > | 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 5955 5956 5957 5958 5959 5960 | } if( nUsed==nOrderBy ){ *pRevMask = revMask; return 1; } return -1; } #ifdef WHERETRACE_ENABLED /* For debugging use only: */ static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){ static char zName[65]; int i; for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; } if( pLast ) zName[i++] = pLast->cId; zName[i] = 0; return zName; } #endif /* ** Given the list of WhereLoop objects on pWInfo->pLoops, this routine ** attempts to find the lowest cost path that visits each WhereLoop ** once. This path is then loaded into the pWInfo->a[].pWLoop fields. ** |
︙ | ︙ | |||
6040 6041 6042 6043 6044 6045 6046 | /* Check to see if pWLoop should be added to the mxChoice best so far */ for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){ if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){ break; } } if( jj>=nTo ){ | | > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > | | | | | | | < < | 6056 6057 6058 6059 6060 6061 6062 6063 6064 6065 6066 6067 6068 6069 6070 6071 6072 6073 6074 6075 6076 6077 6078 6079 6080 6081 6082 6083 6084 6085 6086 6087 6088 6089 6090 6091 6092 6093 6094 6095 6096 6097 6098 6099 6100 6101 6102 6103 6104 6105 6106 6107 6108 6109 6110 6111 6112 6113 6114 6115 6116 6117 6118 6119 6120 6121 6122 6123 6124 6125 6126 6127 6128 6129 6130 6131 6132 6133 6134 6135 6136 6137 6138 6139 6140 6141 6142 6143 6144 6145 6146 6147 6148 | /* Check to see if pWLoop should be added to the mxChoice best so far */ for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){ if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){ break; } } if( jj>=nTo ){ if( nTo>=mxChoice && rCost>=mxCost ){ #ifdef WHERETRACE_ENABLE if( sqlite3WhereTrace>=3 ){ sqlite3DebugPrintf("Skip %s cost=%-7.2g order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); } #endif continue; } /* Add a new Path to the aTo[] set */ if( nTo<mxChoice ){ /* Increase the size of the aTo set by one */ jj = nTo++; }else{ /* New path replaces the prior worst to keep count below mxChoice */ for(jj=nTo-1; aTo[jj].rCost<mxCost; jj--){ assert(jj>0); } } pTo = &aTo[jj]; #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace>=3 ){ sqlite3DebugPrintf("New %s cost=%-7.2g order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); } #endif }else{ if( pTo->rCost<=rCost ){ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace>=3 ){ sqlite3DebugPrintf( "Skip %s cost=%-7.2g order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); sqlite3DebugPrintf(" vs %s cost=%-7.2g order=%c\n", wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); } #endif continue; } /* A new and better score for a previously created equivalent path */ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace>=3 ){ sqlite3DebugPrintf( "Update %s cost=%-7.2g order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); sqlite3DebugPrintf(" was %s cost=%-7.2g order=%c\n", wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); } #endif } /* pWLoop is a winner. Add it to the set of best so far */ pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; pTo->revLoop = revMask; pTo->nRow = pFrom->nRow * pWLoop->nOut; pTo->rCost = rCost; pTo->isOrderedValid = isOrderedValid; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxCost = aTo[0].rCost; for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){ if( pTo->rCost>mxCost ) mxCost = pTo->rCost; } } } } #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace>=2 ){ sqlite3DebugPrintf("---- round %d ----\n", iLoop); for(ii=0, pTo=aTo; ii<nTo; ii++, pTo++){ sqlite3DebugPrintf("%2d: %s cost=%-7.2g nrow=%-7.2g order=%c\n", ii, wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); } } #endif /* Swap the roles of aFrom and aTo for the next generation */ pFrom = aTo; aTo = aFrom; |
︙ | ︙ | |||
6357 6358 6359 6360 6361 6362 6363 | /* Construct the WhereLoop objects */ WHERETRACE(("*** Optimizer Start ***\n")); rc = whereLoopAddAll(&sWLB); if( rc ) goto whereBeginError; /* Display all of the WhereLoop objects if wheretrace is enabled */ | < | > > > > < | | 6415 6416 6417 6418 6419 6420 6421 6422 6423 6424 6425 6426 6427 6428 6429 6430 6431 6432 6433 6434 6435 6436 6437 6438 6439 6440 6441 6442 6443 6444 | /* Construct the WhereLoop objects */ WHERETRACE(("*** Optimizer Start ***\n")); rc = whereLoopAddAll(&sWLB); if( rc ) goto whereBeginError; /* Display all of the WhereLoop objects if wheretrace is enabled */ #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace ){ WhereLoop *p; int i = 0; static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz" "ABCDEFGHIJKLMNOPQRSTUVWYXZ"; for(p=pWInfo->pLoops; p; p=p->pNextLoop){ p->cId = zLabel[(i++)%sizeof(zLabel)]; whereLoopPrint(p, pTabList); } } #endif wherePathSolver(pWInfo); if( db->mallocFailed ) goto whereBeginError; #ifdef WHERETRACE_ENABLED if( sqlite3WhereTrace ){ int ii; sqlite3DebugPrintf("------------ Solution -------------"); if( pWInfo->nOBSat ){ sqlite3DebugPrintf(" ORDER BY omitted\n"); }else{ sqlite3DebugPrintf("\n"); |
︙ | ︙ | |||
6664 6665 6666 6667 6668 6669 6670 | */ assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){ pWInfo->okOnePass = 1; pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } | | | 6724 6725 6726 6727 6728 6729 6730 6731 6732 6733 6734 6735 6736 6737 6738 | */ assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 ); if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){ pWInfo->okOnePass = 1; pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } #if 1 /* Scaffolding: Check the new query plan against the old. Report any ** discrepencies */ for(ii=0; ii<nTabList; ii++){ if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){ sqlite3DebugPrintf("(QP-Mismatch)"); break; } |
︙ | ︙ |
Changes to test/boundary3.test.
︙ | ︙ | |||
119 120 121 122 123 124 125 126 127 128 129 130 131 132 | } } {72057594037927935 17} do_test boundary3-2.1.3 { db eval { SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17 } } {72057594037927935 00ffffffffffffff} do_test boundary3-2.1.gt.1 { db eval { SELECT t2.a FROM t1 JOIN t2 USING(a) WHERE t1.rowid > 72057594037927935 ORDER BY t2.a } } {3 28} do_test boundary3-2.1.gt.2 { | > | 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | } } {72057594037927935 17} do_test boundary3-2.1.3 { db eval { SELECT t1.rowid, x FROM t1 JOIN t2 ON t2.r=t1.rowid WHERE t2.a=17 } } {72057594037927935 00ffffffffffffff} exit do_test boundary3-2.1.gt.1 { db eval { SELECT t2.a FROM t1 JOIN t2 USING(a) WHERE t1.rowid > 72057594037927935 ORDER BY t2.a } } {3 28} do_test boundary3-2.1.gt.2 { |
︙ | ︙ |