/ Check-in [7b446771]
Login

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

Overview
Comment:Avoid passing constraints that are unusable due to LEFT or CROSS joins to virtual table xBestIndex() methods.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 7b446771cadedafbe8924ad0658adc2597816dc7
User & Date: dan 2015-06-10 14:27:40
Context
2015-06-10
18:53
"test" targets on all makefiles use --verbose=file --output=test-out.txt. Add the new "quicktest" target to all makefiles - designed to run in under three minutes. The --quick option on releasetest.tcl now uses quicktest. check-in: 6ddef2ad user: drh tags: trunk
14:27
Avoid passing constraints that are unusable due to LEFT or CROSS joins to virtual table xBestIndex() methods. check-in: 7b446771 user: dan tags: trunk
2015-06-09
15:58
Add the --output=$file and --verbose=(0|1|file) options to tester.tcl. check-in: f7b2c703 user: dan tags: trunk
10:58
Remove some repeated lines of source code. Probably introduced by careless cut'n'pasting. Closed-Leaf check-in: a34cd71c user: dan tags: vtab-left-join
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtreeC.test.

   264    264       sqlite3 db2 test.db
   265    265       db2 eval { DROP TABLE sqlite_stat1 }
   266    266       db2 close
   267    267       execsql { SELECT * FROM rt }
   268    268     } {1 2.0 3.0}
   269    269     db close
   270    270   }
          271  +
          272  +#--------------------------------------------------------------------
          273  +# Test that queries featuring LEFT or CROSS JOINS are handled correctly.
          274  +# Handled correctly in this case means:
          275  +#
          276  +#   * Terms with prereqs that appear to the left of a LEFT JOIN against
          277  +#     the virtual table are always available to xBestIndex.
          278  +#
          279  +#   * Terms with prereqs that appear to the right of a LEFT JOIN against
          280  +#     the virtual table are never available to xBestIndex.
          281  +#
          282  +# And the same behaviour for CROSS joins.
          283  +#
          284  +reset_db
          285  +do_execsql_test 7.0 {
          286  +  CREATE TABLE xdir(x1);
          287  +  CREATE TABLE ydir(y1);
          288  +  CREATE VIRTUAL TABLE rt USING rtree_i32(id, xmin, xmax, ymin, ymax);
          289  +
          290  +  INSERT INTO xdir VALUES(5);
          291  +  INSERT INTO ydir VALUES(10);
          292  +
          293  +  INSERT INTO rt VALUES(1, 2, 7, 12, 14);      -- Not a hit
          294  +  INSERT INTO rt VALUES(2, 2, 7, 8, 12);       -- A hit!
          295  +  INSERT INTO rt VALUES(3, 7, 11, 8, 12);      -- Not a hit!
          296  +  INSERT INTO rt VALUES(4, 5, 5, 10, 10);      -- A hit!
          297  +
          298  +}
          299  +
          300  +proc do_eqp_execsql_test {tn sql res} {
          301  +  set query "EXPLAIN QUERY PLAN $sql ; $sql "
          302  +  uplevel [list do_execsql_test $tn $query $res]
          303  +}
          304  +
          305  +do_eqp_execsql_test 7.1 {
          306  +  SELECT id FROM xdir, rt, ydir 
          307  +  ON (y1 BETWEEN ymin AND ymax)
          308  +  WHERE (x1 BETWEEN xmin AND xmax);
          309  +} {
          310  +  0 0 0 {SCAN TABLE xdir} 
          311  +  0 1 2 {SCAN TABLE ydir} 
          312  +  0 2 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B2D3B0D1}
          313  +  2 4
          314  +}
          315  +
          316  +do_eqp_execsql_test 7.2 {
          317  +  SELECT * FROM xdir, rt LEFT JOIN ydir 
          318  +  ON (y1 BETWEEN ymin AND ymax)
          319  +  WHERE (x1 BETWEEN xmin AND xmax);
          320  +} {
          321  +  0 0 0 {SCAN TABLE xdir} 
          322  +  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1}
          323  +  0 2 2 {SCAN TABLE ydir} 
          324  +
          325  +  5 1 2 7 12 14 {}
          326  +  5 2 2 7  8 12 10
          327  +  5 4 5 5 10 10 10
          328  +}
          329  +
          330  +do_eqp_execsql_test 7.3 {
          331  +  SELECT id FROM xdir, rt CROSS JOIN ydir 
          332  +  ON (y1 BETWEEN ymin AND ymax)
          333  +  WHERE (x1 BETWEEN xmin AND xmax);
          334  +} {
          335  +  0 0 0 {SCAN TABLE xdir} 
          336  +  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1}
          337  +  0 2 2 {SCAN TABLE ydir} 
          338  +  2 4
          339  +}
          340  +
          341  +do_eqp_execsql_test 7.4 {
          342  +  SELECT id FROM rt, xdir CROSS JOIN ydir 
          343  +  ON (y1 BETWEEN ymin AND ymax)
          344  +  WHERE (x1 BETWEEN xmin AND xmax);
          345  +} {
          346  +  0 0 1 {SCAN TABLE xdir} 
          347  +  0 1 0 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:B0D1}
          348  +  0 2 2 {SCAN TABLE ydir} 
          349  +  2 4
          350  +}
          351  +
          352  +finish_test
          353  +
   271    354   
   272    355   
   273    356   finish_test

Changes to src/where.c.

   753    753   ** Allocate and populate an sqlite3_index_info structure. It is the 
   754    754   ** responsibility of the caller to eventually release the structure
   755    755   ** by passing the pointer returned by this function to sqlite3_free().
   756    756   */
   757    757   static sqlite3_index_info *allocateIndexInfo(
   758    758     Parse *pParse,
   759    759     WhereClause *pWC,
          760  +  Bitmask mUnusable,              /* Ignore terms with these prereqs */
   760    761     struct SrcList_item *pSrc,
   761    762     ExprList *pOrderBy
   762    763   ){
   763    764     int i, j;
   764    765     int nTerm;
   765    766     struct sqlite3_index_constraint *pIdxCons;
   766    767     struct sqlite3_index_orderby *pIdxOrderBy;
................................................................................
   769    770     int nOrderBy;
   770    771     sqlite3_index_info *pIdxInfo;
   771    772   
   772    773     /* Count the number of possible WHERE clause constraints referring
   773    774     ** to this virtual table */
   774    775     for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
   775    776       if( pTerm->leftCursor != pSrc->iCursor ) continue;
          777  +    if( pTerm->prereqRight & mUnusable ) continue;
   776    778       assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
   777    779       testcase( pTerm->eOperator & WO_IN );
   778    780       testcase( pTerm->eOperator & WO_ISNULL );
   779    781       testcase( pTerm->eOperator & WO_IS );
   780    782       testcase( pTerm->eOperator & WO_ALL );
   781    783       if( (pTerm->eOperator & ~(WO_ISNULL|WO_EQUIV|WO_IS))==0 ) continue;
   782    784       if( pTerm->wtFlags & TERM_VNULL ) continue;
................................................................................
   823    825     *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
   824    826     *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
   825    827                                                                      pUsage;
   826    828   
   827    829     for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
   828    830       u8 op;
   829    831       if( pTerm->leftCursor != pSrc->iCursor ) continue;
          832  +    if( pTerm->prereqRight & mUnusable ) continue;
   830    833       assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) );
   831    834       testcase( pTerm->eOperator & WO_IN );
   832    835       testcase( pTerm->eOperator & WO_IS );
   833    836       testcase( pTerm->eOperator & WO_ISNULL );
   834    837       testcase( pTerm->eOperator & WO_ALL );
   835    838       if( (pTerm->eOperator & ~(WO_ISNULL|WO_EQUIV|WO_IS))==0 ) continue;
   836    839       if( pTerm->wtFlags & TERM_VNULL ) continue;
................................................................................
  2662   2665     return rc;
  2663   2666   }
  2664   2667   
  2665   2668   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2666   2669   /*
  2667   2670   ** Add all WhereLoop objects for a table of the join identified by
  2668   2671   ** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
         2672  +**
         2673  +** If there are no LEFT or CROSS JOIN joins in the query, both mExtra and
         2674  +** mUnusable are set to 0. Otherwise, mExtra is a mask of all FROM clause
         2675  +** entries that occur before the virtual table in the FROM clause and are
         2676  +** separated from it by at least one LEFT or CROSS JOIN. Similarly, the
         2677  +** mUnusable mask contains all FROM clause entries that occur after the
         2678  +** virtual table and are separated from it by at least one LEFT or 
         2679  +** CROSS JOIN. 
         2680  +**
         2681  +** For example, if the query were:
         2682  +**
         2683  +**   ... FROM t1, t2 LEFT JOIN t3, t4, vt CROSS JOIN t5, t6;
         2684  +**
         2685  +** then mExtra corresponds to (t1, t2) and mUnusable to (t5, t6).
         2686  +**
         2687  +** All the tables in mExtra must be scanned before the current virtual 
         2688  +** table. So any terms for which all prerequisites are satisfied by 
         2689  +** mExtra may be specified as "usable" in all calls to xBestIndex. 
         2690  +** Conversely, all tables in mUnusable must be scanned after the current
         2691  +** virtual table, so any terms for which the prerequisites overlap with
         2692  +** mUnusable should always be configured as "not-usable" for xBestIndex.
  2669   2693   */
  2670   2694   static int whereLoopAddVirtual(
  2671   2695     WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  2672         -  Bitmask mExtra
         2696  +  Bitmask mExtra,              /* Tables that must be scanned before this one */
         2697  +  Bitmask mUnusable            /* Tables that must be scanned after this one */
  2673   2698   ){
  2674   2699     WhereInfo *pWInfo;           /* WHERE analysis context */
  2675   2700     Parse *pParse;               /* The parsing context */
  2676   2701     WhereClause *pWC;            /* The WHERE clause */
  2677   2702     struct SrcList_item *pSrc;   /* The FROM clause term to search */
  2678   2703     Table *pTab;
  2679   2704     sqlite3 *db;
................................................................................
  2686   2711     int nConstraint;
  2687   2712     int seenIn = 0;              /* True if an IN operator is seen */
  2688   2713     int seenVar = 0;             /* True if a non-constant constraint is seen */
  2689   2714     int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
  2690   2715     WhereLoop *pNew;
  2691   2716     int rc = SQLITE_OK;
  2692   2717   
         2718  +  assert( (mExtra & mUnusable)==0 );
  2693   2719     pWInfo = pBuilder->pWInfo;
  2694   2720     pParse = pWInfo->pParse;
  2695   2721     db = pParse->db;
  2696   2722     pWC = pBuilder->pWC;
  2697   2723     pNew = pBuilder->pNew;
  2698   2724     pSrc = &pWInfo->pTabList->a[pNew->iTab];
  2699   2725     pTab = pSrc->pTab;
  2700   2726     assert( IsVirtual(pTab) );
  2701         -  pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pBuilder->pOrderBy);
         2727  +  pIdxInfo = allocateIndexInfo(pParse, pWC, mUnusable, pSrc,pBuilder->pOrderBy);
  2702   2728     if( pIdxInfo==0 ) return SQLITE_NOMEM;
  2703   2729     pNew->prereq = 0;
  2704   2730     pNew->rSetup = 0;
  2705   2731     pNew->wsFlags = WHERE_VIRTUALTABLE;
  2706   2732     pNew->nLTerm = 0;
  2707   2733     pNew->u.vtab.needFree = 0;
  2708   2734     pUsage = pIdxInfo->aConstraintUsage;
................................................................................
  2724   2750         pTerm = &pWC->a[j];
  2725   2751         switch( iPhase ){
  2726   2752           case 0:    /* Constants without IN operator */
  2727   2753             pIdxCons->usable = 0;
  2728   2754             if( (pTerm->eOperator & WO_IN)!=0 ){
  2729   2755               seenIn = 1;
  2730   2756             }
  2731         -          if( pTerm->prereqRight!=0 ){
         2757  +          if( (pTerm->prereqRight & ~mExtra)!=0 ){
  2732   2758               seenVar = 1;
  2733   2759             }else if( (pTerm->eOperator & WO_IN)==0 ){
  2734   2760               pIdxCons->usable = 1;
  2735   2761             }
  2736   2762             break;
  2737   2763           case 1:    /* Constants with IN operators */
  2738   2764             assert( seenIn );
  2739         -          pIdxCons->usable = (pTerm->prereqRight==0);
         2765  +          pIdxCons->usable = (pTerm->prereqRight & ~mExtra)==0;
  2740   2766             break;
  2741   2767           case 2:    /* Variables without IN */
  2742   2768             assert( seenVar );
  2743   2769             pIdxCons->usable = (pTerm->eOperator & WO_IN)==0;
  2744   2770             break;
  2745   2771           default:   /* Variables with IN */
  2746   2772             assert( seenVar && seenIn );
................................................................................
  2831   2857   }
  2832   2858   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  2833   2859   
  2834   2860   /*
  2835   2861   ** Add WhereLoop entries to handle OR terms.  This works for either
  2836   2862   ** btrees or virtual tables.
  2837   2863   */
  2838         -static int whereLoopAddOr(WhereLoopBuilder *pBuilder, Bitmask mExtra){
         2864  +static int whereLoopAddOr(
         2865  +  WhereLoopBuilder *pBuilder, 
         2866  +  Bitmask mExtra, 
         2867  +  Bitmask mUnusable
         2868  +){
  2839   2869     WhereInfo *pWInfo = pBuilder->pWInfo;
  2840   2870     WhereClause *pWC;
  2841   2871     WhereLoop *pNew;
  2842   2872     WhereTerm *pTerm, *pWCEnd;
  2843   2873     int rc = SQLITE_OK;
  2844   2874     int iCur;
  2845   2875     WhereClause tempWC;
................................................................................
  2890   2920             for(i=0; i<sSubBuild.pWC->nTerm; i++){
  2891   2921               whereTermPrint(&sSubBuild.pWC->a[i], i);
  2892   2922             }
  2893   2923           }
  2894   2924   #endif
  2895   2925   #ifndef SQLITE_OMIT_VIRTUALTABLE
  2896   2926           if( IsVirtual(pItem->pTab) ){
  2897         -          rc = whereLoopAddVirtual(&sSubBuild, mExtra);
         2927  +          rc = whereLoopAddVirtual(&sSubBuild, mExtra, mUnusable);
  2898   2928           }else
  2899   2929   #endif
  2900   2930           {
  2901   2931             rc = whereLoopAddBtree(&sSubBuild, mExtra);
  2902   2932           }
  2903   2933           if( rc==SQLITE_OK ){
  2904         -          rc = whereLoopAddOr(&sSubBuild, mExtra);
         2934  +          rc = whereLoopAddOr(&sSubBuild, mExtra, mUnusable);
  2905   2935           }
  2906   2936           assert( rc==SQLITE_OK || sCur.n==0 );
  2907   2937           if( sCur.n==0 ){
  2908   2938             sSum.n = 0;
  2909   2939             break;
  2910   2940           }else if( once ){
  2911   2941             whereOrMove(&sSum, &sCur);
................................................................................
  2959   2989   static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  2960   2990     WhereInfo *pWInfo = pBuilder->pWInfo;
  2961   2991     Bitmask mExtra = 0;
  2962   2992     Bitmask mPrior = 0;
  2963   2993     int iTab;
  2964   2994     SrcList *pTabList = pWInfo->pTabList;
  2965   2995     struct SrcList_item *pItem;
         2996  +  struct SrcList_item *pEnd = &pTabList->a[pWInfo->nLevel];
  2966   2997     sqlite3 *db = pWInfo->pParse->db;
  2967         -  int nTabList = pWInfo->nLevel;
  2968   2998     int rc = SQLITE_OK;
  2969         -  u8 priorJoinType = 0;
  2970   2999     WhereLoop *pNew;
         3000  +  u8 priorJointype = 0;
  2971   3001   
  2972   3002     /* Loop over the tables in the join, from left to right */
  2973   3003     pNew = pBuilder->pNew;
  2974   3004     whereLoopInit(pNew);
  2975         -  for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
         3005  +  for(iTab=0, pItem=pTabList->a; pItem<pEnd; iTab++, pItem++){
         3006  +    Bitmask mUnusable = 0;
  2976   3007       pNew->iTab = iTab;
  2977   3008       pNew->maskSelf = sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor);
  2978         -    if( ((pItem->jointype|priorJoinType) & (JT_LEFT|JT_CROSS))!=0 ){
         3009  +    if( ((pItem->jointype|priorJointype) & (JT_LEFT|JT_CROSS))!=0 ){
         3010  +      /* This condition is true when pItem is the FROM clause term on the
         3011  +      ** right-hand-side of a LEFT or CROSS JOIN.  */
  2979   3012         mExtra = mPrior;
  2980   3013       }
  2981         -    priorJoinType = pItem->jointype;
         3014  +    priorJointype = pItem->jointype;
  2982   3015       if( IsVirtual(pItem->pTab) ){
  2983         -      rc = whereLoopAddVirtual(pBuilder, mExtra);
         3016  +      struct SrcList_item *p;
         3017  +      for(p=&pItem[1]; p<pEnd; p++){
         3018  +        if( mUnusable || (p->jointype & (JT_LEFT|JT_CROSS)) ){
         3019  +          mUnusable |= sqlite3WhereGetMask(&pWInfo->sMaskSet, p->iCursor);
         3020  +        }
         3021  +      }
         3022  +      rc = whereLoopAddVirtual(pBuilder, mExtra, mUnusable);
  2984   3023       }else{
  2985   3024         rc = whereLoopAddBtree(pBuilder, mExtra);
  2986   3025       }
  2987   3026       if( rc==SQLITE_OK ){
  2988         -      rc = whereLoopAddOr(pBuilder, mExtra);
         3027  +      rc = whereLoopAddOr(pBuilder, mExtra, mUnusable);
  2989   3028       }
  2990   3029       mPrior |= pNew->maskSelf;
  2991   3030       if( rc || db->mallocFailed ) break;
  2992   3031     }
         3032  +
  2993   3033     whereLoopClear(db, pNew);
  2994   3034     return rc;
  2995   3035   }
  2996   3036   
  2997   3037   /*
  2998   3038   ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th
  2999   3039   ** parameters) to see if it outputs rows in the requested ORDER BY

Changes to test/join.test.

   682    682     if {[lsearch [db eval {PRAGMA compile_options}] MEMDEBUG]<0} {
   683    683       jointest join-12.10 65534 {1 {at most 64 tables in a join}}
   684    684       jointest join-12.11 65535 {1 {too many references to "t14": max 65535}}
   685    685       jointest join-12.12 65536 {1 {too many references to "t14": max 65535}}
   686    686       jointest join-12.13 65537 {1 {too many references to "t14": max 65535}}
   687    687     }
   688    688   }
          689  +
          690  +
          691  +#-------------------------------------------------------------------------
          692  +# Test a problem with reordering tables following a LEFT JOIN.
          693  +#
          694  +do_execsql_test join-13.0 {
          695  +  CREATE TABLE aa(a);
          696  +  CREATE TABLE bb(b);
          697  +  CREATE TABLE cc(c);
          698  +
          699  +  INSERT INTO aa VALUES(45);
          700  +  INSERT INTO cc VALUES(45);
          701  +  INSERT INTO cc VALUES(45);
          702  +}
          703  +
          704  +do_execsql_test join-13.1 {
          705  +  SELECT * FROM aa LEFT JOIN bb, cc WHERE cc.c=aa.a;
          706  +} {45 {} 45 45 {} 45}
          707  +
          708  +# In the following, the order of [cc] and [bb] must not be exchanged, even
          709  +# though this would be helpful if the query used an inner join.
          710  +do_execsql_test join-13.2 {
          711  +  CREATE INDEX ccc ON cc(c);
          712  +  SELECT * FROM aa LEFT JOIN bb, cc WHERE cc.c=aa.a;
          713  +} {45 {} 45 45 {} 45}
          714  +
   689    715   
   690    716   finish_test