/ Check-in [9b4d7226]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9b4d7226bcee38be5ac68a54bee03b4179cb69fc
User & Date: drh 2014-03-27 18:36:34
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: 7fa85eaa 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: 9b4d7226 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: b4bd2a06 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs 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
....
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046








5047
5048
5049
5050
5051
5052
5053
5054
5055
         && (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;
      }
    }
................................................................................
        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,







>
>
>
>





>
>
>

<
|

|
<
>
>
>
>
>
>
>
>
>
>
>
|







 







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







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
....
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
         && (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;
      }
    }
................................................................................
        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,