Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Attempt to disable inner loops of a join that do not generate output. This does not work, since the inner loops might run zero times and thus inhibit all output. Needs to be enhanced to work only for LEFT JOINs or when we know that the inner loop will always run at least once. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | omit-join-table-opt |
Files: | files | file ages | folders |
SHA1: |
ca839723a21bb13d3e0666a672c15c6f |
User & Date: | drh 2013-06-21 02:05:06.206 |
Context
2013-06-21
| ||
02:15 | Only eliminate inner loops of a JOIN if they are the RHS of a LEFT JOIN and if they give no more than a single result. This appears to give correct answers in all cases. (check-in: d7a25cc797 user: drh tags: omit-join-table-opt) | |
02:05 | Attempt to disable inner loops of a join that do not generate output. This does not work, since the inner loops might run zero times and thus inhibit all output. Needs to be enhanced to work only for LEFT JOINs or when we know that the inner loop will always run at least once. (check-in: ca839723a2 user: drh tags: omit-join-table-opt) | |
00:35 | Modify the query planner interface so that it always passes in the result set. This is the first step toward adding an optimization that will omit tables from a join that do not contribute to the result. (check-in: 2c2577e69c user: drh tags: omit-join-table-opt) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
388 389 390 391 392 393 394 395 396 397 | 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 */ 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 */ | > < | 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 | 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 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 */ }; /* |
︙ | ︙ | |||
5366 5367 5368 5369 5370 5371 5372 | /* Load the lowest cost path into pWInfo */ for(iLoop=0; iLoop<nLoop; iLoop++){ WhereLevel *pLevel = pWInfo->a + iLoop; pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop]; pLevel->iFrom = pWLoop->iTab; pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor; } | | > | | 5366 5367 5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 | /* Load the lowest cost path into pWInfo */ for(iLoop=0; iLoop<nLoop; iLoop++){ 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_WANT_DISTINCT)!=0 && (pWInfo->wctrlFlags & WHERE_DISTINCTBY)==0 && pWInfo->eDistinct==WHERE_DISTINCT_NOOP && nRowEst ){ Bitmask notUsed; int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom, WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], ¬Used); if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } |
︙ | ︙ | |||
5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 | int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ 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[] */ int ii; /* Loop counter */ sqlite3 *db; /* Database connection */ int rc; /* Return code */ /* Variable initialization */ memset(&sWLB, 0, sizeof(sWLB)); sWLB.pOrderBy = pOrderBy; /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ testcase( pTabList->nSrc==BMS ); if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); | > > > > > > > > | 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 | int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ 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 ); if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); |
︙ | ︙ | |||
5599 5600 5601 5602 5603 5604 5605 | /* Allocate and initialize the WhereInfo structure that will become the ** return value. A single allocation is used to store the WhereInfo ** 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. */ | < | 5608 5609 5610 5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 | /* Allocate and initialize the WhereInfo structure that will become the ** return value. A single allocation is used to store the WhereInfo ** 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. */ nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel)); pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereLoop)); if( db->mallocFailed ){ sqlite3DbFree(db, pWInfo); pWInfo = 0; goto whereBeginError; } |
︙ | ︙ | |||
5624 5625 5626 5627 5628 5629 5630 | sWLB.pWC = &pWInfo->sWC; sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList]; whereLoopInit(sWLB.pNew); #ifdef SQLITE_DEBUG sWLB.pNew->cId = '*'; #endif | < < < < < < | 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642 5643 5644 5645 | sWLB.pWC = &pWInfo->sWC; sWLB.pNew = (WhereLoop*)&pWInfo->a[nTabList]; whereLoopInit(sWLB.pNew); #ifdef SQLITE_DEBUG sWLB.pNew->cId = '*'; #endif /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. */ initMaskSet(pMaskSet); whereClauseInit(&pWInfo->sWC, pWInfo); sqlite3ExprCodeConstants(pParse, pWhere); whereSplit(&pWInfo->sWC, pWhere, TK_AND); /* IMP: R-15842-53296 */ |
︙ | ︙ | |||
5714 5715 5716 5717 5718 5719 5720 | } } } if( wctrlFlags & WHERE_WANT_DISTINCT ){ if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){ /* The DISTINCT marking is pointless. Ignore it. */ | < | | | | 5716 5717 5718 5719 5720 5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733 5734 5735 5736 5737 5738 5739 5740 5741 5742 5743 5744 5745 5746 5747 5748 5749 5750 5751 5752 | } } } 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 = pResultSet; } } /* Construct the WhereLoop objects */ WHERETRACE(0xffff,("*** Optimizer Start ***\n")); if( nTabList!=1 || whereShortCut(&sWLB)==0 ){ 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; static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz" "ABCDEFGHIJKLMNOPQRSTUVWYXZ"; for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){ p->cId = zLabel[i%sizeof(zLabel)]; whereLoopPrint(p, pTabList); } } #endif wherePathSolver(pWInfo, 0); if( db->mallocFailed ) goto whereBeginError; |
︙ | ︙ | |||
5778 5779 5780 5781 5782 5783 5784 | } case WHERE_DISTINCT_UNORDERED: { sqlite3DebugPrintf(" DISTINCT=unordered"); break; } } sqlite3DebugPrintf("\n"); | | > > > > > > > > > > > > > > > > > > | 5779 5780 5781 5782 5783 5784 5785 5786 5787 5788 5789 5790 5791 5792 5793 5794 5795 5796 5797 5798 5799 5800 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 5814 5815 | } case WHERE_DISTINCT_UNORDERED: { sqlite3DebugPrintf(" DISTINCT=unordered"); break; } } sqlite3DebugPrintf("\n"); for(ii=0; ii<pWInfo->nLevel; ii++){ whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList); } } #endif /* Attempt to omit tables from the join that do not effect the result */ if( pResultSet!=0 && pWInfo->nLevel>=2 ){ Bitmask tabUsed = exprListTableUsage(pMaskSet, pResultSet); if( pOrderBy ) tabUsed |= exprListTableUsage(pMaskSet, pOrderBy); while( pWInfo->nLevel>=2 ){ pLoop = pWInfo->a[pWInfo->nLevel-1].pWLoop; if( ((wctrlFlags & WHERE_WANT_DISTINCT)!=0 || (pLoop->wsFlags & WHERE_ONEROW)!=0) && (tabUsed & pLoop->maskSelf)==0 ){ WHERETRACE(0xffff, ("-> drop loop %c not used\n", pLoop->cId)); pWInfo->nLevel--; nTabList--; }else{ break; } } } 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. ** The one-pass algorithm only works if the WHERE clause constraints ** the statement to update a single row. |
︙ | ︙ | |||
5951 5952 5953 5954 5955 5956 5957 | /* The "break" point is here, just past the end of the outer loop. ** Set it. */ sqlite3VdbeResolveLabel(v, pWInfo->iBreak); /* Close all of the cursors that were opened by sqlite3WhereBegin. */ | | | 5970 5971 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 | /* The "break" point is here, just past the end of the outer loop. ** Set it. */ sqlite3VdbeResolveLabel(v, pWInfo->iBreak); /* Close all of the cursors that were opened by sqlite3WhereBegin. */ assert( pWInfo->nLevel<=pTabList->nSrc ); for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){ Index *pIdx = 0; struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; Table *pTab = pTabItem->pTab; assert( pTab!=0 ); pLoop = pLevel->pWLoop; if( (pTab->tabFlags & TF_Ephemeral)==0 |
︙ | ︙ |
Changes to test/alter2.test.
︙ | ︙ | |||
116 117 118 119 120 121 122 | } {1 2 10 3 4 {} 5 6 {}} do_test alter2-1.5 { execsql { CREATE INDEX abc_i ON abc(c); } } {} do_test alter2-1.6 { | < | 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | } {1 2 10 3 4 {} 5 6 {}} do_test alter2-1.5 { execsql { CREATE INDEX abc_i ON abc(c); } } {} do_test alter2-1.6 { execsql { SELECT c FROM abc ORDER BY c; } } {{} {} 10} do_test alter2-1.7 { execsql { SELECT * FROM abc WHERE c = 10; |
︙ | ︙ |