Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | In a query with both ORDER BY and LIMIT, if the inner loop satisfies the ORDER BY then try to cut short each invocation of the inner loop once the LIMIT has been satisfied. This check-in is a partial implementation only. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | orderby-limit |
Files: | files | file ages | folders |
SHA1: |
852d1eda6ecca1171f6ed800b06f5b48 |
User & Date: | drh 2016-05-19 22:13:37.318 |
Context
2016-05-19
| ||
22:40 | Appears to work now. Needs test cases, more comments, and code optimization. (check-in: 990fe50c91 user: drh tags: orderby-limit) | |
22:13 | In a query with both ORDER BY and LIMIT, if the inner loop satisfies the ORDER BY then try to cut short each invocation of the inner loop once the LIMIT has been satisfied. This check-in is a partial implementation only. (check-in: 852d1eda6e user: drh tags: orderby-limit) | |
19:31 | Fixup comments on wctrlFlags value definitions. (check-in: 58b516e8c0 user: drh tags: trunk) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
52 53 54 55 56 57 58 59 60 61 62 63 64 65 | int nOBSat; /* Number of ORDER BY terms satisfied by indices */ int iECursor; /* Cursor number for the sorter */ int regReturn; /* Register holding block-output return address */ int labelBkOut; /* Start label for the block-output subroutine */ int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */ int labelDone; /* Jump here when done, ex: LIMIT reached */ u8 sortFlags; /* Zero or more SORTFLAG_* bits */ }; #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */ /* ** Delete all the content of a Select structure. Deallocate the structure ** itself only if bFree is true. */ | > | 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | int nOBSat; /* Number of ORDER BY terms satisfied by indices */ int iECursor; /* Cursor number for the sorter */ int regReturn; /* Register holding block-output return address */ int labelBkOut; /* Start label for the block-output subroutine */ int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */ int labelDone; /* Jump here when done, ex: LIMIT reached */ u8 sortFlags; /* Zero or more SORTFLAG_* bits */ u8 bOrderedInnerLoop; /* ORDER BY correctly sorts the inner loop */ }; #define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */ /* ** Delete all the content of a Select structure. Deallocate the structure ** itself only if bFree is true. */ |
︙ | ︙ | |||
585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 | op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( iLimit ){ int addr; addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, 1); VdbeCoverage(v); sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor); sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor); sqlite3VdbeJumpHere(v, addr); } } /* ** Add code to implement the OFFSET */ | > > > > > > > > > > > > > > > > > > > > | 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 | op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( iLimit ){ int addr; int r1 = 0; /* Fill the sorter until it contains LIMIT+OFFSET entries. (The iLimit ** register is initialized with value of LIMIT+OFFSET.) After the sorter ** fills up, delete the least entry in the sorter after each insert. ** Thus we never hold more than the LIMIT+OFFSET rows in memory at once */ addr = sqlite3VdbeAddOp3(v, OP_IfNotZero, iLimit, 0, 1); VdbeCoverage(v); sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor); if( pSort->bOrderedInnerLoop ){ r1 = ++pParse->nMem; sqlite3VdbeAddOp3(v, OP_Column, pSort->iECursor, nExpr, r1); VdbeComment((v, "seq")); } sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor); if( pSort->bOrderedInnerLoop ){ /* If the inner loop is driven by an index such that values from ** the same iteration of the inner loop are in sorted order, then ** immediately jump to the next iteration of an inner loop if the ** entry from the current iteration does not fit into the top ** LIMIT+OFFSET entries of the sorter. */ int iBrk = sqlite3VdbeCurrentAddr(v) + 2; sqlite3VdbeAddOp3(v, OP_Eq, regBase+nExpr, iBrk, r1); VdbeCoverage(v); } sqlite3VdbeJumpHere(v, addr); } } /* ** Add code to implement the OFFSET */ |
︙ | ︙ | |||
5172 5173 5174 5175 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 | p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo); } if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){ sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); } if( sSort.pOrderBy ){ sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo); if( sSort.nOBSat==sSort.pOrderBy->nExpr ){ sSort.pOrderBy = 0; } } /* If sorting index that was created by a prior OP_OpenEphemeral ** instruction ended up not being needed, then change the OP_OpenEphemeral | > | 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 | p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo); } if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){ sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); } if( sSort.pOrderBy ){ sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo); sSort.bOrderedInnerLoop = sqlite3WhereOrderedInnerLoop(pWInfo); if( sSort.nOBSat==sSort.pOrderBy->nExpr ){ sSort.pOrderBy = 0; } } /* If sorting index that was created by a prior OP_OpenEphemeral ** instruction ended up not being needed, then change the OP_OpenEphemeral |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 | void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); LogEst sqlite3WhereOutputRowCount(WhereInfo*); int sqlite3WhereIsDistinct(WhereInfo*); int sqlite3WhereIsOrdered(WhereInfo*); int sqlite3WhereIsSorted(WhereInfo*); int sqlite3WhereContinueLabel(WhereInfo*); int sqlite3WhereBreakLabel(WhereInfo*); int sqlite3WhereOkOnePass(WhereInfo*, int*); #define ONEPASS_OFF 0 /* Use of ONEPASS not allowed */ #define ONEPASS_SINGLE 1 /* ONEPASS valid for a single row update */ #define ONEPASS_MULTI 2 /* ONEPASS is valid for multiple rows */ | > | 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 | void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); LogEst sqlite3WhereOutputRowCount(WhereInfo*); int sqlite3WhereIsDistinct(WhereInfo*); int sqlite3WhereIsOrdered(WhereInfo*); int sqlite3WhereOrderedInnerLoop(WhereInfo*); int sqlite3WhereIsSorted(WhereInfo*); int sqlite3WhereContinueLabel(WhereInfo*); int sqlite3WhereBreakLabel(WhereInfo*); int sqlite3WhereOkOnePass(WhereInfo*, int*); #define ONEPASS_OFF 0 /* Use of ONEPASS not allowed */ #define ONEPASS_SINGLE 1 /* ONEPASS valid for a single row update */ #define ONEPASS_MULTI 2 /* ONEPASS is valid for multiple rows */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
46 47 48 49 50 51 52 53 54 55 56 57 58 59 | /* ** Return TRUE if the WHERE clause returns rows in ORDER BY order. ** Return FALSE if the output needs to be sorted. */ int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ return pWInfo->nOBSat; } /* ** Return the VDBE address or label to jump to in order to continue ** immediately with the next row of a WHERE clause. */ int sqlite3WhereContinueLabel(WhereInfo *pWInfo){ assert( pWInfo->iContinue!=0 ); | > > > > > > > > > > > > | 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | /* ** Return TRUE if the WHERE clause returns rows in ORDER BY order. ** Return FALSE if the output needs to be sorted. */ int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ return pWInfo->nOBSat; } /* ** Return TRUE if the innermost loop of the WHERE clause implementation ** returns rows in ORDER BY order for complete run of the inner loop. ** ** Across multiple iterations of outer loops, the output rows need not be ** sorted. As long as rows are sorted for just the innermost loop, this ** routine can return TRUE. */ int sqlite3WhereOrderedInnerLoop(WhereInfo *pWInfo){ return pWInfo->bOrderedInnerLoop; } /* ** Return the VDBE address or label to jump to in order to continue ** immediately with the next row of a WHERE clause. */ int sqlite3WhereContinueLabel(WhereInfo *pWInfo){ assert( pWInfo->iContinue!=0 ); |
︙ | ︙ | |||
3894 3895 3896 3897 3898 3899 3900 | if( pWInfo->pOrderBy ){ if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){ if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } }else{ pWInfo->nOBSat = pFrom->isOrdered; | > | | > | 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 | if( pWInfo->pOrderBy ){ if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){ if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } }else{ pWInfo->nOBSat = pFrom->isOrdered; pWInfo->revMask = pFrom->revLoop; if( pWInfo->nOBSat<=0 ){ pWInfo->nOBSat = 0; } } if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP) && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0 ){ Bitmask revMask = 0; int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &revMask |
︙ | ︙ |
Changes to src/whereInt.h.
︙ | ︙ | |||
414 415 416 417 418 419 420 | LogEst nRowOut; /* Estimated number of output rows */ LogEst iLimit; /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */ u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */ u8 sorted; /* True if really sorted (not just grouped) */ u8 eOnePass; /* ONEPASS_OFF, or _SINGLE, or _MULTI */ u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ | | > | 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 | LogEst nRowOut; /* Estimated number of output rows */ LogEst iLimit; /* LIMIT if wctrlFlags has WHERE_USE_LIMIT */ u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */ u8 sorted; /* True if really sorted (not just grouped) */ u8 eOnePass; /* ONEPASS_OFF, or _SINGLE, or _MULTI */ u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ u8 eDistinct; /* One of the WHERE_DISTINCT_* values */ u8 nLevel; /* Number of nested loop */ u8 bOrderedInnerLoop; /* True if only the inner-most loop is ordered */ 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 */ |
︙ | ︙ |