Index: src/btree.c ================================================================== --- src/btree.c +++ src/btree.c @@ -1525,11 +1525,11 @@ /* ** Set up a raw page so that it looks like a database page holding ** no entries. */ -static void zeroPage(MemPage *pPage, int flags){ +static void zeroPage(MemPage *pPage, u8 flags){ unsigned char *data = pPage->aData; BtShared *pBt = pPage->pBt; u8 hdr = pPage->hdrOffset; u16 first; @@ -2583,10 +2583,11 @@ */ static int newDatabase(BtShared *pBt){ MemPage *pP1; unsigned char *data; int rc; + u8 flags; assert( sqlite3_mutex_held(pBt->mutex) ); if( pBt->nPage>0 ){ return SQLITE_OK; } @@ -2605,11 +2606,13 @@ data[20] = (u8)(pBt->pageSize - pBt->usableSize); data[21] = 64; data[22] = 32; data[23] = 32; memset(&data[24], 0, 100-24); - zeroPage(pP1, PTF_INTKEY|PTF_LEAF|PTF_LEAFDATA ); + flags = (pBt->openFlags&BTREE_SINGLE_INDEX) ? PTF_ZERODATA|PTF_LEAF + : PTF_INTKEY|PTF_LEAFDATA|PTF_LEAF; + zeroPage(pP1, flags); pBt->btsFlags |= BTS_PAGESIZE_FIXED; #ifndef SQLITE_OMIT_AUTOVACUUM assert( pBt->autoVacuum==1 || pBt->autoVacuum==0 ); assert( pBt->incrVacuum==1 || pBt->incrVacuum==0 ); put4byte(&data[36 + 4*4], pBt->autoVacuum); @@ -6107,11 +6110,11 @@ int nxDiv; /* Next divider slot in pParent->aCell[] */ int rc = SQLITE_OK; /* The return code */ u16 leafCorrection; /* 4 if pPage is a leaf. 0 if not */ int leafData; /* True if pPage is a leaf of a LEAFDATA tree */ int usableSpace; /* Bytes in pPage beyond the header */ - int pageFlags; /* Value of pPage->aData[0] */ + u8 pageFlags; /* Value of pPage->aData[0] */ int subtotal; /* Subtotal of bytes in cells on one page */ int iSpace1 = 0; /* First unused byte of aSpace1[] */ int iOvflSpace = 0; /* First unused byte of aOvflSpace[] */ int szScratch; /* Size of scratch memory requested */ MemPage *apOld[NB]; /* pPage and up to two siblings */ @@ -7208,11 +7211,11 @@ static int btreeCreateTable(Btree *p, int *piTable, int createTabFlags){ BtShared *pBt = p->pBt; MemPage *pRoot; Pgno pgnoRoot; int rc; - int ptfFlags; /* Page-type flage for the root page of new table */ + u8 ptfFlags; /* Page-type flage for the root page of new table */ assert( sqlite3BtreeHoldsMutex(p) ); assert( pBt->inTransaction==TRANS_WRITE ); assert( (pBt->btsFlags & BTS_READ_ONLY)==0 ); Index: src/btree.h ================================================================== --- src/btree.h +++ src/btree.h @@ -54,14 +54,15 @@ ** following values. ** ** NOTE: These values must match the corresponding PAGER_ values in ** pager.h. */ -#define BTREE_OMIT_JOURNAL 1 /* Do not create or use a rollback journal */ -#define BTREE_MEMORY 2 /* This is an in-memory DB */ -#define BTREE_SINGLE 4 /* The file contains at most 1 b-tree */ -#define BTREE_UNORDERED 8 /* Use of a hash implementation is OK */ +#define BTREE_OMIT_JOURNAL 0x01 /* Do not create or use a rollback journal */ +#define BTREE_MEMORY 0x02 /* This is an in-memory DB */ +#define BTREE_SINGLE 0x04 /* The file contains at most 1 b-tree */ +#define BTREE_UNORDERED 0x08 /* Use of a hash implementation is OK */ +#define BTREE_SINGLE_INDEX 0x10 /* File contains one index btree */ int sqlite3BtreeClose(Btree*); int sqlite3BtreeSetCacheSize(Btree*,int); int sqlite3BtreeSetMmapLimit(Btree*,sqlite3_int64); int sqlite3BtreeSetPagerFlags(Btree*,unsigned); Index: src/delete.c ================================================================== --- src/delete.c +++ src/delete.c @@ -381,11 +381,13 @@ nPk = 1; iRowSet = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Null, 0, iRowSet); }else{ /* For a WITHOUT ROWID table, create an ephermeral table used to - ** hold all primary keys for rows to be deleted. */ + ** hold all primary keys for rows to be deleted. Use OP_OpenEphemeral + ** rather than OP_OpenHash since for efficiency reasons it is good to + ** process the primary keys in order. */ pPk = sqlite3PrimaryKeyIndex(pTab); assert( pPk!=0 ); nPk = pPk->nKeyCol; iPk = pParse->nMem+1; pParse->nMem += nPk; Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -1488,10 +1488,181 @@ int sqlite3CodeOnce(Parse *pParse){ Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */ return sqlite3VdbeAddOp1(v, OP_Once, pParse->nOnce++); } +/* +** Generate code that constructs a transient table for the RHS of an IN +** operator: +** +** x IN (4,5,11) -- IN operator with list on right-hand side +** x IN (SELECT a FROM b) -- IN operator with subquery on the right +** +** The pExpr parameter is the IN expression. +** +** If parameter isRowid is non-zero, then expression pExpr is guaranteed +** to be of the form " IN (?, ?, ?)", where is a reference +** to some integer key column of a table B-Tree. In this case, use an +** intkey B-Tree to store the set of IN(...) values instead of the usual +** (slower) variable length keys B-Tree. +*/ +#ifndef SQLITE_OMIT_SUBQUERY +static void sqlite3CreateInOperatorRhsTable( + Parse *pParse, /* Parsing context */ + Expr *pExpr, /* The IN, SELECT, or EXISTS operator */ + int isRowid, /* If true, LHS of IN operator is a rowid */ + int bOrdered /* If true, must use btree, not a hash */ +){ + int testAddr = -1; /* One-time test address */ + Vdbe *v = sqlite3GetVdbe(pParse); /* prepared stmt under construction */ + char affinity; /* Affinity of the LHS of the IN */ + int addr; /* Address of OP_Open.. instruction */ + Expr *pLeft = pExpr->pLeft; /* the LHS of the IN operator */ + KeyInfo *pKeyInfo = 0; /* Key information */ + + assert( v!=0 ); + assert( pExpr->op==TK_IN ); + sqlite3ExprCachePush(pParse); + + /* This code must be run in its entirety every time it is encountered + ** if any of the following is true: + ** + ** * The right-hand side is a correlated subquery + ** * We are inside a trigger + ** + ** If all of the above are false, then we can run this code just once + ** save the results, and reuse the same result on subsequent invocations. + */ + if( !ExprHasProperty(pExpr, EP_VarSelect) ){ + testAddr = sqlite3CodeOnce(pParse); + } + +#ifndef SQLITE_OMIT_EXPLAIN + if( pParse->explain==2 ){ + char *zMsg = sqlite3MPrintf( + pParse->db, "EXECUTE %sLIST SUBQUERY %d", testAddr>=0?"":"CORRELATED ", + pParse->iNextSelectId + ); + sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC); + } +#endif + + affinity = sqlite3ExprAffinity(pLeft); + + /* Whether this is an 'x IN(SELECT...)' or an 'x IN()' + ** expression it is handled the same way. An ephemeral table is + ** filled with single-field index keys representing the results + ** from the SELECT or the . + ** + ** If the 'x' expression is a column value, or the SELECT... + ** statement returns a column value, then the affinity of that + ** column is used to build the index keys. If both 'x' and the + ** SELECT... statement are columns, then numeric affinity is used + ** if either column has NUMERIC or INTEGER affinity. If neither + ** 'x' nor the SELECT... statement are columns, then numeric affinity + ** is used. + */ + pExpr->iTable = pParse->nTab++; + addr = sqlite3VdbeAddOp2(v, bOrdered ? OP_OpenEphemeral : OP_OpenHash, + pExpr->iTable, !isRowid); + pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, 1, 1); + + if( ExprHasProperty(pExpr, EP_xIsSelect) ){ + /* Case 1: expr IN (SELECT ...) + ** + ** Generate code to write the results of the select into the temporary + ** table allocated and opened above. + */ + SelectDest dest; + ExprList *pEList; + + assert( !isRowid ); + sqlite3SelectDestInit(&dest, SRT_Set, pExpr->iTable); + dest.affSdst = (u8)affinity; + assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable ); + pExpr->x.pSelect->iLimit = 0; + testcase( pKeyInfo==0 ); /* Caused by OOM in sqlite3KeyInfoAlloc() */ + if( sqlite3Select(pParse, pExpr->x.pSelect, &dest) ){ + sqlite3KeyInfoUnref(pKeyInfo); + return; + } + pEList = pExpr->x.pSelect->pEList; + assert( pKeyInfo!=0 ); /* OOM will cause exit after sqlite3Select() */ + assert( pEList!=0 ); + assert( pEList->nExpr>0 ); + assert( sqlite3KeyInfoIsWriteable(pKeyInfo) ); + pKeyInfo->aColl[0] = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, + pEList->a[0].pExpr); + }else if( ALWAYS(pExpr->x.pList!=0) ){ + /* Case 2: expr IN (exprlist) + ** + ** For each expression, build an index key from the evaluation and + ** store it in the temporary table. If is a column, then use + ** that columns affinity when building index keys. If is not + ** a column, use numeric affinity. + */ + int i; + ExprList *pList = pExpr->x.pList; + struct ExprList_item *pItem; + int r1, r2, r3; + + if( !affinity ){ + affinity = SQLITE_AFF_NONE; + } + if( pKeyInfo ){ + assert( sqlite3KeyInfoIsWriteable(pKeyInfo) ); + pKeyInfo->aColl[0] = sqlite3ExprCollSeq(pParse, pExpr->pLeft); + } + + /* Loop through each expression in . */ + r1 = sqlite3GetTempReg(pParse); + r2 = sqlite3GetTempReg(pParse); + sqlite3VdbeAddOp2(v, OP_Null, 0, r2); + for(i=pList->nExpr, pItem=pList->a; i>0; i--, pItem++){ + Expr *pE2 = pItem->pExpr; + int iValToIns; + + /* If the expression is not constant then we will need to + ** disable the test that was generated above that makes sure + ** this code only executes once. Because for a non-constant + ** expression we need to rerun this code each time. + */ + if( testAddr>=0 && !sqlite3ExprIsConstant(pE2) ){ + sqlite3VdbeChangeToNoop(v, testAddr); + testAddr = -1; + } + + /* Evaluate the expression and insert it into the temp table */ + if( isRowid && sqlite3ExprIsInteger(pE2, &iValToIns) ){ + sqlite3VdbeAddOp3(v, OP_InsertInt, pExpr->iTable, r2, iValToIns); + }else{ + r3 = sqlite3ExprCodeTarget(pParse, pE2, r1); + if( isRowid ){ + sqlite3VdbeAddOp2(v, OP_MustBeInt, r3, + sqlite3VdbeCurrentAddr(v)+2); + sqlite3VdbeAddOp3(v, OP_Insert, pExpr->iTable, r2, r3); + }else{ + sqlite3VdbeAddOp4(v, OP_MakeRecord, r3, 1, r2, &affinity, 1); + sqlite3ExprCacheAffinityChange(pParse, r3, 1); + sqlite3VdbeAddOp2(v, OP_IdxInsert, pExpr->iTable, r2); + } + } + } + sqlite3ReleaseTempReg(pParse, r1); + sqlite3ReleaseTempReg(pParse, r2); + } + if( pKeyInfo ){ + sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo, P4_KEYINFO); + } + + if( testAddr>=0 ){ + sqlite3VdbeJumpHere(v, testAddr); + } + sqlite3ExprCachePop(pParse, 1); +} +#endif /* SQLITE_OMIT_SUBQUERY */ + /* ** This function is used by the implementation of the IN (...) operator. ** The pX parameter is the expression on the RHS of the IN operator, which ** might be either a list of expressions or a subquery. ** @@ -1551,32 +1722,36 @@ ** register = 1 ** } ** ** in order to avoid running the ** test more often than is necessary. +** +** IN_INDEX_EPH ephemeral tables must be in key order if the bOrdered flag +** is true. If bOrdered is false, the generated table can be a hash. */ #ifndef SQLITE_OMIT_SUBQUERY -int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound){ +int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound, int bOrdered){ Select *p; /* SELECT to the right of IN operator */ int eType = 0; /* Type of RHS table. IN_INDEX_* */ int iTab = pParse->nTab++; /* Cursor of the RHS table */ int mustBeUnique = (prNotFound==0); /* True if RHS must be unique */ Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */ + assert( v!=0 ); assert( pX->op==TK_IN ); /* Check to see if an existing table or index can be used to ** satisfy the query. This is preferable to generating a new ** ephemeral table. */ p = (ExprHasProperty(pX, EP_xIsSelect) ? pX->x.pSelect : 0); if( ALWAYS(pParse->nErr==0) && isCandidateForInOpt(p) ){ - sqlite3 *db = pParse->db; /* Database connection */ - Table *pTab; /* Table . */ - Expr *pExpr; /* Expression */ - i16 iCol; /* Index of column */ - i16 iDb; /* Database idx for pTab */ + sqlite3 *db = pParse->db; /* Database connection */ + Table *pTab; /* Table
. */ + Expr *pExpr; /* Expression */ + i16 iCol; /* Index of column */ + i16 iDb; /* Database idx for pTab */ assert( p ); /* Because of isCandidateForInOpt(p) */ assert( p->pEList!=0 ); /* Because of isCandidateForInOpt(p) */ assert( p->pEList->a[0].pExpr!=0 ); /* Because of isCandidateForInOpt(p) */ assert( p->pSrc!=0 ); /* Because of isCandidateForInOpt(p) */ @@ -1587,23 +1762,14 @@ /* Code an OP_VerifyCookie and OP_TableLock for
. */ iDb = sqlite3SchemaToIndex(db, pTab->pSchema); sqlite3CodeVerifySchema(pParse, iDb); sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); - /* This function is only called from two places. In both cases the vdbe - ** has already been allocated. So assume sqlite3GetVdbe() is always - ** successful here. - */ - assert(v); if( iCol<0 ){ - int iAddr; - - iAddr = sqlite3CodeOnce(pParse); - + int iAddr = sqlite3CodeOnce(pParse); sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead); eType = IN_INDEX_ROWID; - sqlite3VdbeJumpHere(v, iAddr); }else{ Index *pIdx; /* Iterator variable */ /* The collation sequence used by the comparison. If an index is to @@ -1654,70 +1820,51 @@ pParse->nQueryLoop = 0; if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){ eType = IN_INDEX_ROWID; } } - sqlite3CodeSubselect(pParse, pX, rMayHaveNull, eType==IN_INDEX_ROWID); + sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID,bOrdered); pParse->nQueryLoop = savedNQueryLoop; }else{ pX->iTable = iTab; } return eType; } #endif /* -** Generate code for scalar subqueries used as a subquery expression, EXISTS, -** or IN operators. Examples: +** Generate code for scalar subqueries used as a subquery expression: ** ** (SELECT a FROM b) -- subquery ** EXISTS (SELECT a FROM b) -- EXISTS subquery -** x IN (4,5,11) -- IN operator with list on right-hand side -** x IN (SELECT a FROM b) -- IN operator with subquery on the right -** -** The pExpr parameter describes the expression that contains the IN -** operator or subquery. -** -** If parameter isRowid is non-zero, then expression pExpr is guaranteed -** to be of the form " IN (?, ?, ?)", where is a reference -** to some integer key column of a table B-Tree. In this case, use an -** intkey B-Tree to store the set of IN(...) values instead of the usual -** (slower) variable length keys B-Tree. -** -** If rMayHaveNull is non-zero, that means that the operation is an IN -** (not a SELECT or EXISTS) and that the RHS might contains NULLs. -** Furthermore, the IN is in a WHERE clause and that we really want -** to iterate over the RHS of the IN operator in order to quickly locate -** all corresponding LHS elements. All this routine does is initialize -** the register given by rMayHaveNull to NULL. Calling routines will take -** care of changing this register value to non-NULL if the RHS is NULL-free. -** -** If rMayHaveNull is zero, that means that the subquery is being used -** for membership testing only. There is no need to initialize any -** registers to indicate the presence or absence of NULLs on the RHS. -** -** For a SELECT or EXISTS operator, return the register that holds the -** result. For IN operators or if an error occurs, the return value is 0. +** +** The pExpr parameter describes the expression that contains the subquery. +** +** Return the register that holds the result. */ #ifndef SQLITE_OMIT_SUBQUERY -int sqlite3CodeSubselect( +static int sqlite3CodeScalarSubquery( Parse *pParse, /* Parsing context */ - Expr *pExpr, /* The IN, SELECT, or EXISTS operator */ - int rMayHaveNull, /* Register that records whether NULLs exist in RHS */ - int isRowid /* If true, LHS of IN operator is a rowid */ + Expr *pExpr /* The SELECT or EXISTS operator */ ){ int testAddr = -1; /* One-time test address */ int rReg = 0; /* Register storing resulting */ Vdbe *v = sqlite3GetVdbe(pParse); + Select *pSel; /* SELECT statement to encode */ + SelectDest dest; /* How to deal with SELECt result */ + if( NEVER(v==0) ) return 0; + testcase( pExpr->op==TK_EXISTS ); + testcase( pExpr->op==TK_SELECT ); + assert( pExpr->op==TK_EXISTS || pExpr->op==TK_SELECT ); + assert( ExprHasProperty(pExpr, EP_xIsSelect) ); sqlite3ExprCachePush(pParse); /* This code must be run in its entirety every time it is encountered ** if any of the following is true: ** - ** * The right-hand side is a correlated subquery - ** * The right-hand side is an expression list containing variables + ** * pExpr is a correlated subquery ** * We are inside a trigger ** ** If all of the above are false, then we can run this code just once ** save the results, and reuse the same result on subsequent invocations. */ @@ -1726,177 +1873,37 @@ } #ifndef SQLITE_OMIT_EXPLAIN if( pParse->explain==2 ){ char *zMsg = sqlite3MPrintf( - pParse->db, "EXECUTE %s%s SUBQUERY %d", testAddr>=0?"":"CORRELATED ", - pExpr->op==TK_IN?"LIST":"SCALAR", pParse->iNextSelectId + pParse->db, "EXECUTE %sSCALAR SUBQUERY %d", + testAddr>=0?"":"CORRELATED ", pParse->iNextSelectId ); sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC); } #endif - switch( pExpr->op ){ - case TK_IN: { - char affinity; /* Affinity of the LHS of the IN */ - int addr; /* Address of OP_OpenEphemeral instruction */ - Expr *pLeft = pExpr->pLeft; /* the LHS of the IN operator */ - KeyInfo *pKeyInfo = 0; /* Key information */ - - if( rMayHaveNull ){ - sqlite3VdbeAddOp2(v, OP_Null, 0, rMayHaveNull); - } - - affinity = sqlite3ExprAffinity(pLeft); - - /* Whether this is an 'x IN(SELECT...)' or an 'x IN()' - ** expression it is handled the same way. An ephemeral table is - ** filled with single-field index keys representing the results - ** from the SELECT or the . - ** - ** If the 'x' expression is a column value, or the SELECT... - ** statement returns a column value, then the affinity of that - ** column is used to build the index keys. If both 'x' and the - ** SELECT... statement are columns, then numeric affinity is used - ** if either column has NUMERIC or INTEGER affinity. If neither - ** 'x' nor the SELECT... statement are columns, then numeric affinity - ** is used. - */ - pExpr->iTable = pParse->nTab++; - addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid); - pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, 1, 1); - - if( ExprHasProperty(pExpr, EP_xIsSelect) ){ - /* Case 1: expr IN (SELECT ...) - ** - ** Generate code to write the results of the select into the temporary - ** table allocated and opened above. - */ - SelectDest dest; - ExprList *pEList; - - assert( !isRowid ); - sqlite3SelectDestInit(&dest, SRT_Set, pExpr->iTable); - dest.affSdst = (u8)affinity; - assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable ); - pExpr->x.pSelect->iLimit = 0; - testcase( pKeyInfo==0 ); /* Caused by OOM in sqlite3KeyInfoAlloc() */ - if( sqlite3Select(pParse, pExpr->x.pSelect, &dest) ){ - sqlite3KeyInfoUnref(pKeyInfo); - return 0; - } - pEList = pExpr->x.pSelect->pEList; - assert( pKeyInfo!=0 ); /* OOM will cause exit after sqlite3Select() */ - assert( pEList!=0 ); - assert( pEList->nExpr>0 ); - assert( sqlite3KeyInfoIsWriteable(pKeyInfo) ); - pKeyInfo->aColl[0] = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, - pEList->a[0].pExpr); - }else if( ALWAYS(pExpr->x.pList!=0) ){ - /* Case 2: expr IN (exprlist) - ** - ** For each expression, build an index key from the evaluation and - ** store it in the temporary table. If is a column, then use - ** that columns affinity when building index keys. If is not - ** a column, use numeric affinity. - */ - int i; - ExprList *pList = pExpr->x.pList; - struct ExprList_item *pItem; - int r1, r2, r3; - - if( !affinity ){ - affinity = SQLITE_AFF_NONE; - } - if( pKeyInfo ){ - assert( sqlite3KeyInfoIsWriteable(pKeyInfo) ); - pKeyInfo->aColl[0] = sqlite3ExprCollSeq(pParse, pExpr->pLeft); - } - - /* Loop through each expression in . */ - r1 = sqlite3GetTempReg(pParse); - r2 = sqlite3GetTempReg(pParse); - sqlite3VdbeAddOp2(v, OP_Null, 0, r2); - for(i=pList->nExpr, pItem=pList->a; i>0; i--, pItem++){ - Expr *pE2 = pItem->pExpr; - int iValToIns; - - /* If the expression is not constant then we will need to - ** disable the test that was generated above that makes sure - ** this code only executes once. Because for a non-constant - ** expression we need to rerun this code each time. - */ - if( testAddr>=0 && !sqlite3ExprIsConstant(pE2) ){ - sqlite3VdbeChangeToNoop(v, testAddr); - testAddr = -1; - } - - /* Evaluate the expression and insert it into the temp table */ - if( isRowid && sqlite3ExprIsInteger(pE2, &iValToIns) ){ - sqlite3VdbeAddOp3(v, OP_InsertInt, pExpr->iTable, r2, iValToIns); - }else{ - r3 = sqlite3ExprCodeTarget(pParse, pE2, r1); - if( isRowid ){ - sqlite3VdbeAddOp2(v, OP_MustBeInt, r3, - sqlite3VdbeCurrentAddr(v)+2); - sqlite3VdbeAddOp3(v, OP_Insert, pExpr->iTable, r2, r3); - }else{ - sqlite3VdbeAddOp4(v, OP_MakeRecord, r3, 1, r2, &affinity, 1); - sqlite3ExprCacheAffinityChange(pParse, r3, 1); - sqlite3VdbeAddOp2(v, OP_IdxInsert, pExpr->iTable, r2); - } - } - } - sqlite3ReleaseTempReg(pParse, r1); - sqlite3ReleaseTempReg(pParse, r2); - } - if( pKeyInfo ){ - sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo, P4_KEYINFO); - } - break; - } - - case TK_EXISTS: - case TK_SELECT: - default: { - /* If this has to be a scalar SELECT. Generate code to put the - ** value of this select in a memory cell and record the number - ** of the memory cell in iColumn. If this is an EXISTS, write - ** an integer 0 (not exists) or 1 (exists) into a memory cell - ** and record that memory cell in iColumn. - */ - Select *pSel; /* SELECT statement to encode */ - SelectDest dest; /* How to deal with SELECt result */ - - testcase( pExpr->op==TK_EXISTS ); - testcase( pExpr->op==TK_SELECT ); - assert( pExpr->op==TK_EXISTS || pExpr->op==TK_SELECT ); - - assert( ExprHasProperty(pExpr, EP_xIsSelect) ); - pSel = pExpr->x.pSelect; - sqlite3SelectDestInit(&dest, 0, ++pParse->nMem); - if( pExpr->op==TK_SELECT ){ - dest.eDest = SRT_Mem; - sqlite3VdbeAddOp2(v, OP_Null, 0, dest.iSDParm); - VdbeComment((v, "Init subquery result")); - }else{ - dest.eDest = SRT_Exists; - sqlite3VdbeAddOp2(v, OP_Integer, 0, dest.iSDParm); - VdbeComment((v, "Init EXISTS result")); - } - sqlite3ExprDelete(pParse->db, pSel->pLimit); - pSel->pLimit = sqlite3PExpr(pParse, TK_INTEGER, 0, 0, - &sqlite3IntTokens[1]); - pSel->iLimit = 0; - if( sqlite3Select(pParse, pSel, &dest) ){ - return 0; - } - rReg = dest.iSDParm; - ExprSetVVAProperty(pExpr, EP_NoReduce); - break; - } - } + pSel = pExpr->x.pSelect; + sqlite3SelectDestInit(&dest, 0, ++pParse->nMem); + if( pExpr->op==TK_SELECT ){ + dest.eDest = SRT_Mem; + sqlite3VdbeAddOp2(v, OP_Null, 0, dest.iSDParm); + VdbeComment((v, "Init subquery result")); + }else{ + dest.eDest = SRT_Exists; + sqlite3VdbeAddOp2(v, OP_Integer, 0, dest.iSDParm); + VdbeComment((v, "Init EXISTS result")); + } + sqlite3ExprDelete(pParse->db, pSel->pLimit); + pSel->pLimit = sqlite3PExpr(pParse, TK_INTEGER, 0, 0, + &sqlite3IntTokens[1]); + pSel->iLimit = 0; + if( sqlite3Select(pParse, pSel, &dest) ){ + return 0; + } + rReg = dest.iSDParm; + ExprSetVVAProperty(pExpr, EP_NoReduce); if( testAddr>=0 ){ sqlite3VdbeJumpHere(v, testAddr); } sqlite3ExprCachePop(pParse, 1); @@ -1939,11 +1946,11 @@ ** pExpr->iTable will contains the values that make up the RHS. */ v = pParse->pVdbe; assert( v!=0 ); /* OOM detected prior to this routine */ VdbeNoopComment((v, "begin IN expr")); - eType = sqlite3FindInIndex(pParse, pExpr, &rRhsHasNull); + eType = sqlite3FindInIndex(pParse, pExpr, &rRhsHasNull, 0); /* Figure out the affinity to use to create a key from the results ** of the expression. affinityStr stores a static string suitable for ** P4 of OP_MakeRecord. */ @@ -2811,11 +2818,11 @@ #ifndef SQLITE_OMIT_SUBQUERY case TK_EXISTS: case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); - inReg = sqlite3CodeSubselect(pParse, pExpr, 0, 0); + inReg = sqlite3CodeScalarSubquery(pParse, pExpr); break; } case TK_IN: { int destIfFalse = sqlite3VdbeMakeLabel(v); int destIfNull = sqlite3VdbeMakeLabel(v); Index: src/insert.c ================================================================== --- src/insert.c +++ src/insert.c @@ -717,10 +717,13 @@ ** L: yield X ** if EOF goto M ** insert row from R..R+n into temp table ** goto L ** M: ... + ** + ** Use OP_OpenEphemeral, not OP_OpenHash, so that srcTab behaves as + ** a FIFO. */ int regRec; /* Register to hold packed record */ int regTempRowid; /* Register to hold temp table ROWID */ int addrTop; /* Label "L" */ int addrIf; /* Address of jump to M */ Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -533,12 +533,12 @@ */ typedef struct DistinctCtx DistinctCtx; struct DistinctCtx { u8 isTnct; /* True if the DISTINCT keyword is present */ u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */ - int tabTnct; /* Ephemeral table used for DISTINCT processing */ - int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */ + int tabTnct; /* Table containing previously seen values */ + int addrTnct; /* Address of OpenEphemeral/OpenHash opcode for tabTnct */ }; /* ** This routine generates the code for the inside of the inner loop ** of a SELECT. @@ -1869,11 +1869,11 @@ }else{ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iQueue, nCol); } VdbeComment((v, "Queue table")); if( iDistinct ){ - p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iDistinct, 0); + p->addrOpenEphm[0] = sqlite3VdbeAddOp2(v, OP_OpenHash, iDistinct, 0); p->selFlags |= SF_UsesEphemeral; } /* Detach the ORDER BY clause from the compound SELECT */ p->pOrderBy = 0; @@ -2005,12 +2005,11 @@ /* Create the destination temporary table if necessary */ if( dest.eDest==SRT_EphemTab ){ assert( p->pEList ); - sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr); - sqlite3VdbeChangeP5(v, BTREE_UNORDERED); + sqlite3VdbeAddOp2(v, OP_OpenHash, dest.iSDParm, p->pEList->nExpr); dest.eDest = SRT_Table; } /* Make sure all SELECTs in the statement have the same number of elements ** in their result sets. @@ -2106,11 +2105,11 @@ /* We will need to create our own temporary table to hold the ** intermediate results. */ unionTab = pParse->nTab++; assert( p->pOrderBy==0 ); - addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, unionTab, 0); + addr = sqlite3VdbeAddOp2(v, OP_OpenHash, unionTab, 0); assert( p->addrOpenEphm[0] == -1 ); p->addrOpenEphm[0] = addr; p->pRightmost->selFlags |= SF_UsesEphemeral; assert( p->pEList ); } @@ -2189,11 +2188,12 @@ SelectDest intersectdest; int r1; /* INTERSECT is different from the others since it requires ** two temporary tables. Hence it has its own case. Begin - ** by allocating the tables we will need. + ** by allocating the tables we will need. The tables must be + ** ordered: Use OP_OpenEphermeral, not OP_OpenHash. */ tab1 = pParse->nTab++; tab2 = pParse->nTab++; assert( p->pOrderBy==0 ); @@ -4300,11 +4300,11 @@ sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one " "argument"); pFunc->iDistinct = -1; }else{ KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0); - sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0, + sqlite3VdbeAddOp4(v, OP_OpenHash, pFunc->iDistinct, 0, 0, (char*)pKeyInfo, P4_KEYINFO); } } } } @@ -4719,10 +4719,12 @@ }else{ addrSortIndex = -1; } /* If the output is destined for a temporary table, open that table. + ** Use OP_OpenEphemeral rather than OP_OpenHash to keep the rows in + ** their original order. */ if( pDest->eDest==SRT_EphemTab ){ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr); } @@ -4738,15 +4740,14 @@ /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ sDistinct.tabTnct = pParse->nTab++; - sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, + sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenHash, sDistinct.tabTnct, 0, 0, (char*)keyInfoFromExprList(pParse, p->pEList, 0), P4_KEYINFO); - sqlite3VdbeChangeP5(v, BTREE_UNORDERED); sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED; }else{ sDistinct.eTnctType = WHERE_DISTINCT_NOOP; } Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -3281,11 +3281,10 @@ void sqlite3AlterFunctions(void); void sqlite3AlterRenameTable(Parse*, SrcList*, Token*); int sqlite3GetToken(const unsigned char *, int *); void sqlite3NestedParse(Parse*, const char*, ...); void sqlite3ExpirePreparedStatements(sqlite3*); -int sqlite3CodeSubselect(Parse *, Expr *, int, int); void sqlite3SelectPrep(Parse*, Select*, NameContext*); int sqlite3MatchSpanName(const char*, const char*, const char*, const char*); int sqlite3ResolveExprNames(NameContext*, Expr*); void sqlite3ResolveSelectNames(Parse*, Select*, NameContext*); void sqlite3ResolveSelfReference(Parse*,Table*,int,Expr*,ExprList*); @@ -3477,11 +3476,11 @@ #define IN_INDEX_ROWID 1 #define IN_INDEX_EPH 2 #define IN_INDEX_INDEX_ASC 3 #define IN_INDEX_INDEX_DESC 4 -int sqlite3FindInIndex(Parse *, Expr *, int*); +int sqlite3FindInIndex(Parse *, Expr *, int*, int); #ifdef SQLITE_ENABLE_ATOMIC_WRITE int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); int sqlite3JournalCreate(sqlite3_file *); Index: src/update.c ================================================================== --- src/update.c +++ src/update.c @@ -733,12 +733,11 @@ /* Create the ephemeral table into which the update results will ** be stored. */ assert( v ); ephemTab = pParse->nTab++; - sqlite3VdbeAddOp2(v, OP_OpenEphemeral, ephemTab, pTab->nCol+1+(pRowid!=0)); - sqlite3VdbeChangeP5(v, BTREE_UNORDERED); + sqlite3VdbeAddOp2(v, OP_OpenHash, ephemTab, pTab->nCol+1+(pRowid!=0)); /* fill the ephemeral table */ sqlite3SelectDestInit(&dest, SRT_Table, ephemTab); sqlite3Select(pParse, pSelect, &dest); Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -3293,11 +3293,11 @@ ** since moved into the btree layer. */ pCur->isTable = pOp->p4type!=P4_KEYINFO; break; } -/* Opcode: OpenEphemeral P1 P2 * P4 P5 +/* Opcode: OpenEphemeral P1 P2 * P4 * ** Synopsis: nColumn=P2 ** ** Open a new cursor P1 to a transient table. ** The cursor is always opened read/write even if ** the main database is read-only. The ephemeral @@ -3305,15 +3305,22 @@ ** ** P2 is the number of columns in the ephemeral table. ** The cursor points to a BTree table if P4==0 and to a BTree index ** if P4 is not 0. If P4 is not NULL, it points to a KeyInfo structure ** that defines the format of keys in the index. +*/ +/* Opcode: OpenHash P1 P2 * P4 * +** Synopsis: nColumn=P2 ** -** The P5 parameter can be a mask of the BTREE_* flags defined -** in btree.h. These flags control aspects of the operation of -** the btree. The BTREE_OMIT_JOURNAL and BTREE_SINGLE flags are -** added automatically. +** Open a new cursor P1 to a transient table. +** P2 is the number of columns in the ephemeral table. +** The cursor points to a BTree table if P4==0 and to a BTree index +** if P4 is a KeyInfo structure. +** +** This opcode is identical to OP_OpenEphemeral except that it +** adds the BTREE_UNORDERED parameter to the sqlite3BtreeOpen() call, +** thus causing the underlying table to unordered. */ /* Opcode: OpenAutoindex P1 P2 * P4 * ** Synopsis: nColumn=P2 ** ** This opcode works the same as OP_OpenEphemeral. It has a @@ -3320,54 +3327,52 @@ ** different name to distinguish its use. Tables created using ** by this opcode will be used for automatically created transient ** indices in joins. */ case OP_OpenAutoindex: +case OP_OpenHash: case OP_OpenEphemeral: { VdbeCursor *pCx; - KeyInfo *pKeyInfo; + int btreeFlags; static const int vfsFlags = SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE | SQLITE_OPEN_TRANSIENT_DB; assert( pOp->p1>=0 ); assert( pOp->p2>=0 ); + assert( pOp->p5==0 ); pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); if( pCx==0 ) goto no_mem; pCx->nullRow = 1; - rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, - BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags); + btreeFlags = BTREE_OMIT_JOURNAL | BTREE_SINGLE; + if( pOp->opcode==OP_OpenHash ){ + btreeFlags |= BTREE_UNORDERED; + pCx->isOrdered = 0; + }else{ + pCx->isOrdered = 1; + } + if( pOp->p4.pKeyInfo ){ + assert( pOp->p4type==P4_KEYINFO ); + assert( pOp->p4.pKeyInfo->db==db ); + assert( pOp->p4.pKeyInfo->enc==ENC(db) ); + btreeFlags |= BTREE_SINGLE_INDEX; + pCx->isTable = 0; + }else{ + pCx->isTable = 1; + } + rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, btreeFlags, vfsFlags); if( rc==SQLITE_OK ){ rc = sqlite3BtreeBeginTrans(pCx->pBt, 1); } if( rc==SQLITE_OK ){ - /* If a transient index is required, create it by calling - ** sqlite3BtreeCreateTable() with the BTREE_BLOBKEY flag before - ** opening it. If a transient table is required, just use the - ** automatically created table with root-page 1 (an BLOB_INTKEY table). - */ - if( (pKeyInfo = pOp->p4.pKeyInfo)!=0 ){ - int pgno; - assert( pOp->p4type==P4_KEYINFO ); - rc = sqlite3BtreeCreateTable(pCx->pBt, &pgno, BTREE_BLOBKEY | pOp->p5); - if( rc==SQLITE_OK ){ - assert( pgno==MASTER_ROOT+1 ); - assert( pKeyInfo->db==db ); - assert( pKeyInfo->enc==ENC(db) ); - pCx->pKeyInfo = pKeyInfo; - rc = sqlite3BtreeCursor(pCx->pBt, pgno, 1, pKeyInfo, pCx->pCursor); - } - pCx->isTable = 0; - }else{ - rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor); - pCx->isTable = 1; - } - } - pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED); + rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, pOp->p4.pKeyInfo, + pCx->pCursor); + } + pCx->pKeyInfo = pOp->p4.pKeyInfo; break; } /* Opcode: SorterOpen P1 * * P4 * ** Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -2346,20 +2346,21 @@ ** For a constraint of the form X=expr, the expression is evaluated and its ** result is left on the stack. For constraints of the form X IN (...) ** this routine sets up a loop that will iterate over all values of X. */ static int codeEqualityTerm( - Parse *pParse, /* The parsing context */ + WhereInfo *pWInfo, /* WHERE clause */ WhereTerm *pTerm, /* The term of the WHERE clause to be coded */ WhereLevel *pLevel, /* The level of the FROM clause we are working on */ int iEq, /* Index of the equality term within this level */ int bRev, /* True for reverse-order IN operations */ int iTarget /* Attempt to leave results in this register */ ){ - Expr *pX = pTerm->pExpr; - Vdbe *v = pParse->pVdbe; - int iReg; /* Register holding results */ + Expr *pX = pTerm->pExpr; /* Expression to be coded */ + Parse *pParse = pWInfo->pParse; /* Parsing context */ + Vdbe *v = pParse->pVdbe; /* Prepared stmt under construction */ + int iReg; /* Register holding results */ assert( iTarget>0 ); if( pX->op==TK_EQ ){ iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget); }else if( pX->op==TK_ISNULL ){ @@ -2380,11 +2381,11 @@ testcase( bRev ); bRev = !bRev; } assert( pX->op==TK_IN ); iReg = iTarget; - eType = sqlite3FindInIndex(pParse, pX, 0); + eType = sqlite3FindInIndex(pParse, pX, 0, pWInfo->bOBSat); if( eType==IN_INDEX_INDEX_DESC ){ testcase( bRev ); bRev = !bRev; } iTab = pX->iTable; @@ -2462,18 +2463,19 @@ ** no conversion should be attempted before using a t2.b value as part of ** a key to search the index. Hence the first byte in the returned affinity ** string in this example would be set to SQLITE_AFF_NONE. */ static int codeAllEqualityTerms( - Parse *pParse, /* Parsing context */ + WhereInfo *pWInfo, /* WHERE clause */ WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */ int bRev, /* Reverse the order of IN operators */ int nExtraReg, /* Number of extra registers to allocate */ char **pzAff /* OUT: Set to point to affinity string */ ){ u16 nEq; /* The number of == or IN constraints to code */ u16 nSkip; /* Number of left-most columns to skip */ + Parse *pParse = pWInfo->pParse; /* Parsing context */ Vdbe *v = pParse->pVdbe; /* The vm under construction */ Index *pIdx; /* The index being used for this loop */ WhereTerm *pTerm; /* A single constraint term */ WhereLoop *pLoop; /* The WhereLoop object */ int j; /* Loop counter */ @@ -2524,11 +2526,11 @@ assert( pTerm!=0 ); /* The following testcase is true for indices with redundant columns. ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */ testcase( (pTerm->wtFlags & TERM_CODED)!=0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); - r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j); + r1 = codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, regBase+j); if( r1!=regBase+j ){ if( nReg==1 ){ sqlite3ReleaseTempReg(pParse, regBase); regBase = r1; }else{ @@ -2807,11 +2809,11 @@ for(j=0; jaLTerm[j]; if( pTerm==0 ) continue; if( pTerm->eOperator & WO_IN ){ - codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget); + codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, iTarget); addrNotFound = pLevel->addrNxt; }else{ sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget); } } @@ -2847,11 +2849,11 @@ pTerm = pLoop->aLTerm[0]; assert( pTerm!=0 ); assert( pTerm->pExpr!=0 ); assert( omitTable==0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); - iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg); + iRowidReg = codeEqualityTerm(pWInfo, pTerm, pLevel, 0, bRev, iReleaseReg); addrNxt = pLevel->addrNxt; sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg); sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1); sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); @@ -3037,11 +3039,11 @@ /* Generate code to evaluate all constraint terms using == or IN ** and store the values of those terms in an array of registers ** starting at regBase. */ - regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff); + regBase = codeAllEqualityTerms(pWInfo,pLevel,bRev,nExtraReg,&zStartAff); assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq ); if( zStartAff ) cEndAff = zStartAff[nEq]; addrNxt = pLevel->addrNxt; /* If we are doing a reverse order scan on an ascending index, or Index: test/distinct.test ================================================================== --- test/distinct.test +++ test/distinct.test @@ -49,16 +49,13 @@ proc do_temptables_test {tn sql temptables} { uplevel [list do_test $tn [subst -novar { set ret "" db eval "EXPLAIN [set sql]" { if {$opcode == "OpenEphemeral" || $opcode == "SorterOpen"} { - if {$p5 != "08" && $p5!="00"} { error "p5 = $p5" } - if {$p5 == "08"} { - lappend ret hash - } else { - lappend ret btree - } + lappend ret btree + } elseif {$opcode == "OpenHash"} { + lappend ret hash } } set ret }] $temptables] } Index: test/in3.test ================================================================== --- test/in3.test +++ test/in3.test @@ -27,11 +27,11 @@ # implementation of the sql statement passed as a an argument. # proc nEphemeral {sql} { set nEph 0 foreach op [execsql "EXPLAIN $sql"] { - if {$op eq "OpenEphemeral"} {incr nEph} + if {$op eq "OpenEphemeral" || $op eq "OpenHash"} {incr nEph} } set nEph } # This proc works the same way as execsql, except that the number Index: test/in5.test ================================================================== --- test/in5.test +++ test/in5.test @@ -63,21 +63,21 @@ execsql { SELECT d FROM t2 WHERE a IN t3x AND b IN t3y AND c IN t3z ORDER BY d; } } {12a 56e} do_test in5-2.5.1 { - regexp {OpenEphemeral} [db eval { + regexp {Open(Ephemeral|Hash)} [db eval { EXPLAIN SELECT d FROM t2 WHERE a IN t3x AND b IN t1y AND c IN t1z }] } {1} do_test in5-2.5.2 { - regexp {OpenEphemeral} [db eval { + regexp {Open(Ephemeral|Hash)} [db eval { EXPLAIN SELECT d FROM t2 WHERE a IN t1x AND b IN t3y AND c IN t1z }] } {1} do_test in5-2.5.3 { - regexp {OpenEphemeral} [db eval { + regexp {Open(Ephemeral|Hash)} [db eval { EXPLAIN SELECT d FROM t2 WHERE a IN t1x AND b IN t1y AND c IN t3z }] } {1} do_test in5-3.1 {