where.c

最新的sqlite3.6.2源代码

    }else{
      sortOrder = termSortOrder;
    }
    j++;
    pTerm++;
    if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
      /* If the indexed column is the primary key and everything matches
      ** so far and none of the ORDER BY terms to the right reference other
      ** tables in the join, then we are assured that the index can be used 
      ** to sort because the primary key is unique and so none of the other
      ** columns will make any difference
      */
      j = nTerm;
    }
  }

  *pbRev = sortOrder!=0;
  if( j>=nTerm ){
    /* All terms of the ORDER BY clause are covered by this index so
    ** this index can be used for sorting. */
    return 1;
  }
  if( pIdx->onError!=OE_None && i==pIdx->nColumn
      && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
    /* All terms of this index match some prefix of the ORDER BY clause
    ** and the index is UNIQUE and no terms on the tail of the ORDER BY
    ** clause reference other tables in a join.  If this is all true then
    ** the order by clause is superfluous. */
    return 1;
  }
  return 0;
}

/*
** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
** by sorting in order of ROWID.  Return true if so and set *pbRev to be
** true for reverse ROWID and false for forward ROWID order.
*/
static int sortableByRowid(
  int base,               /* Cursor number for table to be sorted */
  ExprList *pOrderBy,     /* The ORDER BY clause */
  ExprMaskSet *pMaskSet,  /* Mapping from tables to bitmaps */
  int *pbRev              /* Set to 1 if ORDER BY is DESC */
){
  Expr *p;

  assert( pOrderBy!=0 );
  assert( pOrderBy->nExpr>0 );
  p = pOrderBy->a[0].pExpr;
  if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
    && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
    *pbRev = pOrderBy->a[0].sortOrder;
    return 1;
  }
  return 0;
}

/*
** Prepare a crude estimate of the logarithm of the input value.
** The results need not be exact.  This is only used for estimating
** the total cost of performing operations with O(logN) or O(NlogN)
** complexity.  Because N is just a guess, it is no great tragedy if
** logN is a little off.
*/
static double estLog(double N){
  double logN = 1;
  double x = 10;
  while( N>x ){
    logN += 1;
    x *= 10;
  }
  return logN;
}

/*
** Two routines for printing the content of an sqlite3_index_info
** structure.  Used for testing and debugging only.  If neither
** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
** are no-ops.
*/
#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
  int i;
  if( !sqlite3WhereTrace ) return;
  for(i=0; i<p->nConstraint; i++){
    sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
       i,
       p->aConstraint[i].iColumn,
       p->aConstraint[i].iTermOffset,
       p->aConstraint[i].op,
       p->aConstraint[i].usable);
  }
  for(i=0; i<p->nOrderBy; i++){
    sqlite3DebugPrintf("  orderby[%d]: col=%d desc=%d\n",
       i,
       p->aOrderBy[i].iColumn,
       p->aOrderBy[i].desc);
  }
}
static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
  int i;
  if( !sqlite3WhereTrace ) return;
  for(i=0; i<p->nConstraint; i++){
    sqlite3DebugPrintf("  usage[%d]: argvIdx=%d omit=%d\n",
       i,
       p->aConstraintUsage[i].argvIndex,
       p->aConstraintUsage[i].omit);
  }
  sqlite3DebugPrintf("  idxNum=%d\n", p->idxNum);
  sqlite3DebugPrintf("  idxStr=%s\n", p->idxStr);
  sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
  sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
}
#else
#define TRACE_IDX_INPUTS(A)
#define TRACE_IDX_OUTPUTS(A)
#endif

#ifndef SQLITE_OMIT_VIRTUALTABLE
/*
** Compute the best index for a virtual table.
**
** The best index is computed by the xBestIndex method of the virtual
** table module.  This routine is really just a wrapper that sets up
** the sqlite3_index_info structure that is used to communicate with
** xBestIndex.
**
** In a join, this routine might be called multiple times for the
** same virtual table.  The sqlite3_index_info structure is created
** and initialized on the first invocation and reused on all subsequent
** invocations.  The sqlite3_index_info structure is also used when
** code is generated to access the virtual table.  The whereInfoDelete() 
** routine takes care of freeing the sqlite3_index_info structure after
** everybody has finished with it.
*/
static double bestVirtualIndex(
  Parse *pParse,                 /* The parsing context */
  WhereClause *pWC,              /* The WHERE clause */
  struct SrcList_item *pSrc,     /* The FROM clause term to search */
  Bitmask notReady,              /* Mask of cursors that are not available */
  ExprList *pOrderBy,            /* The order by clause */
  int orderByUsable,             /* True if we can potential sort */
  sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
){
  Table *pTab = pSrc->pTab;
  sqlite3_vtab *pVtab = pTab->pVtab;
  sqlite3_index_info *pIdxInfo;
  struct sqlite3_index_constraint *pIdxCons;
  struct sqlite3_index_orderby *pIdxOrderBy;
  struct sqlite3_index_constraint_usage *pUsage;
  WhereTerm *pTerm;
  int i, j;
  int nOrderBy;
  int rc;

  /* If the sqlite3_index_info structure has not been previously
  ** allocated and initialized for this virtual table, then allocate
  ** and initialize it now
  */
  pIdxInfo = *ppIdxInfo;
  if( pIdxInfo==0 ){
    WhereTerm *pTerm;
    int nTerm;
    WHERETRACE(("Recomputing index info for %s...\n", pTab->zName));

    /* Count the number of possible WHERE clause constraints referring
    ** to this virtual table */
    for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
      testcase( pTerm->eOperator==WO_IN );
      testcase( pTerm->eOperator==WO_ISNULL );
      if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
      nTerm++;
    }

    /* If the ORDER BY clause contains only columns in the current 
    ** virtual table then allocate space for the aOrderBy part of
    ** the sqlite3_index_info structure.
    */
    nOrderBy = 0;
    if( pOrderBy ){
      for(i=0; i<pOrderBy->nExpr; i++){
        Expr *pExpr = pOrderBy->a[i].pExpr;
        if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
      }
      if( i==pOrderBy->nExpr ){
        nOrderBy = pOrderBy->nExpr;
      }
    }

    /* Allocate the sqlite3_index_info structure
    */
    pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
                             + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
                             + sizeof(*pIdxOrderBy)*nOrderBy );
    if( pIdxInfo==0 ){
      sqlite3ErrorMsg(pParse, "out of memory");
      return 0.0;
    }
    *ppIdxInfo = pIdxInfo;

    /* Initialize the structure.  The sqlite3_index_info structure contains
    ** many fields that are declared "const" to prevent xBestIndex from
    ** changing them.  We have to do some funky casting in order to
    ** initialize those fields.
    */
    pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
    pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
    pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
    *(int*)&pIdxInfo->nConstraint = nTerm;
    *(int*)&pIdxInfo->nOrderBy = nOrderBy;
    *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
    *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
    *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
                                                                     pUsage;

    for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
      if( pTerm->leftCursor != pSrc->iCursor ) continue;
      assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
      testcase( pTerm->eOperator==WO_IN );
      testcase( pTerm->eOperator==WO_ISNULL );
      if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
      pIdxCons[j].iColumn = pTerm->leftColumn;
      pIdxCons[j].iTermOffset = i;
      pIdxCons[j].op = pTerm->eOperator;
      /* The direct assignment in the previous line is possible only because
      ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical.  The
      ** following asserts verify this fact. */
      assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
      assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
      assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
      assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
      assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
      assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
      assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
      j++;
    }
    for(i=0; i<nOrderBy; i++){
      Expr *pExpr = pOrderBy->a[i].pExpr;
      pIdxOrderBy[i].iColumn = pExpr->iColumn;
      pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
    }
  }

  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  ** to will have been initialized, either during the current invocation or
  ** during some prior invocation.  Now we just have to customize the
  ** details of pIdxInfo for the current invocation and pass it to
  ** xBestIndex.
  */

  /* The module name must be defined. Also, by this point there must
  ** be a pointer to an sqlite3_vtab structure. Otherwise
  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  */
  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  assert( pVtab );
#if 0
  if( pTab->pVtab==0 ){
    sqlite3ErrorMsg(pParse, "undefined module %s for table %s",
        pTab->azModuleArg[0], pTab->zName);
    return 0.0;
  }
#endif

  /* Set the aConstraint[].usable fields and initialize all 
  ** output variables to zero.
  **
  ** aConstraint[].usable is true for constraints where the right-hand
  ** side contains only references to tables to the left of the current
  ** table.  In other words, if the constraint is of the form:
  **
  **           column = expr
  **
  ** and we are evaluating a join, then the constraint on column is 
  ** only valid if all tables referenced in expr occur to the left
  ** of the table containing column.
  **
  ** The aConstraints[] array contains entries for all constraints
  ** on the current table.  That way we only have to compute it once
  ** even though we might try to pick the best index multiple times.
  ** For each attempt at picking an index, the order of tables in the
  ** join might be different so we have to recompute the usable flag
  ** each time.
  */
  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  pUsage = pIdxInfo->aConstraintUsage;
  for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
    j = pIdxCons->iTermOffset;
    pTerm = &pWC->a[j];
    pIdxCons->usable =  (pTerm->prereqRight & notReady)==0;
  }
  memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  if( pIdxInfo->needToFreeIdxStr ){
    sqlite3_free(pIdxInfo->idxStr);
  }
  pIdxInfo->idxStr = 0;
  pIdxInfo->idxNum = 0;
  pIdxInfo->needToFreeIdxStr = 0;
  pIdxInfo->orderByConsumed = 0;
  pIdxInfo->estimatedCost = SQLITE_BIG_DBL / 2.0;
  nOrderBy = pIdxInfo->nOrderBy;
  if( pIdxInfo->nOrderBy && !orderByUsable ){
    *(int*)&pIdxInfo->nOrderBy = 0;
  }

  (void)sqlite3SafetyOff(pParse->db);
  WHERETRACE(("xBestIndex for %s\n", pTab->zName));
  TRACE_IDX_INPUTS(pIdxInfo);
  rc = pVtab->pModule->xBestIndex(pVtab, pIdxInfo);
  TRACE_IDX_OUTPUTS(pIdxInfo);
  (void)sqlite3SafetyOn(pParse->db);

  if( rc!=SQLITE_OK ){
    if( rc==SQLITE_NOMEM ){
      pParse->db->mallocFailed = 1;
    }else if( !pVtab->zErrMsg ){
      sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
    }else{
      sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
    }
  }
  sqlite3DbFree(pParse->db, pVtab->zErrMsg);
  pVtab->zErrMsg = 0;

  for(i=0; i<pIdxInfo->nConstraint; i++){
    if( !pIdxInfo->aConstraint[i].usable && pUsage[i].argvIndex>0 ){
      sqlite3ErrorMsg(pParse, 
          "table %s: xBestIndex returned an invalid plan", pTab->zName);
      return 0.0;
    }
  }

  *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  return pIdxInfo->estimatedCost;
}
#endif /* SQLITE_OMIT_VIRTUALTABLE */

/*
** Find the best index for accessing a particular table.  Return a pointer
** to the index, flags that describe how the index should be used, the
** number of equality constraints, and the "cost" for this index.
**
** The lowest cost index wins.  The cost is an estimate of the amount of
** CPU and disk I/O need to process the request using the selected index.
** Factors that influence cost include:
**
**    *  The estimated number of rows that will be retrieved.  (The
**       fewer the better.)
**
**    *  Whether or not sorting must occur.
**
**    *  Whether or not there must be separate lookups in the
**       index and in the main table.
**
*/
static double bestIndex(
  Parse *pParse,              /* The parsing context */
  WhereClause *pWC,           /* The WHERE clause */
  struct SrcList_item *pSrc,  /* The FROM clause term to search */
  Bitmask notReady,           /* Mask of cursors that are not available */
  ExprList *pOrderBy,         /* The order by clause */
  Index **ppIndex,            /* Make *ppIndex point to the best index */
  int *pFlags,                /* Put flags describing this choice in *pFlags */
  int *pnEq                   /* Put the number of == or IN constraints here */
){
  WhereTerm *pTerm;
  Index *bestIdx = 0;         /* Index that gives the lowest cost */
  double lowestCost;          /* The cost of using bestIdx */
  int bestFlags = 0;          /* Flags associated with bestIdx */
  int bestNEq = 0;            /* Best value for nEq */
  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */