SQLite

Changes On Branch reuse-subqueries
Login

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

Changes In Branch reuse-subqueries Excluding Merge-Ins

This is equivalent to a diff from f856676c to 4fcdc7a2

2018-12-31
20:39
Additional steps to help ensure that scalar subqueries are only evaluated once even if they are used in multiple places within the query. This fixes a performance regression reported on the mailing list and caused by check-in [531eca6104e41e43] which was a fix for ticket [787fa716be3a7f650c]. Think of this check-in as an improved fix for that ticket. (check-in: e1303193 user: drh tags: trunk)
20:13
Remove an optimization that can no longer occur, being superceded by the subquery-reuse optimization. Put an assert in place of the optimization to detect if the need for this optimization ever returns. (Closed-Leaf check-in: 4fcdc7a2 user: drh tags: reuse-subqueries)
18:30
Merge enhancements and bug fixes from trunk. (check-in: 9fb646f2 user: drh tags: reuse-subqueries)
17:58
Small changes to the OP_OpenEphemeral opcode to improve testability. (check-in: f856676c user: drh tags: trunk)
16:36
Fix the OP_OpenEphemeral opcode in the bytecode engine so that if it is called a second or subsequent time, it merely clears the existing table rather than creating a new one. Proposed fix for ticket [d0866b26f83e9c55e30de0821f5d]. (check-in: 4678cb10 user: drh tags: trunk)

Changes to ext/expert/expert1.test.

239
240
241
242
243
244
245

246
247



248
249
250
251
252
253
254
239
240
241
242
243
244
245
246


247
248
249
250
251
252
253
254
255
256







+
-
-
+
+
+







  CREATE TABLE t7(a, b);
} {
  SELECT * FROM t7 WHERE a=? OR b=?
} {
  CREATE INDEX t7_idx_00000062 ON t7(b);
  CREATE INDEX t7_idx_00000061 ON t7(a);
  MULTI-INDEX OR
    INDEX 1
    SEARCH TABLE t7 USING INDEX t7_idx_00000061 (a=?) 
    SEARCH TABLE t7 USING INDEX t7_idx_00000062 (b=?)
      SEARCH TABLE t7 USING INDEX t7_idx_00000061 (a=?) 
    INDEX 2
      SEARCH TABLE t7 USING INDEX t7_idx_00000062 (b=?)
}

# rowid terms.
#
do_setup_rec_test $tn.13.1 {
  CREATE TABLE t8(a, b);
} {

Changes to src/expr.c.

2346
2347
2348
2349
2350
2351
2352
2353


2354
2355
2356
2357
2358
2359
2360
2346
2347
2348
2349
2350
2351
2352

2353
2354
2355
2356
2357
2358
2359
2360
2361







-
+
+







*/
#ifndef SQLITE_OMIT_SUBQUERY
int sqlite3FindInIndex(
  Parse *pParse,             /* Parsing context */
  Expr *pX,                  /* The right-hand side (RHS) of the IN operator */
  u32 inFlags,               /* IN_INDEX_LOOP, _MEMBERSHIP, and/or _NOOP_OK */
  int *prRhsHasNull,         /* Register holding NULL status.  See notes */
  int *aiMap                 /* Mapping from Index fields to RHS fields */
  int *aiMap,                /* Mapping from Index fields to RHS fields */
  int *piTab                 /* OUT: index to use */
){
  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;                     /* True if RHS must be unique */
  Vdbe *v = sqlite3GetVdbe(pParse);     /* Virtual machine being coded */

2539
2540
2541
2542
2543
2544
2545
2546

2547
2548

2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559

2560
2561
2562
2563
2564
2565
2566
2540
2541
2542
2543
2544
2545
2546

2547
2548

2549
2550
2551


2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566







-
+

-
+


-
-







+







      if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){
        eType = IN_INDEX_ROWID;
      }
    }else if( prRhsHasNull ){
      *prRhsHasNull = rMayHaveNull = ++pParse->nMem;
    }
    assert( pX->op==TK_IN );
    sqlite3CodeRhsOfIN(pParse, pX, eType==IN_INDEX_ROWID);
    sqlite3CodeRhsOfIN(pParse, pX, iTab, eType==IN_INDEX_ROWID);
    if( rMayHaveNull ){
      sqlite3SetHasNullFlag(v, pX->iTable, rMayHaveNull);
      sqlite3SetHasNullFlag(v, iTab, rMayHaveNull);
    }
    pParse->nQueryLoop = savedNQueryLoop;
  }else{
    pX->iTable = iTab;
  }

  if( aiMap && eType!=IN_INDEX_INDEX_ASC && eType!=IN_INDEX_INDEX_DESC ){
    int i, n;
    n = sqlite3ExprVectorSize(pX->pLeft);
    for(i=0; i<n; i++) aiMap[i] = i;
  }
  *piTab = iTab;
  return eType;
}
#endif

#ifndef SQLITE_OMIT_SUBQUERY
/*
** Argument pExpr is an (?, ?...) IN(...) expression. This 
2635
2636
2637
2638
2639
2640
2641
2642





2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660

2661
2662
2663

2664
2665
2666
2667
2668
2669
2670

2671
2672
2673

2674
2675
2676
2677
2678
2679
2680
2681


2682
2683
2684


























2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695

2696
2697







2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710


2711
2712
2713
2714
2715
2716
2717
2718

2719
2720
2721
2722
2723
2724
2725
2635
2636
2637
2638
2639
2640
2641

2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667

2668
2669
2670
2671
2672
2673
2674

2675
2676
2677

2678
2679
2680
2681
2682
2683
2684


2685
2686
2687


2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723

2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744


2745
2746
2747
2748
2749
2750
2751
2752
2753

2754
2755
2756
2757
2758
2759
2760
2761







-
+
+
+
+
+


















+


-
+






-
+


-
+






-
-
+
+

-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+










-
+


+
+
+
+
+
+
+











-
-
+
+







-
+







** Generate code that will construct an ephemeral table containing all terms
** in the RHS of an IN operator.  The IN operator can be in either of two
** forms:
**
**     x IN (4,5,11)              -- IN operator with list on right-hand side
**     x IN (SELECT a FROM b)     -- IN operator with subquery on the right
**
** The pExpr parameter is the IN operator.
** The pExpr parameter is the IN operator.  The cursor number for the
** constructed ephermeral table is returned.  The first time the ephemeral
** table is computed, the cursor number is also stored in pExpr->iTable,
** however the cursor number returned might not be the same, as it might
** have been duplicated using OP_OpenDup.
**
** If parameter isRowid is non-zero, then LHS of the IN operator is guaranteed
** to be a non-null integer. In this case, the ephemeral table can be an
** table B-Tree that keyed by only integers.  The more general cases uses
** an index B-Tree which can have arbitrary keys, but is slower to both
** read and write.
**
** If the LHS expression ("x" in the examples) is a column value, or
** the SELECT statement returns a column value, then the affinity of that
** 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.
*/
void sqlite3CodeRhsOfIN(
  Parse *pParse,          /* Parsing context */
  Expr *pExpr,            /* The IN operator */
  int iTab,               /* Use this cursor number */
  int isRowid             /* If true, LHS is a rowid */
){
  int jmpIfDynamic = -1;      /* One-time test address */
  int addrOnce = 0;           /* Address of the OP_Once instruction at top */
  int addr;                   /* Address of OP_OpenEphemeral instruction */
  Expr *pLeft;                /* the LHS of the IN operator */
  KeyInfo *pKeyInfo = 0;      /* Key information */
  int nVal;                   /* Size of vector pLeft */
  Vdbe *v;                    /* The prepared statement under construction */

  v = sqlite3GetVdbe(pParse);
  v = pParse->pVdbe;
  assert( v!=0 );

  /* The evaluation of the RHS of IN operator must be repeated every time it
  /* The evaluation of the IN must be repeated every time it
  ** is encountered if any of the following is true:
  **
  **    *  The right-hand side is a correlated subquery
  **    *  The right-hand side is an expression list containing variables
  **    *  We are inside a trigger
  **
  ** If all of the above are false, then we can run this code just once
  ** save the results, and reuse the same result on subsequent invocations.
  ** If all of the above are false, then we can compute the RHS just once
  ** and reuse it many names.
  */
  if( !ExprHasProperty(pExpr, EP_VarSelect) ){
    jmpIfDynamic = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
  if( !ExprHasProperty(pExpr, EP_VarSelect) && pParse->iSelfTab==0 ){
    /* Reuse of the RHS is allowed */
    /* If this routine has already been coded, but the previous code
    ** might not have been invoked yet, so invoke it now as a subroutine. 
    */
    if( ExprHasProperty(pExpr, EP_Subrtn) ){
      int addr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
      if( ExprHasProperty(pExpr, EP_xIsSelect) ){
        ExplainQueryPlan((pParse, 0, "REUSE LIST SUBQUERY %d",
              pExpr->x.pSelect->selId));
      }
      sqlite3VdbeAddOp2(v, OP_Gosub, pExpr->y.sub.regReturn,
                        pExpr->y.sub.iAddr);
      sqlite3VdbeAddOp2(v, OP_OpenDup, iTab, pExpr->iTable);
      sqlite3VdbeJumpHere(v, addr);
      return;
    }

    /* Begin coding the subroutine */
    ExprSetProperty(pExpr, EP_Subrtn);
    pExpr->y.sub.regReturn = ++pParse->nMem;
    pExpr->y.sub.iAddr =
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pExpr->y.sub.regReturn) + 1;
    VdbeComment((v, "return address"));

    addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
  }

  /* Check to see if this is a vector IN operator */
  pLeft = pExpr->pLeft;
  nVal = sqlite3ExprVectorSize(pLeft);
  assert( !isRowid || nVal==1 );

  /* Construct the ephemeral table that will contain the content of
  ** RHS of the IN operator.
  */
  pExpr->iTable = pParse->nTab++;
  pExpr->iTable = iTab;
  addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, 
      pExpr->iTable, (isRowid?0:nVal));
#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS
  if( ExprHasProperty(pExpr, EP_xIsSelect) ){
    VdbeComment((v, "Result of SELECT %u", pExpr->x.pSelect->selId));
  }else{
    VdbeComment((v, "RHS of IN operator"));
  }
#endif
  pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, nVal, 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.
    */
    Select *pSelect = pExpr->x.pSelect;
    ExprList *pEList = pSelect->pEList;

    ExplainQueryPlan((pParse, 1, "%sLIST SUBQUERY",
        jmpIfDynamic>=0?"":"CORRELATED "
    ExplainQueryPlan((pParse, 1, "%sLIST SUBQUERY %d",
        addrOnce?"":"CORRELATED ", pSelect->selId
    ));
    assert( !isRowid );
    /* If the LHS and RHS of the IN operator do not match, that
    ** error will have been caught long before we reach this point. */
    if( ALWAYS(pEList->nExpr==nVal) ){
      SelectDest dest;
      int i;
      sqlite3SelectDestInit(&dest, SRT_Set, pExpr->iTable);
      sqlite3SelectDestInit(&dest, SRT_Set, iTab);
      dest.zAffSdst = exprINAffinity(pParse, pExpr);
      pSelect->iLimit = 0;
      testcase( pSelect->selFlags & SF_Distinct );
      testcase( pKeyInfo==0 ); /* Caused by OOM in sqlite3KeyInfoAlloc() */
      if( sqlite3Select(pParse, pSelect, &dest) ){
        sqlite3DbFree(pParse->db, dest.zAffSdst);
        sqlite3KeyInfoUnref(pKeyInfo);
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777



2778
2779
2780
2781
2782

2783
2784
2785
2786
2787
2788
2789

2790
2791
2792

2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803





2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824

2825
2826
2827
2828
2829

2830

2831





2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
















2844

2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864


2865
2866
2867
2868
2869
2870
2871
2804
2805
2806
2807
2808
2809
2810



2811
2812
2813
2814
2815
2816
2817

2818
2819
2820
2821
2822
2823
2824

2825
2826
2827

2828
2829
2830
2831
2832
2833
2834
2835
2836
2837


2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862

2863
2864
2865
2866
2867
2868
2869

2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904

2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917








2918
2919
2920
2921
2922
2923
2924
2925
2926







-
-
-
+
+
+




-
+






-
+


-
+









-
-
+
+
+
+
+




















-
+





+
-
+

+
+
+
+
+












+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
+












-
-
-
-
-
-
-
-
+
+







      int iValToIns;

      /* If the expression is not constant then we will need to
      ** disable the test that was generated above that makes sure
      ** this code only executes once.  Because for a non-constant
      ** expression we need to rerun this code each time.
      */
      if( jmpIfDynamic>=0 && !sqlite3ExprIsConstant(pE2) ){
        sqlite3VdbeChangeToNoop(v, jmpIfDynamic);
        jmpIfDynamic = -1;
      if( addrOnce && !sqlite3ExprIsConstant(pE2) ){
        sqlite3VdbeChangeToNoop(v, addrOnce);
        addrOnce = 0;
      }

      /* Evaluate the expression and insert it into the temp table */
      if( isRowid && sqlite3ExprIsInteger(pE2, &iValToIns) ){
        sqlite3VdbeAddOp3(v, OP_InsertInt, pExpr->iTable, r2, iValToIns);
        sqlite3VdbeAddOp3(v, OP_InsertInt, iTab, r2, iValToIns);
      }else{
        r3 = sqlite3ExprCodeTarget(pParse, pE2, r1);
        if( isRowid ){
          sqlite3VdbeAddOp2(v, OP_MustBeInt, r3,
                            sqlite3VdbeCurrentAddr(v)+2);
          VdbeCoverage(v);
          sqlite3VdbeAddOp3(v, OP_Insert, pExpr->iTable, r2, r3);
          sqlite3VdbeAddOp3(v, OP_Insert, iTab, r2, r3);
        }else{
          sqlite3VdbeAddOp4(v, OP_MakeRecord, r3, 1, r2, &affinity, 1);
          sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pExpr->iTable, r2, r3, 1);
          sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iTab, r2, r3, 1);
        }
      }
    }
    sqlite3ReleaseTempReg(pParse, r1);
    sqlite3ReleaseTempReg(pParse, r2);
  }
  if( pKeyInfo ){
    sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo, P4_KEYINFO);
  }
  if( jmpIfDynamic>=0 ){
    sqlite3VdbeJumpHere(v, jmpIfDynamic);
  if( addrOnce ){
    sqlite3VdbeJumpHere(v, addrOnce);
    /* Subroutine return */
    sqlite3VdbeAddOp1(v, OP_Return, pExpr->y.sub.regReturn);
    sqlite3VdbeChangeP1(v, pExpr->y.sub.iAddr-1, sqlite3VdbeCurrentAddr(v)-1);
  }
}
#endif /* SQLITE_OMIT_SUBQUERY */

/*
** Generate code for scalar subqueries used as a subquery expression
** or EXISTS operator:
**
**     (SELECT a FROM b)          -- subquery
**     EXISTS (SELECT a FROM b)   -- EXISTS subquery
**
** The pExpr parameter is the SELECT or EXISTS operator to be coded.
**
** The register that holds the result.  For a multi-column SELECT, 
** the result is stored in a contiguous array of registers and the
** return value is the register of the left-most result column.
** Return 0 if an error occurs.
*/
#ifndef SQLITE_OMIT_SUBQUERY
int sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){
  int jmpIfDynamic = -1;      /* One-time test address */
  int addrOnce = 0;           /* Address of OP_Once at top of subroutine */
  int rReg = 0;               /* Register storing resulting */
  Select *pSel;               /* SELECT statement to encode */
  SelectDest dest;            /* How to deal with SELECT result */
  int nReg;                   /* Registers to allocate */
  Expr *pLimit;               /* New limit expression */

  Vdbe *v = sqlite3GetVdbe(pParse);
  Vdbe *v = pParse->pVdbe;
  assert( v!=0 );
  testcase( pExpr->op==TK_EXISTS );
  testcase( pExpr->op==TK_SELECT );
  assert( pExpr->op==TK_EXISTS || pExpr->op==TK_SELECT );
  assert( ExprHasProperty(pExpr, EP_xIsSelect) );
  pSel = pExpr->x.pSelect;

  /* The evaluation of the EXISTS/SELECT must be repeated every time it
  ** is encountered if any of the following is true:
  **
  **    *  The right-hand side is a correlated subquery
  **    *  The right-hand side is an expression list containing variables
  **    *  We are inside a trigger
  **
  ** If all of the above are false, then we can run this code just once
  ** save the results, and reuse the same result on subsequent invocations.
  */
  if( !ExprHasProperty(pExpr, EP_VarSelect) ){
    /* If this routine has already been coded, then invoke it as a
    ** subroutine. */
    if( ExprHasProperty(pExpr, EP_Subrtn) ){
      ExplainQueryPlan((pParse, 0, "REUSE SUBQUERY %d", pSel->selId));
      sqlite3VdbeAddOp2(v, OP_Gosub, pExpr->y.sub.regReturn,
                        pExpr->y.sub.iAddr);
      return pExpr->iTable;
    }

    /* Begin coding the subroutine */
    ExprSetProperty(pExpr, EP_Subrtn);
    pExpr->y.sub.regReturn = ++pParse->nMem;
    pExpr->y.sub.iAddr =
      sqlite3VdbeAddOp2(v, OP_Integer, 0, pExpr->y.sub.regReturn) + 1;
    VdbeComment((v, "return address"));

    jmpIfDynamic = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
    addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
  }
  
  /* For a SELECT, generate code to put the values for all columns of
  ** the first row into an array of registers and return the index of
  ** the first register.
  **
  ** If this is an EXISTS, write an integer 0 (not exists) or 1 (exists)
  ** into a register and return that register number.
  **
  ** In both cases, the query is augmented with "LIMIT 1".  Any 
  ** preexisting limit is discarded in place of the new LIMIT 1.
  */
  testcase( pExpr->op==TK_EXISTS );
  testcase( pExpr->op==TK_SELECT );
  assert( pExpr->op==TK_EXISTS || pExpr->op==TK_SELECT );
  assert( ExprHasProperty(pExpr, EP_xIsSelect) );

  pSel = pExpr->x.pSelect;
  ExplainQueryPlan((pParse, 1, "%sSCALAR SUBQUERY",
        jmpIfDynamic>=0?"":"CORRELATED "));
  ExplainQueryPlan((pParse, 1, "%sSCALAR SUBQUERY %d",
        addrOnce?"":"CORRELATED ", pSel->selId));
  nReg = pExpr->op==TK_SELECT ? pSel->pEList->nExpr : 1;
  sqlite3SelectDestInit(&dest, 0, pParse->nMem+1);
  pParse->nMem += nReg;
  if( pExpr->op==TK_SELECT ){
    dest.eDest = SRT_Mem;
    dest.iSdst = dest.iSDParm;
    dest.nSdst = nReg;
2883
2884
2885
2886
2887
2888
2889
2890

2891


2892
2893
2894



2895
2896
2897
2898
2899
2900
2901
2938
2939
2940
2941
2942
2943
2944

2945
2946
2947
2948
2949


2950
2951
2952
2953
2954
2955
2956
2957
2958
2959







-
+

+
+

-
-
+
+
+







  }else{
    pSel->pLimit = sqlite3PExpr(pParse, TK_LIMIT, pLimit, 0);
  }
  pSel->iLimit = 0;
  if( sqlite3Select(pParse, pSel, &dest) ){
    return 0;
  }
  rReg = dest.iSDParm;
  pExpr->iTable = rReg = dest.iSDParm;
  ExprSetVVAProperty(pExpr, EP_NoReduce);
  if( addrOnce ){
    sqlite3VdbeJumpHere(v, addrOnce);

  if( jmpIfDynamic>=0 ){
    sqlite3VdbeJumpHere(v, jmpIfDynamic);
    /* Subroutine return */
    sqlite3VdbeAddOp1(v, OP_Return, pExpr->y.sub.regReturn);
    sqlite3VdbeChangeP1(v, pExpr->y.sub.iAddr-1, sqlite3VdbeCurrentAddr(v)-1);
  }

  return rReg;
}
#endif /* SQLITE_OMIT_SUBQUERY */

#ifndef SQLITE_OMIT_SUBQUERY
2964
2965
2966
2967
2968
2969
2970

2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982

2983
2984
2985
2986
2987
2988
2989
2990


2991
2992
2993
2994
2995
2996
2997
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040

3041
3042
3043
3044
3045
3046
3047
3048

3049
3050
3051
3052
3053
3054
3055
3056
3057







+











-
+







-
+
+







  Expr *pLeft;          /* The LHS of the IN operator */
  int i;                /* loop counter */
  int destStep2;        /* Where to jump when NULLs seen in step 2 */
  int destStep6 = 0;    /* Start of code for Step 6 */
  int addrTruthOp;      /* Address of opcode that determines the IN is true */
  int destNotNull;      /* Jump here if a comparison is not true in step 6 */
  int addrTop;          /* Top of the step-6 loop */ 
  int iTab = 0;         /* Index to use */

  pLeft = pExpr->pLeft;
  if( sqlite3ExprCheckIN(pParse, pExpr) ) return;
  zAff = exprINAffinity(pParse, pExpr);
  nVector = sqlite3ExprVectorSize(pExpr->pLeft);
  aiMap = (int*)sqlite3DbMallocZero(
      pParse->db, nVector*(sizeof(int) + sizeof(char)) + 1
  );
  if( pParse->db->mallocFailed ) goto sqlite3ExprCodeIN_oom_error;

  /* Attempt to compute the RHS. After this step, if anything other than
  ** IN_INDEX_NOOP is returned, the table opened ith cursor pExpr->iTable 
  ** IN_INDEX_NOOP is returned, the table opened with cursor iTab
  ** contains the values that make up the RHS. If IN_INDEX_NOOP is returned,
  ** the RHS has not yet been coded.  */
  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, aiMap);
                             destIfFalse==destIfNull ? 0 : &rRhsHasNull,
                             aiMap, &iTab);

  assert( pParse->nErr || nVector==1 || eType==IN_INDEX_EPH
       || eType==IN_INDEX_INDEX_ASC || eType==IN_INDEX_INDEX_DESC 
  );
#ifdef SQLITE_DEBUG
  /* Confirm that aiMap[] contains nVector integer values between 0 and
  ** nVector-1. */
3091
3092
3093
3094
3095
3096
3097
3098

3099
3100
3101
3102
3103
3104
3105

3106
3107
3108
3109
3110

3111
3112
3113
3114
3115
3116
3117
3151
3152
3153
3154
3155
3156
3157

3158
3159
3160
3161
3162
3163
3164

3165
3166
3167
3168
3169

3170
3171
3172
3173
3174
3175
3176
3177







-
+






-
+




-
+







  ** of the RHS using the LHS as a probe.  If found, the result is
  ** true.
  */
  if( eType==IN_INDEX_ROWID ){
    /* In this case, the RHS is the ROWID of table b-tree and so we also
    ** know that the RHS is non-NULL.  Hence, we combine steps 3 and 4
    ** into a single opcode. */
    sqlite3VdbeAddOp3(v, OP_SeekRowid, pExpr->iTable, destIfFalse, rLhs);
    sqlite3VdbeAddOp3(v, OP_SeekRowid, iTab, destIfFalse, rLhs);
    VdbeCoverage(v);
    addrTruthOp = sqlite3VdbeAddOp0(v, OP_Goto);  /* Return True */
  }else{
    sqlite3VdbeAddOp4(v, OP_Affinity, rLhs, nVector, 0, zAff, nVector);
    if( destIfFalse==destIfNull ){
      /* Combine Step 3 and Step 5 into a single opcode */
      sqlite3VdbeAddOp4Int(v, OP_NotFound, pExpr->iTable, destIfFalse,
      sqlite3VdbeAddOp4Int(v, OP_NotFound, iTab, destIfFalse,
                           rLhs, nVector); VdbeCoverage(v);
      goto sqlite3ExprCodeIN_finished;
    }
    /* Ordinary Step 3, for the case where FALSE and NULL are distinct */
    addrTruthOp = sqlite3VdbeAddOp4Int(v, OP_Found, pExpr->iTable, 0,
    addrTruthOp = sqlite3VdbeAddOp4Int(v, OP_Found, iTab, 0,
                                      rLhs, nVector); VdbeCoverage(v);
  }

  /* Step 4.  If the RHS is known to be non-NULL and we did not find
  ** an match on the search above, then the result must be FALSE.
  */
  if( rRhsHasNull && nVector==1 ){
3128
3129
3130
3131
3132
3133
3134
3135

3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150

3151
3152
3153
3154
3155
3156
3157
3158
3159

3160
3161
3162
3163
3164
3165
3166
3188
3189
3190
3191
3192
3193
3194

3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209

3210
3211
3212
3213
3214
3215
3216
3217
3218

3219
3220
3221
3222
3223
3224
3225
3226







-
+














-
+








-
+







  ** If any comparison is NULL, then the result is NULL.  If all
  ** comparisons are FALSE then the final result is FALSE.
  **
  ** For a scalar LHS, it is sufficient to check just the first row
  ** of the RHS.
  */
  if( destStep6 ) sqlite3VdbeResolveLabel(v, destStep6);
  addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse);
  addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, destIfFalse);
  VdbeCoverage(v);
  if( nVector>1 ){
    destNotNull = sqlite3VdbeMakeLabel(pParse);
  }else{
    /* For nVector==1, combine steps 6 and 7 by immediately returning
    ** FALSE if the first comparison is not NULL */
    destNotNull = destIfFalse;
  }
  for(i=0; i<nVector; i++){
    Expr *p;
    CollSeq *pColl;
    int r3 = sqlite3GetTempReg(pParse);
    p = sqlite3VectorFieldSubexpr(pLeft, i);
    pColl = sqlite3ExprCollSeq(pParse, p);
    sqlite3VdbeAddOp3(v, OP_Column, pExpr->iTable, i, r3);
    sqlite3VdbeAddOp3(v, OP_Column, iTab, i, r3);
    sqlite3VdbeAddOp4(v, OP_Ne, rLhs+i, destNotNull, r3,
                      (void*)pColl, P4_COLLSEQ);
    VdbeCoverage(v);
    sqlite3ReleaseTempReg(pParse, r3);
  }
  sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfNull);
  if( nVector>1 ){
    sqlite3VdbeResolveLabel(v, destNotNull);
    sqlite3VdbeAddOp2(v, OP_Next, pExpr->iTable, addrTop+1);
    sqlite3VdbeAddOp2(v, OP_Next, iTab, addrTop+1);
    VdbeCoverage(v);

    /* Step 7:  If we reach this point, we know that the result must
    ** be false. */
    sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfFalse);
  }

Changes to src/select.c.

5831
5832
5833
5834
5835
5836
5837
5838
5839
5840
5841




5842
5843
5844


5845
5846
5847
5848
5849
5850
5851
5852
5853
5854
5855
5856
5857
5858
5859
5860
5831
5832
5833
5834
5835
5836
5837




5838
5839
5840
5841



5842
5843









5844
5845
5846
5847
5848
5849
5850







-
-
-
-
+
+
+
+
-
-
-
+
+
-
-
-
-
-
-
-
-
-








#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
    /* Generate code for all sub-queries in the FROM clause
    */
    pSub = pItem->pSelect;
    if( pSub==0 ) continue;

    /* Sometimes the code for a subquery will be generated more than
    ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
    ** for example.  In that case, do not regenerate the code to manifest
    ** a view or the co-routine to implement a view.  The first instance
    /* The code for a subquery should only be generated once, though it is
    ** technically harmless for it to be generated multiple times. The
    ** following assert() will detect if something changes to cause
    ** the same subquery to be coded multiple times, as a signal to the
    ** is sufficient, though the subroutine to manifest the view does need
    ** to be invoked again. */
    if( pItem->addrFillSub ){
    ** developers to try to optimize the situation. */
    assert( pItem->addrFillSub==0 );
      if( pItem->fg.viaCoroutine==0 ){
        /* The subroutine that manifests the view might be a one-time routine,
        ** or it might need to be rerun on each iteration because it
        ** encodes a correlated subquery. */
        testcase( sqlite3VdbeGetOp(v, pItem->addrFillSub)->opcode==OP_Once );
        sqlite3VdbeAddOp2(v, OP_Gosub, pItem->regReturn, pItem->addrFillSub);
      }
      continue;
    }

    /* Increment Parse.nHeight by the height of the largest expression
    ** tree referred to by this, the parent select. The child select
    ** may contain expression trees of at most
    ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit
    ** more conservative than necessary, but much easier than enforcing
    ** an exact limit.

Changes to src/sqliteInt.h.

2481
2482
2483
2484
2485
2486
2487




2488
2489
2490
2491
2492
2493
2494
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498







+
+
+
+







                         ** TK_COLUMN: the value of p5 for OP_Column
                         ** TK_AGG_FUNCTION: nesting depth */
  AggInfo *pAggInfo;     /* Used by TK_AGG_COLUMN and TK_AGG_FUNCTION */
  union {
    Table *pTab;           /* TK_COLUMN: Table containing column. Can be NULL
                           ** for a column of an index on an expression */
    Window *pWin;          /* TK_FUNCTION: Window definition for the func */
    struct {               /* TK_IN, TK_SELECT, and TK_EXISTS */
      int iAddr;             /* Subroutine entry address */
      int regReturn;         /* Register used to hold return address */
    } sub;
  } y;
};

/*
** The following are the meanings of bits in the Expr.flags field.
*/
#define EP_FromJoin  0x000001 /* Originates in ON/USING clause of outer join */
2512
2513
2514
2515
2516
2517
2518

2519
2520
2521
2522
2523
2524
2525
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530







+







#define EP_Unlikely  0x040000 /* unlikely() or likelihood() function */
#define EP_ConstFunc 0x080000 /* A SQLITE_FUNC_CONSTANT or _SLOCHNG function */
#define EP_CanBeNull 0x100000 /* Can be null despite NOT NULL constraint */
#define EP_Subquery  0x200000 /* Tree contains a TK_SELECT operator */
#define EP_Alias     0x400000 /* Is an alias for a result set column */
#define EP_Leaf      0x800000 /* Expr.pLeft, .pRight, .u.pSelect all NULL */
#define EP_WinFunc  0x1000000 /* TK_FUNCTION with Expr.y.pWin set */
#define EP_Subrtn   0x2000000 /* Uses Expr.y.sub. TK_IN, _SELECT, or _EXISTS */

/*
** The EP_Propagate mask is a set of properties that automatically propagate
** upwards into parent nodes.
*/
#define EP_Propagate (EP_Collate|EP_Subquery|EP_HasFunc)

4254
4255
4256
4257
4258
4259
4260
4261

4262
4263
4264
4265
4266
4267
4268
4259
4260
4261
4262
4263
4264
4265

4266
4267
4268
4269
4270
4271
4272
4273







-
+







void sqlite3Reindex(Parse*, Token*, Token*);
void sqlite3AlterFunctions(void);
void sqlite3AlterRenameTable(Parse*, SrcList*, Token*);
void sqlite3AlterRenameColumn(Parse*, SrcList*, Token*, Token*);
int sqlite3GetToken(const unsigned char *, int *);
void sqlite3NestedParse(Parse*, const char*, ...);
void sqlite3ExpirePreparedStatements(sqlite3*, int);
void sqlite3CodeRhsOfIN(Parse*, Expr*, int);
void sqlite3CodeRhsOfIN(Parse*, Expr*, int, int);
int sqlite3CodeSubselect(Parse*, Expr*);
void sqlite3SelectPrep(Parse*, Select*, NameContext*);
void sqlite3SelectWrongNumTermsError(Parse *pParse, Select *p);
int sqlite3MatchSpanName(const char*, const char*, const char*, const char*);
int sqlite3ResolveExprNames(NameContext*, Expr*);
int sqlite3ResolveExprListNames(NameContext*, ExprList*);
void sqlite3ResolveSelectNames(Parse*, Select*, NameContext*);
4507
4508
4509
4510
4511
4512
4513
4514

4515
4516
4517
4518
4519
4520
4521
4512
4513
4514
4515
4516
4517
4518

4519
4520
4521
4522
4523
4524
4525
4526







-
+







#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*, int*);
int sqlite3FindInIndex(Parse *, Expr *, u32, int*, int*, int*);

int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int);
int sqlite3JournalSize(sqlite3_vfs *);
#if defined(SQLITE_ENABLE_ATOMIC_WRITE) \
 || defined(SQLITE_ENABLE_BATCH_ATOMIC_WRITE)
  int sqlite3JournalCreate(sqlite3_file *);
#endif

Changes to src/vdbe.c.

3606
3607
3608
3609
3610
3611
3612

3613

3614
3615
3616
3617
3618
3619
3620
3606
3607
3608
3609
3610
3611
3612
3613

3614
3615
3616
3617
3618
3619
3620
3621







+
-
+








  pCx = allocateCursor(p, pOp->p1, pOrig->nField, -1, CURTYPE_BTREE);
  if( pCx==0 ) goto no_mem;
  pCx->nullRow = 1;
  pCx->isEphemeral = 1;
  pCx->pKeyInfo = pOrig->pKeyInfo;
  pCx->isTable = pOrig->isTable;
  pCx->pgnoRoot = pOrig->pgnoRoot;
  rc = sqlite3BtreeCursor(pOrig->pBtx, MASTER_ROOT, BTREE_WRCSR,
  rc = sqlite3BtreeCursor(pOrig->pBtx, pCx->pgnoRoot, BTREE_WRCSR,
                          pCx->pKeyInfo, pCx->uc.pCursor);
  /* The sqlite3BtreeCursor() routine can only fail for the first cursor
  ** opened for a database.  Since there is already an open cursor when this
  ** opcode is run, the sqlite3BtreeCursor() cannot fail */
  assert( rc==SQLITE_OK );
  break;
}

Changes to src/vdbe.h.

203
204
205
206
207
208
209

210
211
212
213
214
215
216






217
218
219
220
221
222
223
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230







+







+
+
+
+
+
+







# define sqlite3VdbeVerifyAbortable(A,B)
#endif
VdbeOp *sqlite3VdbeAddOpList(Vdbe*, int nOp, VdbeOpList const *aOp,int iLineno);
#ifndef SQLITE_OMIT_EXPLAIN
  void sqlite3VdbeExplain(Parse*,u8,const char*,...);
  void sqlite3VdbeExplainPop(Parse*);
  int sqlite3VdbeExplainParent(Parse*);
  void sqlite3ExplainBreakpoint(const char*,const char*);
# define ExplainQueryPlan(P)        sqlite3VdbeExplain P
# define ExplainQueryPlanPop(P)     sqlite3VdbeExplainPop(P)
# define ExplainQueryPlanParent(P)  sqlite3VdbeExplainParent(P)
#else
# define ExplainQueryPlan(P)
# define ExplainQueryPlanPop(P)
# define ExplainQueryPlanParent(P) 0
# define sqlite3ExplainBreakpoint(A,B) /*no-op*/
#endif
#if defined(SQLITE_DEBUG) && !defined(SQLITE_OMIT_EXPLAIN)
  void sqlite3ExplainBreakpoint(const char*,const char*);
#else
# define sqlite3ExplainBreakpoint(A,B) /*no-op*/
#endif
void sqlite3VdbeAddParseSchemaOp(Vdbe*,int,char*);
void sqlite3VdbeChangeOpcode(Vdbe*, u32 addr, u8);
void sqlite3VdbeChangeP1(Vdbe*, u32 addr, int P1);
void sqlite3VdbeChangeP2(Vdbe*, u32 addr, int P2);
void sqlite3VdbeChangeP3(Vdbe*, u32 addr, int P3);
void sqlite3VdbeChangeP5(Vdbe*, u16 P5);

Changes to src/vdbeaux.c.

346
347
348
349
350
351
352











353

354
355
356
357
358
359
360
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363

364
365
366
367
368
369
370
371







+
+
+
+
+
+
+
+
+
+
+
-
+







  VdbeOp *pOp;
  if( pParse->addrExplain==0 ) return 0;
  pOp = sqlite3VdbeGetOp(pParse->pVdbe, pParse->addrExplain);
  return pOp->p2;
}

/*
** Set a debugger breakpoint on the following routine in order to
** monitor the EXPLAIN QUERY PLAN code generation.
*/
#if defined(SQLITE_DEBUG)
void sqlite3ExplainBreakpoint(const char *z1, const char *z2){
  (void)z1;
  (void)z2;
}
#endif

/*
** Add a new OP_Explain opcode.
** Add a new OP_ opcode.
**
** If the bPush flag is true, then make this opcode the parent for
** subsequent Explains until sqlite3VdbeExplainPop() is called.
*/
void sqlite3VdbeExplain(Parse *pParse, u8 bPush, const char *zFmt, ...){
#ifndef SQLITE_DEBUG
  /* Always include the OP_Explain opcodes if SQLITE_DEBUG is defined.
369
370
371
372
373
374
375


376


377
378
379
380
381
382
383

384
385
386
387
388
389
390
380
381
382
383
384
385
386
387
388

389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405







+
+
-
+
+







+







    va_start(ap, zFmt);
    zMsg = sqlite3VMPrintf(pParse->db, zFmt, ap);
    va_end(ap);
    v = pParse->pVdbe;
    iThis = v->nOp;
    sqlite3VdbeAddOp4(v, OP_Explain, iThis, pParse->addrExplain, 0,
                      zMsg, P4_DYNAMIC);
    sqlite3ExplainBreakpoint(bPush?"PUSH":"", sqlite3VdbeGetOp(v,-1)->p4.z);
    if( bPush){
    if( bPush) pParse->addrExplain = iThis;
      pParse->addrExplain = iThis;
    }
  }
}

/*
** Pop the EXPLAIN QUERY PLAN stack one level.
*/
void sqlite3VdbeExplainPop(Parse *pParse){
  sqlite3ExplainBreakpoint("POP", 0);
  pParse->addrExplain = sqlite3VdbeExplainParent(pParse);
}
#endif /* SQLITE_OMIT_EXPLAIN */

/*
** Add an OP_ParseSchema opcode.  This routine is broken out from
** sqlite3VdbeAddOp4() since it needs to also needs to mark all btrees

Changes to src/where.c.

850
851
852
853
854
855
856

857
858
859
860
861
862
863
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864







+







  if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue);
  if( pTabItem->fg.viaCoroutine ){
    sqlite3VdbeChangeP2(v, addrCounter, regBase+n);
    testcase( pParse->db->mallocFailed );
    translateColumnToCopy(pParse, addrTop, pLevel->iTabCur,
                          pTabItem->regResult, 1);
    sqlite3VdbeGoto(v, addrTop);
    pTabItem->fg.viaCoroutine = 0;
  }else{
    sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); VdbeCoverage(v);
  }
  sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);
  sqlite3VdbeJumpHere(v, addrTop);
  sqlite3ReleaseTempReg(pParse, regRecord);
  
5070
5071
5072
5073
5074
5075
5076
5077

5078
5079
5080
5081
5082
5083
5084
5071
5072
5073
5074
5075
5076
5077

5078
5079
5080
5081
5082
5083
5084
5085







-
+







      if( db->mallocFailed ) goto whereBeginError;
    }
#endif
    addrExplain = sqlite3WhereExplainOneScan(
        pParse, pTabList, pLevel, wctrlFlags
    );
    pLevel->addrBody = sqlite3VdbeCurrentAddr(v);
    notReady = sqlite3WhereCodeOneLoopStart(pWInfo, ii, notReady);
    notReady = sqlite3WhereCodeOneLoopStart(pParse,v,pWInfo,ii,pLevel,notReady);
    pWInfo->iContinue = pLevel->addrCont;
    if( (wsFlags&WHERE_MULTI_OR)==0 && (wctrlFlags&WHERE_OR_SUBCLAUSE)==0 ){
      sqlite3WhereAddScanStatus(v, pTabList, pLevel, addrExplain);
    }
  }

  /* Done. */

Changes to src/whereInt.h.

503
504
505
506
507
508
509


510
511

512
513
514
515
516
517
518
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521







+
+


+







  WhereLevel *pLvl,               /* Level to add scanstatus() entry for */
  int addrExplain                 /* Address of OP_Explain (or 0) */
);
#else
# define sqlite3WhereAddScanStatus(a, b, c, d) ((void)d)
#endif
Bitmask sqlite3WhereCodeOneLoopStart(
  Parse *pParse,       /* Parsing context */
  Vdbe *v,             /* Prepared statement under construction */
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */
  WhereLevel *pLevel,  /* The current level pointer */
  Bitmask notReady     /* Which tables are currently available */
);

/* whereexpr.c: */
void sqlite3WhereClauseInit(WhereClause*,WhereInfo*);
void sqlite3WhereClauseClear(WhereClause*);
void sqlite3WhereSplit(WhereClause*,Expr*,u8);

Changes to src/wherecode.c.

209
210
211
212
213
214
215

216
217
218
219
220
221
222
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223







+







      sqlite3_str_appendf(&str, " (~%llu rows)",
             sqlite3LogEstToInt(pLoop->nOut));
    }else{
      sqlite3_str_append(&str, " (~1 row)", 9);
    }
#endif
    zMsg = sqlite3StrAccumFinish(&str);
    sqlite3ExplainBreakpoint("",zMsg);
    ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v),
                            pParse->addrExplain, 0, zMsg,P4_DYNAMIC);
  }
  return ret;
}
#endif /* SQLITE_OMIT_EXPLAIN */

534
535
536
537
538
539
540

541
542

543
544
545
546
547
548
549
550


551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
535
536
537
538
539
540
541
542
543

544
545
546
547
548
549
550


551
552
553
554
555
556
557
558
559
560
561

562
563
564
565
566
567
568







+

-
+






-
-
+
+









-







      }
    }
    for(i=iEq;i<pLoop->nLTerm; i++){
      assert( pLoop->aLTerm[i]!=0 );
      if( pLoop->aLTerm[i]->pExpr==pX ) nEq++;
    }

    iTab = 0;
    if( (pX->flags & EP_xIsSelect)==0 || pX->x.pSelect->pEList->nExpr==1 ){
      eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0);
      eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0, &iTab);
    }else{
      sqlite3 *db = pParse->db;
      pX = removeUnindexableInClauseTerms(pParse, iEq, pLoop, pX);

      if( !db->mallocFailed ){
        aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*nEq);
        eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap);
        pTerm->pExpr->iTable = pX->iTable;
        eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap, &iTab);
        pTerm->pExpr->iTable = iTab;
      }
      sqlite3ExprDelete(db, pX);
      pX = pTerm->pExpr;
    }

    if( eType==IN_INDEX_INDEX_DESC ){
      testcase( bRev );
      bRev = !bRev;
    }
    iTab = pX->iTable;
    sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
    VdbeCoverageIf(v, bRev);
    VdbeCoverageIf(v, !bRev);
    assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );

    pLoop->wsFlags |= WHERE_IN_ABLE;
    if( pLevel->u.in.nIn==0 ){
1160
1161
1162
1163
1164
1165
1166


1167
1168

1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177

1178

1179
1180
1181

1182

1183
1184
1185
1186
1187
1188
1189
1190
1191


1192
1193

1194
1195
1196
1197
1198


1199
1200
1201
1202
1203
1204
1205







+
+


+





-

-



-

-









-
-


-





-
-







}

/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
** implementation described by pWInfo.
*/
Bitmask sqlite3WhereCodeOneLoopStart(
  Parse *pParse,       /* Parsing context */
  Vdbe *v,             /* Prepared statement under construction */
  WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
  int iLevel,          /* Which level of pWInfo->a[] should be coded */
  WhereLevel *pLevel,  /* The current level pointer */
  Bitmask notReady     /* Which tables are currently available */
){
  int j, k;            /* Loop counters */
  int iCur;            /* The VDBE cursor for the table */
  int addrNxt;         /* Where to jump to continue with the next IN case */
  int omitTable;       /* True if we use the index only */
  int bRev;            /* True if we need to scan in reverse order */
  WhereLevel *pLevel;  /* The where level to be coded */
  WhereLoop *pLoop;    /* The WhereLoop object being coded */
  WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
  WhereTerm *pTerm;               /* A WHERE clause term */
  Parse *pParse;                  /* Parsing context */
  sqlite3 *db;                    /* Database connection */
  Vdbe *v;                        /* The prepared stmt under constructions */
  struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  int addrBrk;                    /* Jump here to break out of the loop */
  int addrHalt;                   /* addrBrk for the outermost loop */
  int addrCont;                   /* Jump here to continue with next cycle */
  int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
  int iReleaseReg = 0;      /* Temp register to free before returning */
  Index *pIdx = 0;          /* Index used by loop (if any) */
  int iLoop;                /* Iteration of constraint generator loop */

  pParse = pWInfo->pParse;
  v = pParse->pVdbe;
  pWC = &pWInfo->sWC;
  db = pParse->db;
  pLevel = &pWInfo->a[iLevel];
  pLoop = pLevel->pWLoop;
  pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  iCur = pTabItem->iCursor;
  pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur);
  bRev = (pWInfo->revMask>>iLevel)&1;
  omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 
           && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0;
  VdbeModuleComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName));

  /* Create labels for the "break" and "continue" instructions
  ** for the current loop.  Jump to addrBrk to break out of a loop.
  ** Jump to cont to go immediately to the next iteration of the
  ** loop.
  **
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1332
1333
1334
1335
1336
1337
1338

1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356

1357
1358
1359
1360
1361
1362
1363







-


















-







    **          we reference multiple rows using a "rowid IN (...)"
    **          construct.
    */
    assert( pLoop->u.btree.nEq==1 );
    pTerm = pLoop->aLTerm[0];
    assert( pTerm!=0 );
    assert( pTerm->pExpr!=0 );
    assert( omitTable==0 );
    testcase( pTerm->wtFlags & TERM_VIRTUAL );
    iReleaseReg = ++pParse->nMem;
    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
    if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg);
    addrNxt = pLevel->addrNxt;
    sqlite3VdbeAddOp3(v, OP_SeekRowid, iCur, addrNxt, iRowidReg);
    VdbeCoverage(v);
    pLevel->op = OP_Noop;
  }else if( (pLoop->wsFlags & WHERE_IPK)!=0
         && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0
  ){
    /* Case 3:  We have an inequality comparison against the ROWID field.
    */
    int testOp = OP_Noop;
    int start;
    int memEndValue = 0;
    WhereTerm *pStart, *pEnd;

    assert( omitTable==0 );
    j = 0;
    pStart = pEnd = 0;
    if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++];
    if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
    assert( pStart!=0 || pEnd!=0 );
    if( bRev ){
      pTerm = pStart;
1520
1521
1522
1523
1524
1525
1526


1527
1528
1529
1530
1531
1532
1533
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528







+
+







    int iIdxCur;                 /* The VDBE cursor for the index */
    int nExtraReg = 0;           /* Number of extra registers needed */
    int op;                      /* Instruction opcode */
    char *zStartAff;             /* Affinity for start of range constraint */
    char *zEndAff = 0;           /* Affinity for end of range constraint */
    u8 bSeekPastNull = 0;        /* True to seek past initial nulls */
    u8 bStopAtNull = 0;          /* Add condition to terminate at NULLs */
    int omitTable;               /* True if we use the index only */


    pIdx = pLoop->u.btree.pIndex;
    iIdxCur = pLevel->iIdxCur;
    assert( nEq>=pLoop->nSkip );

    /* If this loop satisfies a sort order (pOrderBy) request that 
    ** was passed to this function to implement a "SELECT min(x) ..." 
1721
1722
1723
1724
1725
1726
1727


1728
1729
1730
1731
1732
1733
1734
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731







+
+







    }

    if( pLoop->wsFlags & WHERE_IN_EARLYOUT ){
      sqlite3VdbeAddOp2(v, OP_SeekHit, iIdxCur, 1);
    }

    /* Seek the table cursor, if required */
    omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 
           && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)==0;
    if( omitTable ){
      /* pIdx is a covering index.  No need to access the main table. */
    }else if( HasRowid(pIdx->pTable) ){
      if( (pWInfo->wctrlFlags & WHERE_SEEK_TABLE) || (
          (pWInfo->wctrlFlags & WHERE_SEEK_UNIQ_TABLE) 
       && (pWInfo->eOnePass==ONEPASS_SINGLE)
      )){
1947
1948
1949
1950
1951
1952
1953

1954
1955
1956
1957
1958
1959
1960
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958







+







             || ExprHasProperty(pOrExpr, EP_FromJoin) 
        );
        if( pAndExpr ){
          pAndExpr->pLeft = pOrExpr;
          pOrExpr = pAndExpr;
        }
        /* Loop through table entries that match term pOrTerm. */
        ExplainQueryPlan((pParse, 1, "INDEX %d", ii+1));
        WHERETRACE(0xffff, ("Subplan for OR-clause:\n"));
        pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
                                      wctrlFlags, iCovCur);
        assert( pSubWInfo || pParse->nErr || db->mallocFailed );
        if( pSubWInfo ){
          WhereLoop *pSubLoop;
          int addrExplain = sqlite3WhereExplainOneScan(
2050
2051
2052
2053
2054
2055
2056

2057
2058
2059
2060
2061
2062
2063
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062







+







            pCov = pSubLoop->u.btree.pIndex;
          }else{
            pCov = 0;
          }

          /* Finish the loop through table entries that match term pOrTerm. */
          sqlite3WhereEnd(pSubWInfo);
          ExplainQueryPlanPop(pParse);
        }
      }
    }
    ExplainQueryPlanPop(pParse);
    pLevel->u.pCovidx = pCov;
    if( pCov ) pLevel->iIdxCur = iCovCur;
    if( pAndExpr ){

Changes to test/autoindex1.test.

180
181
182
183
184
185
186
187

188
189
190
191
192
193
194
195
196

197
198
199
200
201
202
203
204
205
206

207
208
209
210
211
212
213
180
181
182
183
184
185
186

187
188
189
190
191
192
193
194
195

196
197
198
199
200
201
202
203
204
205

206
207
208
209
210
211
212
213







-
+








-
+









-
+







}
do_eqp_test autoindex1-500.1 {
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=?);
} {
  QUERY PLAN
  |--SEARCH TABLE t501 USING INTEGER PRIMARY KEY (rowid=?)
  `--LIST SUBQUERY
  `--LIST SUBQUERY xxxxxx
     `--SCAN TABLE t502
}
do_eqp_test autoindex1-501 {
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=t501.b);
} {
  QUERY PLAN
  |--SCAN TABLE t501
  `--CORRELATED LIST SUBQUERY
  `--CORRELATED LIST SUBQUERY xxxxxx
     `--SEARCH TABLE t502 USING AUTOMATIC COVERING INDEX (y=?)
}
do_eqp_test autoindex1-502 {
  SELECT b FROM t501
   WHERE t501.a=123
     AND t501.a IN (SELECT x FROM t502 WHERE y=t501.b);
} {
  QUERY PLAN
  |--SEARCH TABLE t501 USING INTEGER PRIMARY KEY (rowid=?)
  `--CORRELATED LIST SUBQUERY
  `--CORRELATED LIST SUBQUERY xxxxxx
     `--SCAN TABLE t502
}

# The following code checks a performance regression reported on the
# mailing list on 2010-10-19.  The problem is that the nRowEst field
# of ephermeral tables was not being initialized correctly and so no
# automatic index was being created for the emphemeral table when it was
276
277
278
279
280
281
282
283

284
285
286
287
288
289
290
276
277
278
279
280
281
282

283
284
285
286
287
288
289
290







-
+







   WHERE y.sheep_no IS NULL
   ORDER BY x.registering_flock;
} {
  QUERY PLAN
  |--MATERIALIZE xxxxxx
  |  |--SCAN TABLE sheep AS s
  |  |--SEARCH TABLE flock_owner AS prev USING INDEX sqlite_autoindex_flock_owner_1 (flock_no=? AND owner_change_date<?)
  |  `--CORRELATED SCALAR SUBQUERY
  |  `--CORRELATED SCALAR SUBQUERY xxxxxx
  |     `--SEARCH TABLE flock_owner AS later USING COVERING INDEX sqlite_autoindex_flock_owner_1 (flock_no=? AND owner_change_date>? AND owner_change_date<?)
  |--SCAN TABLE sheep AS x USING INDEX sheep_reg_flock_index
  `--SEARCH SUBQUERY xxxxxx AS y USING AUTOMATIC COVERING INDEX (sheep_no=?)
}


do_execsql_test autoindex1-700 {

Changes to test/bestindex3.test.

86
87
88
89
90
91
92

93
94



95
96
97
98
99
100
101

102
103



104
105
106
107
108
109
110
86
87
88
89
90
91
92
93


94
95
96
97
98
99
100
101
102
103
104


105
106
107
108
109
110
111
112
113
114







+
-
-
+
+
+







+
-
-
+
+
+







} {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:a EQ ?}

do_eqp_test 1.3 {
  SELECT * FROM t1 WHERE a = 'abc' OR b = 'def';
} {
  QUERY PLAN
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:a EQ ?
     `--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:b EQ ?
     |  `--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:a EQ ?
     `--INDEX 2
        `--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:b EQ ?
}

do_eqp_test 1.4 {
  SELECT * FROM t1 WHERE a LIKE 'abc%' OR b = 'def';
} {
  QUERY PLAN
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:a LIKE ?
     `--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:b EQ ?
     |  `--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:a LIKE ?
     `--INDEX 2
        `--SCAN TABLE t1 VIRTUAL TABLE INDEX 0:b EQ ?
}

do_execsql_test 1.5 {
  CREATE TABLE ttt(a, b, c);

  INSERT INTO ttt VALUES(1, 'two',   'three');
  INSERT INTO ttt VALUES(2, 'one',   'two');
146
147
148
149
150
151
152

153
154



155
156
157
158
159
160
161
150
151
152
153
154
155
156
157


158
159
160
161
162
163
164
165
166
167







+
-
-
+
+
+







  }

  do_eqp_test 2.2 {
    SELECT * FROM t2 WHERE x LIKE 'abc%' OR y = 'def'
  } [string map {"\n  " \n} {
    QUERY PLAN
    `--MULTI-INDEX OR
       |--INDEX 1
       |--SEARCH TABLE t2 USING INDEX t2x (x>? AND x<?)
       `--SEARCH TABLE t2 USING INDEX t2y (y=?)
       |  `--SEARCH TABLE t2 USING INDEX t2x (x>? AND x<?)
       `--INDEX 2
          `--SEARCH TABLE t2 USING INDEX t2y (y=?)
  }]
}

#-------------------------------------------------------------------------
# Test that any PRIMARY KEY within a sqlite3_decl_vtab() CREATE TABLE 
# statement is currently ignored.
#

Changes to test/cost.test.

54
55
56
57
58
59
60

61
62
63





64
65
66
67
68
69
70
54
55
56
57
58
59
60
61



62
63
64
65
66
67
68
69
70
71
72
73







+
-
-
-
+
+
+
+
+







do_eqp_test 3.2 {
  SELECT a FROM t5 
  WHERE b IS NULL OR c IS NULL OR d IS NULL 
  ORDER BY a;
} {
  QUERY PLAN
  |--MULTI-INDEX OR
  |  |--INDEX 1
  |  |--SEARCH TABLE t5 USING INDEX t5b (b=?)
  |  |--SEARCH TABLE t5 USING INDEX t5c (c=?)
  |  `--SEARCH TABLE t5 USING INDEX t5d (d=?)
  |  |  `--SEARCH TABLE t5 USING INDEX t5b (b=?)
  |  |--INDEX 2
  |  |  `--SEARCH TABLE t5 USING INDEX t5c (c=?)
  |  `--INDEX 3
  |     `--SEARCH TABLE t5 USING INDEX t5d (d=?)
  `--USE TEMP B-TREE FOR ORDER BY
}

#-------------------------------------------------------------------------
# If there is no likelihood() or stat3 data, SQLite assumes that a closed
# range scan (e.g. one constrained by "col BETWEEN ? AND ?" constraint)
# visits 1/64 of the rows in a table.
120
121
122
123
124
125
126

127
128



129
130
131
132
133
134
135
123
124
125
126
127
128
129
130


131
132
133
134
135
136
137
138
139
140







+
-
-
+
+
+







}

do_eqp_test 6.2 {
  SELECT a FROM t3 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a
} {
  QUERY PLAN
  |--MULTI-INDEX OR
  |  |--INDEX 1
  |  |--SEARCH TABLE t3 USING INDEX t3i1 (b>? AND b<?)
  |  `--SEARCH TABLE t3 USING INDEX t3i2 (c=?)
  |  |  `--SEARCH TABLE t3 USING INDEX t3i1 (b>? AND b<?)
  |  `--INDEX 2
  |     `--SEARCH TABLE t3 USING INDEX t3i2 (c=?)
  `--USE TEMP B-TREE FOR ORDER BY
}

#-------------------------------------------------------------------------
#
reset_db
do_execsql_test 7.1 {
145
146
147
148
149
150
151

152
153



154
155
156
157
158
159
160
150
151
152
153
154
155
156
157


158
159
160
161
162
163
164
165
166
167







+
-
-
+
+
+







do_eqp_test 7.2 {
  SELECT a FROM t1
     WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL)
  ORDER BY a
} {
  QUERY PLAN
  |--MULTI-INDEX OR
  |  |--INDEX 1
  |  |--SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)
  |  `--SEARCH TABLE t1 USING INDEX t1b (b=?)
  |  |  `--SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)
  |  `--INDEX 2
  |     `--SEARCH TABLE t1 USING INDEX t1b (b=?)
  `--USE TEMP B-TREE FOR ORDER BY
}

do_eqp_test 7.3 {
  SELECT rowid FROM t1
  WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)

Changes to test/eqp.test.

41
42
43
44
45
46
47

48
49



50
51
52
53
54
55
56
57

58
59



60
61
62
63
64
65
66
41
42
43
44
45
46
47
48


49
50
51
52
53
54
55
56
57
58
59
60


61
62
63
64
65
66
67
68
69
70







+
-
-
+
+
+








+
-
-
+
+
+







}

do_eqp_test 1.2 {
  SELECT * FROM t2, t1 WHERE t1.a=1 OR t1.b=2;
} {
  QUERY PLAN
  |--MULTI-INDEX OR
  |  |--INDEX 1
  |  |--SEARCH TABLE t1 USING INDEX i1 (a=?)
  |  `--SEARCH TABLE t1 USING INDEX i2 (b=?)
  |  |  `--SEARCH TABLE t1 USING INDEX i1 (a=?)
  |  `--INDEX 2
  |     `--SEARCH TABLE t1 USING INDEX i2 (b=?)
  `--SCAN TABLE t2
}
do_eqp_test 1.3 {
  SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a=1 OR t1.b=2;
} {
  QUERY PLAN
  |--SCAN TABLE t2
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SEARCH TABLE t1 USING INDEX i1 (a=?)
     `--SEARCH TABLE t1 USING INDEX i2 (b=?)
     |  `--SEARCH TABLE t1 USING INDEX i1 (a=?)
     `--INDEX 2
        `--SEARCH TABLE t1 USING INDEX i2 (b=?)
}
do_eqp_test 1.3 {
  SELECT a FROM t1 ORDER BY a
} {
  QUERY PLAN
  `--SCAN TABLE t1 USING COVERING INDEX i1
}
221
222
223
224
225
226
227
228

229
230
231
232
233
234
235
236

237
238
239
240
241
242
243
244

245
246
247
248
249
250
251
252
253

254
255
256
257
258
259
260
225
226
227
228
229
230
231

232
233
234
235
236
237
238
239

240
241
242
243
244
245
246
247

248
249
250
251
252
253
254
255
256

257
258
259
260
261
262
263
264







-
+







-
+







-
+








-
+







# Test cases eqp-3.* - tests for select statements that use sub-selects.
#
do_eqp_test 3.1.1 {
  SELECT (SELECT x FROM t1 AS sub) FROM t1;
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--SCALAR SUBQUERY
  `--SCALAR SUBQUERY xxxxxx
     `--SCAN TABLE t1 AS sub
}
do_eqp_test 3.1.2 {
  SELECT * FROM t1 WHERE (SELECT x FROM t1 AS sub);
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--SCALAR SUBQUERY
  `--SCALAR SUBQUERY xxxxxx
     `--SCAN TABLE t1 AS sub
}
do_eqp_test 3.1.3 {
  SELECT * FROM t1 WHERE (SELECT x FROM t1 AS sub ORDER BY y);
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--SCALAR SUBQUERY
  `--SCALAR SUBQUERY xxxxxx
     |--SCAN TABLE t1 AS sub
     `--USE TEMP B-TREE FOR ORDER BY
}
do_eqp_test 3.1.4 {
  SELECT * FROM t1 WHERE (SELECT x FROM t2 ORDER BY x);
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--SCALAR SUBQUERY
  `--SCALAR SUBQUERY xxxxxx
     `--SCAN TABLE t2 USING COVERING INDEX t2i1
}

det 3.2.1 {
  SELECT * FROM (SELECT * FROM t1 ORDER BY x LIMIT 10) ORDER BY y LIMIT 5
} {
  QUERY PLAN
282
283
284
285
286
287
288
289

290
291
292
293
294
295
296
297

298
299
300
301
302
303
304
305

306
307
308
309
310
311
312
286
287
288
289
290
291
292

293
294
295
296
297
298
299
300

301
302
303
304
305
306
307
308

309
310
311
312
313
314
315
316







-
+







-
+







-
+







}

det 3.3.1 {
  SELECT * FROM t1 WHERE y IN (SELECT y FROM t2)
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--LIST SUBQUERY
  `--LIST SUBQUERY xxxxxx
     `--SCAN TABLE t2
}
det 3.3.2 {
  SELECT * FROM t1 WHERE y IN (SELECT y FROM t2 WHERE t1.x!=t2.x)
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--CORRELATED LIST SUBQUERY
  `--CORRELATED LIST SUBQUERY xxxxxx
     `--SCAN TABLE t2
}
det 3.3.3 {
  SELECT * FROM t1 WHERE EXISTS (SELECT y FROM t2 WHERE t1.x!=t2.x)
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--CORRELATED SCALAR SUBQUERY
  `--CORRELATED SCALAR SUBQUERY xxxxxx
     `--SCAN TABLE t2
}

#-------------------------------------------------------------------------
# Test cases eqp-4.* - tests for composite select statements.
#
do_eqp_test 4.1.1 {
809
810
811
812
813
814
815
816

817
818
819
820
821
822
823
824
825
826
813
814
815
816
817
818
819

820
821
822
823
824
825
826
827
828
829
830







-
+










    AND event.objid=thread.last
  ORDER BY 1;
} {
  QUERY PLAN
  |--MATERIALIZE xxxxxx
  |  |--SCAN TABLE forumpost AS x USING INDEX forumthread
  |  |--USING ROWID SEARCH ON TABLE private FOR IN-OPERATOR
  |  |--CORRELATED SCALAR SUBQUERY
  |  |--CORRELATED SCALAR SUBQUERY xxxxxx
  |  |  |--SEARCH TABLE forumpost USING COVERING INDEX forumthread (froot=?)
  |  |  `--USING ROWID SEARCH ON TABLE private FOR IN-OPERATOR
  |  `--USE TEMP B-TREE FOR ORDER BY
  |--SCAN SUBQUERY xxxxxx
  |--SEARCH TABLE blob USING INTEGER PRIMARY KEY (rowid=?)
  |--SEARCH TABLE event USING INTEGER PRIMARY KEY (rowid=?)
  `--USE TEMP B-TREE FOR ORDER BY
}

finish_test

Changes to test/join5.test.

263
264
265
266
267
268
269

270
271



272
273
274
275
276
277
278
263
264
265
266
267
268
269
270


271
272
273
274
275
276
277
278
279
280







+
-
-
+
+
+







  SELECT * FROM t1 LEFT JOIN t2 ON (
    t2.x = t1.x AND (t2.y=? OR (t2.y=? AND t2.z IS NOT NULL))
  );
} {
  QUERY PLAN
  |--SCAN TABLE t1
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SEARCH TABLE t2 USING INDEX t2xy (x=? AND y=?)
     `--SEARCH TABLE t2 USING INDEX t2xy (x=? AND y=?)
     |  `--SEARCH TABLE t2 USING INDEX t2xy (x=? AND y=?)
     `--INDEX 2
        `--SEARCH TABLE t2 USING INDEX t2xy (x=? AND y=?)
}

do_execsql_test 7.3 {
  CREATE TABLE t3(x);

  CREATE TABLE t4(x, y, z);
  CREATE INDEX t4xy ON t4(x, y);

Changes to test/rowvalue4.test.

231
232
233
234
235
236
237
238

239
240

241
242
243
244
245
246
247
231
232
233
234
235
236
237

238
239

240
241
242
243
244
245
246
247







-
+

-
+







do_eqp_test 5.1 {
  SELECT * FROM d2 WHERE 
    (a, b) IN (SELECT x, y FROM d1) AND
    (c) IN (SELECT y FROM d1)
} {
  QUERY PLAN
  |--SEARCH TABLE d2 USING INDEX d2ab (a=? AND b=?)
  |--LIST SUBQUERY
  |--LIST SUBQUERY xxxxxx
  |  `--SCAN TABLE d1
  `--LIST SUBQUERY
  `--LIST SUBQUERY xxxxxx
     `--SCAN TABLE d1
}

do_execsql_test 6.0 {
  CREATE TABLE e1(a, b, c, d, e);
  CREATE INDEX e1ab ON e1(a, b);
  CREATE INDEX e1cde ON e1(c, d, e);

Changes to test/tkt-80ba201079.test.

106
107
108
109
110
111
112


113
114
115
116
117
118
119
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121







+
+







             AND entry_id IN (SELECT change_id
                              FROM object_changes
                               WHERE obj_context = 'exported_pools'));
  }
} {300 object_change 2048}
do_test tkt-80ba2-201 {
  db eval {
PRAGMA vdbe_debug=on;
PRAGMA vdbe_addoptrace=on;
    CREATE INDEX timeline_entry_id_idx on timeline(entry_id);
    SELECT entry_type,
           entry_types.name,
           entry_id
      FROM timeline JOIN entry_types ON entry_type = entry_types.id
     WHERE (entry_types.name = 'cli_command' AND entry_id=2114)
        OR (entry_types.name = 'object_change'

Changes to test/where7.test.

23349
23350
23351
23352
23353
23354
23355

23356
23357



23358
23359
23360
23361
23362
23349
23350
23351
23352
23353
23354
23355
23356


23357
23358
23359
23360
23361
23362
23363
23364







+
-
-
+
+
+





      AND t302.c3 > 1287603136
      AND (t301.c4 = 1407449685622784
           OR t301.c8 = 1407424651264000)
   ORDER BY t302.c5 LIMIT 200;
} {
  QUERY PLAN
  |--MULTI-INDEX OR
  |  |--INDEX 1
  |  |--SEARCH TABLE t301 USING COVERING INDEX t301_c4 (c4=?)
  |  `--SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)
  |  |  `--SEARCH TABLE t301 USING COVERING INDEX t301_c4 (c4=?)
  |  `--INDEX 2
  |     `--SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)
  |--SEARCH TABLE t302 USING INDEX t302_c8_c3 (c8=? AND c3>?)
  `--USE TEMP B-TREE FOR ORDER BY
}

finish_test

Changes to test/where9.test.

360
361
362
363
364
365
366

367
368



369
370
371
372
373
374
375
376
377

378
379



380
381
382
383
384
385
386
360
361
362
363
364
365
366
367


368
369
370
371
372
373
374
375
376
377
378
379
380


381
382
383
384
385
386
387
388
389
390







+
-
-
+
+
+









+
-
-
+
+
+







  do_eqp_test where9-3.1 {
    SELECT t2.a FROM t1, t2
    WHERE t1.a=80 AND ((t1.c=t2.c AND t1.d=t2.d) OR t1.f=t2.f)
  } [string map {"\n  " \n} {
    QUERY PLAN
    |--SEARCH TABLE t1 USING INTEGER PRIMARY KEY (rowid=?)
    `--MULTI-INDEX OR
       |--INDEX 1
       |--SEARCH TABLE t2 USING INDEX t2d (d=?)
       `--SEARCH TABLE t2 USING COVERING INDEX t2f (f=?)
       |  `--SEARCH TABLE t2 USING INDEX t2d (d=?)
       `--INDEX 3
          `--SEARCH TABLE t2 USING COVERING INDEX t2f (f=?)
  }]
  do_eqp_test where9-3.2 {
    SELECT coalesce(t2.a,9999)
    FROM t1 LEFT JOIN t2 ON (t1.c+1=t2.c AND t1.d=t2.d) OR (t1.f||'x')=t2.f
    WHERE t1.a=80
  } [string map {"\n  " \n} {
    QUERY PLAN
    |--SEARCH TABLE t1 USING INTEGER PRIMARY KEY (rowid=?)
    `--MULTI-INDEX OR
       |--INDEX 1
       |--SEARCH TABLE t2 USING INDEX t2d (d=?)
       `--SEARCH TABLE t2 USING COVERING INDEX t2f (f=?)
       |  `--SEARCH TABLE t2 USING INDEX t2d (d=?)
       `--INDEX 2
          `--SEARCH TABLE t2 USING COVERING INDEX t2f (f=?)
  }]
} 

# Make sure that INDEXED BY and multi-index OR clauses play well with
# one another.
#
do_test where9-4.1 {
452
453
454
455
456
457
458

459
460



461
462
463
464
465
466
467
456
457
458
459
460
461
462
463


464
465
466
467
468
469
470
471
472
473







+
-
-
+
+
+







# the former is an equality test which is expected to return fewer rows.
#
do_eqp_test where9-5.1 {
  SELECT a FROM t1 WHERE b>1000 AND (c=31031 OR d IS NULL)
} {
  QUERY PLAN
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SEARCH TABLE t1 USING INDEX t1c (c=?)
     `--SEARCH TABLE t1 USING INDEX t1d (d=?)
     |  `--SEARCH TABLE t1 USING INDEX t1c (c=?)
     `--INDEX 2
        `--SEARCH TABLE t1 USING INDEX t1d (d=?)
}

# In contrast, b=1000 is preferred over any OR-clause.
#
do_eqp_test where9-5.2 {
  SELECT a FROM t1 WHERE b=1000 AND (c=31031 OR d IS NULL)
} {SEARCH TABLE t1 USING INDEX t1b (b=?)}

Changes to test/whereI.test.

27
28
29
30
31
32
33

34
35



36
37
38
39
40
41
42
27
28
29
30
31
32
33
34


35
36
37
38
39
40
41
42
43
44







+
-
-
+
+
+







}

do_eqp_test 1.1 {
  SELECT a FROM t1 WHERE b='b' OR c='x'
} {
  QUERY PLAN
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SEARCH TABLE t1 USING INDEX i1 (b=?)
     `--SEARCH TABLE t1 USING INDEX i2 (c=?)
     |  `--SEARCH TABLE t1 USING INDEX i1 (b=?)
     `--INDEX 2
        `--SEARCH TABLE t1 USING INDEX i2 (c=?)
}

do_execsql_test 1.2 {
  SELECT a FROM t1 WHERE b='b' OR c='x'
} {2 3}

do_execsql_test 1.3 {
57
58
59
60
61
62
63

64
65



66
67
68
69
70
71
72
59
60
61
62
63
64
65
66


67
68
69
70
71
72
73
74
75
76







+
-
-
+
+
+







}

do_eqp_test 2.1 {
  SELECT a FROM t2 WHERE b='b' OR c='x'
} {
  QUERY PLAN
  `--MULTI-INDEX OR
     |--INDEX 1
     |--SEARCH TABLE t2 USING INDEX i3 (b=?)
     `--SEARCH TABLE t2 USING INDEX i4 (c=?)
     |  `--SEARCH TABLE t2 USING INDEX i3 (b=?)
     `--INDEX 2
        `--SEARCH TABLE t2 USING INDEX i4 (c=?)
}

do_execsql_test 2.2 {
  SELECT a FROM t2 WHERE b='b' OR c='x'
} {ii iii}

do_execsql_test 2.3 {

Changes to test/with3.test.

116
117
118
119
120
121
122
123

124
125
126
127
128
129
130
116
117
118
119
120
121
122

123
124
125
126
127
128
129
130







-
+







     SELECT * FROM c, w2, w1
     WHERE c.id=w2.pk AND c.id=w1.pk;
} {
  QUERY PLAN
  |--MATERIALIZE xxxxxx
  |  |--SETUP
  |  |  |--SCAN CONSTANT ROW
  |  |  `--SCALAR SUBQUERY
  |  |  `--SCALAR SUBQUERY xxxxxx
  |  |     `--SCAN TABLE w2
  |  `--RECURSIVE STEP
  |     |--SCAN TABLE w1
  |     `--SCAN TABLE c
  |--SCAN SUBQUERY xxxxxx
  |--SEARCH TABLE w2 USING INTEGER PRIMARY KEY (rowid=?)
  `--SEARCH TABLE w1 USING INTEGER PRIMARY KEY (rowid=?)