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 |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-logcost |
Files: | files | file ages | folders |
SHA1: |
69cf877283d362915edddf1822fbf7a9 |
User & Date: | drh 2013-06-10 20:46:50.026 |
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: aa580e368e user: drh tags: nextgen-query-plan-logcost) | |
20:46 | Fix some minor issues with logarithmic cost in NGQP. (check-in: 69cf877283 user: drh tags: nextgen-query-plan-logcost) | |
19:12 | First attempt to store costs and row counts as a logarithm. (check-in: 9e8109673c user: drh tags: nextgen-query-plan-logcost) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
1535 1536 1537 1538 1539 1540 1541 | if( NEVER(v==0) ) return; /* VDBE should have already been allocated */ if( sqlite3ExprIsInteger(p->pLimit, &n) ){ sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit); VdbeComment((v, "LIMIT counter")); if( n==0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, iBreak); }else{ | | | 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 | if( NEVER(v==0) ) return; /* VDBE should have already been allocated */ if( sqlite3ExprIsInteger(p->pLimit, &n) ){ sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit); VdbeComment((v, "LIMIT counter")); if( n==0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, iBreak); }else{ if( p->nSelectRow > n ) p->nSelectRow = n; } }else{ sqlite3ExprCode(pParse, p->pLimit, iLimit); sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit); VdbeComment((v, "LIMIT counter")); sqlite3VdbeAddOp2(v, OP_IfZero, iLimit, iBreak); } |
︙ | ︙ | |||
1729 1730 1731 1732 1733 1734 1735 | rc = sqlite3Select(pParse, p, &dest); testcase( rc!=SQLITE_OK ); pDelete = p->pPrior; p->pPrior = pPrior; p->nSelectRow += pPrior->nSelectRow; if( pPrior->pLimit && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit) | | | | 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 | rc = sqlite3Select(pParse, p, &dest); testcase( rc!=SQLITE_OK ); pDelete = p->pPrior; p->pPrior = pPrior; p->nSelectRow += pPrior->nSelectRow; if( pPrior->pLimit && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit) && p->nSelectRow > nLimit ){ p->nSelectRow = nLimit; } if( addr ){ sqlite3VdbeJumpHere(v, addr); } break; } case TK_EXCEPT: |
︙ | ︙ | |||
4235 4236 4237 4238 4239 4240 4241 | if( pDest->eDest==SRT_EphemTab ){ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr); } /* Set the limiter. */ iEnd = sqlite3VdbeMakeLabel(v); | | | 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 | if( pDest->eDest==SRT_EphemTab ){ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iSDParm, pEList->nExpr); } /* Set the limiter. */ iEnd = sqlite3VdbeMakeLabel(v); p->nSelectRow = LARGEST_INT64; computeLimitRegisters(pParse, p, iEnd); if( p->iLimit==0 && addrSortIndex>=0 ){ sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen; p->selFlags |= SF_UseSorter; } /* Open a virtual index to use for the distinct set. |
︙ | ︙ | |||
4316 4317 4318 4319 4320 4321 4322 | for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){ pItem->iAlias = 0; } for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){ pItem->iAlias = 0; } | | | | 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 | for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){ pItem->iAlias = 0; } for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){ pItem->iAlias = 0; } if( p->nSelectRow>100 ) p->nSelectRow = 100; }else{ p->nSelectRow = 1; } /* Create a label to jump to when we want to abort the query */ addrEnd = sqlite3VdbeMakeLabel(v); /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2038 2039 2040 2041 2042 2043 2044 | */ struct Select { ExprList *pEList; /* The fields of the result */ u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */ u16 selFlags; /* Various SF_* values */ int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */ int addrOpenEphm[3]; /* OP_OpenEphem opcodes related to this select */ | | | 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 | */ struct Select { ExprList *pEList; /* The fields of the result */ u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */ u16 selFlags; /* Various SF_* values */ int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */ int addrOpenEphm[3]; /* OP_OpenEphem opcodes related to this select */ u64 nSelectRow; /* Estimated number of result rows */ SrcList *pSrc; /* The FROM clause */ Expr *pWhere; /* The WHERE clause */ ExprList *pGroupBy; /* The GROUP BY clause */ Expr *pHaving; /* The HAVING clause */ ExprList *pOrderBy; /* The ORDER BY clause */ Select *pPrior; /* Prior select in a compound select statement */ Select *pNext; /* Next select to the left in a compound */ |
︙ | ︙ | |||
2222 2223 2224 2225 2226 2227 2228 | TableLock *aTableLock; /* Required table locks for shared-cache mode */ #endif AutoincInfo *pAinc; /* Information about AUTOINCREMENT counters */ /* Information used while coding trigger programs. */ Parse *pToplevel; /* Parse structure for main program (or NULL) */ Table *pTriggerTab; /* Table triggers are being coded for */ | | | 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 | TableLock *aTableLock; /* Required table locks for shared-cache mode */ #endif AutoincInfo *pAinc; /* Information about AUTOINCREMENT counters */ /* Information used while coding trigger programs. */ Parse *pToplevel; /* Parse structure for main program (or NULL) */ Table *pTriggerTab; /* Table triggers are being coded for */ u32 nQueryLoop; /* Estimated number of iterations of a query */ u32 oldmask; /* Mask of old.* columns referenced */ u32 newmask; /* Mask of new.* columns referenced */ u8 eTriggerOp; /* TK_UPDATE, TK_INSERT or TK_DELETE */ u8 eOrconf; /* Default ON CONFLICT policy for trigger steps */ u8 disableTriggers; /* True to disable triggers */ /* Above is constant between recursions. Below is reset before and after |
︙ | ︙ | |||
2792 2793 2794 2795 2796 2797 2798 | #if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY) Expr *sqlite3LimitWhere(Parse*,SrcList*,Expr*,ExprList*,Expr*,Expr*,char*); #endif void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); | | | 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 | #if defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) && !defined(SQLITE_OMIT_SUBQUERY) Expr *sqlite3LimitWhere(Parse*,SrcList*,Expr*,ExprList*,Expr*,Expr*,char*); #endif void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); u64 sqlite3WhereOutputRowCount(WhereInfo*); int sqlite3WhereIsDistinct(WhereInfo*); int sqlite3WhereIsOrdered(WhereInfo*); int sqlite3WhereContinueLabel(WhereInfo*); int sqlite3WhereBreakLabel(WhereInfo*); int sqlite3WhereOkOnePass(WhereInfo*); int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8); void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int); |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
41 42 43 44 45 46 47 | typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereLevel WhereLevel; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; | > > > > > > | | 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereLevel WhereLevel; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; /* ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer. The ** maximum cost is 64*(2**63) which becomes 6900. So all costs can be ** be stored in a 16-bit unsigned integer without risk of overflow. */ typedef unsigned short int WhereCost; /* ** For each nested loop in a WHERE clause implementation, the WhereInfo ** structure contains a single instance of this structure. This structure ** is intended to be private to the where.c module and should not be ** access or modified by other modules. ** |
︙ | ︙ | |||
397 398 399 400 401 402 403 404 405 406 | #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_COVER_SCAN 0x00008000 /* Full scan of a covering index */ /* ** Return the estimated number of output rows from a WHERE clause */ | > > > > > > > > > > > > > > | | | 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 | #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_COVER_SCAN 0x00008000 /* Full scan of a covering index */ /* Convert a WhereCost value (10 times log2(X)) into its integer value X. */ static u64 whereCostToInt(WhereCost x){ u64 n; if( x<=10 ) return 1; n = x%10; x /= 10; if( n>=5 ) n -= 2; else if( n>=1 ) n -= 1; if( x>=3 ) return (n+8)<<(x-3); return (n+8)>>(3-x); } /* ** Return the estimated number of output rows from a WHERE clause */ u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){ return whereCostToInt(pWInfo->nRowOut); } /* ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this ** WHERE clause returns outputs for DISTINCT processing. */ int sqlite3WhereIsDistinct(WhereInfo *pWInfo){ |
︙ | ︙ | |||
4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 | Bitmask mPrior = 0; int iTab; SrcList *pTabList = pWInfo->pTabList; struct SrcList_item *pItem; sqlite3 *db = pWInfo->pParse->db; int nTabList = pWInfo->nLevel; int rc = SQLITE_OK; WhereLoop *pNew; /* Loop over the tables in the join, from left to right */ pNew = pBuilder->pNew; whereLoopInit(pNew); for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){ pNew->iTab = iTab; pNew->maskSelf = getMask(&pWInfo->sMaskSet, pItem->iCursor); | > | > | 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758 | Bitmask mPrior = 0; int iTab; SrcList *pTabList = pWInfo->pTabList; struct SrcList_item *pItem; sqlite3 *db = pWInfo->pParse->db; int nTabList = pWInfo->nLevel; int rc = SQLITE_OK; u8 priorJoinType = 0; WhereLoop *pNew; /* Loop over the tables in the join, from left to right */ pNew = pBuilder->pNew; whereLoopInit(pNew); for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){ pNew->iTab = iTab; pNew->maskSelf = getMask(&pWInfo->sMaskSet, pItem->iCursor); if( ((pItem->jointype|priorJoinType) & (JT_LEFT|JT_CROSS))!=0 ){ mExtra = mPrior; } priorJoinType = pItem->jointype; if( IsVirtual(pItem->pTab) ){ rc = whereLoopAddVirtual(pBuilder, mExtra); }else{ rc = whereLoopAddBtree(pBuilder, mExtra); } if( rc==SQLITE_OK ){ rc = whereLoopAddOr(pBuilder, mExtra); |
︙ | ︙ |