From 66d89de8b438326a381b0f45abd66cf7b486c130 Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 2 Nov 2016 16:29:31 +0000 Subject: [PATCH] When the [https://www.sqlite.org/queryplanner.html#partialsort|block sorting optimization] is used in a scalar subquery, be sure to exit the loop as soon as the first valid output row is received. Fix for ticket [cb3aa0641d9a4] backported to the 3.8.9 branch. FossilOrigin-Name: 8e4ba115ededca6da78f0679bc9eff08af9365a8 --- manifest | 15 ++++++++------- manifest.uuid | 2 +- src/select.c | 21 ++++++++++++--------- test/orderby1.test | 17 +++++++++++++++++ 4 files changed, 38 insertions(+), 17 deletions(-) diff --git a/manifest b/manifest index 14c7a6db34..040a26386c 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sthe\sORDER\sBY\sLIMIT\soptimization\sbackport\sso\sthat\sit\sworks\swhen\sthe\nORDER\sBY\suses\sthe\sDESC\sdirection. -D 2016-09-23T18:06:22.679 +C When\sthe\s[https://www.sqlite.org/queryplanner.html#partialsort|block\ssorting\soptimization]\nis\sused\sin\sa\sscalar\ssubquery,\sbe\ssure\sto\sexit\sthe\sloop\sas\ssoon\sas\sthe\sfirst\nvalid\soutput\srow\sis\sreceived.\s\sFix\sfor\sticket\s[cb3aa0641d9a4]\sbackported\nto\sthe\s3.8.9\sbranch. +D 2016-11-02T16:29:31.767 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 00d12636df7a5b08af09116bcd6c7bfd49b8b3b4 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -230,7 +230,7 @@ F src/printf.c 8ae1fa9d30c1200a9268a390ba9e9cea9197b27a F src/random.c ba2679f80ec82c4190062d756f22d0c358180696 F src/resolve.c 41aa91af56d960e9414ce1d7c17cfb68e0d1c6cb F src/rowset.c eccf6af6d620aaa4579bd3b72c1b6395d9e9fa1e -F src/select.c 4123c2bdabb48a7f5a9da749bf82558117da1707 +F src/select.c ec96f4cdc5c39b83f54d8e0cf96bf91f2bb6fac0 F src/shell.c 84a1593bd86aaa14f4da8a8f9b16fbc239d262aa F src/sqlite.h.in 278602140d49575e8708e643161f4263e428a02a F src/sqlite3.rc 992c9f5fb8285ae285d6be28240a7e8d3a7f2bad @@ -772,7 +772,7 @@ F test/notnull.test f8fcf58669ddba79274daa2770d61dfad8274f62 F test/null.test a8b09b8ed87852742343b33441a9240022108993 F test/numcast.test 5d126f7f581432e86a90d1e35cac625164aec4a1 F test/openv2.test 0d3040974bf402e19b7df4b783e447289d7ab394 -F test/orderby1.test eb246e377612b21a418fbea57047ba8ea88aaa6b +F test/orderby1.test 66ca14d7860a2da02411106968afee910ab1e657 F test/orderby2.test bc11009f7cd99d96b1b11e57b199b00633eb5b04 F test/orderby3.test 8619d06a3debdcd80a27c0fdea5c40b468854b99 F test/orderby4.test 4d39bfbaaa3ae64d026ca2ff166353d2edca4ba4 @@ -1250,7 +1250,8 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh 0abfd78ceb09b7f7c27c688c8e3fe93268a13b32 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f -P db3614825fa02ddacc76b85d76a37aad9d2a9dc8 -R 8fe93701829063e8060746a016609ed6 +P 0c3cafb7ebb887dbfa2652f8bf69b52ed265c344 +Q +cdbb0947f9ce18d6d7e29ffab5ea6a2ee5365fbb +R 0ca355757bfd5962ad4a42a2588ffcb2 U drh -Z 16e3e2667c5c6f66c3599e3dc9698a2d +Z 06b72ef4a69c8c5e130f0b97301b13ac diff --git a/manifest.uuid b/manifest.uuid index 5e3cf14f6a..edfa8996b5 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -0c3cafb7ebb887dbfa2652f8bf69b52ed265c344 \ No newline at end of file +8e4ba115ededca6da78f0679bc9eff08af9365a8 \ No newline at end of file diff --git a/src/select.c b/src/select.c index f0c1cbc49d..4788064597 100644 --- a/src/select.c +++ b/src/select.c @@ -53,6 +53,7 @@ struct SortCtx { 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 */ }; @@ -502,6 +503,7 @@ static void pushOntoSorter( int regRecord = ++pParse->nMem; /* Assembled sorter record */ int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */ int op; /* Opcode to add sorter record to sorter */ + int iLimit; /* LIMIT counter */ assert( bSeq==0 || bSeq==1 ); if( nPrefixReg ){ @@ -511,6 +513,9 @@ static void pushOntoSorter( regBase = pParse->nMem + 1; pParse->nMem += nBase; } + assert( pSelect->iOffset==0 || pSelect->iLimit!=0 ); + iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit; + pSort->labelDone = sqlite3VdbeMakeLabel(v); sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, SQLITE_ECEL_DUP); if( bSeq ){ sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr); @@ -518,7 +523,6 @@ static void pushOntoSorter( if( nPrefixReg==0 ){ sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData); } - sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord); if( nOBSat>0 ){ int regPrevKey; /* The first nOBSat columns of the previous row */ @@ -553,6 +557,10 @@ static void pushOntoSorter( pSort->regReturn = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor); + if( iLimit ){ + sqlite3VdbeAddOp2(v, OP_IfNot, iLimit, pSort->labelDone); + VdbeCoverage(v); + } sqlite3VdbeJumpHere(v, addrFirst); sqlite3ExprCodeMove(pParse, regBase, regPrevKey, pSort->nOBSat); sqlite3VdbeJumpHere(v, addrJmp); @@ -563,15 +571,9 @@ static void pushOntoSorter( op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); - if( pSelect->iLimit ){ + if( iLimit ){ int addr; - int iLimit; int r1 = 0; - if( pSelect->iOffset ){ - iLimit = pSelect->iOffset+1; - }else{ - iLimit = pSelect->iLimit; - } /* 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. @@ -1190,7 +1192,7 @@ static void generateSortTail( SelectDest *pDest /* Write the sorted results here */ ){ Vdbe *v = pParse->pVdbe; /* The prepared statement */ - int addrBreak = sqlite3VdbeMakeLabel(v); /* Jump here to exit loop */ + int addrBreak = pSort->labelDone; /* Jump here to exit loop */ int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */ int addr; int addrOnce = 0; @@ -1209,6 +1211,7 @@ static void generateSortTail( struct ExprList_item *aOutEx = p->pEList->a; #endif + assert( addrBreak<0 ); if( pSort->labelBkOut ){ sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); sqlite3VdbeAddOp2(v, OP_Goto, 0, addrBreak); diff --git a/test/orderby1.test b/test/orderby1.test index 6674e32220..dbce37fddf 100644 --- a/test/orderby1.test +++ b/test/orderby1.test @@ -496,4 +496,21 @@ do_execsql_test 7.0 { } {~/ORDER BY/} +#--------------------------------------------------------------------------- +# https://www.sqlite.org/src/tktview/cb3aa0641d9a413841c004293a4fc06cdc122029 +# +# Adverse interaction between scalar subqueries and the partial-sorting +# logic. +# +do_execsql_test 9.0 { + DROP TABLE IF EXISTS t1; + CREATE TABLE t1(x INTEGER PRIMARY KEY); + INSERT INTO t1 VALUES(1),(2); + DROP TABLE IF EXISTS t2; + CREATE TABLE t2(y); + INSERT INTO t2 VALUES(9),(8),(3),(4); + SELECT (SELECT x||y FROM t2, t1 ORDER BY x, y); +} {13} + + finish_test -- 2.47.2