Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Optimisations for expressions of the form "<value> IN (SELECT <column> FROM |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
56d0e32677744df8570b519fae1c04da |
User & Date: | danielk1977 2007-11-29 17:05:18.000 |
Context
2007-11-29
| ||
17:43 | When using an index to scan a database table, read column data from the index in preference to the table. This increases the likelihood that the table will not be required at all. (CVS 4580) (check-in: 061608c72a user: danielk1977 tags: trunk) | |
17:05 |
Optimisations for expressions of the form "<value> IN (SELECT <column> FROM | |
2007-11-28
| ||
22:36 | Add the {quote: StrAccum} object for accumulating strings. Revamp xprintf to use the new object. Rewrite the group_concat() function to use the new object. Productize and test the group_concat() function. (CVS 4578) (check-in: 221aee72be user: drh tags: trunk) | |
Changes
Changes to src/expr.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 routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions 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 routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions in SQLite. ** ** $Id: expr.c,v 1.317 2007/11/29 17:05:18 danielk1977 Exp $ */ #include "sqliteInt.h" #include <ctype.h> /* ** Return the 'affinity' of the expression pExpr if any. ** |
︙ | ︙ | |||
1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 | */ typedef struct QueryCoder QueryCoder; struct QueryCoder { Parse *pParse; /* The parsing context */ NameContext *pNC; /* Namespace of first enclosing query */ }; /* ** Generate code for scalar subqueries used as an expression ** and IN operators. Examples: ** ** (SELECT a FROM b) -- subquery ** EXISTS (SELECT a FROM b) -- EXISTS subquery | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 | */ typedef struct QueryCoder QueryCoder; struct QueryCoder { Parse *pParse; /* The parsing context */ NameContext *pNC; /* Namespace of first enclosing query */ }; #ifdef SQLITE_TEST int sqlite3_enable_in_opt = 1; #else #define sqlite3_enable_in_opt 1 #endif /* ** This function is used by the implementation of the IN (...) operator. ** It's job is to find or create a b-tree structure that may be used ** either to test for membership of the (...) set or to iterate through ** it's members, skipping duplicates. ** ** The cursor opened on the structure (database table, database index ** or ephermal table) is stored in pX->iTable before this function returns. ** The returned value indicates the structure type, as follows: ** ** IN_INDEX_ROWID - The cursor was opened on a database table. ** IN_INDEX_INDEX - The cursor was opened on a database indec. ** IN_INDEX_EPH - The cursor was opened on a specially created and ** populated epheremal table. ** ** An existing structure may only be used if the SELECT is of the simple ** form: ** ** SELECT <column> FROM <table> ** ** If the mustBeUnique parameter is false, the structure will be used ** for fast set membership tests. In this case an epheremal table must ** be used unless <column> is an INTEGER PRIMARY KEY or an index can ** be found with <column> as it's left-most column. ** ** If mustBeUnique is true, then the structure will be used to iterate ** through the set members, skipping any duplicates. In this case an ** epheremal table must be used unless the selected <column> is guaranteed ** to be unique - either because it is an INTEGER PRIMARY KEY or it ** is unique by virtue of a constraint or implicit index. */ int sqlite3FindInIndex(Parse *pParse, Expr *pX, int mustBeUnique){ Select *p; int eType = 0; int iTab = pParse->nTab++; /* The follwing if(...) expression is true if the SELECT is of the ** simple form: ** ** SELECT <column> FROM <table> ** ** If this is the case, it may be possible to use an existing table ** or index instead of generating an epheremal table. */ if( sqlite3_enable_in_opt && (p=pX->pSelect) && !p->pPrior && !p->isDistinct && !p->isAgg && !p->pGroupBy && p->pSrc && p->pSrc->nSrc==1 && !p->pSrc->a[0].pSelect && !p->pSrc->a[0].pTab->pSelect && p->pEList->nExpr==1 && p->pEList->a[0].pExpr->op==TK_COLUMN && !p->pLimit && !p->pOffset && !p->pWhere ){ sqlite3 *db = pParse->db; Index *pIdx; Expr *pExpr = p->pEList->a[0].pExpr; int iCol = pExpr->iColumn; Vdbe *v = sqlite3GetVdbe(pParse); /* 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 iMem = pParse->nMem++; int iAddr; Table *pTab = p->pSrc->a[0].pTab; int iDb = sqlite3SchemaToIndex(db, pTab->pSchema); sqlite3VdbeUsesBtree(v, iDb); sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0); iAddr = sqlite3VdbeAddOp(v, OP_If, 0, iMem); sqlite3VdbeAddOp(v, OP_MemInt, 1, iMem); sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead); eType = IN_INDEX_ROWID; sqlite3VdbeJumpHere(v, iAddr); }else{ /* The collation sequence used by the comparison. If an index is to ** be used in place of a temp-table, it must be ordered according ** to this collation sequence. */ CollSeq *pReq = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pExpr); /* Check that the affinity that will be used to perform the ** comparison is the same as the affinity of the column. If ** it is not, it is not possible to use any index. */ Table *pTab = p->pSrc->a[0].pTab; char aff = comparisonAffinity(pX); int affinity_ok = (pTab->aCol[iCol].affinity==aff||aff==SQLITE_AFF_NONE); for(pIdx=pTab->pIndex; pIdx && eType==0 && affinity_ok; pIdx=pIdx->pNext){ if( (pIdx->aiColumn[0]==iCol) && (pReq==sqlite3FindCollSeq(db, ENC(db), pIdx->azColl[0], -1, 0)) && (!mustBeUnique || (pIdx->nColumn==1 && pIdx->onError!=OE_None)) ){ int iDb; int iMem = pParse->nMem++; int iAddr; char *pKey; pKey = (char *)sqlite3IndexKeyinfo(pParse, pIdx); iDb = sqlite3SchemaToIndex(db, pIdx->pSchema); sqlite3VdbeUsesBtree(v, iDb); sqlite3VdbeAddOp(v, OP_MemLoad, iMem, 0); iAddr = sqlite3VdbeAddOp(v, OP_If, 0, iMem); sqlite3VdbeAddOp(v, OP_MemInt, 1, iMem); sqlite3VdbeAddOp(v, OP_Integer, iDb, 0); VdbeComment((v, "# %s", pIdx->zName)); sqlite3VdbeOp3(v,OP_OpenRead,iTab,pIdx->tnum,pKey,P3_KEYINFO_HANDOFF); eType = IN_INDEX_INDEX; sqlite3VdbeAddOp(v, OP_SetNumColumns, iTab, pIdx->nColumn); sqlite3VdbeJumpHere(v, iAddr); } } } } if( eType==0 ){ sqlite3CodeSubselect(pParse, pX); eType = IN_INDEX_EPH; }else{ pX->iTable = iTab; } return eType; } /* ** Generate code for scalar subqueries used as an expression ** and IN operators. Examples: ** ** (SELECT a FROM b) -- subquery ** EXISTS (SELECT a FROM b) -- EXISTS subquery |
︙ | ︙ | |||
2032 2033 2034 2035 2036 2037 2038 | VdbeComment((v, "# load subquery result")); break; } case TK_IN: { int addr; char affinity; int ckOffset = pParse->ckOffset; | > > > | | > > > > > > | | > > | 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 | VdbeComment((v, "# load subquery result")); break; } case TK_IN: { int addr; char affinity; int ckOffset = pParse->ckOffset; int eType; int iLabel = sqlite3VdbeMakeLabel(v); eType = sqlite3FindInIndex(pParse, pExpr, 0); /* Figure out the affinity to use to create a key from the results ** of the expression. affinityStr stores a static string suitable for ** P3 of OP_MakeRecord. */ affinity = comparisonAffinity(pExpr); sqlite3VdbeAddOp(v, OP_Integer, 1, 0); pParse->ckOffset = (ckOffset ? (ckOffset+1) : 0); /* Code the <expr> from "<expr> IN (...)". The temporary table ** pExpr->iTable contains the values that make up the (...) set. */ sqlite3ExprCode(pParse, pExpr->pLeft); addr = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+4); /* addr + 0 */ sqlite3VdbeAddOp(v, OP_Pop, 2, 0); sqlite3VdbeAddOp(v, OP_Null, 0, 0); sqlite3VdbeAddOp(v, OP_Goto, 0, iLabel); if( eType==IN_INDEX_ROWID ){ int iAddr = sqlite3VdbeCurrentAddr(v)+3; sqlite3VdbeAddOp(v, OP_MustBeInt, 1, iAddr); sqlite3VdbeAddOp(v, OP_NotExists, pExpr->iTable, iAddr); sqlite3VdbeAddOp(v, OP_Goto, pExpr->iTable, iLabel); }else{ sqlite3VdbeOp3(v, OP_MakeRecord, 1, 0, &affinity, 1); /* addr + 4 */ sqlite3VdbeAddOp(v, OP_Found, pExpr->iTable, iLabel); } sqlite3VdbeAddOp(v, OP_AddImm, -1, 0); /* addr + 6 */ sqlite3VdbeResolveLabel(v, iLabel); break; } #endif case TK_BETWEEN: { Expr *pLeft = pExpr->pLeft; struct ExprList_item *pLItem = pExpr->pList->a; |
︙ | ︙ |
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.622 2007/11/29 17:05:18 danielk1977 Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* ** The macro unlikely() is a hint that surrounds a boolean ** expression that is usually false. Macro likely() surrounds |
︙ | ︙ | |||
880 881 882 883 884 885 886 887 888 889 890 891 892 893 | ** otherwise be equal, then return a result as if the second key ** were larger. */ struct KeyInfo { sqlite3 *db; /* The database connection */ u8 enc; /* Text encoding - one of the TEXT_Utf* values */ u8 incrKey; /* Increase 2nd key by epsilon before comparison */ int nField; /* Number of entries in aColl[] */ u8 *aSortOrder; /* If defined an aSortOrder[i] is true, sort DESC */ CollSeq *aColl[1]; /* Collating sequence for each term of the key */ }; /* ** Each SQL index is represented in memory by an | > | 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 | ** otherwise be equal, then return a result as if the second key ** were larger. */ struct KeyInfo { sqlite3 *db; /* The database connection */ u8 enc; /* Text encoding - one of the TEXT_Utf* values */ u8 incrKey; /* Increase 2nd key by epsilon before comparison */ u8 prefixIsEqual; /* Treat a prefix as equal */ int nField; /* Number of entries in aColl[] */ u8 *aSortOrder; /* If defined an aSortOrder[i] is true, sort DESC */ CollSeq *aColl[1]; /* Collating sequence for each term of the key */ }; /* ** Each SQL index is represented in memory by an |
︙ | ︙ | |||
1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 | int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *); FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*); void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**); int sqlite3Reprepare(Vdbe*); void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*); CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *); #ifdef SQLITE_ENABLE_ATOMIC_WRITE int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); int sqlite3JournalCreate(sqlite3_file *); #else #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile) #endif | > > > > > | 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 | int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *); FuncDef *sqlite3VtabOverloadFunction(sqlite3 *,FuncDef*, int nArg, Expr*); void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**); int sqlite3Reprepare(Vdbe*); void sqlite3ExprListCheckLength(Parse*, ExprList*, int, const char*); CollSeq *sqlite3BinaryCompareCollSeq(Parse *, Expr *, Expr *); #define IN_INDEX_ROWID 1 #define IN_INDEX_EPH 2 #define IN_INDEX_INDEX 3 int sqlite3FindInIndex(Parse *, Expr *, int); #ifdef SQLITE_ENABLE_ATOMIC_WRITE int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); int sqlite3JournalCreate(sqlite3_file *); #else #define sqlite3JournalSize(pVfs) ((pVfs)->szOsFile) #endif |
︙ | ︙ |
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 all sorts of SQLite interfaces. 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 all sorts of SQLite interfaces. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** ** $Id: test1.c,v 1.280 2007/11/29 17:05:18 danielk1977 Exp $ */ #include "sqliteInt.h" #include "tcl.h" #include <stdlib.h> #include <string.h> /* |
︙ | ︙ | |||
4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 | #endif #ifdef SQLITE_DEBUG extern int sqlite3_where_trace; extern int sqlite3_os_trace; extern int sqlite3_vdbe_addop_trace; #endif #ifdef SQLITE_TEST extern char sqlite3_query_plan[]; static char *query_plan = sqlite3_query_plan; #endif for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){ Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0); } | > | 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 | #endif #ifdef SQLITE_DEBUG extern int sqlite3_where_trace; extern int sqlite3_os_trace; extern int sqlite3_vdbe_addop_trace; #endif #ifdef SQLITE_TEST extern int sqlite3_enable_in_opt; extern char sqlite3_query_plan[]; static char *query_plan = sqlite3_query_plan; #endif for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){ Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0); } |
︙ | ︙ | |||
4508 4509 4510 4511 4512 4513 4514 4515 4516 | (char*)&sqlite3_temp_directory, TCL_LINK_STRING); Tcl_LinkVar(interp, "bitmask_size", (char*)&bitmask_size, TCL_LINK_INT|TCL_LINK_READ_ONLY); Tcl_LinkVar(interp, "sqlite_sync_count", (char*)&sqlite3_sync_count, TCL_LINK_INT); Tcl_LinkVar(interp, "sqlite_fullsync_count", (char*)&sqlite3_fullsync_count, TCL_LINK_INT); return TCL_OK; } | > > > > | 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 | (char*)&sqlite3_temp_directory, TCL_LINK_STRING); Tcl_LinkVar(interp, "bitmask_size", (char*)&bitmask_size, TCL_LINK_INT|TCL_LINK_READ_ONLY); Tcl_LinkVar(interp, "sqlite_sync_count", (char*)&sqlite3_sync_count, TCL_LINK_INT); Tcl_LinkVar(interp, "sqlite_fullsync_count", (char*)&sqlite3_fullsync_count, TCL_LINK_INT); #ifdef SQLITE_TEST Tcl_LinkVar(interp, "sqlite_enable_in_opt", (char*)&sqlite3_enable_in_opt, TCL_LINK_INT); #endif return TCL_OK; } |
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.655 2007/11/29 17:05:18 danielk1977 Exp $ */ #include "sqliteInt.h" #include <ctype.h> #include "vdbeInt.h" /* ** The following global variable is incremented every time a cursor |
︙ | ︙ | |||
1432 1433 1434 1435 1436 1437 1438 | break; } /* Opcode: MustBeInt P1 P2 * ** ** Force the top of the stack to be an integer. If the top of the ** stack is not an integer and cannot be converted into an integer | | | 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 | break; } /* Opcode: MustBeInt P1 P2 * ** ** Force the top of the stack to be an integer. If the top of the ** stack is not an integer and cannot be converted into an integer ** without data loss, then jump immediately to P2, or if P2==0 ** raise an SQLITE_MISMATCH exception. ** ** If the top of the stack is not an integer and P2 is not zero and ** P1 is 1, then the stack is popped. In all other cases, the depth ** of the stack is unchanged. */ case OP_MustBeInt: { /* no-push */ |
︙ | ︙ | |||
3052 3053 3054 3055 3056 3057 3058 | ** Top of the stack holds a blob constructed by MakeRecord. P1 is an index. ** If an entry that matches the top of the stack exists in P1 then ** jump to P2. If the top of the stack does not match any entry in P1 ** then fall thru. The P1 cursor is left pointing at the matching entry ** if it exists. The blob is popped off the top of the stack. ** ** This instruction is used to implement the IN operator where the | | | | > > > | | | 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 | ** Top of the stack holds a blob constructed by MakeRecord. P1 is an index. ** If an entry that matches the top of the stack exists in P1 then ** jump to P2. If the top of the stack does not match any entry in P1 ** then fall thru. The P1 cursor is left pointing at the matching entry ** if it exists. The blob is popped off the top of the stack. ** ** This instruction is used to implement the IN operator where the ** left-hand side is a SELECT statement. P1 may be a true index, or it ** may be a temporary index that holds the results of the SELECT ** statement. ** ** This instruction checks if index P1 contains a record for which ** the first N serialised values exactly match the N serialised values ** in the record on the stack, where N is the total number of values in ** the stack record (stack record is a prefix of the P1 record). ** ** See also: Distinct, NotFound, MoveTo, IsUnique, NotExists */ /* Opcode: NotFound P1 P2 * ** ** The top of the stack holds a blob constructed by MakeRecord. P1 is ** an index. If no entry exists in P1 that matches the blob then jump |
︙ | ︙ | |||
3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 | assert( i>=0 && i<p->nCursor ); assert( p->apCsr[i]!=0 ); if( (pC = p->apCsr[i])->pCursor!=0 ){ int res; assert( pC->isTable==0 ); assert( pTos->flags & MEM_Blob ); Stringify(pTos, encoding); rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res); if( rc!=SQLITE_OK ){ break; } alreadyExists = (res==0); pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; } | > > > > | 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 | assert( i>=0 && i<p->nCursor ); assert( p->apCsr[i]!=0 ); if( (pC = p->apCsr[i])->pCursor!=0 ){ int res; assert( pC->isTable==0 ); assert( pTos->flags & MEM_Blob ); Stringify(pTos, encoding); if( pOp->opcode==OP_Found ){ pC->pKeyInfo->prefixIsEqual = 1; } rc = sqlite3BtreeMoveto(pC->pCursor, pTos->z, pTos->n, 0, &res); pC->pKeyInfo->prefixIsEqual = 0; if( rc!=SQLITE_OK ){ break; } alreadyExists = (res==0); pC->deferredMoveto = 0; pC->cacheStatus = CACHE_STALE; } |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
2107 2108 2109 2110 2111 2112 2113 | /* One of the keys ran out of fields, but all the fields up to that point ** were equal. If the incrKey flag is true, then the second key is ** treated as larger. */ if( rc==0 ){ if( pKeyInfo->incrKey ){ rc = -1; | > | | | | > | 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 | /* One of the keys ran out of fields, but all the fields up to that point ** were equal. If the incrKey flag is true, then the second key is ** treated as larger. */ if( rc==0 ){ if( pKeyInfo->incrKey ){ rc = -1; }else if( !pKeyInfo->prefixIsEqual ){ if( d1<nKey1 ){ rc = 1; }else if( d2<nKey2 ){ rc = -1; } } }else if( pKeyInfo->aSortOrder && i<pKeyInfo->nField && pKeyInfo->aSortOrder[i] ){ rc = -rc; } return rc; |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
12 13 14 15 16 17 18 | ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. This module is reponsible for ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** | | | 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. This module is reponsible for ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** ** $Id: where.c,v 1.264 2007/11/29 17:05:18 danielk1977 Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 | Vdbe *v = pParse->pVdbe; if( pX->op==TK_EQ ){ sqlite3ExprCode(pParse, pX->pRight); }else if( pX->op==TK_ISNULL ){ sqlite3VdbeAddOp(v, OP_Null, 0, 0); #ifndef SQLITE_OMIT_SUBQUERY }else{ int iTab; struct InLoop *pIn; assert( pX->op==TK_IN ); | > | > | | 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 1766 | Vdbe *v = pParse->pVdbe; if( pX->op==TK_EQ ){ sqlite3ExprCode(pParse, pX->pRight); }else if( pX->op==TK_ISNULL ){ sqlite3VdbeAddOp(v, OP_Null, 0, 0); #ifndef SQLITE_OMIT_SUBQUERY }else{ int eType; int iTab; struct InLoop *pIn; assert( pX->op==TK_IN ); eType = sqlite3FindInIndex(pParse, pX, 1); iTab = pX->iTable; sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0); VdbeComment((v, "# %.*s", pX->span.n, pX->span.z)); if( pLevel->nIn==0 ){ pLevel->nxt = sqlite3VdbeMakeLabel(v); } pLevel->nIn++; pLevel->aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->aInLoop, sizeof(pLevel->aInLoop[0])*pLevel->nIn); pIn = pLevel->aInLoop; if( pIn ){ int op = ((eType==IN_INDEX_ROWID)?OP_Rowid:OP_Column); pIn += pLevel->nIn - 1; pIn->iCur = iTab; pIn->topAddr = sqlite3VdbeAddOp(v, op, iTab, 0); sqlite3VdbeAddOp(v, OP_IsNull, -1, 0); }else{ pLevel->nIn = 0; } #endif } disableTerm(pLevel, pTerm); |
︙ | ︙ |
Added test/in3.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 | # 2007 November 29 # # 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 tests the optimisations made in November 2007 of expressions # of the following form: # # <value> IN (SELECT <column> FROM <table>) # # $Id: in3.test,v 1.1 2007/11/29 17:05:18 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Return the number of OpenEphemeral instructions used in the # 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} } set nEph } # This proc works the same way as execsql, except that the number # of OpenEphemeral instructions used in the implementation of the # statement is inserted into the start of the returned list. # proc exec_neph {sql} { return [concat [nEphemeral $sql] [execsql $sql]] } do_test in3-1.1 { execsql { CREATE TABLE t1(a PRIMARY KEY, b); INSERT INTO t1 VALUES(1, 2); INSERT INTO t1 VALUES(3, 4); INSERT INTO t1 VALUES(5, 6); } } {} # All of these queries should avoid using a temp-table: # do_test in3-1.2 { exec_neph { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid FROM t1); } } {0 1 2 3} do_test in3-1.3 { exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1); } } {0 1 3 5} do_test in3-1.4 { exec_neph { SELECT rowid FROM t1 WHERE rowid+0 IN (SELECT rowid FROM t1); } } {0 1 2 3} do_test in3-1.5 { exec_neph { SELECT a FROM t1 WHERE a+0 IN (SELECT a FROM t1); } } {0 1 3 5} # Because none of the sub-select queries in the following statements # match the pattern ("SELECT <column> FROM <table>"), the following do # require a temp table. # do_test in3-1.6 { exec_neph { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid+0 FROM t1); } } {1 1 2 3} do_test in3-1.7 { exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a+0 FROM t1); } } {1 1 3 5} do_test in3-1.8 { exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 WHERE 1); } } {1 1 3 5} do_test in3-1.9 { exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 GROUP BY a); } } {1 1 3 5} # This should not use a temp-table. Even though the sub-select does # not exactly match the pattern "SELECT <column> FROM <table>", in # this case the ORDER BY is a no-op and can be ignored. do_test in3-1.10 { exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a); } } {0 1 3 5} # These do use the temp-table. Adding the LIMIT clause means the # ORDER BY cannot be ignored. do_test in3-1.11 { exec_neph {SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a LIMIT 1)} } {1 1} do_test in3-1.12 { exec_neph { SELECT a FROM t1 WHERE a IN (SELECT a FROM t1 ORDER BY a LIMIT 1 OFFSET 1) } } {1 3} # Has to use a temp-table because of the compound sub-select. # do_test in3-1.13 { exec_neph { SELECT a FROM t1 WHERE a IN ( SELECT a FROM t1 UNION ALL SELECT a FROM t1 ) } } {1 1 3 5} # The first of these queries has to use the temp-table, because the # collation sequence used for the index on "t1.a" does not match the # collation sequence used by the "IN" comparison. The second does not # require a temp-table, because the collation sequences match. # do_test in3-1.14 { exec_neph { SELECT a FROM t1 WHERE a COLLATE nocase IN (SELECT a FROM t1) } } {1 1 3 5} do_test in3-1.15 { exec_neph { SELECT a FROM t1 WHERE a COLLATE binary IN (SELECT a FROM t1) } } {0 1 3 5} # Neither of these queries require a temp-table. The collation sequence # makes no difference when using a rowid. # do_test in3-1.16 { exec_neph {SELECT a FROM t1 WHERE a COLLATE nocase IN (SELECT rowid FROM t1)} } {0 1 3} do_test in3-1.17 { exec_neph {SELECT a FROM t1 WHERE a COLLATE binary IN (SELECT rowid FROM t1)} } {0 1 3} # The following tests - in3.2.* - test a bug that was difficult to track # down during development. They are not particularly well focused. # do_test in3-2.1 { execsql { DROP TABLE IF EXISTS t1; CREATE TABLE t1(w int, x int, y int); CREATE TABLE t2(p int, q int, r int, s int); } for {set i 1} {$i<=100} {incr i} { set w $i set x [expr {int(log($i)/log(2))}] set y [expr {$i*$i + 2*$i + 1}] execsql "INSERT INTO t1 VALUES($w,$x,$y)" } set maxy [execsql {select max(y) from t1}] db eval { INSERT INTO t2 SELECT 101-w, x, $maxy+1-y, y FROM t1 } } {} do_test in3-2.2 { execsql { SELECT rowid FROM t1 WHERE rowid IN (SELECT rowid FROM t1 WHERE rowid IN (1, 2)); } } {1 2} do_test in3-2.3 { execsql { select rowid from t1 where rowid IN (-1,2,4) } } {2 4} do_test in3-2.4 { execsql { SELECT rowid FROM t1 WHERE rowid IN (select rowid from t1 where rowid IN (-1,2,4)) } } {2 4} #------------------------------------------------------------------------- # This next block of tests - in3-3.* - verify that column affinity is # correctly handled in cases where an index might be used to optimise # an IN (SELECT) expression. # do_test in3-3.1 { catch {execsql { DROP TABLE t1; DROP TABLE t2; }} execsql { CREATE TABLE t1(a BLOB, b NUMBER ,c TEXT); CREATE UNIQUE INDEX t1_i1 ON t1(a); /* no affinity */ CREATE UNIQUE INDEX t1_i2 ON t1(b); /* numeric affinity */ CREATE UNIQUE INDEX t1_i3 ON t1(c); /* text affinity */ CREATE TABLE t2(x BLOB, y NUMBER, z TEXT); CREATE UNIQUE INDEX t2_i1 ON t2(x); /* no affinity */ CREATE UNIQUE INDEX t2_i2 ON t2(y); /* numeric affinity */ CREATE UNIQUE INDEX t2_i3 ON t2(z); /* text affinity */ INSERT INTO t1 VALUES(1, 1, 1); INSERT INTO t2 VALUES('1', '1', '1'); } } {} do_test in3-3.2 { # No affinity is applied before comparing "x" and "a". Therefore # the index can be used (the comparison is false, text!=number). exec_neph { SELECT x IN (SELECT a FROM t1) FROM t2 } } {0 0} do_test in3-3.3 { # Logically, numeric affinity is applied to both sides before # the comparison. Therefore it is possible to use index t1_i2. exec_neph { SELECT x IN (SELECT b FROM t1) FROM t2 } } {0 1} do_test in3-3.4 { # No affinity is applied before the comparison takes place. Making # it possible to use index t1_i3. exec_neph { SELECT x IN (SELECT c FROM t1) FROM t2 } } {0 1} do_test in3-3.5 { # Numeric affinity should be applied to each side before the comparison # takes place. Therefore we cannot use index t1_i1, which has no affinity. exec_neph { SELECT y IN (SELECT a FROM t1) FROM t2 } } {1 1} do_test in3-3.6 { # Numeric affinity is applied to both sides before # the comparison. Therefore it is possible to use index t1_i2. exec_neph { SELECT y IN (SELECT b FROM t1) FROM t2 } } {0 1} do_test in3-3.7 { # Numeric affinity is applied before the comparison takes place. # Making it impossible to use index t1_i3. exec_neph { SELECT y IN (SELECT c FROM t1) FROM t2 } } {1 1} #--------------------------------------------------------------------- # # Test using a multi-column index. # do_test in3-4.1 { execsql { CREATE TABLE t3(a, b, c); CREATE UNIQUE INDEX t3_i ON t3(b, a); } execsql { INSERT INTO t3 VALUES(1, 'numeric', 2); INSERT INTO t3 VALUES(2, 'text', 2); INSERT INTO t3 VALUES(3, 'real', 2); INSERT INTO t3 VALUES(4, 'none', 2); } } {} do_test in3-4.2 { exec_neph { SELECT 'text' IN (SELECT b FROM t3) } } {0 1} do_test in3-4.3 { exec_neph { SELECT 'TEXT' COLLATE nocase IN (SELECT b FROM t3) } } {1 1} do_test in3-4.4 { # A temp table must be used because t3_i.b is not guaranteed to be unique. exec_neph { SELECT b FROM t3 WHERE b IN (SELECT b FROM t3) } } {1 none numeric real text} do_test in3-4.5 { execsql { CREATE UNIQUE INDEX t3_i2 ON t3(b) } exec_neph { SELECT b FROM t3 WHERE b IN (SELECT b FROM t3) } } {0 none numeric real text} do_test in3-4.6 { execsql { DROP INDEX t3_i2 } } {} finish_test |