Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Use OpenHash instead of OpenEphemeral for the RHS of IN operators if the result is not needed for sorting. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | subquery-codegen-refactor |
Files: | files | file ages | folders |
SHA1: |
715fac7749a6b1523fe9f7de8263f0c4 |
User & Date: | drh 2014-02-06 03:31:41.891 |
Context
2014-02-06
| ||
14:59 | Change more OP_OpenEphemeral operations to OP_OpenHash. (Leaf check-in: 881164cf6e user: drh tags: subquery-codegen-refactor) | |
03:31 | Use OpenHash instead of OpenEphemeral for the RHS of IN operators if the result is not needed for sorting. (check-in: 715fac7749 user: drh tags: subquery-codegen-refactor) | |
2014-02-05
| ||
19:10 | Separate out the code generators for the RHS of an IN operator and for SELECT/EXISTS expressions. (check-in: 61c34ba71b user: drh tags: subquery-codegen-refactor) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
1505 1506 1507 1508 1509 1510 1511 | ** 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 */ | | > | 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 | ** 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 */ |
︙ | ︙ | |||
1557 1558 1559 1560 1561 1562 1563 | ** 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++; | > | | 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 | ** 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. |
︙ | ︙ | |||
1718 1719 1720 1721 1722 1723 1724 1725 1726 | ** if( register==NULL ){ ** has_null = <test if data structure contains null> ** register = 1 ** } ** ** in order to avoid running the <test if data structure contains null> ** test more often than is necessary. */ #ifndef SQLITE_OMIT_SUBQUERY | > > > | | 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 | ** if( register==NULL ){ ** has_null = <test if data structure contains null> ** register = 1 ** } ** ** in order to avoid running the <test if data structure contains null> ** 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 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 ); |
︙ | ︙ | |||
1813 1814 1815 1816 1817 1818 1819 | }else{ testcase( pParse->nQueryLoop>0 ); pParse->nQueryLoop = 0; if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){ eType = IN_INDEX_ROWID; } } | | | 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 | }else{ testcase( pParse->nQueryLoop>0 ); pParse->nQueryLoop = 0; if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){ eType = IN_INDEX_ROWID; } } sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID,bOrdered); pParse->nQueryLoop = savedNQueryLoop; }else{ pX->iTable = iTab; } return eType; } #endif |
︙ | ︙ | |||
1939 1940 1941 1942 1943 1944 1945 | /* 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")); | | | 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 | /* 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, 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. */ affinity = comparisonAffinity(pExpr); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
3474 3475 3476 3477 3478 3479 3480 | #define sqlite3EndBenignMalloc() #endif #define IN_INDEX_ROWID 1 #define IN_INDEX_EPH 2 #define IN_INDEX_INDEX_ASC 3 #define IN_INDEX_INDEX_DESC 4 | | | 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 | #define sqlite3EndBenignMalloc() #endif #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); #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); #else |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
2344 2345 2346 2347 2348 2349 2350 | ** The current value for the constraint is left in register iReg. ** ** 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( | | | > | | | 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 | ** The current value for the constraint is left in register iReg. ** ** 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( 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; /* 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 ){ iReg = iTarget; sqlite3VdbeAddOp2(v, OP_Null, 0, iReg); |
︙ | ︙ | |||
2378 2379 2380 2381 2382 2383 2384 | ){ testcase( iEq==0 ); testcase( bRev ); bRev = !bRev; } assert( pX->op==TK_IN ); iReg = iTarget; | | | 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 | ){ testcase( iEq==0 ); testcase( bRev ); bRev = !bRev; } assert( pX->op==TK_IN ); iReg = iTarget; eType = sqlite3FindInIndex(pParse, pX, 0, pWInfo->bOBSat); if( eType==IN_INDEX_INDEX_DESC ){ testcase( bRev ); bRev = !bRev; } iTab = pX->iTable; sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0); assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 ); |
︙ | ︙ | |||
2460 2461 2462 2463 2464 2465 2466 | ** In the example above, the index on t1(a) has TEXT affinity. But since ** the right hand side of the equality constraint (t2.b) has NONE affinity, ** 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( | | > | 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 | ** In the example above, the index on t1(a) has TEXT affinity. But since ** the right hand side of the equality constraint (t2.b) has NONE affinity, ** 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( 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 */ int regBase; /* Base register */ int nReg; /* Number of registers to allocate */ |
︙ | ︙ | |||
2522 2523 2524 2525 2526 2527 2528 | int r1; pTerm = pLoop->aLTerm[j]; 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 ); | | | 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 | int r1; pTerm = pLoop->aLTerm[j]; 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(pWInfo, pTerm, pLevel, j, bRev, regBase+j); if( r1!=regBase+j ){ if( nReg==1 ){ sqlite3ReleaseTempReg(pParse, regBase); regBase = r1; }else{ sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j); } |
︙ | ︙ | |||
2805 2806 2807 2808 2809 2810 2811 | iReg = sqlite3GetTempRange(pParse, nConstraint+2); addrNotFound = pLevel->addrBrk; for(j=0; j<nConstraint; j++){ int iTarget = iReg+j+2; pTerm = pLoop->aLTerm[j]; if( pTerm==0 ) continue; if( pTerm->eOperator & WO_IN ){ | | | 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 | iReg = sqlite3GetTempRange(pParse, nConstraint+2); addrNotFound = pLevel->addrBrk; for(j=0; j<nConstraint; j++){ int iTarget = iReg+j+2; pTerm = pLoop->aLTerm[j]; if( pTerm==0 ) continue; if( pTerm->eOperator & WO_IN ){ codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, iTarget); addrNotFound = pLevel->addrNxt; }else{ sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget); } } sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg); sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1); |
︙ | ︙ | |||
2845 2846 2847 2848 2849 2850 2851 | assert( pLoop->u.btree.nEq==1 ); iReleaseReg = sqlite3GetTempReg(pParse); pTerm = pLoop->aLTerm[0]; assert( pTerm!=0 ); assert( pTerm->pExpr!=0 ); assert( omitTable==0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); | | | 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 | assert( pLoop->u.btree.nEq==1 ); iReleaseReg = sqlite3GetTempReg(pParse); pTerm = pLoop->aLTerm[0]; assert( pTerm!=0 ); assert( pTerm->pExpr!=0 ); assert( omitTable==0 ); testcase( pTerm->wtFlags & TERM_VIRTUAL ); 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); VdbeComment((v, "pk")); pLevel->op = OP_Noop; |
︙ | ︙ | |||
3035 3036 3037 3038 3039 3040 3041 | nExtraReg = 1; } /* 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. */ | | | 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 | nExtraReg = 1; } /* 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(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 ** a forward order scan on a descending index, interchange the ** start and end terms (pRangeStart and pRangeEnd). |
︙ | ︙ |
Changes to test/in3.test.
︙ | ︙ | |||
25 26 27 28 29 30 31 | # 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"] { | | | 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | # 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" || $op eq "OpenHash"} {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. |
︙ | ︙ |
Changes to test/in5.test.
︙ | ︙ | |||
61 62 63 64 65 66 67 | } {0} do_test in5-2.4 { 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 { | | | | | 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 | } {0} do_test in5-2.4 { 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 {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 {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 {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 { execsql { DROP INDEX t2abc; |
︙ | ︙ |