SQLite

Check-in [9b4d7226bc]
Login

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

Overview
Comment:Minor cleanup of the code in the query planner that computes the costs estimates for the various plans. There are no changes to the costs at this time. But the code is slightly more readable now and that might facilitate future enhancements.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9b4d7226bcee38be5ac68a54bee03b4179cb69fc
User & Date: drh 2014-03-27 18:36:34.321
Context
2014-03-28
03:12
Enhance the sqlite3VdbeRecordCompare() routines so that if they encounter database corruption, they will set the UnpackedRecord.isCorrupt field and return 0. The sqlite3BtreeMovetoUnpacked() routine detects this and returns SQLITE_CORRUPT, causing the corruption to be reported back to the top-level. (check-in: 7fa85eaaaf user: drh tags: trunk)
2014-03-27
18:36
Minor cleanup of the code in the query planner that computes the costs estimates for the various plans. There are no changes to the costs at this time. But the code is slightly more readable now and that might facilitate future enhancements. (check-in: 9b4d7226bc user: drh tags: trunk)
14:05
Enhance the logest.c utility with new operators: "dup", "inv", "log", and "nlogn". Provide help on an invalid input. (check-in: b4bd2a062c user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
4324
4325
4326
4327
4328
4329
4330




4331
4332
4333
4334
4335



4336
4337
4338
4339
4340
4341










4342
4343
4344
4345
4346
4347
4348
4349
         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;




        if( m==0 ){
          /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
          **  +  The extra factor K of between 1.1 and 3.0 that depends
          **     on the relative sizes of the table and the index.  K
          **     is smaller for smaller indices, thus favoring them.



          */
          pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 1 +
                        (15*pProbe->szIdxRow)/pTab->szTabRow;
        }else{
          /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
          ** which we will simplify to just N*log2(N) */










          pNew->rRun = rSize + rLogSize;
        }
        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }







>
>
>
>





>
>
>

<
|

|
|
>
>
>
>
>
>
>
>
>
>
|







4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343

4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
         && (pProbe->szIdxRow<pTab->szTabRow)
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        /* TUNING:  The base cost of an index scan is N + log2(N).
        ** The log2(N) is for the initial seek to the beginning and the N
        ** is for the scan itself. */
        pNew->rRun = sqlite3LogEstAdd(rSize, rLogSize);
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
          **  +  The extra factor K of between 1.1 and 3.0 that depends
          **     on the relative sizes of the table and the index.  K
          **     is smaller for smaller indices, thus favoring them.
          **     The upper bound on K (3.0) matches the penalty factor
          **     on a full table scan that tries to encourage the use of
          **     indexed lookups over full scans.
          */

          pNew->rRun +=  1 + (15*pProbe->szIdxRow)/pTab->szTabRow;
        }else{
          /* TUNING: The cost of scanning a non-covering index is multiplied
          ** by log2(N) to account for the binary search of the main table
          ** that must happen for each row of the index.
          ** TODO: Should there be a multiplier here, analogous to the 3x
          ** multiplier for a fulltable scan or covering index scan, to
          ** further discourage the use of an index scan?  Or is the log2(N)
          ** term sufficient discouragement?
          ** TODO: What if some or all of the WHERE clause terms can be
          ** computed without reference to the original table.  Then the
          ** penality should reduce to logK where K is the number of output
          ** rows.
          */
          pNew->rRun += rLogSize;
        }
        whereLoopOutputAdjust(pWC, pNew);
        rc = whereLoopInsert(pBuilder, pNew);
        pNew->nOut = rSize;
        if( rc ) break;
      }
    }
5037
5038
5039
5040
5041
5042
5043
5044

5045




5046



5047
5048
5049
5050
5051
5052
5053
5054
5055
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting cost as roughly N*log(N).

            ** If some but not all of the columns are in sorted order, then




            ** scale down the log(N) term. */



            LogEst rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy);
            LogEst rSortCost = nRowEst + estLog(nRowEst) + rScale - 66;
            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** also N*log(N) but it has a larger constant of proportionality.
            ** Multiply by 3.0. */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,







|
>
|
>
>
>
>
|
>
>
>
|
|







5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
        nOut = pFrom->nRow + pWLoop->nOut;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( isOrdered<0 ){
          isOrdered = wherePathSatisfiesOrderBy(pWInfo,
                       pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
                       iLoop, pWLoop, &revMask);
          if( isOrdered>=0 && isOrdered<nOrderBy ){
            /* TUNING: Estimated cost of sorting is N*log(N).
            ** If the order-by clause has X terms but only the last Y terms
            ** are out of order, then block-sorting will reduce the sorting
            ** cost to N*log(N)*log(Y/X).  The log(Y/X) term is computed
            ** by rScale.
            ** TODO: Should the sorting cost get a small multiplier to help
            ** discourage the use of sorting and encourage the use of index
            ** scans instead?
            */
            LogEst rScale, rSortCost;
            assert( nOrderBy>0 );
            rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy) - 66;
            rSortCost = nRowEst + estLog(nRowEst) + rScale;
            /* TUNING: The cost of implementing DISTINCT using a B-TREE is
            ** also N*log(N) but it has a larger constant of proportionality.
            ** Multiply by 3.0. */
            if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){
              rSortCost += 16;
            }
            WHERETRACE(0x002,