Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -10,11 +10,11 @@ ** ************************************************************************* ** This file contains routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions in SQLite. ** -** $Id: expr.c,v 1.222 2005/08/30 00:54:02 drh Exp $ +** $Id: expr.c,v 1.223 2005/09/01 03:07:44 drh Exp $ */ #include "sqliteInt.h" #include /* @@ -544,13 +544,16 @@ pNew->pPrior = sqlite3SelectDup(p->pPrior); pNew->pLimit = sqlite3ExprDup(p->pLimit); pNew->pOffset = sqlite3ExprDup(p->pOffset); pNew->iLimit = -1; pNew->iOffset = -1; - pNew->ppOpenVirtual = 0; pNew->isResolved = p->isResolved; pNew->isAgg = p->isAgg; + pNew->pRightmost = 0; + pNew->addrOpenVirt[0] = -1; + pNew->addrOpenVirt[1] = -1; + pNew->addrOpenVirt[2] = -1; return pNew; } #else Select *sqlite3SelectDup(Select *p){ assert( p==0 ); Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -10,11 +10,11 @@ ** ************************************************************************* ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. ** -** $Id: select.c,v 1.257 2005/08/31 18:20:00 drh Exp $ +** $Id: select.c,v 1.258 2005/09/01 03:07:44 drh Exp $ */ #include "sqliteInt.h" /* @@ -58,10 +58,13 @@ pNew->op = TK_SELECT; pNew->pLimit = pLimit; pNew->pOffset = pOffset; pNew->iLimit = -1; pNew->iOffset = -1; + pNew->addrOpenVirt[0] = -1; + pNew->addrOpenVirt[1] = -1; + pNew->addrOpenVirt[2] = -1; } return pNew; } /* @@ -325,12 +328,13 @@ ** 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_MakeRecord, pOrderBy->nExpr, 0); - sqlite3VdbeAddOp(v, OP_SortInsert, 0, 0); + sqlite3VdbeAddOp(v, OP_Pull, pOrderBy->nExpr, 0); + sqlite3VdbeAddOp(v, OP_MakeRecord, pOrderBy->nExpr + 1, 0); + sqlite3VdbeAddOp(v, OP_IdxInsert, pOrderBy->iTab, 0); } /* ** Add code to implement the OFFSET and LIMIT */ @@ -552,10 +556,16 @@ } /* ** Given an expression list, generate a KeyInfo structure that records ** the collating sequence for each expression in that expression list. +** +** If the ExprList is an ORDER BY or GROUP BY clause then the resulting +** KeyInfo structure is appropriate for initializing a virtual index to +** implement that clause. If the ExprList is the result set of a SELECT +** then the KeyInfo structure is appropriate for initializing a virtual +** index to implement a DISTINCT test. ** ** Space to hold the KeyInfo structure is obtain from malloc. The calling ** function is responsible for seeing that this structure is eventually ** freed. Add the KeyInfo structure to the P3 field of an opcode using ** P3_KEYINFO_HANDOFF is the usual way of dealing with this. @@ -599,21 +609,21 @@ 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 end1 = sqlite3VdbeMakeLabel(v); - int end2 = sqlite3VdbeMakeLabel(v); + int brk = sqlite3VdbeMakeLabel(v); + int cont = sqlite3VdbeMakeLabel(v); int addr; - KeyInfo *pInfo; + int iTab; + ExprList *pOrderBy = p->pOrderBy; if( eDest==SRT_Sorter ) return; - pInfo = keyInfoFromExprList(pParse, p->pOrderBy); - if( pInfo==0 ) return; - sqlite3VdbeOp3(v, OP_Sort, 0, 0, (char*)pInfo, P3_KEYINFO_HANDOFF); - addr = sqlite3VdbeAddOp(v, OP_SortNext, 0, end1); - codeLimiter(v, p, addr, end2, 1); + iTab = pOrderBy->iTab; + addr = 1 + sqlite3VdbeAddOp(v, OP_Sort, iTab, brk); + codeLimiter(v, p, cont, brk, 0); + sqlite3VdbeAddOp(v, OP_Column, iTab, pOrderBy->nExpr); switch( eDest ){ case SRT_Table: case SRT_TempTable: { sqlite3VdbeAddOp(v, OP_NewRowid, iParm, 0); sqlite3VdbeAddOp(v, OP_Pull, 1, 0); @@ -632,11 +642,11 @@ } case SRT_Exists: case SRT_Mem: { assert( nColumn==1 ); sqlite3VdbeAddOp(v, OP_MemStore, iParm, 1); - sqlite3VdbeAddOp(v, OP_Goto, 0, end1); + sqlite3VdbeAddOp(v, OP_Goto, 0, brk); break; } #endif case SRT_Callback: case SRT_Subroutine: { @@ -657,15 +667,13 @@ default: { /* Do nothing */ break; } } - sqlite3VdbeAddOp(v, OP_Goto, 0, addr); - sqlite3VdbeResolveLabel(v, end2); - sqlite3VdbeAddOp(v, OP_Pop, 1, 0); - sqlite3VdbeResolveLabel(v, end1); - sqlite3VdbeAddOp(v, OP_SortReset, 0, 0); + sqlite3VdbeResolveLabel(v, cont); + sqlite3VdbeAddOp(v, OP_Next, iTab, addr); + sqlite3VdbeResolveLabel(v, brk); } /* ** Return a pointer to a string containing the 'declaration type' of the ** expression pExpr. The string may be treated as static by the caller. @@ -1325,52 +1333,24 @@ p->iOffset = iMem; } } /* -** Generate VDBE instructions that will open a transient table that -** will be used for an index or to store keyed results for a compound -** select. In other words, open a transient table that needs a -** KeyInfo structure. The number of columns in the KeyInfo is determined -** by the result set of the SELECT statement in the second argument. -** -** Specifically, this routine is called to open an index table for -** DISTINCT, UNION, INTERSECT and EXCEPT select statements (but not -** UNION ALL). -** -** The value returned is the address of the OP_OpenVirtual instruction. +** Allocate a virtual index to use for sorting. */ -static int openVirtualIndex(Parse *pParse, Select *p, int iTab){ - KeyInfo *pKeyInfo; - Vdbe *v = pParse->pVdbe; - int addr; - - if( prepSelectStmt(pParse, p) ){ - return 0; +static 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 ); + p->addrOpenVirt[2] = addr; } - pKeyInfo = keyInfoFromExprList(pParse, p->pEList); - if( pKeyInfo==0 ) return 0; - addr = sqlite3VdbeOp3(v, OP_OpenVirtual, iTab, 0, - (char*)pKeyInfo, P3_KEYINFO_HANDOFF); - return addr; } -#ifndef SQLITE_OMIT_COMPOUND_SELECT -/* -** Add the address "addr" to the set of all OpenVirtual opcode addresses -** that are being accumulated in p->ppOpenVirtual. -*/ -static int multiSelectOpenVirtualAddr(Select *p, int addr){ - IdList *pList = *p->ppOpenVirtual = sqlite3IdListAppend(*p->ppOpenVirtual, 0); - if( pList==0 ){ - return SQLITE_NOMEM; - } - pList->a[pList->nId-1].idx = addr; - return SQLITE_OK; -} -#endif /* SQLITE_OMIT_COMPOUND_SELECT */ - #ifndef SQLITE_OMIT_COMPOUND_SELECT /* ** Return the appropriate collating sequence for the iCol-th column of ** the result set for the compound-select statement "p". Return NULL if ** the column has no default collating sequence. @@ -1431,23 +1411,25 @@ char *aff /* If eDest is SRT_Union, the affinity string */ ){ int rc = SQLITE_OK; /* Success code from a subroutine */ Select *pPrior; /* Another SELECT immediately to our left */ Vdbe *v; /* Generate code to this VDBE */ - IdList *pOpenVirtual = 0;/* OP_OpenVirtual opcodes that need a KeyInfo */ - int aAddr[5]; /* Addresses of SetNumColumns operators */ - int nAddr = 0; /* Number used */ int nCol; /* Number of columns in the result set */ + ExprList *pOrderBy; /* The ORDER BY clause on p */ + int aSetP2[2]; /* Set P2 value of these op to number of columns */ + int nSetP2 = 0; /* Number of slots in aSetP2[] used */ /* Make sure there is no ORDER BY or LIMIT clause on prior SELECTs. Only ** the last (right-most) SELECT in the series may have an ORDER BY or LIMIT. */ if( p==0 || p->pPrior==0 ){ rc = 1; goto multi_select_end; } pPrior = p->pPrior; + assert( pPrior->pRightmost!=pPrior ); + assert( pPrior->pRightmost==p->pRightmost ); if( pPrior->pOrderBy ){ sqlite3ErrorMsg(pParse,"ORDER BY clause should come after %s not before", selectOpName(p->op)); rc = 1; goto multi_select_end; @@ -1465,36 +1447,25 @@ if( v==0 ){ rc = 1; goto multi_select_end; } - /* If *p this is the right-most select statement, then initialize - ** p->ppOpenVirtual to point to pOpenVirtual. If *p is not the right most - ** statement then p->ppOpenVirtual will have already been initialized - ** by a prior call to this same procedure. Pass along the pOpenVirtual - ** pointer to pPrior, the next statement to our left. - */ - if( p->ppOpenVirtual==0 ){ - p->ppOpenVirtual = &pOpenVirtual; - } - pPrior->ppOpenVirtual = p->ppOpenVirtual; - /* Create the destination temporary table if necessary */ if( eDest==SRT_TempTable ){ assert( p->pEList ); - sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 0); - assert( nAddr==0 ); - aAddr[nAddr++] = sqlite3VdbeAddOp(v, OP_SetNumColumns, iParm, 0); + assert( nSetP2pOrderBy; switch( p->op ){ case TK_ALL: { - if( p->pOrderBy==0 ){ + if( pOrderBy==0 ){ assert( !pPrior->pLimit ); pPrior->pLimit = p->pLimit; pPrior->pOffset = p->pOffset; rc = sqlite3Select(pParse, pPrior, eDest, iParm, 0, 0, 0, aff); if( rc ){ @@ -1518,38 +1489,37 @@ case TK_UNION: { int unionTab; /* Cursor number of the temporary table holding result */ int op = 0; /* One of the SRT_ operations to apply to self */ int priorOp; /* The SRT_ operation to apply to prior selects */ Expr *pLimit, *pOffset; /* Saved values of p->nLimit and p->nOffset */ - ExprList *pOrderBy; /* The ORDER BY clause for the right SELECT */ int addr; priorOp = p->op==TK_ALL ? SRT_Table : SRT_Union; - if( eDest==priorOp && p->pOrderBy==0 && !p->pLimit && !p->pOffset ){ + if( eDest==priorOp && pOrderBy==0 && !p->pLimit && !p->pOffset ){ /* We can reuse a temporary table generated by a SELECT to our ** right. */ unionTab = iParm; }else{ /* We will need to create our own temporary table to hold the ** intermediate results. */ unionTab = pParse->nTab++; - if( p->pOrderBy - && matchOrderbyToColumn(pParse, p, p->pOrderBy, unionTab, 1) ){ + if( pOrderBy && matchOrderbyToColumn(pParse, p, pOrderBy, unionTab,1) ){ rc = 1; goto multi_select_end; } addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, unionTab, 0); - if( p->op!=TK_ALL ){ - rc = multiSelectOpenVirtualAddr(p, addr); - if( rc!=SQLITE_OK ){ - goto multi_select_end; - } + if( priorOp==SRT_Table ){ + assert( nSetP2addrOpenVirt[0] == -1 ); + p->addrOpenVirt[0] = addr; + p->pRightmost->usesVirt = 1; } - assert( nAddrpEList ); } /* Code the SELECT statements to our left */ @@ -1565,11 +1535,10 @@ case TK_EXCEPT: op = SRT_Except; break; case TK_UNION: op = SRT_Union; break; case TK_ALL: op = SRT_Table; break; } p->pPrior = 0; - pOrderBy = p->pOrderBy; p->pOrderBy = 0; pLimit = p->pLimit; p->pLimit = 0; pOffset = p->pOffset; p->pOffset = 0; @@ -1599,11 +1568,11 @@ iCont = sqlite3VdbeMakeLabel(v); sqlite3VdbeAddOp(v, OP_Rewind, unionTab, iBreak); computeLimitRegisters(pParse, p); iStart = sqlite3VdbeCurrentAddr(v); rc = selectInnerLoop(pParse, p, p->pEList, unionTab, p->pEList->nExpr, - p->pOrderBy, -1, eDest, iParm, + pOrderBy, -1, eDest, iParm, iCont, iBreak, 0); if( rc ){ rc = 1; goto multi_select_end; } @@ -1624,22 +1593,20 @@ ** two temporary tables. Hence it has its own case. Begin ** by allocating the tables we will need. */ tab1 = pParse->nTab++; tab2 = pParse->nTab++; - if( p->pOrderBy && matchOrderbyToColumn(pParse,p,p->pOrderBy,tab1,1) ){ + if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,tab1,1) ){ rc = 1; goto multi_select_end; } + createSortingIndex(pParse, p, pOrderBy); addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, tab1, 0); - rc = multiSelectOpenVirtualAddr(p, addr); - if( rc!=SQLITE_OK ){ - goto multi_select_end; - } - assert( nAddraddrOpenVirt[0] == -1 ); + p->addrOpenVirt[0] = addr; + p->pRightmost->usesVirt = 1; assert( p->pEList ); /* Code the SELECTs to our left into temporary table "tab1". */ rc = sqlite3Select(pParse, pPrior, SRT_Union, tab1, 0, 0, 0, aff); @@ -1648,16 +1615,12 @@ } /* Code the current SELECT into temporary table "tab2" */ addr = sqlite3VdbeAddOp(v, OP_OpenVirtual, tab2, 0); - rc = multiSelectOpenVirtualAddr(p, addr); - if( rc!=SQLITE_OK ){ - goto multi_select_end; - } - assert( nAddraddrOpenVirt[1] == -1 ); + p->addrOpenVirt[1] = addr; p->pPrior = 0; pLimit = p->pLimit; p->pLimit = 0; pOffset = p->pOffset; p->pOffset = 0; @@ -1682,11 +1645,11 @@ sqlite3VdbeAddOp(v, OP_Rewind, tab1, iBreak); computeLimitRegisters(pParse, p); iStart = sqlite3VdbeAddOp(v, OP_RowKey, tab1, 0); sqlite3VdbeAddOp(v, OP_NotFound, tab2, iCont); rc = selectInnerLoop(pParse, p, p->pEList, tab1, p->pEList->nExpr, - p->pOrderBy, -1, eDest, iParm, + pOrderBy, -1, eDest, iParm, iCont, iBreak, 0); if( rc ){ rc = 1; goto multi_select_end; } @@ -1711,13 +1674,12 @@ } /* Set the number of columns in temporary tables */ nCol = p->pEList->nExpr; - while( nAddr>0 ){ - nAddr--; - sqlite3VdbeChangeP2(v, aAddr[nAddr], nCol); + while( nSetP2 ){ + sqlite3VdbeChangeP2(v, aSetP2[--nSetP2], nCol); } /* Compute collating sequences used by either the ORDER BY clause or ** by any temporary tables needed to implement the compound select. ** Attach the KeyInfo structure to all temporary tables. Invoke the @@ -1726,64 +1688,78 @@ ** This section is run by the right-most SELECT statement only. ** SELECT statements to the left always skip this part. The right-most ** SELECT might also skip this part if it has no ORDER BY clause and ** no temp tables are required. */ - if( p->pOrderBy || (pOpenVirtual && pOpenVirtual->nId>0) ){ + if( pOrderBy || p->usesVirt ){ 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->ppOpenVirtual == &pOpenVirtual ); - pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*sizeof(CollSeq*)); + assert( p->pRightmost==p ); + pKeyInfo = sqliteMalloc(sizeof(*pKeyInfo)+nCol*2*sizeof(CollSeq*)); if( !pKeyInfo ){ rc = SQLITE_NOMEM; goto multi_select_end; } pKeyInfo->enc = pParse->db->enc; pKeyInfo->nField = nCol; - for(i=0; iaColl[i] = multiSelectCollSeq(pParse, p, i); - if( !pKeyInfo->aColl[i] ){ - pKeyInfo->aColl[i] = pParse->db->pDfltColl; + for(i=0, apColl=pKeyInfo->aColl; idb->pDfltColl; + } + } + + for(pLoop=p; pLoop; pLoop=pLoop->pPrior){ + for(i=0; i<2; i++){ + int addr = pLoop->addrOpenVirt[i]; + if( addr<0 ){ + /* If [0] is unused then [1] is also unused. So we can + ** always safely abort as soon as the first unused slot is found */ + assert( pLoop->addrOpenVirt[1]<0 ); + break; + } + sqlite3VdbeChangeP2(v, addr, nCol); + sqlite3VdbeChangeP3(v, addr, (char*)pKeyInfo, P3_KEYINFO); } } - for(i=0; pOpenVirtual && inId; i++){ - int p3type = (i==0?P3_KEYINFO_HANDOFF:P3_KEYINFO); - int addr = pOpenVirtual->a[i].idx; - sqlite3VdbeChangeP3(v, addr, (char *)pKeyInfo, p3type); - } + if( pOrderBy ){ + struct ExprList_item *pOTerm = pOrderBy->a; + int nExpr = pOrderBy->nExpr; + int addr; - if( p->pOrderBy ){ - struct ExprList_item *pOrderByTerm = p->pOrderBy->a; - for(i=0; ipOrderBy->nExpr; i++, pOrderByTerm++){ - Expr *pExpr = pOrderByTerm->pExpr; - char *zName = pOrderByTerm->zName; + aCopy = (CollSeq**)&pKeyInfo[1]; + memcpy(aCopy, pKeyInfo->aColl, nCol*sizeof(CollSeq*)); + apColl = pKeyInfo->aColl; + for(i=0; inExpr; i++, pOTerm++, apColl++){ + Expr *pExpr = pOTerm->pExpr; + char *zName = pOTerm->zName; assert( pExpr->op==TK_COLUMN && pExpr->iColumnpColl ); */ if( zName ){ - pExpr->pColl = sqlite3LocateCollSeq(pParse, zName, -1); + *apColl = sqlite3LocateCollSeq(pParse, zName, -1); }else{ - pExpr->pColl = pKeyInfo->aColl[pExpr->iColumn]; + *apColl = aCopy[pExpr->iColumn]; } } + 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); generateSortTail(pParse, p, v, p->pEList->nExpr, eDest, iParm); } - if( !pOpenVirtual ){ - /* This happens for UNION ALL ... ORDER BY */ - sqliteFree(pKeyInfo); - } + sqliteFree(pKeyInfo); } multi_select_end: - if( pOpenVirtual ){ - sqlite3IdListDelete(pOpenVirtual); - } - p->ppOpenVirtual = 0; return rc; } #endif /* SQLITE_OMIT_COMPOUND_SELECT */ #ifndef SQLITE_OMIT_VIEW @@ -2515,10 +2491,16 @@ #ifndef SQLITE_OMIT_COMPOUND_SELECT /* If there is are a sequence of queries, do the earlier ones first. */ if( p->pPrior ){ + if( p->pRightmost==0 ){ + Select *pLoop; + for(pLoop=p; pLoop; pLoop=pLoop->pPrior){ + pLoop->pRightmost = p; + } + } return multiSelect(pParse, p, eDest, iParm, aff); } #endif saveAggregateInfo(pParse, &sAggInfo); @@ -2637,29 +2619,35 @@ /* If there is an ORDER BY clause, resolve any collation sequences ** names that have been explicitly specified. */ if( pOrderBy ){ struct ExprList_item *pTerm; + KeyInfo *pKeyInfo; + int addr; for(i=0, pTerm=pOrderBy->a; inExpr; i++, pTerm++){ if( pTerm->zName ){ pTerm->pExpr->pColl = sqlite3LocateCollSeq(pParse, pTerm->zName, -1); } } if( pParse->nErr ){ goto select_end; } + pKeyInfo = keyInfoFromExprList(pParse, pOrderBy); + pOrderBy->iTab = pParse->nTab++; + addr = sqlite3VdbeOp3(v, OP_OpenVirtual, pOrderBy->iTab, pOrderBy->nExpr+1, + (char*)pKeyInfo, P3_KEYINFO_HANDOFF); + p->addrOpenVirt[2] = addr; } /* Set the limiter. */ computeLimitRegisters(pParse, p); /* If the output is destined for a temporary table, open that table. */ if( eDest==SRT_TempTable ){ - sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, 0); - sqlite3VdbeAddOp(v, OP_SetNumColumns, iParm, pEList->nExpr); + sqlite3VdbeAddOp(v, OP_OpenVirtual, iParm, pEList->nExpr); } /* Do an analysis of aggregate expressions. */ if( isAgg || pGroupBy ){ @@ -2718,12 +2706,15 @@ } /* Open a virtual index to use for the distinct set. */ if( isDistinct ){ + KeyInfo *pKeyInfo; distinct = pParse->nTab++; - openVirtualIndex(pParse, p, distinct); + pKeyInfo = keyInfoFromExprList(pParse, p->pEList); + sqlite3VdbeOp3(v, OP_OpenVirtual, distinct, 0, + (char*)pKeyInfo, P3_KEYINFO_HANDOFF); }else{ distinct = -1; } /* Begin the database scan Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -9,11 +9,11 @@ ** May you share freely, never taking more than you give. ** ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.406 2005/08/30 00:54:03 drh Exp $ +** @(#) $Id: sqliteInt.h,v 1.407 2005/09/01 03:07:44 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* @@ -884,17 +884,17 @@ ** field is not used. */ struct ExprList { int nExpr; /* Number of expressions on the list */ int nAlloc; /* Number of entries allocated below */ + int iTab; /* VDBE Cursor associated with this ExprList */ struct ExprList_item { Expr *pExpr; /* The list of expressions */ char *zName; /* Token associated with this expression */ u8 sortOrder; /* 1 for DESC or 0 for ASC */ u8 isAgg; /* True if this is an aggregate like count(*) */ u8 done; /* A flag to indicate when processing is finished */ - u8 orderByDup[2]; /* Corresponding term in OrderBy/GroupBy clause */ } *a; /* One entry for each expression */ }; /* ** An instance of this structure can hold a simple list of identifiers, @@ -1043,27 +1043,39 @@ ** nLimit is set to -1 if there is no LIMIT clause. nOffset is set to 0. ** If there is a LIMIT clause, the parser sets nLimit to the value of the ** limit and nOffset to the value of the offset (or 0 if there is not ** offset). But later on, nLimit and nOffset become the memory locations ** in the VDBE that record the limit and offset counters. +** +** addrOpenVirt[] entries contain the address of OP_OpenVirtual opcodes. +** These addresses must be stored so that we can go back and fill in +** the P3_KEYINFO and P2 parameters later. Neither the KeyInfo nor +** the number of columns in P2 can be computed at the same time +** as the OP_OpenVirtual instruction is coded because not +** enough information about the compound query is known at that point. +** The KeyInfo for addrOpenVirt[0] and [1] contains collating sequences +** for the result set. The KeyInfo for addrOpenVirt[2] contains collating +** sequences for the ORDER BY clause. */ struct Select { ExprList *pEList; /* The fields of the result */ u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */ u8 isDistinct; /* True if the DISTINCT keyword is present */ + u8 isResolved; /* True once sqlite3SelectResolve() has run. */ + u8 isAgg; /* True if this is an aggregate query */ + u8 usesVirt; /* True if uses an OpenVirtual opcode */ SrcList *pSrc; /* The FROM clause */ Expr *pWhere; /* The WHERE clause */ ExprList *pGroupBy; /* The GROUP BY clause */ Expr *pHaving; /* The HAVING clause */ ExprList *pOrderBy; /* The ORDER BY clause */ Select *pPrior; /* Prior select in a compound select statement */ + Select *pRightmost; /* Right-most select in a compound select statement */ Expr *pLimit; /* LIMIT expression. NULL means not used. */ Expr *pOffset; /* OFFSET expression. NULL means not used. */ int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */ - IdList **ppOpenVirtual;/* OP_OpenVirtual addresses used by multi-selects */ - u8 isResolved; /* True once sqlite3SelectResolve() has run. */ - u8 isAgg; /* True if this is an aggregate query */ + int addrOpenVirt[3]; /* OP_OpenVirtual opcodes related to this select */ }; /* ** The results of a select can be distributed in several ways. */ Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -41,11 +41,11 @@ ** 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.478 2005/07/28 20:51:19 drh Exp $ +** $Id: vdbe.c,v 1.479 2005/09/01 03:07:44 drh Exp $ */ #include "sqliteInt.h" #include "os.h" #include #include "vdbeInt.h" @@ -203,43 +203,10 @@ pTos--; } *ppTos = pTos; } -/* -** The parameters are pointers to the head of two sorted lists -** of Sorter structures. Merge these two lists together and return -** a single sorted list. This routine forms the core of the merge-sort -** algorithm. -** -** In the case of a tie, left sorts in front of right. -*/ -static Sorter *Merge(Sorter *pLeft, Sorter *pRight, KeyInfo *pKeyInfo){ - Sorter sHead; - Sorter *pTail; - pTail = &sHead; - pTail->pNext = 0; - while( pLeft && pRight ){ - int c = sqlite3VdbeRecordCompare(pKeyInfo, pLeft->nKey, pLeft->zKey, - pRight->nKey, pRight->zKey); - if( c<=0 ){ - pTail->pNext = pLeft; - pLeft = pLeft->pNext; - }else{ - pTail->pNext = pRight; - pRight = pRight->pNext; - } - pTail = pTail->pNext; - } - if( pLeft ){ - pTail->pNext = pLeft; - }else if( pRight ){ - pTail->pNext = pRight; - } - return sHead.pNext; -} - /* ** Allocate cursor number iCur. Return a pointer to it. Return NULL ** if we run out of memory. */ static Cursor *allocateCursor(Vdbe *p, int iCur){ @@ -633,11 +600,11 @@ break; } /* Opcode: Halt P1 P2 P3 ** -** Exit immediately. All open cursors, Lists, Sorts, etc are closed +** Exit immediately. All open cursors, Fifos, etc are closed ** automatically. ** ** P1 is the result code returned by sqlite3_exec(), sqlite3_reset(), ** or sqlite3_finalize(). For a normal halt, this should be SQLITE_OK (0). ** For errors, it can be some other value. If P1!=0 then P2 will determine @@ -2601,17 +2568,18 @@ } } break; } -/* Opcode: OpenVirtual P1 * P3 +/* Opcode: OpenVirtual P1 P2 P3 ** -** Open a new cursor to a transient or virtual table. +** Open a new cursor P1 to a transient or virtual table. ** The cursor is always opened read/write even if ** the main database is read-only. The transient or virtual ** table is deleted automatically when the cursor is closed. ** +** P2 is the number of columns in the virtual table. ** The cursor points to a BTree table if P3==0 and to a BTree index ** if P3 is not 0. If P3 is not NULL, it points to a KeyInfo structure ** that defines the format of keys in the index. */ case OP_OpenVirtual: { /* no-push */ @@ -2648,10 +2616,11 @@ rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, 0, &pCx->pCursor); pCx->isTable = 1; pCx->pIncrKey = &pCx->bogusIncrKey; } } + pCx->nField = pOp->p2; pCx->isIndex = !pCx->isTable; break; } #ifndef SQLITE_OMIT_TRIGGER @@ -3462,10 +3431,27 @@ pC->nullRow = 0; } break; } + +/* Opcode: Sort P1 P2 * +** +** This opcode does exactly the same thing as OP_Rewind except that +** it increments an undocumented global variable used for testing. +** +** Sorting is accomplished by writing records into a sorting index, +** then rewinding that index and playing it back from beginning to +** 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. @@ -4089,112 +4075,10 @@ p->sFifo = pContext->sFifo; break; } #endif /* #ifndef SQLITE_OMIT_TRIGGER */ -/* Opcode: SortInsert * * * -** -** The TOS is the key and the NOS is the data. Pop both from the stack -** and put them on the sorter. The key and data should have been -** made using the MakeRecord opcode. -*/ -case OP_SortInsert: { /* no-push */ - Mem *pNos = &pTos[-1]; - Sorter *pSorter; - assert( pNos>=p->aStack ); - if( Dynamicify(pTos, db->enc) ) goto no_mem; - pSorter = sqliteMallocRaw( sizeof(Sorter) ); - if( pSorter==0 ) goto no_mem; - pSorter->pNext = 0; - if( p->pSortTail ){ - p->pSortTail->pNext = pSorter; - }else{ - p->pSort = pSorter; - } - p->pSortTail = pSorter; - assert( pTos->flags & MEM_Dyn ); - pSorter->nKey = pTos->n; - pSorter->zKey = pTos->z; - pSorter->data.flags = MEM_Null; - rc = sqlite3VdbeMemMove(&pSorter->data, pNos); - pTos -= 2; - break; -} - -/* Opcode: Sort * * P3 -** -** Sort all elements on the sorter. The algorithm is a -** mergesort. The P3 argument is a pointer to a KeyInfo structure -** that describes the keys to be sorted. -*/ -case OP_Sort: { /* no-push */ - int i; - KeyInfo *pKeyInfo = (KeyInfo*)pOp->p3; - Sorter *pElem; - Sorter *apSorter[NSORT]; - sqlite3_sort_count++; - pKeyInfo->enc = p->db->enc; - for(i=0; ipSort ){ - pElem = p->pSort; - p->pSort = pElem->pNext; - pElem->pNext = 0; - for(i=0; i=NSORT-1 ){ - apSorter[NSORT-1] = Merge(apSorter[NSORT-1],pElem, pKeyInfo); - } - } - pElem = 0; - for(i=0; ipSort = pElem; - break; -} - -/* Opcode: SortNext * P2 * -** -** Push the data for the topmost element in the sorter onto the -** stack, then remove the element from the sorter. If the sorter -** is empty, push nothing on the stack and instead jump immediately -** to instruction P2. -*/ -case OP_SortNext: { - Sorter *pSorter = p->pSort; - CHECK_FOR_INTERRUPT; - if( pSorter!=0 ){ - p->pSort = pSorter->pNext; - pTos++; - pTos->flags = MEM_Null; - rc = sqlite3VdbeMemMove(pTos, &pSorter->data); - sqliteFree(pSorter->zKey); - sqliteFree(pSorter); - }else{ - pc = pOp->p2 - 1; - } - break; -} - -/* Opcode: SortReset * * * -** -** Remove any elements that remain on the sorter. -*/ -case OP_SortReset: { /* no-push */ - sqlite3VdbeSorterReset(p); - break; -} - /* Opcode: MemStore P1 P2 * ** ** Write the top of the stack into memory location P1. ** P1 should be a small integer since space is allocated ** for all memory locations between 0 and P1 inclusive. Index: src/vdbeInt.h ================================================================== --- src/vdbeInt.h +++ src/vdbeInt.h @@ -123,27 +123,10 @@ void (*xDel)(void *); /* If not null, call this function to delete Mem.z */ char zShort[NBFS]; /* Space for short strings */ }; typedef struct Mem Mem; -/* -** A sorter builds a list of elements to be sorted. Each element of -** the list is an instance of the following structure. -*/ -typedef struct Sorter Sorter; -struct Sorter { - int nKey; /* Number of bytes in the key */ - char *zKey; /* The key by which we will sort */ - Mem data; - Sorter *pNext; /* Next in the list */ -}; - -/* -** Number of buckets used for merge-sort. -*/ -#define NSORT 30 - /* One or more of the following flags are set to indicate the validOK ** representations of the value stored in the Mem struct. ** ** If the MEM_Null flag is set, then the value is an SQL NULL value. ** No other flags may be set in this case. @@ -322,12 +305,10 @@ Mem *pTos; /* Top entry in the operand stack */ Mem **apArg; /* Arguments to currently executing user function */ Mem *aColName; /* Column names to return */ int nCursor; /* Number of slots in apCsr[] */ Cursor **apCsr; /* One element of this array for each open cursor */ - Sorter *pSort; /* A linked list of objects to be sorted */ - Sorter *pSortTail; /* Last element on the pSort list */ int nVar; /* Number of entries in aVar[] */ Mem *aVar; /* Values for the OP_Variable opcode. */ char **azVar; /* Name of variables */ int okVar; /* True if azVar[] has been initialized */ int magic; /* Magic number for sanity checking */ @@ -371,11 +352,10 @@ /* ** Function prototypes */ void sqlite3VdbeFreeCursor(Cursor*); -void sqlite3VdbeSorterReset(Vdbe*); int sqlite3VdbeAggReset(sqlite3*, Agg *, KeyInfo *); void sqliteVdbePopStack(Vdbe*,int); int sqlite3VdbeCursorMoveto(Cursor*); #if defined(SQLITE_DEBUG) || defined(VDBE_PROFILE) void sqlite3VdbePrintOp(FILE*, int, Op*); Index: src/vdbeaux.c ================================================================== --- src/vdbeaux.c +++ src/vdbeaux.c @@ -761,25 +761,10 @@ } } #endif } - -/* -** Remove any elements that remain on the sorter for the VDBE given. -*/ -void sqlite3VdbeSorterReset(Vdbe *p){ - while( p->pSort ){ - Sorter *pSorter = p->pSort; - p->pSort = pSorter->pNext; - sqliteFree(pSorter->zKey); - sqlite3VdbeMemRelease(&pSorter->data); - sqliteFree(pSorter); - } - p->pSortTail = 0; -} - /* ** Free all resources allociated with AggElem pElem, an element of ** aggregate pAgg. */ static void freeAggElem(AggElem *pElem, Agg *pAgg){ @@ -963,11 +948,10 @@ for(i=0; icontextStackTop; i++){ sqlite3VdbeFifoClear(&p->contextStack[i].sFifo); } sqliteFree(p->contextStack); } - sqlite3VdbeSorterReset(p); for(i=0; inAgg; i++){ sqlite3VdbeAggReset(0, &p->apAgg[i], 0); } p->contextStack = 0; p->contextStackDepth = 0; Index: test/conflict.test ================================================================== --- test/conflict.test +++ test/conflict.test @@ -11,11 +11,11 @@ # This file implements regression tests for SQLite library. # # This file implements tests for the conflict resolution extension # to SQLite. # -# $Id: conflict.test,v 1.24 2005/06/07 02:12:30 drh Exp $ +# $Id: conflict.test,v 1.25 2005/09/01 03:07:45 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Create tables for the first group of tests. @@ -279,22 +279,22 @@ # t2 Content of "x" column of t3 # t3 Number of temporary files created # foreach {i conf1 cmd t0 t1 t2 t3} { 1 {} UPDATE 1 {6 7 8 9} 1 1 - 2 REPLACE UPDATE 0 {7 6 9} 1 0 - 3 IGNORE UPDATE 0 {6 7 3 9} 1 0 + 2 REPLACE UPDATE 0 {7 6 9} 1 1 + 3 IGNORE UPDATE 0 {6 7 3 9} 1 1 4 FAIL UPDATE 1 {6 7 3 4} 1 0 5 ABORT UPDATE 1 {1 2 3 4} 1 1 6 ROLLBACK UPDATE 1 {1 2 3 4} 0 0 - 7 REPLACE {UPDATE OR IGNORE} 0 {6 7 3 9} 1 0 - 8 IGNORE {UPDATE OR REPLACE} 0 {7 6 9} 1 0 - 9 FAIL {UPDATE OR IGNORE} 0 {6 7 3 9} 1 0 - 10 ABORT {UPDATE OR REPLACE} 0 {7 6 9} 1 0 - 11 ROLLBACK {UPDATE OR IGNORE} 0 {6 7 3 9} 1 0 - 12 {} {UPDATE OR IGNORE} 0 {6 7 3 9} 1 0 - 13 {} {UPDATE OR REPLACE} 0 {7 6 9} 1 0 + 7 REPLACE {UPDATE OR IGNORE} 0 {6 7 3 9} 1 1 + 8 IGNORE {UPDATE OR REPLACE} 0 {7 6 9} 1 1 + 9 FAIL {UPDATE OR IGNORE} 0 {6 7 3 9} 1 1 + 10 ABORT {UPDATE OR REPLACE} 0 {7 6 9} 1 1 + 11 ROLLBACK {UPDATE OR IGNORE} 0 {6 7 3 9} 1 1 + 12 {} {UPDATE OR IGNORE} 0 {6 7 3 9} 1 1 + 13 {} {UPDATE OR REPLACE} 0 {7 6 9} 1 1 14 {} {UPDATE OR FAIL} 1 {6 7 3 4} 1 0 15 {} {UPDATE OR ABORT} 1 {1 2 3 4} 1 1 16 {} {UPDATE OR ROLLBACK} 1 {1 2 3 4} 0 0 } { if {$t0} {set t1 {column a is not unique}}