From d59ba6ce610e55721ff59578cd500b0b02afa5a7 Mon Sep 17 00:00:00 2001 From: drh Date: Sun, 8 Jan 2006 05:02:54 +0000 Subject: [PATCH] Reduce memory requirements for ORDER BY combined with LIMIT. Ticket #1586. (CVS 2887) FossilOrigin-Name: 55e703ecac6e03d7364c2d919ba18d7293d6b7f6 --- manifest | 12 ++++++------ manifest.uuid | 2 +- src/select.c | 45 +++++++++++++++++++++++++++++++++++---------- 3 files changed, 42 insertions(+), 17 deletions(-) diff --git a/manifest b/manifest index ee076b8125..27a9c4b508 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Invalidate\sall\sVDBE\scursor\srow\scaches\sin\sbetween\scalls\sto\ssqlite3_step()\nsince\sthe\semphemeral\scontent\sthat\sthose\scaches\spoint\sto\smight\schange\sif\nthe\sstatement\sis\sREAD\sUNCOMMITTED.\s(CVS\s2886) -D 2006-01-07T18:48:26 +C Reduce\smemory\srequirements\sfor\sORDER\sBY\scombined\swith\sLIMIT.\s\sTicket\s#1586.\s(CVS\s2887) +D 2006-01-08T05:02:55 F Makefile.in c79fbdaa264c6afcd435f2fb492551de5a8cf80d F Makefile.linux-gcc aee18d8a05546dcf1888bd4547e442008a49a092 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028 @@ -66,7 +66,7 @@ F src/pragma.c ae8b135531e7a4d692c60bd909c819d0b3fc588a F src/prepare.c fef89dc92703d345251142af966b60e44a66cfc5 F src/printf.c f47a2f4b5387cd2ebb12e9117a1a5d6bd9a2b812 F src/random.c d40f8d356cecbd351ccfab6eaedd7ec1b54f5261 -F src/select.c 77bcb71f609ff95247a529acf7dfc1c1ec09154b +F src/select.c ad632ffd92ac280d9f8565fe27256e0c4e94c2c9 F src/shell.c 66b073375efbdee19045e7e0cd38b85f9aff71da F src/sqlite.h.in ba3a29daa6a16e054191ccb384a981964e882a1d F src/sqliteInt.h 40c3511c05df83c7c1c244d0432baa9497feee4d @@ -335,7 +335,7 @@ F www/tclsqlite.tcl bb0d1357328a42b1993d78573e587c6dcbc964b9 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0 F www/version3.tcl a99cf5f6d8bd4d5537584a2b342f0fb9fa601d8b F www/whentouse.tcl 97e2b5cd296f7d8057e11f44427dea8a4c2db513 -P 15fda14ee0c0524d3064d767f48edd689c090d95 -R 8b6ba0a7cf083b8ec0fb5215eb91310f +P 0ae461313c1642a49a9f6cda608c42c7c0053ce4 +R 79c569a066edb0857c89ee545cff9b3e U drh -Z c1686b0c208bc7bdd63ff2b9442034c8 +Z e2eb2297d27afb66b9b69713714cfa42 diff --git a/manifest.uuid b/manifest.uuid index 7f3a78821a..dd1dcb56b2 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -0ae461313c1642a49a9f6cda608c42c7c0053ce4 \ No newline at end of file +55e703ecac6e03d7364c2d919ba18d7293d6b7f6 \ No newline at end of file diff --git a/src/select.c b/src/select.c index c1eaec9bf0..b482de90d8 100644 --- a/src/select.c +++ b/src/select.c @@ -12,7 +12,7 @@ ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. ** -** $Id: select.c,v 1.286 2006/01/07 13:21:04 danielk1977 Exp $ +** $Id: select.c,v 1.287 2006/01/08 05:02:55 drh Exp $ */ #include "sqliteInt.h" @@ -351,12 +351,28 @@ void sqlite3SelectDelete(Select *p){ ** Insert code into "v" that will push the record on the top of the ** stack into the sorter. */ -static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){ +static void pushOntoSorter( + Parse *pParse, /* Parser context */ + ExprList *pOrderBy, /* The ORDER BY clause */ + Select *pSelect /* The whole SELECT statement */ +){ + Vdbe *v = pParse->pVdbe; sqlite3ExprCodeExprList(pParse, pOrderBy); sqlite3VdbeAddOp(v, OP_Sequence, pOrderBy->iECursor, 0); sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr + 1, 0); sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 2, 0); sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iECursor, 0); + if( pSelect->iLimit>=0 ){ + int addr1; + sqlite3VdbeAddOp(v, OP_MemIncr, pSelect->iLimit+1, 0); + addr1 = sqlite3VdbeAddOp(v, OP_IfMemPos, pSelect->iLimit+1, 0); + sqlite3VdbeAddOp(v, OP_Goto, 0, 0); + sqlite3VdbeJumpHere(v, addr1); + sqlite3VdbeAddOp(v, OP_Last, pOrderBy->iECursor, 0); + sqlite3VdbeAddOp(v, OP_Delete, pOrderBy->iECursor, 0); + sqlite3VdbeJumpHere(v, addr1+1); + pSelect->iLimit = -1; + } } /* @@ -504,7 +520,7 @@ static int selectInnerLoop( case SRT_VirtualTab: { sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0); if( pOrderBy ){ - pushOntoSorter(pParse, v, pOrderBy); + pushOntoSorter(pParse, pOrderBy, p); }else{ sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0); sqlite3VdbeAddOp(v, OP_Pull, 1, 0); @@ -531,7 +547,7 @@ static int selectInnerLoop( ** ORDER BY in this case since the order of entries in the set ** does not matter. But there might be a LIMIT clause, in which ** case the order does matter */ - pushOntoSorter(pParse, v, pOrderBy); + pushOntoSorter(pParse, pOrderBy, p); }else{ char aff = (iParm>>16)&0xFF; aff = sqlite3CompareAffinity(pEList->a[0].pExpr, aff); @@ -558,7 +574,7 @@ static int selectInnerLoop( case SRT_Mem: { assert( nColumn==1 ); if( pOrderBy ){ - pushOntoSorter(pParse, v, pOrderBy); + pushOntoSorter(pParse, pOrderBy, p); }else{ sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1); /* The LIMIT clause will jump out of the loop for us */ @@ -575,7 +591,7 @@ static int selectInnerLoop( case SRT_Callback: { if( pOrderBy ){ sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0); - pushOntoSorter(pParse, v, pOrderBy); + pushOntoSorter(pParse, pOrderBy, p); }else if( eDest==SRT_Subroutine ){ sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm); }else{ @@ -1358,7 +1374,7 @@ Vdbe *sqlite3GetVdbe(Parse *pParse){ ** the limit and offset. If there is no limit and/or offset, then ** iLimit and iOffset are negative. ** -** This routine changes the values if iLimit and iOffset only if +** This routine changes the values of iLimit and iOffset only if ** a limit or offset is defined by pLimit and pOffset. iLimit and ** iOffset should have been preset to appropriate default values ** (usually but not always -1) prior to calling this routine. @@ -1375,13 +1391,14 @@ static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){ ** no rows. */ if( p->pLimit ){ - int iMem = pParse->nMem++; + int iMem = pParse->nMem; + pParse->nMem += 2; Vdbe *v = sqlite3GetVdbe(pParse); if( v==0 ) return; sqlite3ExprCode(pParse, p->pLimit); sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0); sqlite3VdbeAddOp(v, OP_Negative, 0, 0); - sqlite3VdbeAddOp(v, OP_MemStore, iMem, 1); + sqlite3VdbeAddOp(v, OP_MemStore, iMem, 0); VdbeComment((v, "# LIMIT counter")); sqlite3VdbeAddOp(v, OP_IfMemZero, iMem, iBreak); p->iLimit = iMem; @@ -1393,10 +1410,18 @@ static void computeLimitRegisters(Parse *pParse, Select *p, int iBreak){ sqlite3ExprCode(pParse, p->pOffset); sqlite3VdbeAddOp(v, OP_MustBeInt, 0, 0); sqlite3VdbeAddOp(v, OP_Negative, 0, 0); - sqlite3VdbeAddOp(v, OP_MemStore, iMem, 1); + sqlite3VdbeAddOp(v, OP_MemStore, iMem, p->pLimit==0); VdbeComment((v, "# OFFSET counter")); + if( p->pLimit ){ + sqlite3VdbeAddOp(v, OP_Add, 0, 0); + } p->iOffset = iMem; } + if( p->pLimit ){ + Vdbe *v = pParse->pVdbe; + sqlite3VdbeAddOp(v, OP_MemStore, p->iLimit+1, 1); + VdbeComment((v, "# LIMIT+OFFSET")); + } } /* -- 2.47.2