/ Check-in [19544438]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Change the way SQLite invokes the xBestIndex method of virtual tables so that N-way joins involving virtual tables work as expected.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 195444380bafd3d95d37ad83047c75ca20978de4
User & Date: dan 2016-03-05 21:07:49
Context
2016-03-05
21:32
Fix a problem in the previous commit affecting queries with three or more tables joined together to the right of a LEFT or CROSS JOIN operator. check-in: d8d89d69 user: dan tags: trunk
21:07
Change the way SQLite invokes the xBestIndex method of virtual tables so that N-way joins involving virtual tables work as expected. check-in: 19544438 user: dan tags: trunk
20:28
Adjust the cost estimates for RTREE such that the expected number of rows and expected cost is halved for each additional constraint. Closed-Leaf check-in: fd7cd060 user: drh tags: xbestindex-fix
15:35
Remove the unused journal.c source file (its function have been subsumed into memjournal.c). Refactor some of the names in memjournal.c. No functional changes. check-in: 5f2a262d user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

  1737   1737   
  1738   1738     pIdxInfo->idxNum = 2;
  1739   1739     pIdxInfo->needToFreeIdxStr = 1;
  1740   1740     if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
  1741   1741       return SQLITE_NOMEM;
  1742   1742     }
  1743   1743   
  1744         -  nRow = pRtree->nRowEst / (iIdx + 1);
         1744  +  nRow = pRtree->nRowEst >> (iIdx/2);
  1745   1745     pIdxInfo->estimatedCost = (double)6.0 * (double)nRow;
  1746   1746     setEstimatedRows(pIdxInfo, nRow);
  1747   1747   
  1748   1748     return rc;
  1749   1749   }
  1750   1750   
  1751   1751   /*

Changes to src/test_bestindex.c.

   111    111   };
   112    112   
   113    113   /* A tcl cursor object */
   114    114   struct tcl_cursor {
   115    115     sqlite3_vtab_cursor base;
   116    116     sqlite3_stmt *pStmt;            /* Read data from here */
   117    117   };
          118  +
          119  +/*
          120  +** Dequote string z in place.
          121  +*/
          122  +static void tclDequote(char *z){
          123  +  char q = z[0];
          124  +
          125  +  /* Set stack variable q to the close-quote character */
          126  +  if( q=='[' || q=='\'' || q=='"' || q=='`' ){
          127  +    int iIn = 1;
          128  +    int iOut = 0;
          129  +    if( q=='[' ) q = ']';  
          130  +
          131  +    while( ALWAYS(z[iIn]) ){
          132  +      if( z[iIn]==q ){
          133  +        if( z[iIn+1]!=q ){
          134  +          /* Character iIn was the close quote. */
          135  +          iIn++;
          136  +          break;
          137  +        }else{
          138  +          /* Character iIn and iIn+1 form an escaped quote character. Skip
          139  +          ** the input cursor past both and copy a single quote character 
          140  +          ** to the output buffer. */
          141  +          iIn += 2;
          142  +          z[iOut++] = q;
          143  +        }
          144  +      }else{
          145  +        z[iOut++] = z[iIn++];
          146  +      }
          147  +    }
          148  +
          149  +    z[iOut] = '\0';
          150  +  }
          151  +}
   118    152   
   119    153   /*
   120    154   ** This function is the implementation of both the xConnect and xCreate
   121    155   ** methods of the fs virtual table.
   122    156   **
   123    157   ** The argv[] array contains the following:
   124    158   **
................................................................................
   131    165     sqlite3 *db,
   132    166     void *pAux,
   133    167     int argc, const char *const*argv,
   134    168     sqlite3_vtab **ppVtab,
   135    169     char **pzErr
   136    170   ){
   137    171     Tcl_Interp *interp = (Tcl_Interp*)pAux;
   138         -  tcl_vtab *pTab;
   139         -  const char *zCmd;
          172  +  tcl_vtab *pTab = 0;
          173  +  char *zCmd = 0;
   140    174     Tcl_Obj *pScript = 0;
   141         -  int rc;
          175  +  int rc = SQLITE_OK;
   142    176   
   143    177     if( argc!=4 ){
   144    178       *pzErr = sqlite3_mprintf("wrong number of arguments");
   145    179       return SQLITE_ERROR;
   146    180     }
   147         -  zCmd = argv[3];
   148    181   
          182  +  zCmd = sqlite3_malloc(strlen(argv[3])+1);
   149    183     pTab = (tcl_vtab*)sqlite3_malloc(sizeof(tcl_vtab));
   150         -  if( pTab==0 ) return SQLITE_NOMEM;
   151         -  memset(pTab, 0, sizeof(tcl_vtab));
   152         -
   153         -  pTab->pCmd = Tcl_NewStringObj(zCmd, -1);
   154         -  pTab->interp = interp;
   155         -  pTab->db = db;
   156         -  Tcl_IncrRefCount(pTab->pCmd);
   157         -
   158         -  pScript = Tcl_DuplicateObj(pTab->pCmd);
   159         -  Tcl_IncrRefCount(pScript);
   160         -  Tcl_ListObjAppendElement(interp, pScript, Tcl_NewStringObj("xConnect", -1));
   161         -
   162         -  rc = Tcl_EvalObjEx(interp, pScript, TCL_EVAL_GLOBAL);
   163         -  if( rc!=TCL_OK ){
   164         -    *pzErr = sqlite3_mprintf("%s", Tcl_GetStringResult(interp));
   165         -    rc = SQLITE_ERROR;
          184  +  if( zCmd && pTab ){
          185  +    memcpy(zCmd, argv[3], strlen(argv[3])+1);
          186  +    tclDequote(zCmd);
          187  +    memset(pTab, 0, sizeof(tcl_vtab));
          188  +
          189  +    pTab->pCmd = Tcl_NewStringObj(zCmd, -1);
          190  +    pTab->interp = interp;
          191  +    pTab->db = db;
          192  +    Tcl_IncrRefCount(pTab->pCmd);
          193  +
          194  +    pScript = Tcl_DuplicateObj(pTab->pCmd);
          195  +    Tcl_IncrRefCount(pScript);
          196  +    Tcl_ListObjAppendElement(interp, pScript, Tcl_NewStringObj("xConnect", -1));
          197  +
          198  +    rc = Tcl_EvalObjEx(interp, pScript, TCL_EVAL_GLOBAL);
          199  +    if( rc!=TCL_OK ){
          200  +      *pzErr = sqlite3_mprintf("%s", Tcl_GetStringResult(interp));
          201  +      rc = SQLITE_ERROR;
          202  +    }else{
          203  +      rc = sqlite3_declare_vtab(db, Tcl_GetStringResult(interp));
          204  +    }
          205  +
          206  +    if( rc!=SQLITE_OK ){
          207  +      sqlite3_free(pTab);
          208  +      pTab = 0;
          209  +    }
   166    210     }else{
   167         -    rc = sqlite3_declare_vtab(db, Tcl_GetStringResult(interp));
          211  +    rc = SQLITE_NOMEM;
   168    212     }
   169    213   
   170         -  if( rc!=SQLITE_OK ){
   171         -    sqlite3_free(pTab);
   172         -    pTab = 0;
   173         -  }
   174         -
          214  +  sqlite3_free(zCmd);
   175    215     *ppVtab = &pTab->base;
   176    216     return rc;
   177    217   }
   178    218   
   179    219   /* The xDisconnect and xDestroy methods are also the same */
   180    220   static int tclDisconnect(sqlite3_vtab *pVtab){
   181    221     tcl_vtab *pTab = (tcl_vtab*)pVtab;

Changes to src/where.c.

  2744   2744       ** considered. */
  2745   2745       if( pSrc->pIBIndex ) break;
  2746   2746     }
  2747   2747     return rc;
  2748   2748   }
  2749   2749   
  2750   2750   #ifndef SQLITE_OMIT_VIRTUALTABLE
         2751  +
         2752  +/*
         2753  +** Argument pIdxInfo is already populated with all constraints that may
         2754  +** be used by the virtual table identified by pBuilder->pNew->iTab. This
         2755  +** function marks a subset of those constraints usable, invokes the
         2756  +** xBestIndex method and adds the returned plan to pBuilder.
         2757  +**
         2758  +** A constraint is marked usable if:
         2759  +**
         2760  +**   * Argument mUsable indicates that its prerequisites are available, and
         2761  +**
         2762  +**   * It is not one of the operators specified in the mExclude mask passed
         2763  +**     as the fourth argument (which in practice is either WO_IN or 0).
         2764  +**
         2765  +** Argument mExtra is a mask of tables that must be scanned before the
         2766  +** virtual table in question. These are added to the plans prerequisites
         2767  +** before it is added to pBuilder.
         2768  +**
         2769  +** Output parameter *pbIn is set to true if the plan added to pBuilder
         2770  +** uses one or more WO_IN terms, or false otherwise.
         2771  +*/
         2772  +static int whereLoopAddVirtualOne(
         2773  +  WhereLoopBuilder *pBuilder,
         2774  +  Bitmask mExtra,                 /* Mask of tables that must be used. */
         2775  +  Bitmask mUsable,                /* Mask of usable prereqs */
         2776  +  u16 mExclude,                   /* Exclude terms for this operator */
         2777  +  sqlite3_index_info *pIdxInfo,   /* Populated object for xBestIndex */
         2778  +  int *pbIn                       /* OUT: True if plan uses an IN(...) op */
         2779  +){
         2780  +  WhereClause *pWC = pBuilder->pWC;
         2781  +  struct sqlite3_index_constraint *pIdxCons;
         2782  +  struct sqlite3_index_constraint_usage *pUsage = pIdxInfo->aConstraintUsage;
         2783  +  int i;
         2784  +  int mxTerm;
         2785  +  int rc = SQLITE_OK;
         2786  +  WhereLoop *pNew = pBuilder->pNew;
         2787  +  Parse *pParse = pBuilder->pWInfo->pParse;
         2788  +  struct SrcList_item *pSrc = &pBuilder->pWInfo->pTabList->a[pNew->iTab];
         2789  +  int nConstraint = pIdxInfo->nConstraint;
         2790  +
         2791  +  assert( (mUsable & mExtra)==mExtra );
         2792  +  *pbIn = 0;
         2793  +  pNew->prereq = mExtra;
         2794  +
         2795  +  /* Set the usable flag on the subset of constraints identified by 
         2796  +  ** arguments mUsable and mExclude. */
         2797  +  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
         2798  +  for(i=0; i<nConstraint; i++, pIdxCons++){
         2799  +    WhereTerm *pTerm = &pWC->a[pIdxCons->iTermOffset];
         2800  +    pIdxCons->usable = 0;
         2801  +    if( (pTerm->prereqRight & mUsable)==pTerm->prereqRight 
         2802  +     && (pTerm->eOperator & mExclude)==0
         2803  +    ){
         2804  +      pIdxCons->usable = 1;
         2805  +    }
         2806  +  }
         2807  +
         2808  +  /* Initialize the output fields of the sqlite3_index_info structure */
         2809  +  memset(pUsage, 0, sizeof(pUsage[0])*nConstraint);
         2810  +  if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
         2811  +  pIdxInfo->idxStr = 0;
         2812  +  pIdxInfo->idxNum = 0;
         2813  +  pIdxInfo->needToFreeIdxStr = 0;
         2814  +  pIdxInfo->orderByConsumed = 0;
         2815  +  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2;
         2816  +  pIdxInfo->estimatedRows = 25;
         2817  +  pIdxInfo->idxFlags = 0;
         2818  +  pIdxInfo->colUsed = (sqlite3_int64)pSrc->colUsed;
         2819  +
         2820  +  /* Invoke the virtual table xBestIndex() method */
         2821  +  rc = vtabBestIndex(pParse, pSrc->pTab, pIdxInfo);
         2822  +  if( rc ) return rc;
         2823  +
         2824  +  mxTerm = -1;
         2825  +  assert( pNew->nLSlot>=nConstraint );
         2826  +  for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
         2827  +  pNew->u.vtab.omitMask = 0;
         2828  +  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
         2829  +  for(i=0; i<nConstraint; i++, pIdxCons++){
         2830  +    int iTerm;
         2831  +    if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
         2832  +      WhereTerm *pTerm;
         2833  +      int j = pIdxCons->iTermOffset;
         2834  +      if( iTerm>=nConstraint
         2835  +       || j<0
         2836  +       || j>=pWC->nTerm
         2837  +       || pNew->aLTerm[iTerm]!=0
         2838  +      ){
         2839  +        rc = SQLITE_ERROR;
         2840  +        sqlite3ErrorMsg(pParse,"%s.xBestIndex() malfunction",pSrc->pTab->zName);
         2841  +        return rc;
         2842  +      }
         2843  +      testcase( iTerm==nConstraint-1 );
         2844  +      testcase( j==0 );
         2845  +      testcase( j==pWC->nTerm-1 );
         2846  +      pTerm = &pWC->a[j];
         2847  +      pNew->prereq |= pTerm->prereqRight;
         2848  +      assert( iTerm<pNew->nLSlot );
         2849  +      pNew->aLTerm[iTerm] = pTerm;
         2850  +      if( iTerm>mxTerm ) mxTerm = iTerm;
         2851  +      testcase( iTerm==15 );
         2852  +      testcase( iTerm==16 );
         2853  +      if( iTerm<16 && pUsage[i].omit ) pNew->u.vtab.omitMask |= 1<<iTerm;
         2854  +      if( (pTerm->eOperator & WO_IN)!=0 ){
         2855  +        /* A virtual table that is constrained by an IN clause may not
         2856  +        ** consume the ORDER BY clause because (1) the order of IN terms
         2857  +        ** is not necessarily related to the order of output terms and
         2858  +        ** (2) Multiple outputs from a single IN value will not merge
         2859  +        ** together.  */
         2860  +        pIdxInfo->orderByConsumed = 0;
         2861  +        pIdxInfo->idxFlags &= ~SQLITE_INDEX_SCAN_UNIQUE;
         2862  +        *pbIn = 1;
         2863  +      }
         2864  +    }
         2865  +  }
         2866  +
         2867  +  pNew->nLTerm = mxTerm+1;
         2868  +  assert( pNew->nLTerm<=pNew->nLSlot );
         2869  +  pNew->u.vtab.idxNum = pIdxInfo->idxNum;
         2870  +  pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
         2871  +  pIdxInfo->needToFreeIdxStr = 0;
         2872  +  pNew->u.vtab.idxStr = pIdxInfo->idxStr;
         2873  +  pNew->u.vtab.isOrdered = (i8)(pIdxInfo->orderByConsumed ?
         2874  +      pIdxInfo->nOrderBy : 0);
         2875  +  pNew->rSetup = 0;
         2876  +  pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
         2877  +  pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows);
         2878  +
         2879  +  /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
         2880  +  ** that the scan will visit at most one row. Clear it otherwise. */
         2881  +  if( pIdxInfo->idxFlags & SQLITE_INDEX_SCAN_UNIQUE ){
         2882  +    pNew->wsFlags |= WHERE_ONEROW;
         2883  +  }else{
         2884  +    pNew->wsFlags &= ~WHERE_ONEROW;
         2885  +  }
         2886  +  whereLoopInsert(pBuilder, pNew);
         2887  +  if( pNew->u.vtab.needFree ){
         2888  +    sqlite3_free(pNew->u.vtab.idxStr);
         2889  +    pNew->u.vtab.needFree = 0;
         2890  +  }
         2891  +
         2892  +  return SQLITE_OK;
         2893  +}
         2894  +
         2895  +
  2751   2896   /*
  2752   2897   ** Add all WhereLoop objects for a table of the join identified by
  2753   2898   ** pBuilder->pNew->iTab.  That table is guaranteed to be a virtual table.
  2754   2899   **
  2755   2900   ** If there are no LEFT or CROSS JOIN joins in the query, both mExtra and
  2756   2901   ** mUnusable are set to 0. Otherwise, mExtra is a mask of all FROM clause
  2757   2902   ** entries that occur before the virtual table in the FROM clause and are
................................................................................
  2774   2919   ** mUnusable should always be configured as "not-usable" for xBestIndex.
  2775   2920   */
  2776   2921   static int whereLoopAddVirtual(
  2777   2922     WhereLoopBuilder *pBuilder,  /* WHERE clause information */
  2778   2923     Bitmask mExtra,              /* Tables that must be scanned before this one */
  2779   2924     Bitmask mUnusable            /* Tables that must be scanned after this one */
  2780   2925   ){
         2926  +  int rc = SQLITE_OK;          /* Return code */
  2781   2927     WhereInfo *pWInfo;           /* WHERE analysis context */
  2782   2928     Parse *pParse;               /* The parsing context */
  2783   2929     WhereClause *pWC;            /* The WHERE clause */
  2784   2930     struct SrcList_item *pSrc;   /* The FROM clause term to search */
  2785         -  Table *pTab;
  2786         -  sqlite3 *db;
  2787         -  sqlite3_index_info *pIdxInfo;
  2788         -  struct sqlite3_index_constraint *pIdxCons;
  2789         -  struct sqlite3_index_constraint_usage *pUsage;
  2790         -  WhereTerm *pTerm;
  2791         -  int i, j;
  2792         -  int iTerm, mxTerm;
  2793         -  int nConstraint;
  2794         -  int seenIn = 0;              /* True if an IN operator is seen */
  2795         -  int seenVar = 0;             /* True if a non-constant constraint is seen */
  2796         -  int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
         2931  +  sqlite3_index_info *p;       /* Object to pass to xBestIndex() */
         2932  +  int nConstraint;             /* Number of constraints in p */
         2933  +  int bIn;                     /* True if plan uses IN(...) operator */
  2797   2934     WhereLoop *pNew;
  2798         -  int rc = SQLITE_OK;
         2935  +  Bitmask mBest;               /* Tables used by best possible plan */
  2799   2936   
  2800   2937     assert( (mExtra & mUnusable)==0 );
  2801   2938     pWInfo = pBuilder->pWInfo;
  2802   2939     pParse = pWInfo->pParse;
  2803         -  db = pParse->db;
  2804   2940     pWC = pBuilder->pWC;
  2805   2941     pNew = pBuilder->pNew;
  2806   2942     pSrc = &pWInfo->pTabList->a[pNew->iTab];
  2807         -  pTab = pSrc->pTab;
  2808         -  assert( IsVirtual(pTab) );
  2809         -  pIdxInfo = allocateIndexInfo(pParse, pWC, mUnusable, pSrc,pBuilder->pOrderBy);
  2810         -  if( pIdxInfo==0 ) return SQLITE_NOMEM_BKPT;
  2811         -  pNew->prereq = 0;
         2943  +  assert( IsVirtual(pSrc->pTab) );
         2944  +  p = allocateIndexInfo(pParse, pWC, mUnusable, pSrc,pBuilder->pOrderBy);
         2945  +  if( p==0 ) return SQLITE_NOMEM_BKPT;
  2812   2946     pNew->rSetup = 0;
  2813   2947     pNew->wsFlags = WHERE_VIRTUALTABLE;
  2814   2948     pNew->nLTerm = 0;
  2815   2949     pNew->u.vtab.needFree = 0;
  2816         -  pUsage = pIdxInfo->aConstraintUsage;
  2817         -  nConstraint = pIdxInfo->nConstraint;
  2818         -  if( whereLoopResize(db, pNew, nConstraint) ){
  2819         -    sqlite3DbFree(db, pIdxInfo);
         2950  +  nConstraint = p->nConstraint;
         2951  +  if( whereLoopResize(pParse->db, pNew, nConstraint) ){
         2952  +    sqlite3DbFree(pParse->db, p);
  2820   2953       return SQLITE_NOMEM_BKPT;
  2821   2954     }
  2822   2955   
  2823         -  for(iPhase=0; iPhase<=3; iPhase++){
  2824         -    if( !seenIn && (iPhase&1)!=0 ){
  2825         -      iPhase++;
  2826         -      if( iPhase>3 ) break;
  2827         -    }
  2828         -    if( !seenVar && iPhase>1 ) break;
  2829         -    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2830         -    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2831         -      j = pIdxCons->iTermOffset;
  2832         -      pTerm = &pWC->a[j];
  2833         -      switch( iPhase ){
  2834         -        case 0:    /* Constants without IN operator */
  2835         -          pIdxCons->usable = 0;
  2836         -          if( (pTerm->eOperator & WO_IN)!=0 ){
  2837         -            seenIn = 1;
  2838         -          }
  2839         -          if( (pTerm->prereqRight & ~mExtra)!=0 ){
  2840         -            seenVar = 1;
  2841         -          }else if( (pTerm->eOperator & WO_IN)==0 ){
  2842         -            pIdxCons->usable = 1;
  2843         -          }
  2844         -          break;
  2845         -        case 1:    /* Constants with IN operators */
  2846         -          assert( seenIn );
  2847         -          pIdxCons->usable = (pTerm->prereqRight & ~mExtra)==0;
  2848         -          break;
  2849         -        case 2:    /* Variables without IN */
  2850         -          assert( seenVar );
  2851         -          pIdxCons->usable = (pTerm->eOperator & WO_IN)==0;
  2852         -          break;
  2853         -        default:   /* Variables with IN */
  2854         -          assert( seenVar && seenIn );
  2855         -          pIdxCons->usable = 1;
  2856         -          break;
  2857         -      }
  2858         -    }
  2859         -    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  2860         -    if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  2861         -    pIdxInfo->idxStr = 0;
  2862         -    pIdxInfo->idxNum = 0;
  2863         -    pIdxInfo->needToFreeIdxStr = 0;
  2864         -    pIdxInfo->orderByConsumed = 0;
  2865         -    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / (double)2;
  2866         -    pIdxInfo->estimatedRows = 25;
  2867         -    pIdxInfo->idxFlags = 0;
  2868         -    pIdxInfo->colUsed = (sqlite3_int64)pSrc->colUsed;
  2869         -    rc = vtabBestIndex(pParse, pTab, pIdxInfo);
  2870         -    if( rc ) goto whereLoopAddVtab_exit;
  2871         -    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2872         -    pNew->prereq = mExtra;
  2873         -    mxTerm = -1;
  2874         -    assert( pNew->nLSlot>=nConstraint );
  2875         -    for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
  2876         -    pNew->u.vtab.omitMask = 0;
  2877         -    for(i=0; i<nConstraint; i++, pIdxCons++){
  2878         -      if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
  2879         -        j = pIdxCons->iTermOffset;
  2880         -        if( iTerm>=nConstraint
  2881         -         || j<0
  2882         -         || j>=pWC->nTerm
  2883         -         || pNew->aLTerm[iTerm]!=0
  2884         -        ){
  2885         -          rc = SQLITE_ERROR;
  2886         -          sqlite3ErrorMsg(pParse, "%s.xBestIndex() malfunction", pTab->zName);
  2887         -          goto whereLoopAddVtab_exit;
  2888         -        }
  2889         -        testcase( iTerm==nConstraint-1 );
  2890         -        testcase( j==0 );
  2891         -        testcase( j==pWC->nTerm-1 );
  2892         -        pTerm = &pWC->a[j];
  2893         -        pNew->prereq |= pTerm->prereqRight;
  2894         -        assert( iTerm<pNew->nLSlot );
  2895         -        pNew->aLTerm[iTerm] = pTerm;
  2896         -        if( iTerm>mxTerm ) mxTerm = iTerm;
  2897         -        testcase( iTerm==15 );
  2898         -        testcase( iTerm==16 );
  2899         -        if( iTerm<16 && pUsage[i].omit ) pNew->u.vtab.omitMask |= 1<<iTerm;
  2900         -        if( (pTerm->eOperator & WO_IN)!=0 ){
  2901         -          /* A virtual table that is constrained by an IN clause may not
  2902         -          ** consume the ORDER BY clause because (1) the order of IN terms
  2903         -          ** is not necessarily related to the order of output terms and
  2904         -          ** (2) Multiple outputs from a single IN value will not merge
  2905         -          ** together.  */
  2906         -          pIdxInfo->orderByConsumed = 0;
  2907         -          pIdxInfo->idxFlags &= ~SQLITE_INDEX_SCAN_UNIQUE;
  2908         -        }
  2909         -      }
  2910         -    }
  2911         -    if( i>=nConstraint ){
  2912         -      pNew->nLTerm = mxTerm+1;
  2913         -      assert( pNew->nLTerm<=pNew->nLSlot );
  2914         -      pNew->u.vtab.idxNum = pIdxInfo->idxNum;
  2915         -      pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  2916         -      pIdxInfo->needToFreeIdxStr = 0;
  2917         -      pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  2918         -      pNew->u.vtab.isOrdered = (i8)(pIdxInfo->orderByConsumed ?
  2919         -                                      pIdxInfo->nOrderBy : 0);
  2920         -      pNew->rSetup = 0;
  2921         -      pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
  2922         -      pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows);
  2923         -
  2924         -      /* Set the WHERE_ONEROW flag if the xBestIndex() method indicated
  2925         -      ** that the scan will visit at most one row. Clear it otherwise. */
  2926         -      if( pIdxInfo->idxFlags & SQLITE_INDEX_SCAN_UNIQUE ){
  2927         -        pNew->wsFlags |= WHERE_ONEROW;
  2928         -      }else{
  2929         -        pNew->wsFlags &= ~WHERE_ONEROW;
  2930         -      }
  2931         -      whereLoopInsert(pBuilder, pNew);
  2932         -      if( pNew->u.vtab.needFree ){
  2933         -        sqlite3_free(pNew->u.vtab.idxStr);
  2934         -        pNew->u.vtab.needFree = 0;
  2935         -      }
  2936         -    }
  2937         -  }  
  2938         -
  2939         -whereLoopAddVtab_exit:
  2940         -  if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  2941         -  sqlite3DbFree(db, pIdxInfo);
         2956  +  /* First call xBestIndex() with all constraints usable. */
         2957  +  rc = whereLoopAddVirtualOne(pBuilder, mExtra, (Bitmask)(-1), 0, p, &bIn);
         2958  +  mBest = pNew->prereq & ~mExtra;
         2959  +
         2960  +  /* If the call to xBestIndex() with all terms enabled produced a plan
         2961  +  ** that does not require any source tables, there is no point in making
         2962  +  ** any further calls - if the xBestIndex() method is sane they will all
         2963  +  ** return the same plan anyway.
         2964  +  */
         2965  +  if( mBest ){
         2966  +    int seenZero = 0;             /* True if a plan with no prereqs seen */
         2967  +    int seenZeroNoIN = 0;         /* Plan with no prereqs and no IN(...) seen */
         2968  +    Bitmask mPrev = 0;
         2969  +    Bitmask mBestNoIn = 0;
         2970  +
         2971  +    /* If the plan produced by the earlier call uses an IN(...) term, call
         2972  +    ** xBestIndex again, this time with IN(...) terms disabled. */
         2973  +    if( rc==SQLITE_OK && bIn ){
         2974  +      rc = whereLoopAddVirtualOne(pBuilder, mExtra, (Bitmask)-1, WO_IN, p,&bIn);
         2975  +      mBestNoIn = pNew->prereq & ~mExtra;
         2976  +      if( mBestNoIn==0 ){
         2977  +        seenZero = 1;
         2978  +        if( bIn==0 ) seenZeroNoIN = 1;
         2979  +      }
         2980  +    }
         2981  +
         2982  +    /* Call xBestIndex once for each distinct value of (prereqRight & ~mExtra) 
         2983  +    ** in the set of terms that apply to the current virtual table.  */
         2984  +    while( rc==SQLITE_OK ){
         2985  +      int i;
         2986  +      Bitmask mNext = (Bitmask)(-1);
         2987  +      assert( mNext>0 );
         2988  +      for(i=0; i<nConstraint; i++){
         2989  +        Bitmask mThis = (
         2990  +            pWC->a[p->aConstraint[i].iTermOffset].prereqRight & ~mExtra
         2991  +        );
         2992  +        if( mThis>mPrev && mThis<mNext ) mNext = mThis;
         2993  +      }
         2994  +      mPrev = mNext;
         2995  +      if( mNext==(Bitmask)(-1) ) break;
         2996  +      if( mNext==mBest || mNext==mBestNoIn ) continue;
         2997  +      rc = whereLoopAddVirtualOne(pBuilder, mExtra, mNext, 0, p, &bIn);
         2998  +      if( pNew->prereq==mExtra ){
         2999  +        seenZero = 1;
         3000  +        if( bIn==0 ) seenZeroNoIN = 1;
         3001  +      }
         3002  +    }
         3003  +
         3004  +    /* If the calls to xBestIndex() in the above loop did not find a plan
         3005  +    ** that requires no source tables at all (i.e. one guaranteed to be
         3006  +    ** usable), make a call here with all source tables disabled */
         3007  +    if( rc==SQLITE_OK && seenZero==0 ){
         3008  +      rc = whereLoopAddVirtualOne(pBuilder, mExtra, mExtra, 0, p, &bIn);
         3009  +      if( bIn==0 ) seenZeroNoIN = 1;
         3010  +    }
         3011  +
         3012  +    /* If the calls to xBestIndex() have so far failed to find a plan
         3013  +    ** that requires no source tables at all and does not use an IN(...)
         3014  +    ** operator, make a final call to obtain one here.  */
         3015  +    if( rc==SQLITE_OK && seenZeroNoIN==0 ){
         3016  +      rc = whereLoopAddVirtualOne(pBuilder, mExtra, mExtra, WO_IN, p, &bIn);
         3017  +    }
         3018  +  }
         3019  +
         3020  +  if( p->needToFreeIdxStr ) sqlite3_free(p->idxStr);
         3021  +  sqlite3DbFree(pParse->db, p);
  2942   3022     return rc;
  2943   3023   }
  2944   3024   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  2945   3025   
  2946   3026   /*
  2947   3027   ** Add WhereLoop entries to handle OR terms.  This works for either
  2948   3028   ** btrees or virtual tables.

Added test/bestindex2.test.

            1  +# 2016 March 3
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +
           12  +set testdir [file dirname $argv0]
           13  +source $testdir/tester.tcl
           14  +set testprefix bestindex2
           15  +
           16  +
           17  +#-------------------------------------------------------------------------
           18  +# Virtual table callback for table named $tbl, with the columns specified
           19  +# by list argument $cols. e.g. if the function is invoked as:
           20  +#
           21  +#   vtab_cmd t1 {a b c} ...
           22  +#
           23  +# The table created is:
           24  +#
           25  +#      "CREATE TABLE t1 (a, b, c)"
           26  +#
           27  +# The tables xBestIndex method behaves as if all possible combinations of
           28  +# "=" constraints (but no others) may be optimized. The cost of a full table
           29  +# scan is:
           30  +#
           31  +#      "WHERE 1"                "cost 1000000 rows 1000000"
           32  +#
           33  +# If one or more "=" constraints are in use, the cost and estimated number
           34  +# of rows returned are both is (11 - nCons)*1000, where nCons is the number
           35  +# of constraints used. e.g.
           36  +#
           37  +#   "WHERE a=? AND b=?"    ->   "cost  900 rows  900"
           38  +#   "WHERE c=? AND b<?"    ->   "cost 1000 rows 1000"
           39  +#  
           40  +proc vtab_cmd {tbl cols method args} {
           41  +  switch -- $method {
           42  +    xConnect {
           43  +      return "CREATE TABLE $tbl ([join $cols ,])"
           44  +    }
           45  +    xBestIndex {
           46  +      foreach {clist orderby mask} $args {}
           47  +
           48  +      set cons [list]
           49  +      set used [list]
           50  +
           51  +      for {set i 0} {$i < [llength $clist]} {incr i} {
           52  +        array unset C
           53  +        array set C [lindex $clist $i]
           54  +        if {$C(op)=="eq" && $C(usable) && [lsearch $cons $C(column)]<0} {
           55  +          lappend used use $i
           56  +          lappend cons $C(column)
           57  +        }
           58  +      }
           59  +
           60  +      set nCons [llength $cons]
           61  +      if {$nCons==0} {
           62  +        return "cost 1000000 rows 1000000"
           63  +      } else {
           64  +        set cost [expr (11-$nCons) * 1000]
           65  +        set ret [concat $used "cost $cost rows $cost"]
           66  +
           67  +        set txt [list]
           68  +        foreach c $cons { lappend txt "[lindex $cols $c]=?" }
           69  +        lappend ret idxstr "indexed([join $txt { AND }])"
           70  +
           71  +        return $ret
           72  +      }
           73  +    }
           74  +  }
           75  +  return ""
           76  +}
           77  +
           78  +register_tcl_module db
           79  +
           80  +do_execsql_test 1.0 {
           81  +  CREATE VIRTUAL TABLE t1 USING tcl("vtab_cmd t1 {a b}");
           82  +  CREATE VIRTUAL TABLE t2 USING tcl("vtab_cmd t2 {c d}");
           83  +  CREATE VIRTUAL TABLE t3 USING tcl("vtab_cmd t3 {e f}");
           84  +}
           85  +
           86  +do_eqp_test 1.1 {
           87  +  SELECT * FROM t1 WHERE a='abc'
           88  +} {
           89  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:indexed(a=?)}
           90  +}
           91  +do_eqp_test 1.2 {
           92  +  SELECT * FROM t1 WHERE a='abc' AND b='def'
           93  +} {
           94  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:indexed(a=? AND b=?)}
           95  +}
           96  +do_eqp_test 1.3 {
           97  +  SELECT * FROM t1 WHERE a='abc' AND a='def'
           98  +} {
           99  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:indexed(a=?)}
          100  +}
          101  +do_eqp_test 1.4 {
          102  +  SELECT * FROM t1,t2 WHERE c=a
          103  +} {
          104  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:} 
          105  +  0 1 1 {SCAN TABLE t2 VIRTUAL TABLE INDEX 0:indexed(c=?)}
          106  +}
          107  +
          108  +do_eqp_test 1.5 {
          109  +  SELECT * FROM t1, t2 CROSS JOIN t3 WHERE t2.c = +t1.b AND t3.e=t2.d
          110  +} {
          111  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:} 
          112  +  0 1 1 {SCAN TABLE t2 VIRTUAL TABLE INDEX 0:indexed(c=?)} 
          113  +  0 2 2 {SCAN TABLE t3 VIRTUAL TABLE INDEX 0:indexed(e=?)}
          114  +}
          115  +
          116  +# This is the one that fails (as of 2016/3/3).
          117  +#
          118  +do_eqp_test 1.6 {
          119  +  SELECT * FROM t1, t2, t3 WHERE t2.c = +t1.b AND t3.e = t2.d
          120  +} {
          121  +  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 0:} 
          122  +  0 1 1 {SCAN TABLE t2 VIRTUAL TABLE INDEX 0:indexed(c=?)} 
          123  +  0 2 2 {SCAN TABLE t3 VIRTUAL TABLE INDEX 0:indexed(e=?)}
          124  +}
          125  +
          126  +finish_test
          127  +