/ Check-in [22989f35]
Login

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

Overview
Comment:Change the internal sqlite3WhereBegin() to report that the ORDER BY clause is satisfied by indices using the WhereInfo.nOBSat field of the returned structure.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 22989f3588531efd555cc29d6c576e7a34b7edc4
User & Date: drh 2012-09-24 15:30:54
Context
2012-09-24
19:50
Remove an unused subfunction parameter and an obsolete comment from the query planner logic in where.c. check-in: 349a55cd user: drh tags: trunk
15:30
Change the internal sqlite3WhereBegin() to report that the ORDER BY clause is satisfied by indices using the WhereInfo.nOBSat field of the returned structure. check-in: 22989f35 user: drh tags: trunk
11:43
Update documentation to describe the threadsafety of sqlite3_enable_shared_cache(). check-in: e081890c user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  4094   4094     }
  4095   4095   
  4096   4096     if( !isAgg && pGroupBy==0 ){
  4097   4097       /* No aggregate functions and no GROUP BY clause */
  4098   4098       ExprList *pDist = (sDistinct.isTnct ? p->pEList : 0);
  4099   4099   
  4100   4100       /* Begin the database scan. */
  4101         -    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pOrderBy, pDist, 0,0);
         4101  +    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, pDist, 0,0);
  4102   4102       if( pWInfo==0 ) goto select_end;
  4103   4103       if( pWInfo->nRowOut < p->nSelectRow ) p->nSelectRow = pWInfo->nRowOut;
  4104   4104       if( pWInfo->eDistinct ) sDistinct.eTnctType = pWInfo->eDistinct;
         4105  +    if( pOrderBy && pWInfo->nOBSat==pOrderBy->nExpr ) pOrderBy = 0;
  4105   4106   
  4106   4107       /* If sorting index that was created by a prior OP_OpenEphemeral 
  4107   4108       ** instruction ended up not being needed, then change the OP_OpenEphemeral
  4108   4109       ** into an OP_Noop.
  4109   4110       */
  4110   4111       if( addrSortIndex>=0 && pOrderBy==0 ){
  4111   4112         sqlite3VdbeChangeToNoop(v, addrSortIndex);
................................................................................
  4225   4226   
  4226   4227         /* Begin a loop that will extract all source rows in GROUP BY order.
  4227   4228         ** This might involve two separate loops with an OP_Sort in between, or
  4228   4229         ** it might be a single loop that uses an index to extract information
  4229   4230         ** in the right order to begin with.
  4230   4231         */
  4231   4232         sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
  4232         -      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pGroupBy, 0, 0, 0);
         4233  +      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, 0, 0);
  4233   4234         if( pWInfo==0 ) goto select_end;
  4234         -      if( pGroupBy==0 ){
         4235  +      if( pWInfo->nOBSat==pGroupBy->nExpr ){
  4235   4236           /* The optimizer is able to deliver rows in group by order so
  4236   4237           ** we do not have to sort.  The OP_OpenEphemeral table will be
  4237   4238           ** cancelled later because we still need to use the pKeyInfo
  4238   4239           */
  4239         -        pGroupBy = p->pGroupBy;
  4240   4240           groupBySort = 0;
  4241   4241         }else{
  4242   4242           /* Rows are coming out in undetermined order.  We have to push
  4243   4243           ** each row into a sorting index, terminate the first loop,
  4244   4244           ** then loop over the sorting index in order to get the output
  4245   4245           ** in sorted order
  4246   4246           */
................................................................................
  4482   4482           **     satisfying the 'ORDER BY' clause than it does in other cases.
  4483   4483           **     Refer to code and comments in where.c for details.
  4484   4484           */
  4485   4485           ExprList *pMinMax = 0;
  4486   4486           u8 flag = minMaxQuery(p);
  4487   4487           if( flag ){
  4488   4488             assert( !ExprHasProperty(p->pEList->a[0].pExpr, EP_xIsSelect) );
         4489  +          assert( p->pEList->a[0].pExpr->x.pList->nExpr==1 );
  4489   4490             pMinMax = sqlite3ExprListDup(db, p->pEList->a[0].pExpr->x.pList,0);
  4490   4491             pDel = pMinMax;
  4491   4492             if( pMinMax && !db->mallocFailed ){
  4492   4493               pMinMax->a[0].sortOrder = flag!=WHERE_ORDERBY_MIN ?1:0;
  4493   4494               pMinMax->a[0].pExpr->op = TK_COLUMN;
  4494   4495             }
  4495   4496           }
  4496   4497     
  4497   4498           /* This case runs if the aggregate has no GROUP BY clause.  The
  4498   4499           ** processing is much simpler since there is only a single row
  4499   4500           ** of output.
  4500   4501           */
  4501   4502           resetAccumulator(pParse, &sAggInfo);
  4502         -        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pMinMax,0,flag,0);
         4503  +        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0);
  4503   4504           if( pWInfo==0 ){
  4504   4505             sqlite3ExprListDelete(db, pDel);
  4505   4506             goto select_end;
  4506   4507           }
  4507   4508           updateAccumulator(pParse, &sAggInfo);
  4508         -        if( !pMinMax && flag ){
         4509  +        if( pWInfo->nOBSat>0 ){
  4509   4510             sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak);
  4510   4511             VdbeComment((v, "%s() by index",
  4511   4512                   (flag==WHERE_ORDERBY_MIN?"min":"max")));
  4512   4513           }
  4513   4514           sqlite3WhereEnd(pWInfo);
  4514   4515           finalizeAggFunctions(pParse, &sAggInfo);
  4515   4516         }

Changes to src/sqliteInt.h.

  1978   1978   ** The WHERE clause processing routine has two halves.  The
  1979   1979   ** first part does the start of the WHERE loop and the second
  1980   1980   ** half does the tail of the WHERE loop.  An instance of
  1981   1981   ** this structure is returned by the first half and passed
  1982   1982   ** into the second half to give some continuity.
  1983   1983   */
  1984   1984   struct WhereInfo {
  1985         -  Parse *pParse;       /* Parsing and code generating context */
  1986         -  u16 wctrlFlags;      /* Flags originally passed to sqlite3WhereBegin() */
  1987         -  u8 okOnePass;        /* Ok to use one-pass algorithm for UPDATE or DELETE */
  1988         -  u8 untestedTerms;    /* Not all WHERE terms resolved by outer loop */
  1989         -  u8 eDistinct;                  /* One of the WHERE_DISTINCT_* values below */
  1990         -  SrcList *pTabList;             /* List of tables in the join */
  1991         -  int iTop;                      /* The very beginning of the WHERE loop */
  1992         -  int iContinue;                 /* Jump here to continue with next record */
  1993         -  int iBreak;                    /* Jump here to break out of the loop */
  1994         -  int nLevel;                    /* Number of nested loop */
  1995         -  struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  1996         -  double savedNQueryLoop;        /* pParse->nQueryLoop outside the WHERE loop */
  1997         -  double nRowOut;                /* Estimated number of output rows */
  1998         -  WhereLevel a[1];               /* Information about each nest loop in WHERE */
         1985  +  Parse *pParse;            /* Parsing and code generating context */
         1986  +  SrcList *pTabList;        /* List of tables in the join */
         1987  +  u16 nOBSat;               /* Number of ORDER BY terms satisfied by indices */
         1988  +  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
         1989  +  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
         1990  +  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
         1991  +  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
         1992  +  int iTop;                 /* The very beginning of the WHERE loop */
         1993  +  int iContinue;            /* Jump here to continue with next record */
         1994  +  int iBreak;               /* Jump here to break out of the loop */
         1995  +  int nLevel;               /* Number of nested loop */
         1996  +  struct WhereClause *pWC;  /* Decomposition of the WHERE clause */
         1997  +  double savedNQueryLoop;   /* pParse->nQueryLoop outside the WHERE loop */
         1998  +  double nRowOut;           /* Estimated number of output rows */
         1999  +  WhereLevel a[1];          /* Information about each nest loop in WHERE */
  1999   2000   };
  2000   2001   
  2001   2002   /* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */
  2002   2003   #define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
  2003   2004   #define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
  2004   2005   #define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
  2005   2006   #define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */
................................................................................
  2807   2808   int sqlite3IsReadOnly(Parse*, Table*, int);
  2808   2809   void sqlite3OpenTable(Parse*, int iCur, int iDb, Table*, int);
  2809   2810   #if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY)
  2810   2811   Expr *sqlite3LimitWhere(Parse *, SrcList *, Expr *, ExprList *, Expr *, Expr *, char *);
  2811   2812   #endif
  2812   2813   void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
  2813   2814   void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
  2814         -WhereInfo *sqlite3WhereBegin(
  2815         -    Parse*,SrcList*,Expr*,ExprList**,ExprList*,u16,int);
         2815  +WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
  2816   2816   void sqlite3WhereEnd(WhereInfo*);
  2817   2817   int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8);
  2818   2818   void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int);
  2819   2819   void sqlite3ExprCodeMove(Parse*, int, int, int);
  2820   2820   void sqlite3ExprCacheStore(Parse*, int, int, int);
  2821   2821   void sqlite3ExprCachePush(Parse*);
  2822   2822   void sqlite3ExprCachePop(Parse*, int);

Changes to src/where.c.

  4663   4663   **        move the row2 cursor to a null row
  4664   4664   **        goto start
  4665   4665   **      fi
  4666   4666   **    end
  4667   4667   **
  4668   4668   ** ORDER BY CLAUSE PROCESSING
  4669   4669   **
  4670         -** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
         4670  +** pOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
  4671   4671   ** if there is one.  If there is no ORDER BY clause or if this routine
  4672         -** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
         4672  +** is called from an UPDATE or DELETE statement, then pOrderBy is NULL.
  4673   4673   **
  4674   4674   ** If an index can be used so that the natural output order of the table
  4675   4675   ** scan is correct for the ORDER BY clause, then that index is used and
  4676         -** *ppOrderBy is set to NULL.  This is an optimization that prevents an
  4677         -** unnecessary sort of the result set if an index appropriate for the
  4678         -** ORDER BY clause already exists.
         4676  +** the returned WhereInfo.nOBSat field is set to pOrderBy->nExpr.  This
         4677  +** is an optimization that prevents an unnecessary sort of the result set
         4678  +** if an index appropriate for the ORDER BY clause already exists.
  4679   4679   **
  4680   4680   ** If the where clause loops cannot be arranged to provide the correct
  4681         -** output order, then the *ppOrderBy is unchanged.
         4681  +** output order, then WhereInfo.nOBSat is 0.
  4682   4682   */
  4683   4683   WhereInfo *sqlite3WhereBegin(
  4684   4684     Parse *pParse,        /* The parser context */
  4685   4685     SrcList *pTabList,    /* A list of all tables to be scanned */
  4686   4686     Expr *pWhere,         /* The WHERE clause */
  4687         -  ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
         4687  +  ExprList *pOrderBy,   /* An ORDER BY clause, or NULL */
  4688   4688     ExprList *pDistinct,  /* The select-list for DISTINCT queries - or NULL */
  4689   4689     u16 wctrlFlags,       /* One of the WHERE_* flags defined in sqliteInt.h */
  4690   4690     int iIdxCur           /* If WHERE_ONETABLE_ONLY is set, index cursor number */
  4691   4691   ){
  4692   4692     int i;                     /* Loop counter */
  4693   4693     int nByteWInfo;            /* Num. bytes allocated for WhereInfo struct */
  4694   4694     int nTabList;              /* Number of elements in pTabList */
................................................................................
  4905   4905       nUnconstrained = 0;
  4906   4906       notIndexed = 0;
  4907   4907       for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){
  4908   4908         Bitmask mask;             /* Mask of tables not yet ready */
  4909   4909         for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
  4910   4910           int doNotReorder;    /* True if this table should not be reordered */
  4911   4911           WhereCost sCost;     /* Cost information from best[Virtual]Index() */
  4912         -        ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */
         4912  +        ExprList *pOB;       /* ORDER BY clause for index to optimize */
  4913   4913           ExprList *pDist;     /* DISTINCT clause for index to optimize */
  4914   4914     
  4915   4915           doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
  4916   4916           if( j!=iFrom && doNotReorder ) break;
  4917   4917           m = getMask(pMaskSet, pTabItem->iCursor);
  4918   4918           if( (m & notReady)==0 ){
  4919   4919             if( j==iFrom ) iFrom++;
  4920   4920             continue;
  4921   4921           }
  4922   4922           mask = (isOptimal ? m : notReady);
  4923         -        pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
         4923  +        pOB = (i==0) ? pOrderBy : 0;
  4924   4924           pDist = (i==0 ? pDistinct : 0);
  4925   4925           if( pTabItem->pIndex==0 ) nUnconstrained++;
  4926   4926     
  4927   4927           WHERETRACE(("=== trying table %d with isOptimal=%d ===\n",
  4928   4928                       j, isOptimal));
  4929   4929           assert( pTabItem->pTab );
  4930   4930   #ifndef SQLITE_OMIT_VIRTUALTABLE
  4931   4931           if( IsVirtual(pTabItem->pTab) ){
  4932   4932             sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
  4933         -          bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
         4933  +          bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOB,
  4934   4934                              &sCost, pp);
  4935   4935           }else 
  4936   4936   #endif
  4937   4937           {
  4938         -          bestBtreeIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
         4938  +          bestBtreeIndex(pParse, pWC, pTabItem, mask, notReady, pOB,
  4939   4939                 pDist, &sCost);
  4940   4940           }
  4941   4941           assert( isOptimal || (sCost.used&notReady)==0 );
  4942   4942   
  4943   4943           /* If an INDEXED BY clause is present, then the plan must use that
  4944   4944           ** index if it uses any index at all */
  4945   4945           assert( pTabItem->pIndex==0 
................................................................................
  4991   4991       }
  4992   4992       assert( bestJ>=0 );
  4993   4993       assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
  4994   4994       WHERETRACE(("*** Optimizer selects table %d for loop %d"
  4995   4995                   " with cost=%g and nRow=%g\n",
  4996   4996                   bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow));
  4997   4997       /* The ALWAYS() that follows was added to hush up clang scan-build */
  4998         -    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 && ALWAYS(ppOrderBy) ){
  4999         -      *ppOrderBy = 0;
         4998  +    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
         4999  +      pWInfo->nOBSat = pOrderBy->nExpr;
  5000   5000       }
  5001   5001       if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
  5002   5002         assert( pWInfo->eDistinct==0 );
  5003   5003         pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5004   5004       }
  5005   5005       andFlags &= bestPlan.plan.wsFlags;
  5006   5006       pLevel->plan = bestPlan.plan;
................................................................................
  5045   5045     if( pParse->nErr || db->mallocFailed ){
  5046   5046       goto whereBeginError;
  5047   5047     }
  5048   5048   
  5049   5049     /* If the total query only selects a single row, then the ORDER BY
  5050   5050     ** clause is irrelevant.
  5051   5051     */
  5052         -  if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
  5053         -    *ppOrderBy = 0;
         5052  +  if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){
         5053  +    pWInfo->nOBSat = pOrderBy->nExpr;
  5054   5054     }
  5055   5055   
  5056   5056     /* If the caller is an UPDATE or DELETE statement that is requesting
  5057   5057     ** to use a one-pass algorithm, determine if this is appropriate.
  5058   5058     ** The one-pass algorithm only works if the WHERE clause constraints
  5059   5059     ** the statement to update a single row.
  5060   5060     */