SQLite

Check-in [715fac7749]
Login

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: 715fac7749a6b1523fe9f7de8263f0c4d1571d07
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
Side-by-Side Diff Ignore Whitespace Patch
Changes to src/expr.c.
1505
1506
1507
1508
1509
1510
1511
1512


1513
1514
1515
1516
1517
1518
1519
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 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

1564

1565
1566
1567
1568
1569
1570
1571
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,
  addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid);
                           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
1727

1728
1729
1730
1731
1732
1733
1734
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 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
1820

1821
1822
1823
1824
1825
1826
1827
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);
    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
1946

1947
1948
1949
1950
1951
1952
1953
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);
  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
3481

3482
3483
3484
3485
3486
3487
3488
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 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
2351

2352
2353
2354
2355
2356
2357
2358
2359
2360




2361
2362
2363
2364
2365
2366
2367
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(
  Parse *pParse,      /* The parsing context */
  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;
  Vdbe *v = pParse->pVdbe;
  int iReg;                  /* Register holding results */
  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
2385

2386
2387
2388
2389
2390
2391
2392
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);
    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
2467

2468
2469
2470
2471
2472
2473
2474

2475
2476
2477
2478
2479
2480
2481
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(
  Parse *pParse,        /* Parsing context */
  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
2529

2530
2531
2532
2533
2534
2535
2536
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(pParse, pTerm, pLevel, j, bRev, regBase+j);
    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
2812

2813
2814
2815
2816
2817
2818
2819
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(pParse, pTerm, pLevel, j, bRev, iTarget);
        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
2852

2853
2854
2855
2856
2857
2858
2859
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(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
    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
3042

3043
3044
3045
3046
3047
3048
3049
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(pParse,pLevel,bRev,nExtraReg,&zStartAff);
    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
32

33
34
35
36
37
38
39
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"} {incr nEph}
    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
68

69
70
71
72
73

74
75
76
77
78

79
80
81
82
83
84
85
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 {OpenEphemeral} [db eval {
  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 {OpenEphemeral} [db eval {
  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 {OpenEphemeral} [db eval {
  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;