Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Factor out the IN operator code generation into a subroutine. Use this subroutine to implement both logic and branching versions of the IN operator. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
fcff5b7e2d059ffb8d21df57d0c9648b |
User & Date: | drh 2009-11-12 17:52:24.000 |
Context
2009-11-12
| ||
19:59 | Enhance the OP_Found and OP_NotFound opcodes so that they can accept an array of registers as an unpacked record in addition to a record built using OP_MakeRecord. Use this to avoid OP_MakeRecord calls during IN expression processing. (check-in: b9eab885cd user: drh tags: trunk) | |
17:52 | Factor out the IN operator code generation into a subroutine. Use this subroutine to implement both logic and branching versions of the IN operator. (check-in: fcff5b7e2d user: drh tags: trunk) | |
13:32 | Factor out the code generator for BETWEEN into a subroutine. (check-in: 5735f60b23 user: drh tags: trunk) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
1341 1342 1343 1344 1345 1346 1347 | ** 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 its left-most column. ** ** When the b-tree is being used for membership tests, the calling function ** needs to know whether or not the structure contains an SQL NULL ** value in order to correctly evaluate expressions like "X IN (Y, Z)". | | | | | | | 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 | ** 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 its left-most column. ** ** When the b-tree is being used for membership tests, the calling function ** needs to know whether or not the structure contains an SQL NULL ** value in order to correctly evaluate expressions like "X IN (Y, Z)". ** 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 *prNotFound. If there is no chance that the (...) contains a ** NULL value, then *prNotFound is left unchanged. ** ** If a register is allocated and its location stored in *prNotFound, then ** its initial value is NULL. If the (...) does not remain constant ** for the duration of the query (i.e. the SELECT within the (...) ** is a correlated subquery) then the value of the allocated register is ** reset to NULL each time the subquery is rerun. This allows the ** caller to use vdbe code equivalent to the following: ** ** if( register==NULL ){ ** has_null = <test if data structure contains null> ** register = 1 ** } ** |
︙ | ︙ | |||
1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 | } sqlite3ExprCachePop(pParse, 1); return rReg; } #endif /* SQLITE_OMIT_SUBQUERY */ /* ** Duplicate an 8-byte value */ static char *dup8bytes(Vdbe *v, const char *in){ char *out = sqlite3DbMallocRaw(sqlite3VdbeDb(v), 8); if( out ){ memcpy(out, in, 8); | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 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 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 | } sqlite3ExprCachePop(pParse, 1); return rReg; } #endif /* SQLITE_OMIT_SUBQUERY */ #ifndef SQLITE_OMIT_SUBQUERY /* ** Generate code for an IN expression. ** ** x IN (SELECT ...) ** x IN (value, value, ...) ** ** The left-hand side (LHS) is a scalar expression. The right-hand side (RHS) ** is an array of zero or more values. The expression is true if the LHS is ** contained within the RHS. The value of the expression is unknown (NULL) ** if the LHS is NULL or if the LHS is not contained within the RHS and the ** RHS contains one or more NULL values. ** ** This routine generates code will jump to destIfFalse if the LHS is not ** contained within the RHS. If due to NULLs we cannot determine if the LHS ** is contained in the RHS then jump to destIfNull. If the LHS is contained ** within the RHS then fall through. */ static void sqlite3ExprCodeIN( Parse *pParse, /* Parsing and code generating context */ Expr *pExpr, /* The IN expression */ int destIfFalse, /* Jump here if LHS is not contained in the RHS */ int destIfNull /* Jump here if the results are unknown due to NULLs */ ){ int rRhsHasNull = 0; /* Register that is true if RHS contains NULL values */ char affinity; /* Comparison affinity to use */ int eType; /* Type of the RHS */ int r1; /* Temporary use register */ Vdbe *v; /* Statement under construction */ /* 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, &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); sqlite3VdbeAddOp2(v, OP_IsNull, r1, destIfNull); if( eType==IN_INDEX_ROWID ){ /* In this case, the RHS is the ROWID of table b-tree */ sqlite3VdbeAddOp2(v, OP_MustBeInt, r1, destIfFalse); sqlite3VdbeAddOp3(v, OP_NotExists, pExpr->iTable, destIfFalse, r1); }else{ /* In this case, the RHS is an index b-tree. */ int r2; /* Register holding LHS value as a Record */ /* Create a record that can be used for membership testing. */ r2 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp4(v, OP_MakeRecord, r1, 1, r2, &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. */ if( rRhsHasNull==0 || destIfFalse==destIfNull ){ /* 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. */ sqlite3VdbeAddOp3(v, OP_NotFound, pExpr->iTable, destIfFalse, r2); }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. */ static const char nullRecord[] = { 0x02, 0x00 }; int j1, j2, j3; /* First check to see if the LHS is contained in the RHS. If so, ** then the presence of NULLs in the RHS does not matter, so jump ** over all of the code that follows. */ j1 = sqlite3VdbeAddOp3(v, OP_Found, pExpr->iTable, 0, r2); /* Here we begin generating code that runs if the LHS is not ** contained within the RHS. Generate additional code that ** tests the RHS for NULLs. If the RHS contains a NULL then ** jump to destIfNull. If there are no NULLs in the RHS then ** jump to destIfFalse. */ j2 = sqlite3VdbeAddOp1(v, OP_NotNull, rRhsHasNull); sqlite3VdbeAddOp4(v, OP_Blob, 2, r2, 0, nullRecord, P4_STATIC); j3 = sqlite3VdbeAddOp3(v, OP_Found, pExpr->iTable, 0, r2); sqlite3VdbeAddOp2(v, OP_Integer, -1, rRhsHasNull); sqlite3VdbeJumpHere(v, j3); sqlite3VdbeAddOp2(v, OP_AddImm, rRhsHasNull, 1); sqlite3VdbeJumpHere(v, j2); /* Jump to the appropriate target depending on whether or not ** the RHS contains a NULL */ sqlite3VdbeAddOp2(v, OP_If, rRhsHasNull, destIfNull); sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfFalse); /* The OP_Found at the top of this branch jumps here when true, ** causing the overall IN expression evaluation to fall through. */ sqlite3VdbeJumpHere(v, j1); } sqlite3ReleaseTempReg(pParse, r2); } sqlite3ReleaseTempReg(pParse, r1); sqlite3ExprCachePop(pParse, 1); VdbeComment((v, "end IN expr")); } #endif /* SQLITE_OMIT_SUBQUERY */ /* ** Duplicate an 8-byte value */ static char *dup8bytes(Vdbe *v, const char *in){ char *out = sqlite3DbMallocRaw(sqlite3VdbeDb(v), 8); if( out ){ memcpy(out, in, 8); |
︙ | ︙ | |||
2468 2469 2470 2471 2472 2473 2474 | case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); inReg = sqlite3CodeSubselect(pParse, pExpr, 0, 0); break; } case TK_IN: { | < < < < < | < < < < < < < < < < < < < < < < < < < < < < < | < < | < < | < < < < < | < | < < < < < < < < < < < < | < < < < < < < < < < < < < < < | < | < < < < < | > | < < < < < | < | 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 | case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); inReg = sqlite3CodeSubselect(pParse, pExpr, 0, 0); break; } case TK_IN: { int destIfFalse = sqlite3VdbeMakeLabel(v); int destIfNull = sqlite3VdbeMakeLabel(v); sqlite3VdbeAddOp2(v, OP_Null, 0, target); sqlite3ExprCodeIN(pParse, pExpr, destIfFalse, destIfNull); sqlite3VdbeAddOp2(v, OP_Integer, 1, target); sqlite3VdbeResolveLabel(v, destIfFalse); sqlite3VdbeAddOp2(v, OP_AddImm, target, 0); sqlite3VdbeResolveLabel(v, destIfNull); break; } #endif /* SQLITE_OMIT_SUBQUERY */ /* ** x BETWEEN y AND z ** ** This is equivalent to ** ** x>=y AND x<=z ** |
︙ | ︙ | |||
3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 | sqlite3VdbeAddOp2(v, op, r1, dest); testcase( regFree1==0 ); break; } case TK_BETWEEN: { exprCodeBetween(pParse, pExpr, dest, 1, jumpIfNull); break; } default: { r1 = sqlite3ExprCodeTemp(pParse, pExpr, ®Free1); sqlite3VdbeAddOp3(v, OP_If, r1, dest, jumpIfNull!=0); testcase( regFree1==0 ); testcase( jumpIfNull==0 ); break; | > > > > > > > > | 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 | sqlite3VdbeAddOp2(v, op, r1, dest); testcase( regFree1==0 ); break; } case TK_BETWEEN: { exprCodeBetween(pParse, pExpr, dest, 1, jumpIfNull); break; } case TK_IN: { int destIfFalse = sqlite3VdbeMakeLabel(v); int destIfNull = jumpIfNull ? dest : destIfFalse; sqlite3ExprCodeIN(pParse, pExpr, destIfFalse, destIfNull); sqlite3VdbeAddOp2(v, OP_Goto, 0, dest); sqlite3VdbeResolveLabel(v, destIfFalse); break; } default: { r1 = sqlite3ExprCodeTemp(pParse, pExpr, ®Free1); sqlite3VdbeAddOp3(v, OP_If, r1, dest, jumpIfNull!=0); testcase( regFree1==0 ); testcase( jumpIfNull==0 ); break; |
︙ | ︙ | |||
3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 | sqlite3VdbeAddOp2(v, op, r1, dest); testcase( regFree1==0 ); break; } case TK_BETWEEN: { exprCodeBetween(pParse, pExpr, dest, 0, jumpIfNull); break; } default: { r1 = sqlite3ExprCodeTemp(pParse, pExpr, ®Free1); sqlite3VdbeAddOp3(v, OP_IfNot, r1, dest, jumpIfNull!=0); testcase( regFree1==0 ); testcase( jumpIfNull==0 ); break; | > > > > > > > > > > | 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 | sqlite3VdbeAddOp2(v, op, r1, dest); testcase( regFree1==0 ); break; } case TK_BETWEEN: { exprCodeBetween(pParse, pExpr, dest, 0, jumpIfNull); break; } case TK_IN: { if( jumpIfNull ){ sqlite3ExprCodeIN(pParse, pExpr, dest, dest); }else{ int destIfNull = sqlite3VdbeMakeLabel(v); sqlite3ExprCodeIN(pParse, pExpr, dest, destIfNull); sqlite3VdbeResolveLabel(v, destIfNull); } break; } default: { r1 = sqlite3ExprCodeTemp(pParse, pExpr, ®Free1); sqlite3VdbeAddOp3(v, OP_IfNot, r1, dest, jumpIfNull!=0); testcase( regFree1==0 ); testcase( jumpIfNull==0 ); break; |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3353 3354 3355 3356 3357 3358 3359 | break; } /* Opcode: Found P1 P2 P3 * * ** ** Register P3 holds a blob constructed by MakeRecord. P1 is an index. | < | | < < < < < < < < < < < < < < | | > | | 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 | break; } /* Opcode: Found P1 P2 P3 * * ** ** Register P3 holds a blob constructed by MakeRecord. P1 is an index. ** If P3 is a prefix of any entry in P1 then a jump is made to P2 and ** P1 is left pointing at the matching entry. */ /* Opcode: NotFound P1 P2 P3 * * ** ** Register P3 holds a blob constructed by MakeRecord. P1 is ** an index. If P3 is not the prefix of any entry in P1 then a jump ** is made to P2. If P1 does contain an entry whose prefix matches ** P3 then control falls through to the next instruction and P1 is ** left pointing at the matching entry. ** ** See also: Found, NotExists, IsUnique */ case OP_NotFound: /* jump, in3 */ case OP_Found: { /* jump, in3 */ int alreadyExists; VdbeCursor *pC; |
︙ | ︙ | |||
3406 3407 3408 3409 3410 3411 3412 | assert( pIn3->flags & MEM_Blob ); ExpandBlob(pIn3); pIdxKey = sqlite3VdbeRecordUnpack(pC->pKeyInfo, pIn3->n, pIn3->z, aTempRec, sizeof(aTempRec)); if( pIdxKey==0 ){ goto no_mem; } | < | < | 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 | assert( pIn3->flags & MEM_Blob ); ExpandBlob(pIn3); pIdxKey = sqlite3VdbeRecordUnpack(pC->pKeyInfo, pIn3->n, pIn3->z, aTempRec, sizeof(aTempRec)); if( pIdxKey==0 ){ goto no_mem; } pIdxKey->flags |= UNPACKED_PREFIX_MATCH; rc = sqlite3BtreeMovetoUnpacked(pC->pCursor, pIdxKey, 0, 0, &res); sqlite3VdbeDeleteUnpackedRecord(pIdxKey); if( rc!=SQLITE_OK ){ break; } alreadyExists = (res==0); pC->deferredMoveto = 0; |
︙ | ︙ |