Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Changes to src/expr.c.

  1505   1505   ** intkey B-Tree to store the set of IN(...) values instead of the usual
  1506   1506   ** (slower) variable length keys B-Tree.
  1507   1507   */
  1508   1508   #ifndef SQLITE_OMIT_SUBQUERY
  1509   1509   static void sqlite3CreateInOperatorRhsTable(
  1510   1510     Parse *pParse,          /* Parsing context */
  1511   1511     Expr *pExpr,            /* The IN, SELECT, or EXISTS operator */
  1512         -  int isRowid             /* If true, LHS of IN operator is a rowid */
         1512  +  int isRowid,            /* If true, LHS of IN operator is a rowid */
         1513  +  int bOrdered            /* If true, must use btree, not a hash */
  1513   1514   ){
  1514   1515     int testAddr = -1;                      /* One-time test address */
  1515   1516     Vdbe *v = sqlite3GetVdbe(pParse);       /* prepared stmt under construction */
  1516   1517     char affinity;                          /* Affinity of the LHS of the IN */
  1517   1518     int addr;                               /* Address of OP_Open.. instruction */
  1518   1519     Expr *pLeft = pExpr->pLeft;             /* the LHS of the IN operator */
  1519   1520     KeyInfo *pKeyInfo = 0;                  /* Key information */
................................................................................
  1557   1558     ** column is used to build the index keys. If both 'x' and the
  1558   1559     ** SELECT... statement are columns, then numeric affinity is used
  1559   1560     ** if either column has NUMERIC or INTEGER affinity. If neither
  1560   1561     ** 'x' nor the SELECT... statement are columns, then numeric affinity
  1561   1562     ** is used.
  1562   1563     */
  1563   1564     pExpr->iTable = pParse->nTab++;
  1564         -  addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid);
         1565  +  addr = sqlite3VdbeAddOp2(v, bOrdered ? OP_OpenEphemeral : OP_OpenHash,
         1566  +                           pExpr->iTable, !isRowid);
  1565   1567     pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, 1, 1);
  1566   1568   
  1567   1569     if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  1568   1570       /* Case 1:     expr IN (SELECT ...)
  1569   1571       **
  1570   1572       ** Generate code to write the results of the select into the temporary
  1571   1573       ** table allocated and opened above.
................................................................................
  1718   1720   **   if( register==NULL ){
  1719   1721   **     has_null = <test if data structure contains null>
  1720   1722   **     register = 1
  1721   1723   **   }
  1722   1724   **
  1723   1725   ** in order to avoid running the <test if data structure contains null>
  1724   1726   ** test more often than is necessary.
         1727  +**
         1728  +** IN_INDEX_EPH ephemeral tables must be in key order if the bOrdered flag
         1729  +** is true.  If bOrdered is false, the generated table can be a hash.
  1725   1730   */
  1726   1731   #ifndef SQLITE_OMIT_SUBQUERY
  1727         -int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound){
         1732  +int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound, int bOrdered){
  1728   1733     Select *p;                            /* SELECT to the right of IN operator */
  1729   1734     int eType = 0;                        /* Type of RHS table. IN_INDEX_* */
  1730   1735     int iTab = pParse->nTab++;            /* Cursor of the RHS table */
  1731   1736     int mustBeUnique = (prNotFound==0);   /* True if RHS must be unique */
  1732   1737     Vdbe *v = sqlite3GetVdbe(pParse);     /* Virtual machine being coded */
  1733   1738   
  1734   1739     assert( v!=0 );
................................................................................
  1813   1818       }else{
  1814   1819         testcase( pParse->nQueryLoop>0 );
  1815   1820         pParse->nQueryLoop = 0;
  1816   1821         if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){
  1817   1822           eType = IN_INDEX_ROWID;
  1818   1823         }
  1819   1824       }
  1820         -    sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID);
         1825  +    sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID,bOrdered);
  1821   1826       pParse->nQueryLoop = savedNQueryLoop;
  1822   1827     }else{
  1823   1828       pX->iTable = iTab;
  1824   1829     }
  1825   1830     return eType;
  1826   1831   }
  1827   1832   #endif
................................................................................
  1939   1944   
  1940   1945     /* Compute the RHS.   After this step, the table with cursor
  1941   1946     ** pExpr->iTable will contains the values that make up the RHS.
  1942   1947     */
  1943   1948     v = pParse->pVdbe;
  1944   1949     assert( v!=0 );       /* OOM detected prior to this routine */
  1945   1950     VdbeNoopComment((v, "begin IN expr"));
  1946         -  eType = sqlite3FindInIndex(pParse, pExpr, &rRhsHasNull);
         1951  +  eType = sqlite3FindInIndex(pParse, pExpr, &rRhsHasNull, 0);
  1947   1952   
  1948   1953     /* Figure out the affinity to use to create a key from the results
  1949   1954     ** of the expression. affinityStr stores a static string suitable for
  1950   1955     ** P4 of OP_MakeRecord.
  1951   1956     */
  1952   1957     affinity = comparisonAffinity(pExpr);
  1953   1958   

Changes to src/sqliteInt.h.

  3474   3474     #define sqlite3EndBenignMalloc()
  3475   3475   #endif
  3476   3476   
  3477   3477   #define IN_INDEX_ROWID           1
  3478   3478   #define IN_INDEX_EPH             2
  3479   3479   #define IN_INDEX_INDEX_ASC       3
  3480   3480   #define IN_INDEX_INDEX_DESC      4
  3481         -int sqlite3FindInIndex(Parse *, Expr *, int*);
         3481  +int sqlite3FindInIndex(Parse *, Expr *, int*, int);
  3482   3482   
  3483   3483   #ifdef SQLITE_ENABLE_ATOMIC_WRITE
  3484   3484     int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
  3485   3485     int sqlite3JournalSize(sqlite3_vfs *);
  3486   3486     int sqlite3JournalCreate(sqlite3_file *);
  3487   3487     int sqlite3JournalExists(sqlite3_file *p);
  3488   3488   #else

Changes to src/where.c.

  2344   2344   ** The current value for the constraint is left in register iReg.
  2345   2345   **
  2346   2346   ** For a constraint of the form X=expr, the expression is evaluated and its
  2347   2347   ** result is left on the stack.  For constraints of the form X IN (...)
  2348   2348   ** this routine sets up a loop that will iterate over all values of X.
  2349   2349   */
  2350   2350   static int codeEqualityTerm(
  2351         -  Parse *pParse,      /* The parsing context */
         2351  +  WhereInfo *pWInfo,  /* WHERE clause */
  2352   2352     WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
  2353   2353     WhereLevel *pLevel, /* The level of the FROM clause we are working on */
  2354   2354     int iEq,            /* Index of the equality term within this level */
  2355   2355     int bRev,           /* True for reverse-order IN operations */
  2356   2356     int iTarget         /* Attempt to leave results in this register */
  2357   2357   ){
  2358         -  Expr *pX = pTerm->pExpr;
  2359         -  Vdbe *v = pParse->pVdbe;
  2360         -  int iReg;                  /* Register holding results */
         2358  +  Expr *pX = pTerm->pExpr;            /* Expression to be coded */
         2359  +  Parse *pParse = pWInfo->pParse;     /* Parsing context */
         2360  +  Vdbe *v = pParse->pVdbe;            /* Prepared stmt under construction */
         2361  +  int iReg;                           /* Register holding results */
  2361   2362   
  2362   2363     assert( iTarget>0 );
  2363   2364     if( pX->op==TK_EQ ){
  2364   2365       iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
  2365   2366     }else if( pX->op==TK_ISNULL ){
  2366   2367       iReg = iTarget;
  2367   2368       sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
................................................................................
  2378   2379       ){
  2379   2380         testcase( iEq==0 );
  2380   2381         testcase( bRev );
  2381   2382         bRev = !bRev;
  2382   2383       }
  2383   2384       assert( pX->op==TK_IN );
  2384   2385       iReg = iTarget;
  2385         -    eType = sqlite3FindInIndex(pParse, pX, 0);
         2386  +    eType = sqlite3FindInIndex(pParse, pX, 0, pWInfo->bOBSat);
  2386   2387       if( eType==IN_INDEX_INDEX_DESC ){
  2387   2388         testcase( bRev );
  2388   2389         bRev = !bRev;
  2389   2390       }
  2390   2391       iTab = pX->iTable;
  2391   2392       sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
  2392   2393       assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );
................................................................................
  2460   2461   ** In the example above, the index on t1(a) has TEXT affinity. But since
  2461   2462   ** the right hand side of the equality constraint (t2.b) has NONE affinity,
  2462   2463   ** no conversion should be attempted before using a t2.b value as part of
  2463   2464   ** a key to search the index. Hence the first byte in the returned affinity
  2464   2465   ** string in this example would be set to SQLITE_AFF_NONE.
  2465   2466   */
  2466   2467   static int codeAllEqualityTerms(
  2467         -  Parse *pParse,        /* Parsing context */
         2468  +  WhereInfo *pWInfo,    /* WHERE clause */
  2468   2469     WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  2469   2470     int bRev,             /* Reverse the order of IN operators */
  2470   2471     int nExtraReg,        /* Number of extra registers to allocate */
  2471   2472     char **pzAff          /* OUT: Set to point to affinity string */
  2472   2473   ){
  2473   2474     u16 nEq;                      /* The number of == or IN constraints to code */
  2474   2475     u16 nSkip;                    /* Number of left-most columns to skip */
         2476  +  Parse *pParse = pWInfo->pParse; /* Parsing context */
  2475   2477     Vdbe *v = pParse->pVdbe;      /* The vm under construction */
  2476   2478     Index *pIdx;                  /* The index being used for this loop */
  2477   2479     WhereTerm *pTerm;             /* A single constraint term */
  2478   2480     WhereLoop *pLoop;             /* The WhereLoop object */
  2479   2481     int j;                        /* Loop counter */
  2480   2482     int regBase;                  /* Base register */
  2481   2483     int nReg;                     /* Number of registers to allocate */
................................................................................
  2522   2524       int r1;
  2523   2525       pTerm = pLoop->aLTerm[j];
  2524   2526       assert( pTerm!=0 );
  2525   2527       /* The following testcase is true for indices with redundant columns. 
  2526   2528       ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
  2527   2529       testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
  2528   2530       testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2529         -    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
         2531  +    r1 = codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, regBase+j);
  2530   2532       if( r1!=regBase+j ){
  2531   2533         if( nReg==1 ){
  2532   2534           sqlite3ReleaseTempReg(pParse, regBase);
  2533   2535           regBase = r1;
  2534   2536         }else{
  2535   2537           sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
  2536   2538         }
................................................................................
  2805   2807       iReg = sqlite3GetTempRange(pParse, nConstraint+2);
  2806   2808       addrNotFound = pLevel->addrBrk;
  2807   2809       for(j=0; j<nConstraint; j++){
  2808   2810         int iTarget = iReg+j+2;
  2809   2811         pTerm = pLoop->aLTerm[j];
  2810   2812         if( pTerm==0 ) continue;
  2811   2813         if( pTerm->eOperator & WO_IN ){
  2812         -        codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
         2814  +        codeEqualityTerm(pWInfo, pTerm, pLevel, j, bRev, iTarget);
  2813   2815           addrNotFound = pLevel->addrNxt;
  2814   2816         }else{
  2815   2817           sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
  2816   2818         }
  2817   2819       }
  2818   2820       sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
  2819   2821       sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);
................................................................................
  2845   2847       assert( pLoop->u.btree.nEq==1 );
  2846   2848       iReleaseReg = sqlite3GetTempReg(pParse);
  2847   2849       pTerm = pLoop->aLTerm[0];
  2848   2850       assert( pTerm!=0 );
  2849   2851       assert( pTerm->pExpr!=0 );
  2850   2852       assert( omitTable==0 );
  2851   2853       testcase( pTerm->wtFlags & TERM_VIRTUAL );
  2852         -    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
         2854  +    iRowidReg = codeEqualityTerm(pWInfo, pTerm, pLevel, 0, bRev, iReleaseReg);
  2853   2855       addrNxt = pLevel->addrNxt;
  2854   2856       sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
  2855   2857       sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
  2856   2858       sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1);
  2857   2859       sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
  2858   2860       VdbeComment((v, "pk"));
  2859   2861       pLevel->op = OP_Noop;
................................................................................
  3035   3037         nExtraReg = 1;
  3036   3038       }
  3037   3039   
  3038   3040       /* Generate code to evaluate all constraint terms using == or IN
  3039   3041       ** and store the values of those terms in an array of registers
  3040   3042       ** starting at regBase.
  3041   3043       */
  3042         -    regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
         3044  +    regBase = codeAllEqualityTerms(pWInfo,pLevel,bRev,nExtraReg,&zStartAff);
  3043   3045       assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
  3044   3046       if( zStartAff ) cEndAff = zStartAff[nEq];
  3045   3047       addrNxt = pLevel->addrNxt;
  3046   3048   
  3047   3049       /* If we are doing a reverse order scan on an ascending index, or
  3048   3050       ** a forward order scan on a descending index, interchange the 
  3049   3051       ** start and end terms (pRangeStart and pRangeEnd).

Changes to test/in3.test.

    25     25   
    26     26   # Return the number of OpenEphemeral instructions used in the
    27     27   # implementation of the sql statement passed as a an argument.
    28     28   #
    29     29   proc nEphemeral {sql} {
    30     30     set nEph 0
    31     31     foreach op [execsql "EXPLAIN $sql"] {
    32         -    if {$op eq "OpenEphemeral"} {incr nEph}
           32  +    if {$op eq "OpenEphemeral" || $op eq "OpenHash"} {incr nEph}
    33     33     }
    34     34     set nEph
    35     35   }
    36     36   
    37     37   # This proc works the same way as execsql, except that the number
    38     38   # of OpenEphemeral instructions used in the implementation of the
    39     39   # statement is inserted into the start of the returned list.

Changes to test/in5.test.

    61     61   } {0}
    62     62   do_test in5-2.4 {
    63     63     execsql {
    64     64       SELECT d FROM t2 WHERE a IN t3x AND b IN t3y AND c IN t3z ORDER BY d;
    65     65     }
    66     66   } {12a 56e}
    67     67   do_test in5-2.5.1 {
    68         -  regexp {OpenEphemeral} [db eval {
           68  +  regexp {Open(Ephemeral|Hash)} [db eval {
    69     69       EXPLAIN SELECT d FROM t2 WHERE a IN t3x AND b IN t1y AND c IN t1z
    70     70     }]
    71     71   } {1}
    72     72   do_test in5-2.5.2 {
    73         -  regexp {OpenEphemeral} [db eval {
           73  +  regexp {Open(Ephemeral|Hash)} [db eval {
    74     74       EXPLAIN SELECT d FROM t2 WHERE a IN t1x AND b IN t3y AND c IN t1z
    75     75     }]
    76     76   } {1}
    77     77   do_test in5-2.5.3 {
    78         -  regexp {OpenEphemeral} [db eval {
           78  +  regexp {Open(Ephemeral|Hash)} [db eval {
    79     79       EXPLAIN SELECT d FROM t2 WHERE a IN t1x AND b IN t1y AND c IN t3z
    80     80     }]
    81     81   } {1}
    82     82   
    83     83   do_test in5-3.1 {
    84     84     execsql {
    85     85       DROP INDEX t2abc;