/ Check-in [4f20ac90]
Login

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

Overview
Comment:Code simplifications in select.c and where.c.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | view-optimization
Files: files | file ages | folders
SHA1: 4f20ac90bce8bd7ba43ef59af5cc4ef7aa282fe8
User & Date: drh 2015-06-06 18:30:17
Context
2015-06-06
20:12
Split out the bulk of the actual VDBE code generation logic from where.c into a new file, leaving behind the analysis logic. This makes the original where.c smaller and hopefully easier to edit. check-in: faa0e420 user: drh tags: view-optimization
18:30
Code simplifications in select.c and where.c. check-in: 4f20ac90 user: drh tags: view-optimization
00:18
Minor cleanup of the sqlite3Select() procedure. check-in: f4c90d06 user: drh tags: view-optimization
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  1306   1306   ** The declaration type for any expression other than a column is NULL.
  1307   1307   **
  1308   1308   ** This routine has either 3 or 6 parameters depending on whether or not
  1309   1309   ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used.
  1310   1310   */
  1311   1311   #ifdef SQLITE_ENABLE_COLUMN_METADATA
  1312   1312   # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F)
         1313  +#else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
         1314  +# define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
         1315  +#endif
  1313   1316   static const char *columnTypeImpl(
  1314   1317     NameContext *pNC, 
  1315   1318     Expr *pExpr,
         1319  +#ifdef SQLITE_ENABLE_COLUMN_METADATA
  1316   1320     const char **pzOrigDb,
  1317   1321     const char **pzOrigTab,
  1318   1322     const char **pzOrigCol,
         1323  +#endif
  1319   1324     u8 *pEstWidth
  1320   1325   ){
         1326  +  char const *zType = 0;
         1327  +  int j;
         1328  +  u8 estWidth = 1;
         1329  +#ifdef SQLITE_ENABLE_COLUMN_METADATA
  1321   1330     char const *zOrigDb = 0;
  1322   1331     char const *zOrigTab = 0;
  1323   1332     char const *zOrigCol = 0;
  1324         -#else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */
  1325         -# define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F)
  1326         -static const char *columnTypeImpl(
  1327         -  NameContext *pNC, 
  1328         -  Expr *pExpr,
  1329         -  u8 *pEstWidth
  1330         -){
  1331         -#endif /* !defined(SQLITE_ENABLE_COLUMN_METADATA) */
  1332         -  char const *zType = 0;
  1333         -  int j;
  1334         -  u8 estWidth = 1;
         1333  +#endif
  1335   1334   
  1336   1335     if( NEVER(pExpr==0) || pNC->pSrcList==0 ) return 0;
  1337   1336     switch( pExpr->op ){
  1338   1337       case TK_AGG_COLUMN:
  1339   1338       case TK_COLUMN: {
  1340   1339         /* The expression is a column. Locate the table the column is being
  1341   1340         ** extracted from in NameContext.pSrcList. This table may be real

Changes to src/where.c.

   612    612   }
   613    613   
   614    614   /* Forward reference */
   615    615   static void exprAnalyze(SrcList*, WhereClause*, int);
   616    616   
   617    617   /*
   618    618   ** Call exprAnalyze on all terms in a WHERE clause.  
          619  +**
          620  +** Note that exprAnalyze() might add new virtual terms onto the
          621  +** end of the WHERE clause.  We do not want to analyze these new
          622  +** virtual terms, so start analyzing at the end and work forward
          623  +** so that the added virtual terms are never processed.
   619    624   */
   620    625   static void exprAnalyzeAll(
   621    626     SrcList *pTabList,       /* the FROM clause */
   622    627     WhereClause *pWC         /* the WHERE clause to be analyzed */
   623    628   ){
   624    629     int i;
   625    630     for(i=pWC->nTerm-1; i>=0; i--){
................................................................................
   887    892   **
   888    893   ** then create a new virtual term like this:
   889    894   **
   890    895   **      x IN (expr1,expr2,expr3)
   891    896   **
   892    897   ** CASE 2:
   893    898   **
   894         -** If there are exactly two disjuncts one side has x>A and the other side
          899  +** If there are exactly two disjuncts and one side has x>A and the other side
   895    900   ** has x=A (for the same x and A) then add a new virtual conjunct term to the
   896    901   ** WHERE clause of the form "x>=A".  Example:
   897    902   **
   898    903   **      x>A OR (x=A AND y>B)    adds:    x>=A
   899    904   **
   900    905   ** The added conjunct can sometimes be helpful in query planning.
   901    906   **
................................................................................
   916    921   **
   917    922   ** From another point of view, "indexable" means that the subterm could
   918    923   ** potentially be used with an index if an appropriate index exists.
   919    924   ** This analysis does not consider whether or not the index exists; that
   920    925   ** is decided elsewhere.  This analysis only looks at whether subterms
   921    926   ** appropriate for indexing exist.
   922    927   **
   923         -** All examples A through E above satisfy case 2.  But if a term
          928  +** All examples A through E above satisfy case 3.  But if a term
   924    929   ** also satisfies case 1 (such as B) we know that the optimizer will
   925         -** always prefer case 1, so in that case we pretend that case 2 is not
          930  +** always prefer case 1, so in that case we pretend that case 3 is not
   926    931   ** satisfied.
   927    932   **
   928    933   ** It might be the case that multiple tables are indexable.  For example,
   929    934   ** (E) above is indexable on tables P, Q, and R.
   930    935   **
   931         -** Terms that satisfy case 2 are candidates for lookup by using
          936  +** Terms that satisfy case 3 are candidates for lookup by using
   932    937   ** separate indices to find rowids for each subterm and composing
   933    938   ** the union of all rowids using a RowSet object.  This is similar
   934    939   ** to "bitmap indices" in other database engines.
   935    940   **
   936    941   ** OTHERWISE:
   937    942   **
   938         -** If neither case 1 nor case 2 apply, then leave the eOperator set to
          943  +** If none of cases 1, 2, or 3 apply, then leave the eOperator set to
   939    944   ** zero.  This term is not useful for search.
   940    945   */
   941    946   static void exprAnalyzeOrTerm(
   942    947     SrcList *pSrc,            /* the FROM clause */
   943    948     WhereClause *pWC,         /* the complete WHERE clause */
   944    949     int idxTerm               /* Index of the OR-term to be analyzed */
   945    950   ){
................................................................................
   969    974     whereClauseInit(pOrWc, pWInfo);
   970    975     whereSplit(pOrWc, pExpr, TK_OR);
   971    976     exprAnalyzeAll(pSrc, pOrWc);
   972    977     if( db->mallocFailed ) return;
   973    978     assert( pOrWc->nTerm>=2 );
   974    979   
   975    980     /*
   976         -  ** Compute the set of tables that might satisfy cases 1 or 2.
          981  +  ** Compute the set of tables that might satisfy cases 1 or 3.
   977    982     */
   978    983     indexable = ~(Bitmask)0;
   979    984     chngToIN = ~(Bitmask)0;
   980    985     for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
   981    986       if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
   982    987         WhereAndInfo *pAndInfo;
   983    988         assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
................................................................................
  1184   1189   
  1185   1190   /*
  1186   1191   ** We already know that pExpr is a binary operator where both operands are
  1187   1192   ** column references.  This routine checks to see if pExpr is an equivalence
  1188   1193   ** relation:
  1189   1194   **   1.  The SQLITE_Transitive optimization must be enabled
  1190   1195   **   2.  Must be either an == or an IS operator
  1191         -**   3.  Not originating the ON clause of an OUTER JOIN
         1196  +**   3.  Not originating in the ON clause of an OUTER JOIN
  1192   1197   **   4.  The affinities of A and B must be compatible
  1193   1198   **   5a. Both operands use the same collating sequence OR
  1194   1199   **   5b. The overall collating sequence is BINARY
  1195   1200   ** If this routine returns TRUE, that means that the RHS can be substituted
  1196   1201   ** for the LHS anyplace else in the WHERE clause where the LHS column occurs.
  1197   1202   ** This is an optimization.  No harm comes from returning 0.  But if 1 is
  1198   1203   ** returned when it should not be, then incorrect answers might result.
................................................................................
  1585   1590     return -1;
  1586   1591   }
  1587   1592   
  1588   1593   /*
  1589   1594   ** Return true if the DISTINCT expression-list passed as the third argument
  1590   1595   ** is redundant.
  1591   1596   **
  1592         -** A DISTINCT list is redundant if the database contains some subset of
  1593         -** columns that are unique and non-null.
         1597  +** A DISTINCT list is redundant if any subset of the columns in the
         1598  +** DISTINCT list are collectively unique and individually non-null.
  1594   1599   */
  1595   1600   static int isDistinctRedundant(
  1596   1601     Parse *pParse,            /* Parsing context */
  1597   1602     SrcList *pTabList,        /* The FROM clause */
  1598   1603     WhereClause *pWC,         /* The WHERE clause */
  1599   1604     ExprList *pDistinct       /* The result set that needs to be DISTINCT */
  1600   1605   ){
................................................................................
  6685   6690         Bitmask m = getMask(pMaskSet, pTabList->a[ii].iCursor);
  6686   6691         assert( (m-1)==toTheLeft );
  6687   6692         toTheLeft |= m;
  6688   6693       }
  6689   6694     }
  6690   6695   #endif
  6691   6696   
  6692         -  /* Analyze all of the subexpressions.  Note that exprAnalyze() might
  6693         -  ** add new virtual terms onto the end of the WHERE clause.  We do not
  6694         -  ** want to analyze these virtual terms, so start analyzing at the end
  6695         -  ** and work forward so that the added virtual terms are never processed.
  6696         -  */
         6697  +  /* Analyze all of the subexpressions. */
  6697   6698     exprAnalyzeAll(pTabList, &pWInfo->sWC);
  6698         -  if( db->mallocFailed ){
  6699         -    goto whereBeginError;
  6700         -  }
         6699  +  if( db->mallocFailed ) goto whereBeginError;
  6701   6700   
  6702   6701     if( wctrlFlags & WHERE_WANT_DISTINCT ){
  6703   6702       if( isDistinctRedundant(pParse, pTabList, &pWInfo->sWC, pResultSet) ){
  6704   6703         /* The DISTINCT marking is pointless.  Ignore it. */
  6705   6704         pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
  6706   6705       }else if( pOrderBy==0 ){
  6707   6706         /* Try to ORDER BY the result set to make distinct processing easier */
................................................................................
  6709   6708         pWInfo->pOrderBy = pResultSet;
  6710   6709       }
  6711   6710     }
  6712   6711   
  6713   6712     /* Construct the WhereLoop objects */
  6714   6713     WHERETRACE(0xffff,("*** Optimizer Start ***\n"));
  6715   6714   #if defined(WHERETRACE_ENABLED)
  6716         -  /* Display all terms of the WHERE clause */
  6717         -  if( sqlite3WhereTrace & 0x100 ){
         6715  +  if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */
  6718   6716       int i;
  6719   6717       for(i=0; i<sWLB.pWC->nTerm; i++){
  6720   6718         whereTermPrint(&sWLB.pWC->a[i], i);
  6721   6719       }
  6722   6720     }
  6723   6721   #endif
  6724   6722   
  6725   6723     if( nTabList!=1 || whereShortCut(&sWLB)==0 ){
  6726   6724       rc = whereLoopAddAll(&sWLB);
  6727   6725       if( rc ) goto whereBeginError;
  6728   6726     
  6729         -    /* Display all of the WhereLoop objects if wheretrace is enabled */
  6730         -#ifdef WHERETRACE_ENABLED /* !=0 */
  6731         -    if( sqlite3WhereTrace ){
         6727  +#ifdef WHERETRACE_ENABLED
         6728  +    if( sqlite3WhereTrace ){    /* Display all of the WhereLoop objects */
  6732   6729         WhereLoop *p;
  6733   6730         int i;
  6734         -      static char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
  6735         -                                       "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
         6731  +      static const char zLabel[] = "0123456789abcdefghijklmnopqrstuvwyxz"
         6732  +                                             "ABCDEFGHIJKLMNOPQRSTUVWYXZ";
  6736   6733         for(p=pWInfo->pLoops, i=0; p; p=p->pNextLoop, i++){
  6737   6734           p->cId = zLabel[i%sizeof(zLabel)];
  6738   6735           whereLoopPrint(p, sWLB.pWC);
  6739   6736         }
  6740   6737       }
  6741   6738   #endif
  6742   6739     
................................................................................
  6749   6746     }
  6750   6747     if( pWInfo->pOrderBy==0 && (db->flags & SQLITE_ReverseOrder)!=0 ){
  6751   6748        pWInfo->revMask = (Bitmask)(-1);
  6752   6749     }
  6753   6750     if( pParse->nErr || NEVER(db->mallocFailed) ){
  6754   6751       goto whereBeginError;
  6755   6752     }
  6756         -#ifdef WHERETRACE_ENABLED /* !=0 */
         6753  +#ifdef WHERETRACE_ENABLED
  6757   6754     if( sqlite3WhereTrace ){
  6758   6755       sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut);
  6759   6756       if( pWInfo->nOBSat>0 ){
  6760   6757         sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask);
  6761   6758       }
  6762   6759       switch( pWInfo->eDistinct ){
  6763   6760         case WHERE_DISTINCT_UNIQUE: {
................................................................................
  6812   6809     }
  6813   6810     WHERETRACE(0xffff,("*** Optimizer Finished ***\n"));
  6814   6811     pWInfo->pParse->nQueryLoop += pWInfo->nRowOut;
  6815   6812   
  6816   6813     /* If the caller is an UPDATE or DELETE statement that is requesting
  6817   6814     ** to use a one-pass algorithm, determine if this is appropriate.
  6818   6815     ** The one-pass algorithm only works if the WHERE clause constrains
  6819         -  ** the statement to update a single row.
         6816  +  ** the statement to update or delete a single row.
  6820   6817     */
  6821   6818     assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  6822   6819     if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 
  6823   6820      && (pWInfo->a[0].pWLoop->wsFlags & WHERE_ONEROW)!=0 ){
  6824   6821       pWInfo->okOnePass = 1;
  6825   6822       if( HasRowid(pTabList->a[0].pTab) ){
  6826   6823         pWInfo->a[0].pWLoop->wsFlags &= ~WHERE_IDX_ONLY;
  6827   6824       }
  6828   6825     }
  6829   6826   
  6830   6827     /* Open all tables in the pTabList and any indices selected for
  6831   6828     ** searching those tables.
  6832   6829     */
  6833         -  notReady = ~(Bitmask)0;
  6834   6830     for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
  6835   6831       Table *pTab;     /* Table to open */
  6836   6832       int iDb;         /* Index of database containing table/index */
  6837   6833       struct SrcList_item *pTabItem;
  6838   6834   
  6839   6835       pTabItem = &pTabList->a[pLevel->iFrom];
  6840   6836       pTab = pTabItem->pTab;
................................................................................
  6915   6911           ){
  6916   6912             sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */
  6917   6913           }
  6918   6914           VdbeComment((v, "%s", pIx->zName));
  6919   6915         }
  6920   6916       }
  6921   6917       if( iDb>=0 ) sqlite3CodeVerifySchema(pParse, iDb);
  6922         -    notReady &= ~getMask(&pWInfo->sMaskSet, pTabItem->iCursor);
  6923   6918     }
  6924   6919     pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
  6925   6920     if( db->mallocFailed ) goto whereBeginError;
  6926   6921   
  6927   6922     /* Generate the code to do the search.  Each iteration of the for
  6928   6923     ** loop below generates code for a single nested loop of the VM
  6929   6924     ** program.