From 4db38a7092f3195ec690e30f045084b575bd0fda Mon Sep 17 00:00:00 2001 From: drh Date: Thu, 1 Sep 2005 12:16:28 +0000 Subject: [PATCH] All regression tests now pass with the new bounded-memory sort code. There is still lots of opportunity for optimization, however. (CVS 2654) FossilOrigin-Name: 81259a01f1e85ba50a1d017b1282bf841b16f0a5 --- manifest | 24 ++++++++++++------------ manifest.uuid | 2 +- src/select.c | 25 +++++++++++++++---------- src/test1.c | 9 ++++++--- src/vdbe.c | 21 ++++++++++++++++++++- src/vdbeInt.h | 1 + src/vdbeaux.c | 5 +++++ test/enc2.test | 3 ++- test/where.test | 8 ++++---- 9 files changed, 66 insertions(+), 32 deletions(-) diff --git a/manifest b/manifest index 711d29e14b..f8736b2964 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Sorting\sis\snow\sdone\susing\sa\ssorting\sindex\srather\sthan\sloading\sthe\sentire\nresult\sset\sinto\smemory\sand\sdoing\sa\smerge\ssort.\s\sThe\sold\smerge\ssort\stechnique\nwas\sa\scarry-over\sfrom\sSQLite\sversion\s1.\s\sThe\snew\smethod\suses\sa\sbounded\samount\nof\smemory\sand\sscales\sto\smuch\slarger\sresult\ssets.\s\sThere\sare\sstill\serrors:\nsome\s39\sregression\stests\sfail.\s(CVS\s2653) -D 2005-09-01T03:07:44 +C All\sregression\stests\snow\spass\swith\sthe\snew\sbounded-memory\ssort\scode.\nThere\sis\sstill\slots\sof\sopportunity\sfor\soptimization,\showever.\s(CVS\s2654) +D 2005-09-01T12:16:29 F Makefile.in 12784cdce5ffc8dfb707300c34e4f1eb3b8a14f1 F Makefile.linux-gcc 06be33b2a9ad4f005a5f42b22c4a19dab3cbb5c7 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028 @@ -63,13 +63,13 @@ F src/pragma.c 69413fbdc0c6aaa493a776ea52c1b3e6cf35dfb2 F src/prepare.c 86f0d8e744b8d956eff6bc40e29049efee017610 F src/printf.c d2678b06cfa07be9b14c330a42310f62340e34ce F src/random.c 90adff4e73a3b249eb4f1fc2a6ff9cf78c7233a4 -F src/select.c a0b10feee29d4e86731c6e381e0ff0ecf9d5eac8 +F src/select.c aabc227c8806fb942dff17965a0e63fe2a9ced67 F src/shell.c b21daba017b8feef2fdc65ecde57f70209494217 F src/sqlite.h.in d6561d51025d08de4f455607f3f9f9aa76e855d5 F src/sqliteInt.h 845ff6f8019f80baafb1bdbb8ef80fcd04d9d0f9 F src/table.c 25b3ff2b39b7d87e8d4a5da0713d68dfc06cbee9 F src/tclsqlite.c ac94682f9e601dd373912c46414a5a842db2089a -F src/test1.c 97425910c6adf87b5dc867ae7704f0430441663c +F src/test1.c ca4b959ce0a966ede87727cd8d3f5905743dfd4e F src/test2.c 792f203be69fea88668fa221321194f0a28dfdfa F src/test3.c f4e6a16a602091696619a1171bda25c0e3df49f7 F src/test4.c a8fd681e139e1c61f22a77d07fc3a99cb28fff3f @@ -80,11 +80,11 @@ F src/update.c a9d2c5f504212d62da1b094476f1389c0e02f83f F src/utf.c bda5eb85039ef16f2d17004c1e18c96e1ab0a80c F src/util.c 5650f6fe5ee30e0678985ad7b94da91e3f85752b F src/vacuum.c 829d9e1a6d7c094b80e0899686670932eafd768c -F src/vdbe.c 70e2dd078b0dfa15b70c0b9d31e7127da7408f15 +F src/vdbe.c efde23f8829b5902cfbc8cca3f3fab51a7e9c99a F src/vdbe.h 3b29a9af6c7a64ed692bef1fc5f61338f40d2f67 -F src/vdbeInt.h c9dcaec8b411384da8b01c362cc856b6560b04f1 +F src/vdbeInt.h 52811a5182c6f98a10d34a1d1d0188fe3582ae03 F src/vdbeapi.c f0d36ff0f06bb5315efac5645b62e99db2c175b8 -F src/vdbeaux.c 68d5d0881ded9867db1521fa2c0ae5ac8007a9d5 +F src/vdbeaux.c afb689d2d5c413ec3448f8f697d07dcd35bd8766 F src/vdbefifo.c 9efb94c8c3f4c979ebd0028219483f88e57584f5 F src/vdbemem.c 4732fd4d1a75dc38549493d7f9a81d02bf7c59b5 F src/where.c bbb973cbbd862b6b872faac39716a3fe13adfb44 @@ -141,7 +141,7 @@ F test/delete2.test e382b6a97787197eb8b93dd4ccd37797c3725ea3 F test/delete3.test 555e84a00a99230b7d049d477a324a631126a6ab F test/diskfull.test ba27afd587af1216f92d2bb00132cbc0e39354fc F test/enc.test 7a03417a1051fe8bc6c7641cf4c8c3f7e0066d52 -F test/enc2.test d1ab077b84f4d3099246915422b1ab6b81481e0a +F test/enc2.test 76c13b8c00beaf95b15c152e95dab51292eb1f0d F test/enc3.test f6a5f0b7b7f3a88f030d3143729b87cd5c86d837 F test/expr.test 71b8cba7fe5c228147c93e530e098144565aaa46 F test/fkey1.test 153004438d51e6769fb1ce165f6313972d6263ce @@ -235,7 +235,7 @@ F test/vacuum.test 5d4857ae2afc9c20d0edb8acc58bdc8d630126a9 F test/vacuum2.test 5d77e98c458bcdbeecc6327de5107179ba1aa095 F test/varint.test ab7b110089a08b9926ed7390e7e97bdefeb74102 F test/view.test ce0f0ad39fa4a3572acffcf1e634850ee151aae0 -F test/where.test 8fcdf3e787d16d3be2d96a94d30273a98c9bbed1 +F test/where.test 9a5d0aaf3dd32ecf7b555049a163e2111d95a274 F test/where2.test 503e2e2b6abe14c5c10222e72d08ef84c1bf1ffb F tool/diffdb.c 7524b1b5df217c20cd0431f6789851a4e0cb191b F tool/lemon.c c88936c67f6411608db8fa4254d254f509fa40f6 @@ -306,7 +306,7 @@ F www/tclsqlite.tcl 3df553505b6efcad08f91e9b975deb2e6c9bb955 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0 F www/version3.tcl a99cf5f6d8bd4d5537584a2b342f0fb9fa601d8b F www/whentouse.tcl 97e2b5cd296f7d8057e11f44427dea8a4c2db513 -P a25801df06e218e70570a6b9eae71603d590fe3a -R 7dae09495a78580995d7ecb2f7ce6601 +P 09db0a24241f9248584250d1728117b8a3159626 +R a28ffb891eb181a1cfb6d78b2bf4c660 U drh -Z 29fbd68d397ac0605a1223b60872d370 +Z 0218deeb57fbf0ef13b89eb807c70c2a diff --git a/manifest.uuid b/manifest.uuid index 2524895de5..61bf402dc3 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -09db0a24241f9248584250d1728117b8a3159626 \ No newline at end of file +81259a01f1e85ba50a1d017b1282bf841b16f0a5 \ No newline at end of file diff --git a/src/select.c b/src/select.c index 3da05e1087..2ff7e282ac 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.258 2005/09/01 03:07:44 drh Exp $ +** $Id: select.c,v 1.259 2005/09/01 12:16:29 drh Exp $ */ #include "sqliteInt.h" @@ -330,8 +330,9 @@ void sqlite3SelectDelete(Select *p){ */ static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){ sqlite3ExprCodeExprList(pParse, pOrderBy); - sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr, 0); - sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 1, 0); + sqlite3VdbeAddOp(v, OP_Sequence, pOrderBy->iTab, 0); + sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr + 1, 0); + sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 2, 0); sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iTab, 0); } @@ -621,7 +622,7 @@ static void generateSortTail( iTab = pOrderBy->iTab; addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk); codeLimiter(v, p, cont, brk, 0); - sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr); + sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1); switch( eDest ){ case SRT_Table: case SRT_TempTable: { @@ -1337,7 +1338,7 @@ static void computeLimitRegisters(Parse *pParse, Select *p){ /* ** Allocate a virtual index to use for sorting. */ -static createSortingIndex(Parse *pParse, Select *p, ExprList *pOrderBy){ +static void createSortingIndex(Parse *pParse, Select *p, ExprList *pOrderBy){ if( pOrderBy ){ int addr; assert( pOrderBy->iTab==0 ); @@ -1698,7 +1699,7 @@ static int multiSelect( CollSeq **aCopy; assert( p->pRightmost==p ); - pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*2*sizeof(CollSeq*)); + pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*2*sizeof(CollSeq*) + nCol); if( !pKeyInfo ){ rc = SQLITE_NOMEM; goto multi_select_end; @@ -1732,11 +1733,13 @@ static int multiSelect( struct ExprList_item *pOTerm = pOrderBy->a; int nExpr = pOrderBy->nExpr; int addr; + u8 *pSortOrder; aCopy = (CollSeq**)&pKeyInfo[1]; + pSortOrder = pKeyInfo->aSortOrder = (u8*)&aCopy[nExpr]; memcpy(aCopy, pKeyInfo->aColl, nCol*sizeof(CollSeq*)); apColl = pKeyInfo->aColl; - for(i=0; inExpr; i++, pOTerm++, apColl++){ + for(i=0; inExpr; i++, pOTerm++, apColl++, pSortOrder++){ Expr *pExpr = pOTerm->pExpr; char *zName = pOTerm->zName; assert( pExpr->op==TK_COLUMN && pExpr->iColumniColumn]; } + *pSortOrder = pOTerm->sortOrder; } assert( p->pRightmost==p ); assert( p->addrOpenVirt[2]>=0 ); addr = p->addrOpenVirt[2]; - sqlite3VdbeChangeP2(v, addr, p->pEList->nExpr+1); - sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO); + sqlite3VdbeChangeP2(v, addr, p->pEList->nExpr+2); + sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO_HANDOFF); + pKeyInfo = 0; generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm); } @@ -2633,7 +2638,7 @@ int sqlite3Select( } pKeyInfo = keyInfoFromExprList(pParse, pOrderBy); pOrderBy->iTab = pParse->nTab++; - addr = sqlite3VdbeOp3(v, OP_OpenVirtual, pOrderBy->iTab, pOrderBy->nExpr+1, + addr = sqlite3VdbeOp3(v, OP_OpenVirtual, pOrderBy->iTab, pOrderBy->nExpr+2, (char*)pKeyInfo, P3_KEYINFO_HANDOFF); p->addrOpenVirt[2] = addr; } diff --git a/src/test1.c b/src/test1.c index 8aafd15ac2..3b555a39ef 100644 --- a/src/test1.c +++ b/src/test1.c @@ -13,7 +13,7 @@ ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** -** $Id: test1.c,v 1.157 2005/08/30 19:30:59 drh Exp $ +** $Id: test1.c,v 1.158 2005/09/01 12:16:29 drh Exp $ */ #include "sqliteInt.h" #include "tcl.h" @@ -1141,6 +1141,7 @@ static int test_collate_func( Tcl_Interp *i = pTestCollateInterp; int encin = (int)pCtx; int res; + int n; sqlite3_value *pVal; Tcl_Obj *pX; @@ -1164,9 +1165,11 @@ static int test_collate_func( pVal = sqlite3ValueNew(); sqlite3ValueSetStr(pVal, nA, zA, encin, SQLITE_STATIC); - Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj(sqlite3_value_text(pVal),-1)); + n = sqlite3_value_bytes(pVal); + Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj(sqlite3_value_text(pVal),n)); sqlite3ValueSetStr(pVal, nB, zB, encin, SQLITE_STATIC); - Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj(sqlite3_value_text(pVal),-1)); + n = sqlite3_value_bytes(pVal); + Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj(sqlite3_value_text(pVal),n)); sqlite3ValueFree(pVal); Tcl_EvalObjEx(i, pX, 0); diff --git a/src/vdbe.c b/src/vdbe.c index 57bda63e00..62898ec9d2 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -43,7 +43,7 @@ ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** -** $Id: vdbe.c,v 1.479 2005/09/01 03:07:44 drh Exp $ +** $Id: vdbe.c,v 1.480 2005/09/01 12:16:29 drh Exp $ */ #include "sqliteInt.h" #include "os.h" @@ -3004,6 +3004,24 @@ case OP_NotExists: { /* no-push */ break; } +/* Opcode: Sequence P1 * * +** +** Push an integer onto the stack which is the next available +** sequence number for cursor P1. The sequence number on the +** cursor is incremented after the push. +*/ +case OP_Sequence: { + int i = pOp->p1; + assert( pTos>=p->aStack ); + assert( i>=0 && inCursor ); + assert( p->apCsr[i]!=0 ); + pTos++; + pTos->i = p->apCsr[i]->seqCount++; + pTos->flags = MEM_Int; + break; +} + + /* Opcode: NewRowid P1 P2 * ** ** Get a new integer record number (a.k.a "rowid") used as the key to a table. @@ -3448,6 +3466,7 @@ case OP_Last: { /* no-push */ */ case OP_Sort: { /* no-push */ sqlite3_sort_count++; + sqlite3_search_count--; /* Fall through into OP_Rewind */ } /* Opcode: Rewind P1 P2 * diff --git a/src/vdbeInt.h b/src/vdbeInt.h index 1936d092d1..36b711487f 100644 --- a/src/vdbeInt.h +++ b/src/vdbeInt.h @@ -81,6 +81,7 @@ struct Cursor { u8 *pIncrKey; /* Pointer to pKeyInfo->incrKey */ KeyInfo *pKeyInfo; /* Info about index keys needed by index cursors */ int nField; /* Number of fields in the header */ + i64 seqCount; /* Sequence counter */ /* Cached information about the header for the data record that the ** cursor is currently pointing to. Only valid if cacheValid is true. diff --git a/src/vdbeaux.c b/src/vdbeaux.c index fc7c35c9fb..60a60dcd15 100644 --- a/src/vdbeaux.c +++ b/src/vdbeaux.c @@ -405,6 +405,11 @@ void sqlite3VdbeChangeP3(Vdbe *p, int addr, const char *zP3, int n){ }else if( n==P3_KEYINFO ){ KeyInfo *pKeyInfo; int nField, nByte; + + /* KeyInfo structures that include an KeyInfo.aSortOrder are always + ** sent in using P3_KEYINFO_HANDOFF. The KeyInfo.aSortOrder array + ** is not duplicated when P3_KEYINFO is used. */ + /* assert( pKeyInfo->aSortOrder==0 ); */ nField = ((KeyInfo*)zP3)->nField; nByte = sizeof(*pKeyInfo) + (nField-1)*sizeof(pKeyInfo->aColl[0]); pKeyInfo = sqliteMallocRaw( nByte ); diff --git a/test/enc2.test b/test/enc2.test index 295cd44c83..e91d14abcd 100644 --- a/test/enc2.test +++ b/test/enc2.test @@ -13,7 +13,7 @@ # various suported unicode encodings (UTF-8, UTF-16, UTF-16le and # UTF-16be). # -# $Id: enc2.test,v 1.22 2005/02/26 17:31:28 drh Exp $ +# $Id: enc2.test,v 1.23 2005/09/01 12:16:29 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl @@ -185,6 +185,7 @@ proc test_collate {enc lhs rhs} { set l [lsearch -exact $::values $lhs] set r [lsearch -exact $::values $rhs] set res [expr $l - $r] + # puts "enc=$enc lhs=$lhs/$l rhs=$rhs/$r res=$res" return $res } diff --git a/test/where.test b/test/where.test index 6e2995353b..25cb6314ef 100644 --- a/test/where.test +++ b/test/where.test @@ -11,7 +11,7 @@ # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clases. # -# $Id: where.test,v 1.33 2005/08/24 03:52:19 drh Exp $ +# $Id: where.test,v 1.34 2005/09/01 12:16:29 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl @@ -336,7 +336,7 @@ ifcapable subquery { count { SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1; } - } {1 0 4 2 1 9 3 1 16 3} + } {1 0 4 2 1 9 3 1 16 4} do_test where-5.2 { count { SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1; @@ -346,7 +346,7 @@ ifcapable subquery { count { SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1; } - } {1 0 4 2 1 9 3 1 16 13} + } {1 0 4 2 1 9 3 1 16 14} do_test where-5.4 { count { SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1; @@ -409,7 +409,7 @@ ifcapable subquery { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1; } - } {2 1 9 9} + } {2 1 9 8} do_test where-5.15 { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1; -- 2.47.2