/ Check-in [69cf8772]
Login

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

Overview
Comment:Fix some minor issues with logarithmic cost in NGQP.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-logcost
Files: files | file ages | folders
SHA1: 69cf877283d362915edddf1822fbf7a9f86278b3
User & Date: drh 2013-06-10 20:46:50
Context
2013-06-10
23:30
Fix test cases for the new EXPLAIN QUERY PLAN format. Add the wherecosttest tool. Other fixes to logarithm cost. check-in: aa580e36 user: drh tags: nextgen-query-plan-logcost
20:46
Fix some minor issues with logarithmic cost in NGQP. check-in: 69cf8772 user: drh tags: nextgen-query-plan-logcost
19:12
First attempt to store costs and row counts as a logarithm. check-in: 9e810967 user: drh tags: nextgen-query-plan-logcost
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  1535   1535       if( NEVER(v==0) ) return;  /* VDBE should have already been allocated */
  1536   1536       if( sqlite3ExprIsInteger(p->pLimit, &n) ){
  1537   1537         sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit);
  1538   1538         VdbeComment((v, "LIMIT counter"));
  1539   1539         if( n==0 ){
  1540   1540           sqlite3VdbeAddOp2(v, OP_Goto, 0, iBreak);
  1541   1541         }else{
  1542         -        if( p->nSelectRow > (double)n ) p->nSelectRow = (double)n;
         1542  +        if( p->nSelectRow > n ) p->nSelectRow = n;
  1543   1543         }
  1544   1544       }else{
  1545   1545         sqlite3ExprCode(pParse, p->pLimit, iLimit);
  1546   1546         sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit);
  1547   1547         VdbeComment((v, "LIMIT counter"));
  1548   1548         sqlite3VdbeAddOp2(v, OP_IfZero, iLimit, iBreak);
  1549   1549       }
................................................................................
  1729   1729         rc = sqlite3Select(pParse, p, &dest);
  1730   1730         testcase( rc!=SQLITE_OK );
  1731   1731         pDelete = p->pPrior;
  1732   1732         p->pPrior = pPrior;
  1733   1733         p->nSelectRow += pPrior->nSelectRow;
  1734   1734         if( pPrior->pLimit
  1735   1735          && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit)
  1736         -       && p->nSelectRow > (double)nLimit 
         1736  +       && p->nSelectRow > nLimit 
  1737   1737         ){
  1738         -        p->nSelectRow = (double)nLimit;
         1738  +        p->nSelectRow = nLimit;
  1739   1739         }
  1740   1740         if( addr ){
  1741   1741           sqlite3VdbeJumpHere(v, addr);
  1742   1742         }
  1743   1743         break;
  1744   1744       }
  1745   1745       case TK_EXCEPT:
................................................................................
  4235   4235     if( pDest->eDest==SRT_EphemTab ){
  4236   4236       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr);
  4237   4237     }
  4238   4238   
  4239   4239     /* Set the limiter.
  4240   4240     */
  4241   4241     iEnd = sqlite3VdbeMakeLabel(v);
  4242         -  p->nSelectRow = (double)LARGEST_INT64;
         4242  +  p->nSelectRow = LARGEST_INT64;
  4243   4243     computeLimitRegisters(pParse, p, iEnd);
  4244   4244     if( p->iLimit==0 && addrSortIndex>=0 ){
  4245   4245       sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen;
  4246   4246       p->selFlags |= SF_UseSorter;
  4247   4247     }
  4248   4248   
  4249   4249     /* Open a virtual index to use for the distinct set.
................................................................................
  4316   4316   
  4317   4317         for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){
  4318   4318           pItem->iAlias = 0;
  4319   4319         }
  4320   4320         for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){
  4321   4321           pItem->iAlias = 0;
  4322   4322         }
  4323         -      if( p->nSelectRow>(double)100 ) p->nSelectRow = (double)100;
         4323  +      if( p->nSelectRow>100 ) p->nSelectRow = 100;
  4324   4324       }else{
  4325         -      p->nSelectRow = (double)1;
         4325  +      p->nSelectRow = 1;
  4326   4326       }
  4327   4327   
  4328   4328    
  4329   4329       /* Create a label to jump to when we want to abort the query */
  4330   4330       addrEnd = sqlite3VdbeMakeLabel(v);
  4331   4331   
  4332   4332       /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in

Changes to src/sqliteInt.h.

  2038   2038   */
  2039   2039   struct Select {
  2040   2040     ExprList *pEList;      /* The fields of the result */
  2041   2041     u8 op;                 /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */
  2042   2042     u16 selFlags;          /* Various SF_* values */
  2043   2043     int iLimit, iOffset;   /* Memory registers holding LIMIT & OFFSET counters */
  2044   2044     int addrOpenEphm[3];   /* OP_OpenEphem opcodes related to this select */
  2045         -  double nSelectRow;     /* Estimated number of result rows */
         2045  +  u64 nSelectRow;        /* Estimated number of result rows */
  2046   2046     SrcList *pSrc;         /* The FROM clause */
  2047   2047     Expr *pWhere;          /* The WHERE clause */
  2048   2048     ExprList *pGroupBy;    /* The GROUP BY clause */
  2049   2049     Expr *pHaving;         /* The HAVING clause */
  2050   2050     ExprList *pOrderBy;    /* The ORDER BY clause */
  2051   2051     Select *pPrior;        /* Prior select in a compound select statement */
  2052   2052     Select *pNext;         /* Next select to the left in a compound */
................................................................................
  2222   2222     TableLock *aTableLock; /* Required table locks for shared-cache mode */
  2223   2223   #endif
  2224   2224     AutoincInfo *pAinc;  /* Information about AUTOINCREMENT counters */
  2225   2225   
  2226   2226     /* Information used while coding trigger programs. */
  2227   2227     Parse *pToplevel;    /* Parse structure for main program (or NULL) */
  2228   2228     Table *pTriggerTab;  /* Table triggers are being coded for */
  2229         -  double nQueryLoop;   /* Estimated number of iterations of a query */
         2229  +  u32 nQueryLoop;      /* Estimated number of iterations of a query */
  2230   2230     u32 oldmask;         /* Mask of old.* columns referenced */
  2231   2231     u32 newmask;         /* Mask of new.* columns referenced */
  2232   2232     u8 eTriggerOp;       /* TK_UPDATE, TK_INSERT or TK_DELETE */
  2233   2233     u8 eOrconf;          /* Default ON CONFLICT policy for trigger steps */
  2234   2234     u8 disableTriggers;  /* True to disable triggers */
  2235   2235   
  2236   2236     /* Above is constant between recursions.  Below is reset before and after
................................................................................
  2792   2792   #if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY)
  2793   2793   Expr *sqlite3LimitWhere(Parse*,SrcList*,Expr*,ExprList*,Expr*,Expr*,char*);
  2794   2794   #endif
  2795   2795   void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
  2796   2796   void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
  2797   2797   WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
  2798   2798   void sqlite3WhereEnd(WhereInfo*);
  2799         -double sqlite3WhereOutputRowCount(WhereInfo*);
         2799  +u64 sqlite3WhereOutputRowCount(WhereInfo*);
  2800   2800   int sqlite3WhereIsDistinct(WhereInfo*);
  2801   2801   int sqlite3WhereIsOrdered(WhereInfo*);
  2802   2802   int sqlite3WhereContinueLabel(WhereInfo*);
  2803   2803   int sqlite3WhereBreakLabel(WhereInfo*);
  2804   2804   int sqlite3WhereOkOnePass(WhereInfo*);
  2805   2805   int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8);
  2806   2806   void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int);

Changes to src/where.c.

    41     41   typedef struct WhereAndInfo WhereAndInfo;
    42     42   typedef struct WhereLevel WhereLevel;
    43     43   typedef struct WhereLoop WhereLoop;
    44     44   typedef struct WherePath WherePath;
    45     45   typedef struct WhereTerm WhereTerm;
    46     46   typedef struct WhereLoopBuilder WhereLoopBuilder;
    47     47   typedef struct WhereScan WhereScan;
    48         -typedef unsigned short int WhereCost;  /* 10 times log2() of run-time */
           48  +
           49  +/*
           50  +** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
           51  +** maximum cost is 64*(2**63) which becomes 6900.  So all costs can be
           52  +** be stored in a 16-bit unsigned integer without risk of overflow.
           53  +*/
           54  +typedef unsigned short int WhereCost;
    49     55   
    50     56   /*
    51     57   ** For each nested loop in a WHERE clause implementation, the WhereInfo
    52     58   ** structure contains a single instance of this structure.  This structure
    53     59   ** is intended to be private to the where.c module and should not be
    54     60   ** access or modified by other modules.
    55     61   **
................................................................................
   397    403   #define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
   398    404   #define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
   399    405   #define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
   400    406   #define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
   401    407   #define WHERE_TEMP_INDEX   0x00004000  /* Uses an ephemeral index */
   402    408   #define WHERE_COVER_SCAN   0x00008000  /* Full scan of a covering index */
   403    409   
          410  +
          411  +/* Convert a WhereCost value (10 times log2(X)) into its integer value X.
          412  +*/
          413  +static u64 whereCostToInt(WhereCost x){
          414  +  u64 n;
          415  +  if( x<=10 ) return 1;
          416  +  n = x%10;
          417  +  x /= 10;
          418  +  if( n>=5 ) n -= 2;
          419  +  else if( n>=1 ) n -= 1;
          420  +  if( x>=3 ) return (n+8)<<(x-3);
          421  +  return (n+8)>>(3-x);
          422  +}
          423  +
   404    424   /*
   405    425   ** Return the estimated number of output rows from a WHERE clause
   406    426   */
   407         -double sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
   408         -  return (double)pWInfo->nRowOut;
          427  +u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
          428  +  return whereCostToInt(pWInfo->nRowOut);
   409    429   }
   410    430   
   411    431   /*
   412    432   ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
   413    433   ** WHERE clause returns outputs for DISTINCT processing.
   414    434   */
   415    435   int sqlite3WhereIsDistinct(WhereInfo *pWInfo){
................................................................................
  4712   4732     Bitmask mPrior = 0;
  4713   4733     int iTab;
  4714   4734     SrcList *pTabList = pWInfo->pTabList;
  4715   4735     struct SrcList_item *pItem;
  4716   4736     sqlite3 *db = pWInfo->pParse->db;
  4717   4737     int nTabList = pWInfo->nLevel;
  4718   4738     int rc = SQLITE_OK;
         4739  +  u8 priorJoinType = 0;
  4719   4740     WhereLoop *pNew;
  4720   4741   
  4721   4742     /* Loop over the tables in the join, from left to right */
  4722   4743     pNew = pBuilder->pNew;
  4723   4744     whereLoopInit(pNew);
  4724   4745     for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
  4725   4746       pNew->iTab = iTab;
  4726   4747       pNew->maskSelf = getMask(&pWInfo->sMaskSet, pItem->iCursor);
  4727         -    if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
         4748  +    if( ((pItem->jointype|priorJoinType) & (JT_LEFT|JT_CROSS))!=0 ){
  4728   4749         mExtra = mPrior;
  4729   4750       }
         4751  +    priorJoinType = pItem->jointype;
  4730   4752       if( IsVirtual(pItem->pTab) ){
  4731   4753         rc = whereLoopAddVirtual(pBuilder, mExtra);
  4732   4754       }else{
  4733   4755         rc = whereLoopAddBtree(pBuilder, mExtra);
  4734   4756       }
  4735   4757       if( rc==SQLITE_OK ){
  4736   4758         rc = whereLoopAddOr(pBuilder, mExtra);