Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | All regression tests now pass with the new bounded-memory sort code. There is still lots of opportunity for optimization, however. (CVS 2654) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
81259a01f1e85ba50a1d017b1282bf84 |
User & Date: | drh 2005-09-01 12:16:29.000 |
Context
2005-09-01
| ||
17:47 | Fix over-aggressive optimization of ORDER BY as reported on the mailing list. (CVS 2655) (check-in: efbb4bc83c user: drh tags: trunk) | |
12:16 | All regression tests now pass with the new bounded-memory sort code. There is still lots of opportunity for optimization, however. (CVS 2654) (check-in: 81259a01f1 user: drh tags: trunk) | |
03:07 | Sorting is now done using a sorting index rather than loading the entire result set into memory and doing a merge sort. The old merge sort technique was a carry-over from SQLite version 1. The new method uses a bounded amount of memory and scales to much larger result sets. There are still errors: some 39 regression tests fail. (CVS 2653) (check-in: 09db0a2424 user: drh tags: trunk) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
8 9 10 11 12 13 14 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. ** | | | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. ** ** $Id: select.c,v 1.259 2005/09/01 12:16:29 drh Exp $ */ #include "sqliteInt.h" /* ** Allocate a new Select structure and return a pointer to that ** structure. |
︙ | ︙ | |||
326 327 328 329 330 331 332 | /* ** 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){ sqlite3ExprCodeExprList(pParse, pOrderBy); | > | | | 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 | /* ** 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){ sqlite3ExprCodeExprList(pParse, pOrderBy); 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); } /* ** Add code to implement the OFFSET and LIMIT */ static void codeLimiter( |
︙ | ︙ | |||
617 618 619 620 621 622 623 | int iTab; ExprList *pOrderBy = p->pOrderBy; if( eDest==SRT_Sorter ) return; iTab = pOrderBy->iTab; addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk); codeLimiter(v, p, cont, brk, 0); | | | 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 | int iTab; ExprList *pOrderBy = p->pOrderBy; if( eDest==SRT_Sorter ) return; iTab = pOrderBy->iTab; addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk); codeLimiter(v, p, cont, brk, 0); sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1); switch( eDest ){ case SRT_Table: case SRT_TempTable: { sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0); sqlite3VdbeAddOp(v, OP_Pull, 1, 0); sqlite3VdbeAddOp(v, OP_Insert, iParm, 0); break; |
︙ | ︙ | |||
1333 1334 1335 1336 1337 1338 1339 | p->iOffset = iMem; } } /* ** Allocate a virtual index to use for sorting. */ | | | 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 | p->iOffset = iMem; } } /* ** Allocate a virtual index to use for sorting. */ static void createSortingIndex(Parse *pParse, Select *p, ExprList *pOrderBy){ if( pOrderBy ){ int addr; assert( pOrderBy->iTab==0 ); pOrderBy->iTab = pParse->nTab++; addr = sqlite3VdbeAddOp(pParse->pVdbe, OP_OpenVirtual, pOrderBy->iTab, pOrderBy->nExpr+1); assert( p->addrOpenVirt[2] == -1 ); |
︙ | ︙ | |||
1694 1695 1696 1697 1698 1699 1700 | int i; /* Loop counter */ KeyInfo *pKeyInfo; /* Collating sequence for the result set */ Select *pLoop; /* For looping through SELECT statements */ CollSeq **apColl; CollSeq **aCopy; assert( p->pRightmost==p ); | | | 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 | int i; /* Loop counter */ KeyInfo *pKeyInfo; /* Collating sequence for the result set */ Select *pLoop; /* For looping through SELECT statements */ CollSeq **apColl; CollSeq **aCopy; assert( p->pRightmost==p ); pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*2*sizeof(CollSeq*) + nCol); if( !pKeyInfo ){ rc = SQLITE_NOMEM; goto multi_select_end; } pKeyInfo->enc = pParse->db->enc; pKeyInfo->nField = nCol; |
︙ | ︙ | |||
1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 | } } if( pOrderBy ){ struct ExprList_item *pOTerm = pOrderBy->a; int nExpr = pOrderBy->nExpr; int addr; aCopy = (CollSeq**)&pKeyInfo[1]; memcpy(aCopy, pKeyInfo->aColl, nCol*sizeof(CollSeq*)); apColl = pKeyInfo->aColl; | > > | > | | > | 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 | } } if( pOrderBy ){ 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; i<pOrderBy->nExpr; i++, pOTerm++, apColl++, pSortOrder++){ Expr *pExpr = pOTerm->pExpr; char *zName = pOTerm->zName; assert( pExpr->op==TK_COLUMN && pExpr->iColumn<nCol ); if( zName ){ *apColl = sqlite3LocateCollSeq(pParse, zName, -1); }else{ *apColl = aCopy[pExpr->iColumn]; } *pSortOrder = pOTerm->sortOrder; } assert( p->pRightmost==p ); assert( p->addrOpenVirt[2]>=0 ); addr = p->addrOpenVirt[2]; 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); } sqliteFree(pKeyInfo); } multi_select_end: |
︙ | ︙ | |||
2629 2630 2631 2632 2633 2634 2635 | } } if( pParse->nErr ){ goto select_end; } pKeyInfo = keyInfoFromExprList(pParse, pOrderBy); pOrderBy->iTab = pParse->nTab++; | | | 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 | } } if( pParse->nErr ){ goto select_end; } pKeyInfo = keyInfoFromExprList(pParse, pOrderBy); pOrderBy->iTab = pParse->nTab++; addr = sqlite3VdbeOp3(v, OP_OpenVirtual, pOrderBy->iTab, pOrderBy->nExpr+2, (char*)pKeyInfo, P3_KEYINFO_HANDOFF); p->addrOpenVirt[2] = addr; } /* Set the limiter. */ computeLimitRegisters(pParse, p); |
︙ | ︙ |
Changes to src/test1.c.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** Code for testing the printf() interface to SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** Code for testing the printf() interface to SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** ** $Id: test1.c,v 1.158 2005/09/01 12:16:29 drh Exp $ */ #include "sqliteInt.h" #include "tcl.h" #include "os.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 | void *pCtx, int nA, const void *zA, int nB, const void *zB ){ Tcl_Interp *i = pTestCollateInterp; int encin = (int)pCtx; int res; sqlite3_value *pVal; Tcl_Obj *pX; pX = Tcl_NewStringObj("test_collate", -1); Tcl_IncrRefCount(pX); | > | 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 | void *pCtx, int nA, const void *zA, int nB, const void *zB ){ Tcl_Interp *i = pTestCollateInterp; int encin = (int)pCtx; int res; int n; sqlite3_value *pVal; Tcl_Obj *pX; pX = Tcl_NewStringObj("test_collate", -1); Tcl_IncrRefCount(pX); |
︙ | ︙ | |||
1160 1161 1162 1163 1164 1165 1166 | break; default: assert(0); } pVal = sqlite3ValueNew(); sqlite3ValueSetStr(pVal, nA, zA, encin, SQLITE_STATIC); | > | > | | 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 | break; default: assert(0); } pVal = sqlite3ValueNew(); sqlite3ValueSetStr(pVal, nA, zA, encin, SQLITE_STATIC); n = sqlite3_value_bytes(pVal); Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj(sqlite3_value_text(pVal),n)); sqlite3ValueSetStr(pVal, nB, zB, encin, SQLITE_STATIC); n = sqlite3_value_bytes(pVal); Tcl_ListObjAppendElement(i,pX,Tcl_NewStringObj(sqlite3_value_text(pVal),n)); sqlite3ValueFree(pVal); Tcl_EvalObjEx(i, pX, 0); Tcl_DecrRefCount(pX); Tcl_GetIntFromObj(i, Tcl_GetObjResult(i), &res); return res; } |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
39 40 41 42 43 44 45 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** | | | 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** 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.480 2005/09/01 12:16:29 drh Exp $ */ #include "sqliteInt.h" #include "os.h" #include <ctype.h> #include "vdbeInt.h" /* |
︙ | ︙ | |||
2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 | pC->rowidIsValid = 0; } } Release(pTos); pTos--; break; } /* Opcode: NewRowid P1 P2 * ** ** Get a new integer record number (a.k.a "rowid") used as the key to a table. ** The record number is not previously used as a key in the database ** table that cursor P1 points to. The new record number is pushed ** onto the stack. | > > > > > > > > > > > > > > > > > > | 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 | pC->rowidIsValid = 0; } } Release(pTos); pTos--; 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 && i<p->nCursor ); 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. ** The record number is not previously used as a key in the database ** table that cursor P1 points to. The new record number is pushed ** onto the stack. |
︙ | ︙ | |||
3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 | ** end. We use the OP_Sort opcode instead of OP_Rewind to do the ** rewinding so that the global variable will be incremented and ** regression tests can determine whether or not the optimizer is ** correctly optimizing out sorts. */ case OP_Sort: { /* no-push */ sqlite3_sort_count++; /* Fall through into OP_Rewind */ } /* Opcode: Rewind P1 P2 * ** ** The next use of the Rowid or Column or Next instruction for P1 ** will refer to the first entry in the database table or index. ** If the table or index is empty and P2>0, then jump immediately to P2. | > | 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 | ** end. We use the OP_Sort opcode instead of OP_Rewind to do the ** rewinding so that the global variable will be incremented and ** regression tests can determine whether or not the optimizer is ** correctly optimizing out sorts. */ case OP_Sort: { /* no-push */ sqlite3_sort_count++; sqlite3_search_count--; /* Fall through into OP_Rewind */ } /* Opcode: Rewind P1 P2 * ** ** The next use of the Rowid or Column or Next instruction for P1 ** will refer to the first entry in the database table or index. ** If the table or index is empty and P2>0, then jump immediately to P2. |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
77 78 79 80 81 82 83 84 85 86 87 88 89 90 | Btree *pBt; /* Separate file holding temporary table */ int nData; /* Number of bytes in pData */ char *pData; /* Data for a NEW or OLD pseudo-table */ i64 iKey; /* Key for the NEW or OLD pseudo-table row */ u8 *pIncrKey; /* Pointer to pKeyInfo->incrKey */ KeyInfo *pKeyInfo; /* Info about index keys needed by index cursors */ int nField; /* Number of fields in the header */ /* Cached information about the header for the data record that the ** cursor is currently pointing to. Only valid if cacheValid is true. ** zRow might point to (ephemeral) data for the current row, or it might ** be NULL. */ Bool cacheValid; /* True if the cache is valid */ int payloadSize; /* Total number of bytes in the record */ | > | 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | Btree *pBt; /* Separate file holding temporary table */ int nData; /* Number of bytes in pData */ char *pData; /* Data for a NEW or OLD pseudo-table */ i64 iKey; /* Key for the NEW or OLD pseudo-table row */ 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. ** zRow might point to (ephemeral) data for the current row, or it might ** be NULL. */ Bool cacheValid; /* True if the cache is valid */ int payloadSize; /* Total number of bytes in the record */ |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
401 402 403 404 405 406 407 408 409 410 411 412 413 414 | } if( zP3==0 ){ pOp->p3 = 0; pOp->p3type = P3_NOTUSED; }else if( n==P3_KEYINFO ){ KeyInfo *pKeyInfo; int nField, nByte; nField = ((KeyInfo*)zP3)->nField; nByte = sizeof(*pKeyInfo) + (nField-1)*sizeof(pKeyInfo->aColl[0]); pKeyInfo = sqliteMallocRaw( nByte ); pOp->p3 = (char*)pKeyInfo; if( pKeyInfo ){ memcpy(pKeyInfo, zP3, nByte); pOp->p3type = P3_KEYINFO; | > > > > > | 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 | } if( zP3==0 ){ pOp->p3 = 0; pOp->p3type = P3_NOTUSED; }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 ); pOp->p3 = (char*)pKeyInfo; if( pKeyInfo ){ memcpy(pKeyInfo, zP3, nByte); pOp->p3type = P3_KEYINFO; |
︙ | ︙ |
Changes to test/enc2.test.
︙ | ︙ | |||
9 10 11 12 13 14 15 | # #*********************************************************************** # This file implements regression tests for SQLite library. The focus of # this file is testing the SQLite routines used for converting between the # various suported unicode encodings (UTF-8, UTF-16, UTF-16le and # UTF-16be). # | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # #*********************************************************************** # This file implements regression tests for SQLite library. The focus of # this file is testing the SQLite routines used for converting between the # various suported unicode encodings (UTF-8, UTF-16, UTF-16le and # UTF-16be). # # $Id: enc2.test,v 1.23 2005/09/01 12:16:29 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # If UTF16 support is disabled, ignore the tests in this file # ifcapable {!utf16} { |
︙ | ︙ | |||
181 182 183 184 185 186 187 188 189 190 191 192 193 194 | set ::values [list one two three four five] set ::test_collate_enc INVALID proc test_collate {enc lhs rhs} { set ::test_collate_enc $enc set l [lsearch -exact $::values $lhs] set r [lsearch -exact $::values $rhs] set res [expr $l - $r] return $res } file delete -force test.db set DB [sqlite3 db test.db] do_test enc2-5.0 { execsql { | > | 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 | set ::values [list one two three four five] set ::test_collate_enc INVALID proc test_collate {enc lhs rhs} { set ::test_collate_enc $enc 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 } file delete -force test.db set DB [sqlite3 db test.db] do_test enc2-5.0 { execsql { |
︙ | ︙ |
Changes to test/where.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2001 September 15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clases. # | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 2001 September 15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # 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.34 2005/09/01 12:16:29 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test where-1.0 { |
︙ | ︙ | |||
332 333 334 335 336 337 338 | # Omit these tests if the build is not capable of sub-queries. # ifcapable subquery { do_test where-5.1 { count { SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1; } | | | | 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 | # Omit these tests if the build is not capable of sub-queries. # ifcapable subquery { do_test where-5.1 { count { SELECT * FROM t1 WHERE rowid IN (1,2,3,1234) order by 1; } } {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; } } {1 0 4 2 1 9 3 1 16 199} do_test where-5.3 { count { SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1; } } {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; } } {1 0 4 2 1 9 3 1 16 199} do_test where-5.5 { count { |
︙ | ︙ | |||
405 406 407 408 409 410 411 | SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1; } } {2 1 9 3 1 16 7} do_test where-5.14 { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1; } | | | 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 | SELECT * FROM t1 WHERE x IN (1,7) AND y NOT IN (6400,8100) ORDER BY 1; } } {2 1 9 3 1 16 7} do_test where-5.14 { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,10) ORDER BY 1; } } {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 1 9 3 1 16 11} } |
︙ | ︙ |