Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhancements to the code generator for the IN operator that result in much faster queries in some cases, for example when the RHS of the IN operator changes for each row of a large table scan. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | IN-operator-improvements |
Files: | files | file ages | folders |
SHA1: |
436e884215e2b33ca3fbb555362237b1 |
User & Date: | drh 2014-08-02 21:03:33.699 |
Context
2014-08-04
| ||
16:39 | Refinements to the enhanced IN-operator logic. (check-in: 92ba282146 user: drh tags: IN-operator-improvements) | |
2014-08-02
| ||
21:03 | Enhancements to the code generator for the IN operator that result in much faster queries in some cases, for example when the RHS of the IN operator changes for each row of a large table scan. (check-in: 436e884215 user: drh tags: IN-operator-improvements) | |
20:44 | Remove (newly) incorrect preprocessor check to fix build on WinRT. (check-in: ba78265429 user: mistachkin tags: trunk) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 | j1 = sqlite3VdbeAddOp1(v, OP_Rewind, iCur); VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_Column, iCur, 0, regHasNull); sqlite3VdbeChangeP5(v, OPFLAG_TYPEOFARG); VdbeComment((v, "first_entry_in(%d)", iCur)); sqlite3VdbeJumpHere(v, j1); } /* ** 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. ** ** The job of this routine is to find or create a b-tree object that can ** be used either to test for membership in the RHS set or to iterate through ** all members of the RHS set, skipping duplicates. ** ** A cursor is opened on the b-tree object that is the RHS of the IN operator ** and pX->iTable is set to the index of that cursor. ** ** The returned value of this function indicates the b-tree type, as follows: ** ** IN_INDEX_ROWID - The cursor was opened on a database table. ** IN_INDEX_INDEX_ASC - The cursor was opened on an ascending index. ** IN_INDEX_INDEX_DESC - The cursor was opened on a descending index. ** IN_INDEX_EPH - The cursor was opened on a specially created and ** populated epheremal table. ** ** An existing b-tree might be used if the RHS expression pX is a simple ** subquery such as: ** ** SELECT <column> FROM <table> ** ** If the RHS of the IN operator is a list or a more complex subquery, then | > > > > > > > > > > > > > > > > > > > > | 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 | j1 = sqlite3VdbeAddOp1(v, OP_Rewind, iCur); VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_Column, iCur, 0, regHasNull); sqlite3VdbeChangeP5(v, OPFLAG_TYPEOFARG); VdbeComment((v, "first_entry_in(%d)", iCur)); sqlite3VdbeJumpHere(v, j1); } #ifndef SQLITE_OMIT_SUBQUERY /* ** The argument is an IN operator with a list (not a subquery) on the ** right-hand side. Return TRUE if that list is constant. */ static int sqlite3InRhsIsConstant(Expr *pIn){ Expr *pLHS; int res; assert( !ExprHasProperty(pIn, EP_xIsSelect) ); pLHS = pIn->pLeft; pIn->pLeft = 0; res = sqlite3ExprIsConstant(pIn); pIn->pLeft = pLHS; return res; } #endif /* ** 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. ** ** The job of this routine is to find or create a b-tree object that can ** be used either to test for membership in the RHS set or to iterate through ** all members of the RHS set, skipping duplicates. ** ** A cursor is opened on the b-tree object that is the RHS of the IN operator ** and pX->iTable is set to the index of that cursor. ** ** The returned value of this function indicates the b-tree type, as follows: ** ** IN_INDEX_ROWID - The cursor was opened on a database table. ** IN_INDEX_INDEX_ASC - The cursor was opened on an ascending index. ** IN_INDEX_INDEX_DESC - The cursor was opened on a descending index. ** IN_INDEX_EPH - The cursor was opened on a specially created and ** populated epheremal table. ** IN_INDEX_NOOP - No cursor was allocated. The IN operator must be ** implemented as a sequence of comparisons. ** ** An existing b-tree might be used if the RHS expression pX is a simple ** subquery such as: ** ** SELECT <column> FROM <table> ** ** If the RHS of the IN operator is a list or a more complex subquery, then |
︙ | ︙ | |||
1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 | ** to be unique - either because it is an INTEGER PRIMARY KEY or it ** has a UNIQUE constraint or UNIQUE index. ** ** When IN_INDEX_MEMBERSHIP is used (and the b-tree will be used ** for fast set membership tests) then an epheremal table must ** be used unless <column> is an INTEGER PRIMARY KEY or an index can ** be found with <column> as its left-most column. ** ** When the b-tree is being used for membership tests, the calling function ** might need to know whether or not the RHS side of the IN operator ** contains a NULL. If prRhsHasNull is not a NULL pointer and ** if there is any chance that the (...) might contain a NULL value at ** runtime, then a register is allocated and the register number written ** to *prRhsHasNull. If there is no chance that the (...) contains a | > > > > > > > | 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 | ** to be unique - either because it is an INTEGER PRIMARY KEY or it ** has a UNIQUE constraint or UNIQUE index. ** ** When IN_INDEX_MEMBERSHIP is used (and the b-tree will be used ** for fast set membership tests) then an epheremal table must ** be used unless <column> is an INTEGER PRIMARY KEY or an index can ** be found with <column> as its left-most column. ** ** If the IN_INDEX_NOOP_OK and IN_INDEX_MEMBERSHIP are both set and ** if the RHS of the IN operator is a list (not a subquery) then this ** routine might decide that creating an ephemeral b-tree for membership ** testing is too expensive and return IN_INDEX_NOOP. In that case, the ** calling routine should implement the IN operator using a sequence ** of Eq or Ne comparison operations. ** ** When the b-tree is being used for membership tests, the calling function ** might need to know whether or not the RHS side of the IN operator ** contains a NULL. If prRhsHasNull is not a NULL pointer and ** if there is any chance that the (...) might contain a NULL value at ** runtime, then a register is allocated and the register number written ** to *prRhsHasNull. If there is no chance that the (...) contains a |
︙ | ︙ | |||
1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 | sqlite3SetHasNullFlag(v, iTab, *prRhsHasNull); } sqlite3VdbeJumpHere(v, iAddr); } } } } if( eType==0 ){ /* Could not find an existing table or index to use as the RHS b-tree. ** We will have to generate an ephemeral table to do the job. */ u32 savedNQueryLoop = pParse->nQueryLoop; int rMayHaveNull = 0; | > > > > > > > > > > > > > > > > | 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 | sqlite3SetHasNullFlag(v, iTab, *prRhsHasNull); } sqlite3VdbeJumpHere(v, iAddr); } } } } /* If no preexisting index is available for the IN clause ** and IN_INDEX_NOOP is an allowed reply ** and the RHS of the IN operator is a list, not a subquery ** and the RHS is not contant or has two or fewer terms, ** then it is not worth creating an ephermeral table to evaluate ** the IN operator so return IN_INDEX_NOOP. */ if( eType==0 && (inFlags & IN_INDEX_NOOP_OK) && !ExprHasProperty(pX, EP_xIsSelect) && (!sqlite3InRhsIsConstant(pX) || pX->x.pList->nExpr<=2) ){ eType = IN_INDEX_NOOP; } if( eType==0 ){ /* Could not find an existing table or index to use as the RHS b-tree. ** We will have to generate an ephemeral table to do the job. */ u32 savedNQueryLoop = pParse->nQueryLoop; int rMayHaveNull = 0; |
︙ | ︙ | |||
1931 1932 1933 1934 1935 1936 1937 | /* Compute the RHS. After this step, the table with cursor ** 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")); | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | > | 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 | /* Compute the RHS. After this step, the table with cursor ** 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, IN_INDEX_MEMBERSHIP | IN_INDEX_NOOP_OK, destIfFalse==destIfNull ? 0 : &rRhsHasNull); /* 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. */ affinity = comparisonAffinity(pExpr); /* Code the LHS, the <expr> from "<expr> IN (...)". */ sqlite3ExprCachePush(pParse); r1 = sqlite3GetTempReg(pParse); sqlite3ExprCode(pParse, pExpr->pLeft, r1); /* If sqlite3FindInIndex() did not find or create an index that is ** suitable for evaluating the IN operator, then evaluate using a ** sequence of comparisons. */ if( eType==IN_INDEX_NOOP ){ ExprList *pList = pExpr->x.pList; CollSeq *pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft); int labelOk = sqlite3VdbeMakeLabel(v); int r2, regToFree; int regCkNull = 0; int ii; assert( !ExprHasProperty(pExpr, EP_xIsSelect) ); sqlite3VdbeAddOp2(v, OP_IsNull, r1, destIfNull); VdbeCoverage(v); if( destIfNull!=destIfFalse ){ regCkNull = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp2(v, OP_Integer, 0, regCkNull); } for(ii=0; ii<pList->nExpr; ii++){ r2 = sqlite3ExprCodeTemp(pParse, pList->a[ii].pExpr, ®ToFree); if( regCkNull ){ sqlite3VdbeAddOp3(v, OP_BitAnd, regCkNull, r2, regCkNull); } if( ii<pList->nExpr-1 || destIfNull!=destIfFalse ){ sqlite3VdbeAddOp4(v, OP_Eq, r1, labelOk, r2, (void*)pColl, P4_COLLSEQ); VdbeCoverage(v); sqlite3VdbeChangeP5(v, affinity); }else{ assert( destIfNull==destIfFalse ); sqlite3VdbeAddOp4(v, OP_Ne, r1, destIfFalse, r2, (void*)pColl, P4_COLLSEQ); VdbeCoverage(v); sqlite3VdbeChangeP5(v, affinity | SQLITE_JUMPIFNULL); } sqlite3ReleaseTempReg(pParse, regToFree); } if( regCkNull ){ sqlite3VdbeAddOp2(v, OP_IsNull, regCkNull, destIfNull); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfFalse); } sqlite3VdbeResolveLabel(v, labelOk); sqlite3ReleaseTempReg(pParse, regCkNull); }else{ /* If the LHS is NULL, then the result is either false or NULL depending ** on whether the RHS is empty or not, respectively. */ if( destIfNull==destIfFalse ){ /* Shortcut for the common case where the false and NULL outcomes are ** the same. */ sqlite3VdbeAddOp2(v, OP_IsNull, r1, destIfNull); VdbeCoverage(v); }else{ int addr1 = sqlite3VdbeAddOp1(v, OP_NotNull, r1); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfNull); sqlite3VdbeJumpHere(v, addr1); } if( eType==IN_INDEX_ROWID ){ /* In this case, the RHS is the ROWID of table b-tree */ sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, destIfFalse); VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_NotExists, pExpr->iTable, destIfFalse, r1); VdbeCoverage(v); }else{ /* In this case, the RHS is an index b-tree. */ sqlite3VdbeAddOp4(v, OP_Affinity, r1, 1, 0, &affinity, 1); /* If the set membership test fails, then the result of the ** "x IN (...)" expression must be either 0 or NULL. If the set ** contains no NULL values, then the result is 0. If the set ** contains one or more NULL values, then the result of the ** expression is also NULL. */ assert( destIfFalse!=destIfNull || rRhsHasNull==0 ); if( rRhsHasNull==0 ){ /* This branch runs if it is known at compile time that the RHS ** cannot contain NULL values. This happens as the result ** of a "NOT NULL" constraint in the database schema. ** ** Also run this branch if NULL is equivalent to FALSE ** for this particular IN operator. */ sqlite3VdbeAddOp4Int(v, OP_NotFound, pExpr->iTable, destIfFalse, r1, 1); VdbeCoverage(v); }else{ /* In this branch, the RHS of the IN might contain a NULL and ** the presence of a NULL on the RHS makes a difference in the ** outcome. */ int j1; /* First check to see if the LHS is contained in the RHS. If so, ** then the answer is TRUE the presence of NULLs in the RHS does ** not matter. If the LHS is not contained in the RHS, then the ** answer is NULL if the RHS contains NULLs and the answer is ** FALSE if the RHS is NULL-free. */ j1 = sqlite3VdbeAddOp4Int(v, OP_Found, pExpr->iTable, 0, r1, 1); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_IsNull, rRhsHasNull, destIfNull); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfFalse); sqlite3VdbeJumpHere(v, j1); } } } sqlite3ReleaseTempReg(pParse, r1); sqlite3ExprCachePop(pParse); VdbeComment((v, "end IN expr")); } #endif /* SQLITE_OMIT_SUBQUERY */ |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 | /* ** Allowed return values from sqlite3FindInIndex() */ #define IN_INDEX_ROWID 1 /* Search the rowid of the table */ #define IN_INDEX_EPH 2 /* Search an ephemeral b-tree */ #define IN_INDEX_INDEX_ASC 3 /* Existing index ASCENDING */ #define IN_INDEX_INDEX_DESC 4 /* Existing index DESCENDING */ /* ** Allowed flags for the 3rd parameter to sqlite3FindInIndex(). */ | > > | | | 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 | /* ** Allowed return values from sqlite3FindInIndex() */ #define IN_INDEX_ROWID 1 /* Search the rowid of the table */ #define IN_INDEX_EPH 2 /* Search an ephemeral b-tree */ #define IN_INDEX_INDEX_ASC 3 /* Existing index ASCENDING */ #define IN_INDEX_INDEX_DESC 4 /* Existing index DESCENDING */ #define IN_INDEX_NOOP 5 /* No table available. Use comparisons */ /* ** Allowed flags for the 3rd parameter to sqlite3FindInIndex(). */ #define IN_INDEX_NOOP_OK 0x0001 /* OK to return IN_INDEX_NOOP */ #define IN_INDEX_MEMBERSHIP 0x0002 /* IN operator used for membership test */ #define IN_INDEX_LOOP 0x0004 /* IN operator used as a loop */ int sqlite3FindInIndex(Parse *, Expr *, u32, int*); #ifdef SQLITE_ENABLE_ATOMIC_WRITE int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); int sqlite3JournalCreate(sqlite3_file *); int sqlite3JournalExists(sqlite3_file *p); |
︙ | ︙ |
Changes to test/in4.test.
︙ | ︙ | |||
227 228 229 230 231 232 233 | SELECT * FROM t3 WHERE x IN (10); } {10 10 10} do_execsql_test in4-3.44 { EXPLAIN SELECT * FROM t3 WHERE x IN (10); } {~/OpenEphemeral/} do_execsql_test in4-3.45 { | | | | 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 | SELECT * FROM t3 WHERE x IN (10); } {10 10 10} do_execsql_test in4-3.44 { EXPLAIN SELECT * FROM t3 WHERE x IN (10); } {~/OpenEphemeral/} do_execsql_test in4-3.45 { SELECT * FROM t3 WHERE x NOT IN (10,11,99999); } {1 1 1} do_execsql_test in4-3.46 { EXPLAIN SELECT * FROM t3 WHERE x NOT IN (10,11,99999); } {/OpenEphemeral/} do_execsql_test in4-3.47 { SELECT * FROM t3 WHERE x NOT IN (10); } {1 1 1} do_execsql_test in4-3.48 { EXPLAIN SELECT * FROM t3 WHERE x NOT IN (10); |
︙ | ︙ |
Changes to test/tkt-80e031a00f.test.
︙ | ︙ | |||
156 157 158 159 160 161 162 163 164 165 166 167 168 169 | do_execsql_test tkt-80e031a00f.319 {SELECT 'c' NOT IN t7} 0 do_execsql_test tkt-80e031a00f.320 {SELECT 'c' IN t7n} 1 do_execsql_test tkt-80e031a00f.321 {SELECT 'd' NOT IN t7n} 0 do_execsql_test tkt-80e031a00f.322 {SELECT 'b' IN t8} 1 do_execsql_test tkt-80e031a00f.323 {SELECT 'c' NOT IN t8} 0 do_execsql_test tkt-80e031a00f.324 {SELECT 'c' IN t8n} 1 do_execsql_test tkt-80e031a00f.325 {SELECT 'd' NOT IN t8n} 0 # # Row 4: do_execsql_test tkt-80e031a00f.400 {SELECT 1 IN (2,3,4,null)} {{}} do_execsql_test tkt-80e031a00f.401 {SELECT 1 NOT IN (2,3,4,null)} {{}} do_execsql_test tkt-80e031a00f.402 {SELECT 'a' IN ('b','c',null,'d')} {{}} do_execsql_test tkt-80e031a00f.403 {SELECT 'a' NOT IN (null,'b','c','d')} {{}} do_execsql_test tkt-80e031a00f.404 {SELECT 1 IN t4n} {{}} | > > > > | 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 | do_execsql_test tkt-80e031a00f.319 {SELECT 'c' NOT IN t7} 0 do_execsql_test tkt-80e031a00f.320 {SELECT 'c' IN t7n} 1 do_execsql_test tkt-80e031a00f.321 {SELECT 'd' NOT IN t7n} 0 do_execsql_test tkt-80e031a00f.322 {SELECT 'b' IN t8} 1 do_execsql_test tkt-80e031a00f.323 {SELECT 'c' NOT IN t8} 0 do_execsql_test tkt-80e031a00f.324 {SELECT 'c' IN t8n} 1 do_execsql_test tkt-80e031a00f.325 {SELECT 'd' NOT IN t8n} 0 do_execsql_test tkt-80e031a00f.326 {SELECT 'a' IN (NULL,'a')} 1 do_execsql_test tkt-80e031a00f.327 {SELECT 'a' IN (NULL,'b')} {{}} do_execsql_test tkt-80e031a00f.328 {SELECT 'a' NOT IN (NULL,'a')} 0 do_execsql_test tkt-80e031a00f.329 {SELECT 'a' NOT IN (NULL,'b')} {{}} # # Row 4: do_execsql_test tkt-80e031a00f.400 {SELECT 1 IN (2,3,4,null)} {{}} do_execsql_test tkt-80e031a00f.401 {SELECT 1 NOT IN (2,3,4,null)} {{}} do_execsql_test tkt-80e031a00f.402 {SELECT 'a' IN ('b','c',null,'d')} {{}} do_execsql_test tkt-80e031a00f.403 {SELECT 'a' NOT IN (null,'b','c','d')} {{}} do_execsql_test tkt-80e031a00f.404 {SELECT 1 IN t4n} {{}} |
︙ | ︙ |