Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Much faster sorting when there are a large number of columns in the result set. (CVS 3141) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
6b3717aeb4ac45a433f2a30bdd0264ed |
User & Date: | drh 2006-03-17 00:04:03.000 |
Context
2006-03-17
| ||
00:26 | Code and comment cleanup for the sorting optimization of the previous check-in. (CVS 3142) (check-in: f3fbe72733 user: drh tags: trunk) | |
00:04 | Much faster sorting when there are a large number of columns in the result set. (CVS 3141) (check-in: 6b3717aeb4 user: drh tags: trunk) | |
2006-03-16
| ||
16:19 | Fix some compiler warnings. (CVS 3140) (check-in: 6c5175bc0f 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.308 2006/03/17 00:04:03 drh Exp $ */ #include "sqliteInt.h" /* ** Delete all the content of a Select structure but do not deallocate ** the select structure itself. |
︙ | ︙ | |||
676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 | /* ** If the inner loop was generated using a non-null pOrderBy argument, ** then the results were placed in a sorter. After the loop is terminated ** we need to run the sorter and output the results. The following ** routine generates the code needed to do that. */ static void generateSortTail( Select *p, /* The SELECT statement */ Vdbe *v, /* Generate code into this VDBE */ int nColumn, /* Number of columns of data */ int eDest, /* Write the sorted results here */ int iParm /* Optional parameter associated with eDest */ ){ int brk = sqlite3VdbeMakeLabel(v); int cont = sqlite3VdbeMakeLabel(v); int addr; int iTab; ExprList *pOrderBy = p->pOrderBy; iTab = pOrderBy->iECursor; addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk); codeOffset(v, p, cont, 0); sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1); switch( eDest ){ case SRT_Table: case SRT_VirtualTab: { sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0); sqlite3VdbeAddOp(v, OP_Pull, 1, 0); sqlite3VdbeAddOp(v, OP_Insert, iParm, 0); | > > > > > > > > > > | 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 | /* ** If the inner loop was generated using a non-null pOrderBy argument, ** then the results were placed in a sorter. After the loop is terminated ** we need to run the sorter and output the results. The following ** routine generates the code needed to do that. */ static void generateSortTail( Parse *pParse, /* Parsing context */ Select *p, /* The SELECT statement */ Vdbe *v, /* Generate code into this VDBE */ int nColumn, /* Number of columns of data */ int eDest, /* Write the sorted results here */ int iParm /* Optional parameter associated with eDest */ ){ int brk = sqlite3VdbeMakeLabel(v); int cont = sqlite3VdbeMakeLabel(v); int addr; int iTab; int pseudoTab; ExprList *pOrderBy = p->pOrderBy; iTab = pOrderBy->iECursor; if( eDest==SRT_Callback || eDest==SRT_Subroutine ){ pseudoTab = pParse->nTab++; sqlite3VdbeAddOp(v, OP_OpenPseudo, pseudoTab, 0); sqlite3VdbeAddOp(v, OP_SetNumColumns, pseudoTab, nColumn); } addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk); codeOffset(v, p, cont, 0); if( eDest==SRT_Callback || eDest==SRT_Subroutine ){ sqlite3VdbeAddOp(v, OP_Integer, 1, 0); } sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr + 1); switch( eDest ){ case SRT_Table: case SRT_VirtualTab: { sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0); sqlite3VdbeAddOp(v, OP_Pull, 1, 0); sqlite3VdbeAddOp(v, OP_Insert, iParm, 0); |
︙ | ︙ | |||
720 721 722 723 724 725 726 | /* The LIMIT clause will terminate the loop for us */ break; } #endif case SRT_Callback: case SRT_Subroutine: { int i; | < | | < > > > > | 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 | /* The LIMIT clause will terminate the loop for us */ break; } #endif case SRT_Callback: case SRT_Subroutine: { int i; sqlite3VdbeAddOp(v, OP_Insert, pseudoTab, 0); for(i=0; i<nColumn; i++){ sqlite3VdbeAddOp(v, OP_Column, pseudoTab, i); } if( eDest==SRT_Callback ){ sqlite3VdbeAddOp(v, OP_Callback, nColumn, 0); }else{ sqlite3VdbeAddOp(v, OP_Gosub, 0, iParm); } break; } default: { /* Do nothing */ break; } } /* Jump to the end of the loop when the LIMIT is reached */ if( p->iLimit>=0 ){ sqlite3VdbeAddOp(v, OP_MemIncr, -1, p->iLimit); sqlite3VdbeAddOp(v, OP_IfMemZero, p->iLimit, brk); } /* The bottom of the loop */ sqlite3VdbeResolveLabel(v, cont); sqlite3VdbeAddOp(v, OP_Next, iTab, addr); sqlite3VdbeResolveLabel(v, brk); if( eDest==SRT_Callback || eDest==SRT_Subroutine ){ sqlite3VdbeAddOp(v, OP_Close, pseudoTab, 0); } } /* ** Return a pointer to a string containing the 'declaration type' of the ** expression pExpr. The string may be treated as static by the caller. ** ** The declaration type is the exact datatype definition extracted from the |
︙ | ︙ | |||
1960 1961 1962 1963 1964 1965 1966 | assert( p->pRightmost==p ); assert( p->addrOpenVirt[2]>=0 ); addr = p->addrOpenVirt[2]; sqlite3VdbeChangeP2(v, addr, p->pEList->nExpr+2); pKeyInfo->nField = nOrderByExpr; sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO_HANDOFF); pKeyInfo = 0; | | | 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 | assert( p->pRightmost==p ); assert( p->addrOpenVirt[2]>=0 ); addr = p->addrOpenVirt[2]; sqlite3VdbeChangeP2(v, addr, p->pEList->nExpr+2); pKeyInfo->nField = nOrderByExpr; sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO_HANDOFF); pKeyInfo = 0; generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm); } sqliteFree(pKeyInfo); } multi_select_end: return rc; |
︙ | ︙ | |||
3249 3250 3251 3252 3253 3254 3255 | } /* endif aggregate query */ /* If there is an ORDER BY clause, then we need to sort the results ** and send them to the callback one by one. */ if( pOrderBy ){ | | | 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 | } /* endif aggregate query */ /* If there is an ORDER BY clause, then we need to sort the results ** and send them to the callback one by one. */ if( pOrderBy ){ generateSortTail(pParse, p, v, pEList->nExpr, eDest, iParm); } #ifndef SQLITE_OMIT_SUBQUERY /* If this was a subquery, we have now converted the subquery into a ** temporary table. So set the SrcList_item.isPopulated flag to prevent ** this subquery from being evaluated again and to force the use of ** the temporary table. |
︙ | ︙ |
Changes to src/sqliteInt.h.
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. ** ************************************************************************* ** Internal interface definitions for SQLite. ** | | | 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. ** ************************************************************************* ** Internal interface definitions for SQLite. ** ** @(#) $Id: sqliteInt.h,v 1.490 2006/03/17 00:04:04 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* ** Extra interface definitions for those who need them */ |
︙ | ︙ | |||
1635 1636 1637 1638 1639 1640 1641 | TriggerStep *sqlite3TriggerUpdateStep(Token*, ExprList*, Expr*, int); TriggerStep *sqlite3TriggerDeleteStep(Token*, Expr*); void sqlite3DeleteTrigger(Trigger*); void sqlite3UnlinkAndDeleteTrigger(sqlite3*,int,const char*); #else # define sqlite3TriggersExist(A,B,C,D,E,F) 0 # define sqlite3DeleteTrigger(A) | | | 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 | TriggerStep *sqlite3TriggerUpdateStep(Token*, ExprList*, Expr*, int); TriggerStep *sqlite3TriggerDeleteStep(Token*, Expr*); void sqlite3DeleteTrigger(Trigger*); void sqlite3UnlinkAndDeleteTrigger(sqlite3*,int,const char*); #else # define sqlite3TriggersExist(A,B,C,D,E,F) 0 # define sqlite3DeleteTrigger(A) # define sqlite3DropTriggerPtr(A,B) # define sqlite3UnlinkAndDeleteTrigger(A,B,C) # define sqlite3CodeRowTrigger(A,B,C,D,E,F,G,H,I) 0 #endif int sqlite3JoinType(Parse*, Token*, Token*, Token*); void sqlite3CreateForeignKey(Parse*, ExprList*, Token*, ExprList*, int); void sqlite3DeferForeignKey(Parse*, int); |
︙ | ︙ |
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.546 2006/03/17 00:04:04 drh Exp $ */ #include "sqliteInt.h" #include "os.h" #include <ctype.h> #include "vdbeInt.h" /* |
︙ | ︙ | |||
1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 | ** ** We also compute the number of columns in the record. For cursors, ** the number of columns is stored in the Cursor.nField element. For ** records on the stack, the next entry down on the stack is an integer ** which is the number of records. */ assert( p1<0 || p->apCsr[p1]!=0 ); if( p1<0 ){ /* Take the record off of the stack */ Mem *pRec = &pTos[p1]; Mem *pCnt = &pRec[-1]; assert( pRec>=p->aStack ); assert( pRec->flags & MEM_Blob ); payloadSize = pRec->n; zRec = pRec->z; assert( pCnt>=p->aStack ); assert( pCnt->flags & MEM_Int ); nField = pCnt->i; pCrsr = 0; | > > > | < < | 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 | ** ** We also compute the number of columns in the record. For cursors, ** the number of columns is stored in the Cursor.nField element. For ** records on the stack, the next entry down on the stack is an integer ** which is the number of records. */ assert( p1<0 || p->apCsr[p1]!=0 ); #if 0 if( p1<0 ){ /* Take the record off of the stack */ Mem *pRec = &pTos[p1]; Mem *pCnt = &pRec[-1]; assert( pRec>=p->aStack ); assert( pRec->flags & MEM_Blob ); payloadSize = pRec->n; zRec = pRec->z; assert( pCnt>=p->aStack ); assert( pCnt->flags & MEM_Int ); nField = pCnt->i; pCrsr = 0; }else #endif if( (pC = p->apCsr[p1])->pCursor!=0 ){ /* The record is stored in a B-Tree */ rc = sqlite3VdbeCursorMoveto(pC); if( rc ) goto abort_due_to_error; zRec = 0; pCrsr = pC->pCursor; if( pC->nullRow ){ payloadSize = 0; }else if( pC->cacheStatus==p->cacheCtr ){ payloadSize = pC->payloadSize; zRec = (char*)pC->aRow; }else if( pC->isIndex ){ i64 payloadSize64; sqlite3BtreeKeySize(pCrsr, &payloadSize64); payloadSize = payloadSize64; }else{ sqlite3BtreeDataSize(pCrsr, &payloadSize); } nField = pC->nField; }else if( pC->pseudoTable ){ /* The record is the sole entry of a pseudo-table */ payloadSize = pC->nData; zRec = pC->pData; pC->cacheStatus = CACHE_STALE; assert( payloadSize==0 || zRec!=0 ); nField = pC->nField; pCrsr = 0; }else{ zRec = 0; payloadSize = 0; pCrsr = 0; nField = 0; } |
︙ | ︙ | |||
2107 2108 2109 2110 2111 2112 2113 | }else{ pTos->flags = MEM_Null; } } /* If we dynamically allocated space to hold the data (in the ** sqlite3VdbeMemFromBtree() call above) then transfer control of that | | | 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 | }else{ pTos->flags = MEM_Null; } } /* If we dynamically allocated space to hold the data (in the ** sqlite3VdbeMemFromBtree() call above) then transfer control of that ** dynamically allocated space over to the pTos structure. ** This prevents a memory copy. */ if( (sMem.flags & MEM_Dyn)!=0 ){ assert( pTos->flags & MEM_Ephem ); assert( pTos->flags & (MEM_Str|MEM_Blob) ); assert( pTos->z==sMem.z ); assert( sMem.flags & MEM_Term ); |
︙ | ︙ | |||
2718 2719 2720 2721 2722 2723 2724 | } } pCx->nField = pOp->p2; pCx->isIndex = !pCx->isTable; break; } | < | > > < | 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 | } } pCx->nField = pOp->p2; pCx->isIndex = !pCx->isTable; break; } /* Opcode: OpenPseudo P1 * * ** ** Open a new cursor that points to a fake table that contains a single ** row of data. Any attempt to write a second row of data causes the ** first row to be deleted. All data is deleted when the cursor is ** closed. ** ** A pseudo-table created by this opcode is useful for holding the ** NEW or OLD tables in a trigger. Also used to hold the a single ** row output from the sorter so that the row can be decomposed into ** individual columns using the OP_Column opcode. */ case OP_OpenPseudo: { /* no-push */ int i = pOp->p1; Cursor *pCx; assert( i>=0 ); pCx = allocateCursor(p, i, -1); if( pCx==0 ) goto no_mem; pCx->nullRow = 1; pCx->pseudoTable = 1; pCx->pIncrKey = &pCx->bogusIncrKey; pCx->isTable = 1; pCx->isIndex = 0; break; } /* Opcode: Close P1 * * ** ** Close a cursor previously opened as P1. If P1 is not ** currently open, this instruction is a no-op. */ case OP_Close: { /* no-push */ |
︙ | ︙ | |||
3316 3317 3318 3319 3320 3321 3322 | } if( pTos->flags & MEM_Null ){ pTos->z = 0; pTos->n = 0; }else{ assert( pTos->flags & (MEM_Blob|MEM_Str) ); } | < < < < | 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 | } if( pTos->flags & MEM_Null ){ pTos->z = 0; pTos->n = 0; }else{ assert( pTos->flags & (MEM_Blob|MEM_Str) ); } if( pC->pseudoTable ){ sqliteFree(pC->pData); pC->iKey = iKey; pC->nData = pTos->n; if( pTos->flags & MEM_Dyn ){ pC->pData = pTos->z; pTos->flags = MEM_Null; }else{ pC->pData = sqliteMallocRaw( pC->nData+2 ); if( !pC->pData ) goto no_mem; memcpy(pC->pData, pTos->z, pC->nData); pC->pData[pC->nData] = 0; pC->pData[pC->nData+1] = 0; } pC->nullRow = 0; }else{ rc = sqlite3BtreeInsert(pC->pCursor, 0, iKey, pTos->z, pTos->n); } pC->rowidIsValid = 0; pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; /* Invoke the update-hook if required. */ if( rc==SQLITE_OK && db->xUpdateCallback && pOp->p3 ){ |
︙ | ︙ | |||
3494 3495 3496 3497 3498 3499 3500 | pTos->z = z; } if( pC->isIndex ){ sqlite3BtreeKey(pCrsr, 0, n, pTos->z); }else{ sqlite3BtreeData(pCrsr, 0, n, pTos->z); } | < < | 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 | pTos->z = z; } if( pC->isIndex ){ sqlite3BtreeKey(pCrsr, 0, n, pTos->z); }else{ sqlite3BtreeData(pCrsr, 0, n, pTos->z); } }else if( pC->pseudoTable ){ pTos->n = pC->nData; pTos->z = pC->pData; pTos->flags = MEM_Blob|MEM_Ephem; }else{ pTos->flags = MEM_Null; } pTos->enc = SQLITE_UTF8; /* In case the blob is ever cast to text */ break; } |
︙ | ︙ |