/ Check-in [cb34cfe5]
Login

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

Overview
Comment:Multiply all cursor step cost estimates by the estimated size of the row in bytes, in order to get the query planner ot make use of estimated row sizes. This check-in uses magic numbers in a few places (for example, estimates of the size of output rows) and needs lots of refinement. Consider this a proof-of-concept only.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | row-size-est
Files: files | file ages | folders
SHA1: cb34cfe57c2a664fbfae8106e95114400ea222d5
User & Date: drh 2013-10-07 17:32:15
Context
2013-10-08
18:40
Further refinement of the idea of multiplying run-time cost estimates by the estimated row size. check-in: 18bd6ba9 user: drh tags: row-size-est
2013-10-07
17:32
Multiply all cursor step cost estimates by the estimated size of the row in bytes, in order to get the query planner ot make use of estimated row sizes. This check-in uses magic numbers in a few places (for example, estimates of the size of output rows) and needs lots of refinement. Consider this a proof-of-concept only. check-in: cb34cfe5 user: drh tags: row-size-est
10:48
Merge bug fixes from trunk. check-in: 1d7b2dc0 user: drh tags: row-size-est
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  4364   4364   #endif
  4365   4365       if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){
  4366   4366         /* Each row involves a step of the index, then a binary search of
  4367   4367         ** the main table */
  4368   4368         pNew->rRun =  sqlite3LogEstAdd(pNew->rRun,rLogSize>27 ? rLogSize-17 : 10);
  4369   4369       }
  4370   4370       /* Step cost for each output row */
  4371         -    pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut);
         4371  +    pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut) + pProbe->szIdxRow;
  4372   4372       whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor);
  4373   4373       rc = whereLoopInsert(pBuilder, pNew);
  4374   4374       if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
  4375   4375        && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
  4376   4376       ){
  4377   4377         whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
  4378   4378       }
................................................................................
  4467   4467     WhereLoop *pNew;            /* Template WhereLoop object */
  4468   4468     int rc = SQLITE_OK;         /* Return code */
  4469   4469     int iSortIdx = 1;           /* Index number */
  4470   4470     int b;                      /* A boolean value */
  4471   4471     LogEst rSize;               /* number of rows in the table */
  4472   4472     LogEst rLogSize;            /* Logarithm of the number of rows in the table */
  4473   4473     WhereClause *pWC;           /* The parsed WHERE clause */
         4474  +  Table *pTab;                /* Table being queried */
  4474   4475     
  4475   4476     pNew = pBuilder->pNew;
  4476   4477     pWInfo = pBuilder->pWInfo;
  4477   4478     pTabList = pWInfo->pTabList;
  4478   4479     pSrc = pTabList->a + pNew->iTab;
         4480  +  pTab = pSrc->pTab;
  4479   4481     pWC = pBuilder->pWC;
  4480   4482     assert( !IsVirtual(pSrc->pTab) );
  4481   4483   
  4482   4484     if( pSrc->pIndex ){
  4483   4485       /* An INDEXED BY clause specifies a particular index to use */
  4484   4486       pProbe = pSrc->pIndex;
  4485   4487     }else{
................................................................................
  4489   4491       ** indices to follow */
  4490   4492       Index *pFirst;                  /* First of real indices on the table */
  4491   4493       memset(&sPk, 0, sizeof(Index));
  4492   4494       sPk.nColumn = 1;
  4493   4495       sPk.aiColumn = &aiColumnPk;
  4494   4496       sPk.aiRowEst = aiRowEstPk;
  4495   4497       sPk.onError = OE_Replace;
  4496         -    sPk.pTable = pSrc->pTab;
  4497         -    aiRowEstPk[0] = pSrc->pTab->nRowEst;
         4498  +    sPk.pTable = pTab;
         4499  +    aiRowEstPk[0] = pTab->nRowEst;
  4498   4500       aiRowEstPk[1] = 1;
  4499   4501       pFirst = pSrc->pTab->pIndex;
  4500   4502       if( pSrc->notIndexed==0 ){
  4501   4503         /* The real indices of the table are only considered if the
  4502   4504         ** NOT INDEXED qualifier is omitted from the FROM clause */
  4503   4505         sPk.pNext = pFirst;
  4504   4506       }
  4505   4507       pProbe = &sPk;
  4506   4508     }
  4507         -  rSize = sqlite3LogEst(pSrc->pTab->nRowEst);
         4509  +  rSize = sqlite3LogEst(pTab->nRowEst);
  4508   4510     rLogSize = estLog(rSize);
  4509   4511   
  4510   4512   #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  4511   4513     /* Automatic indexes */
  4512   4514     if( !pBuilder->pOrSet
  4513   4515      && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
  4514   4516      && pSrc->pIndex==0
................................................................................
  4526   4528           pNew->u.btree.pIndex = 0;
  4527   4529           pNew->nLTerm = 1;
  4528   4530           pNew->aLTerm[0] = pTerm;
  4529   4531           /* TUNING: One-time cost for computing the automatic index is
  4530   4532           ** approximately 7*N*log2(N) where N is the number of rows in
  4531   4533           ** the table being indexed. */
  4532   4534           pNew->rSetup = rLogSize + rSize + 28;  assert( 28==sqlite3LogEst(7) );
         4535  +        pNew->rSetup += pTab->szTabRow;
  4533   4536           /* TUNING: Each index lookup yields 20 rows in the table.  This
  4534   4537           ** is more than the usual guess of 10 rows, since we have no way
  4535   4538           ** of knowning how selective the index will ultimately be.  It would
  4536   4539           ** not be unreasonable to make this value much larger. */
  4537   4540           pNew->nOut = 43;  assert( 43==sqlite3LogEst(20) );
  4538         -        pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
         4541  +        pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut) + pTab->szTabRow;
  4539   4542           pNew->wsFlags = WHERE_AUTO_INDEX;
  4540   4543           pNew->prereq = mExtra | pTerm->prereqRight;
  4541   4544           rc = whereLoopInsert(pBuilder, pNew);
  4542   4545         }
  4543   4546       }
  4544   4547     }
  4545   4548   #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
................................................................................
  4566   4569         pNew->wsFlags = WHERE_IPK;
  4567   4570   
  4568   4571         /* Full table scan */
  4569   4572         pNew->iSortIdx = b ? iSortIdx : 0;
  4570   4573         /* TUNING: Cost of full table scan is 3*(N + log2(N)).
  4571   4574         **  +  The extra 3 factor is to encourage the use of indexed lookups
  4572   4575         **     over full scans.  FIXME */
  4573         -      pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16;
         4576  +      pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16 + pTab->szTabRow;
  4574   4577         whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
  4575   4578         rc = whereLoopInsert(pBuilder, pNew);
  4576   4579         pNew->nOut = rSize;
  4577   4580         if( rc ) break;
  4578   4581       }else{
  4579   4582         Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
  4580   4583         pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
................................................................................
  4598   4601             pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 10;
  4599   4602           }else{
  4600   4603             assert( b!=0 ); 
  4601   4604             /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
  4602   4605             ** which we will simplify to just N*log2(N) */
  4603   4606             pNew->rRun = rSize + rLogSize;
  4604   4607           }
         4608  +        pNew->rRun += pProbe->szIdxRow;
  4605   4609           whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
  4606   4610           rc = whereLoopInsert(pBuilder, pNew);
  4607   4611           pNew->nOut = rSize;
  4608   4612           if( rc ) break;
  4609   4613         }
  4610   4614       }
  4611   4615   
................................................................................
  4769   4773         pNew->u.vtab.idxNum = pIdxInfo->idxNum;
  4770   4774         pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  4771   4775         pIdxInfo->needToFreeIdxStr = 0;
  4772   4776         pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  4773   4777         pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
  4774   4778                                        && pIdxInfo->orderByConsumed);
  4775   4779         pNew->rSetup = 0;
  4776         -      pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost);
         4780  +      pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost) + 55;
  4777   4781         /* TUNING: Every virtual table query returns 25 rows */
  4778   4782         pNew->nOut = 46;  assert( 46==sqlite3LogEst(25) );
  4779   4783         whereLoopInsert(pBuilder, pNew);
  4780   4784         if( pNew->u.vtab.needFree ){
  4781   4785           sqlite3_free(pNew->u.vtab.idxStr);
  4782   4786           pNew->u.vtab.needFree = 0;
  4783   4787         }
................................................................................
  5260   5264     ** to sqlite3WhereBegin() was concerned about sorting */
  5261   5265     rSortCost = 0;
  5262   5266     if( pWInfo->pOrderBy==0 || nRowEst==0 ){
  5263   5267       aFrom[0].isOrderedValid = 1;
  5264   5268     }else{
  5265   5269       /* TUNING: Estimated cost of sorting is N*log2(N) where N is the
  5266   5270       ** number of output rows. */
  5267         -    rSortCost = nRowEst + estLog(nRowEst);
         5271  +    rSortCost = nRowEst + estLog(nRowEst) + 55;
  5268   5272       WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
  5269   5273     }
  5270   5274   
  5271   5275     /* Compute successively longer WherePaths using the previous generation
  5272   5276     ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  5273   5277     ** best paths at each generation */
  5274   5278     for(iLoop=0; iLoop<nLoop; iLoop++){