/ Check-in [d97898e8]
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:Add in the cost of doing a table lookup on OR searches. Make test case changes to deal with difference in STAT3 behavior.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: d97898e8e3990ae8c1882c9102b57692d8810730
User & Date: drh 2013-06-19 18:01:44
Context
2013-06-19
23:48
Merge in trunk changes to os_unix.c that allow the code to build on unix platforms that lack posix_fallocate(). check-in: bf576406 user: drh tags: nextgen-query-plan-exp
18:01
Add in the cost of doing a table lookup on OR searches. Make test case changes to deal with difference in STAT3 behavior. check-in: d97898e8 user: drh tags: nextgen-query-plan-exp
13:59
Additional compiler warning fixes. check-in: 8d2ae8e2 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

   626    626   ** The original WHERE clause in pExpr is unaltered.  All this routine
   627    627   ** does is make slot[] entries point to substructure within pExpr.
   628    628   **
   629    629   ** In the previous sentence and in the diagram, "slot[]" refers to
   630    630   ** the WhereClause.a[] array.  The slot[] array grows as needed to contain
   631    631   ** all terms of the WHERE clause.
   632    632   */
   633         -static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
   634         -  pWC->op = (u8)op;
          633  +static void whereSplit(WhereClause *pWC, Expr *pExpr, u8 op){
          634  +  pWC->op = op;
   635    635     if( pExpr==0 ) return;
   636    636     if( pExpr->op!=op ){
   637    637       whereClauseInsert(pWC, pExpr, 0);
   638    638     }else{
   639    639       whereSplit(pWC, pExpr->pLeft, op);
   640    640       whereSplit(pWC, pExpr->pRight, op);
   641    641     }
................................................................................
  4512   4512     */
  4513   4513     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
  4514   4514       pNew->u.btree.nEq = 0;
  4515   4515       pNew->nLTerm = 0;
  4516   4516       pNew->iSortIdx = 0;
  4517   4517       pNew->rSetup = 0;
  4518   4518       pNew->prereq = mExtra;
         4519  +    pNew->nOut = rSize;
  4519   4520       pNew->u.btree.pIndex = pProbe;
  4520   4521       b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
  4521   4522       /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
  4522   4523       assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
  4523   4524       if( pProbe->tnum<=0 ){
  4524   4525         /* Integer primary key index */
  4525   4526         pNew->wsFlags = WHERE_IPK;
  4526   4527   
  4527   4528         /* Full table scan */
  4528   4529         pNew->iSortIdx = b ? iSortIdx : 0;
  4529         -      pNew->nOut = rSize;
  4530   4530         /* TUNING: Cost of full table scan is 3*(N + log2(N)).
  4531   4531         **  +  The extra 3 factor is to encourage the use of indexed lookups
  4532   4532         **     over full scans.  A smaller constant 2 is used for covering
  4533   4533         **     index scans so that a covering index scan will be favored over
  4534   4534         **     a table scan. */
  4535   4535         pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
  4536   4536         rc = whereLoopInsert(pBuilder, pNew);
................................................................................
  4545   4545            && pProbe->bUnordered==0
  4546   4546            && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  4547   4547            && sqlite3GlobalConfig.bUseCis
  4548   4548            && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
  4549   4549             )
  4550   4550         ){
  4551   4551           pNew->iSortIdx = b ? iSortIdx : 0;
  4552         -        pNew->nOut = rSize;
  4553   4552           if( m==0 ){
  4554   4553             /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
  4555   4554             **  +  The extra 2 factor is to encourage the use of indexed lookups
  4556   4555             **     over index scans.  A table scan uses a factor of 3 so that
  4557   4556             **     index scans are favored over table scans.
  4558   4557             **  +  If this covering index might also help satisfy the ORDER BY
  4559   4558             **     clause, then the cost is fudged down slightly so that this
................................................................................
  4820   4819         }
  4821   4820         assert( pNew->nLSlot>=1 );
  4822   4821         if( sBest.maskSelf ){
  4823   4822           pNew->nLTerm = 1;
  4824   4823           pNew->aLTerm[0] = pTerm;
  4825   4824           pNew->wsFlags = WHERE_MULTI_OR;
  4826   4825           pNew->rSetup = 0;
  4827         -        pNew->rRun = rTotal;
         4826  +        /* TUNING: Multiple by 3.5 for the secondary table lookup */
         4827  +        pNew->rRun = rTotal + 18; assert( 18==whereCost(7)-whereCost(2) );
  4828   4828           pNew->nOut = nRow;
  4829   4829           pNew->prereq = prereq;
  4830   4830           memset(&pNew->u, 0, sizeof(pNew->u));
  4831   4831           rc = whereLoopInsert(pBuilder, pNew);
  4832   4832         }
  4833   4833         whereLoopClear(pWInfo->pParse->db, &sBest);
  4834   4834       }

Changes to test/where9.test.

   594    594     count_steps {
   595    595       BEGIN;
   596    596       DELETE FROM t1
   597    597        WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
   598    598           OR (b NOT NULL AND c IS NULL AND d NOT NULL)
   599    599           OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   600    600     }
   601         -} {scan 0 sort 0}   ;# DELETEs rows 90 91 92 97
          601  +} {scan 98 sort 0}   ;# DELETEs rows 90 91 92 97
   602    602   do_test where9-6.3.6 {
   603    603     db eval {
   604    604       SELECT count(*) FROM t1 UNION ALL
   605    605       SELECT a FROM t1 WHERE a BETWEEN 85 AND 100;
   606    606       ROLLBACK;
   607    607     }
   608    608   } {95 85 86 87 88 89 93 94 95 96 98 99}
................................................................................
   611    611     count_steps {
   612    612       BEGIN;
   613    613       UPDATE t1 SET a=a+100
   614    614        WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
   615    615           OR (b NOT NULL AND +c IS NULL AND d NOT NULL)
   616    616           OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   617    617     }
   618         -} {scan 0 sort 0}   ;# Add 100 to rowids 90 91 92 97
          618  +} {scan 98 sort 0}   ;# Add 100 to rowids 90 91 92 97
   619    619   do_test where9-6.3.8 {
   620    620     db eval {
   621    621       SELECT count(*) FROM t1 UNION ALL
   622    622       SELECT a FROM t1 WHERE a BETWEEN 85 AND 100;
   623    623       ROLLBACK;
   624    624     }
   625    625   } {99 85 86 87 88 89 93 94 95 96 98 99}
................................................................................
   701    701     count_steps {
   702    702       BEGIN;
   703    703       DELETE FROM t1
   704    704        WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
   705    705           OR (b NOT NULL AND +c IS NULL AND d NOT NULL)
   706    706           OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   707    707     }
   708         -} {scan 0 sort 0}   ;# DELETEs rows 90 91 92 97
          708  +} {scan 98 sort 0}   ;# DELETEs rows 90 91 92 97
   709    709   do_test where9-6.6.2 {
   710    710     db eval {
   711    711       SELECT count(*) FROM t1 UNION ALL
   712    712       SELECT a FROM t1 WHERE a BETWEEN 85 AND 100;
   713    713       ROLLBACK;
   714    714     }
   715    715   } {95 85 86 87 88 89 93 94 95 96 98 99}
................................................................................
   718    718     count_steps {
   719    719       BEGIN;
   720    720       UPDATE t1 SET a=a+100
   721    721        WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
   722    722           OR (b NOT NULL AND +c IS NULL AND d NOT NULL)
   723    723           OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   724    724     }
   725         -} {scan 0 sort 0}   ;# Add 100 to rowids 90 91 92 97
          725  +} {scan 98 sort 0}   ;# Add 100 to rowids 90 91 92 97
   726    726   do_test where9-6.6.4 {
   727    727     db eval {
   728    728       SELECT count(*) FROM t1 UNION ALL
   729    729       SELECT a FROM t1 WHERE a BETWEEN 85 AND 200;
   730    730       ROLLBACK;
   731    731     }
   732    732   } {99 85 86 87 88 89 93 94 95 96 98 99 190 191 192 197}
................................................................................
   777    777     catchsql {
   778    778       UPDATE t1 INDEXED BY t1b SET a=a+100
   779    779        WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
   780    780           OR (b NOT NULL AND c IS NULL AND d NOT NULL)
   781    781           OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   782    782     }
   783    783   } {1 {no query solution}}
   784         -do_test where9-6.8.3 {
   785         -  catchsql {
   786         -    UPDATE t1 INDEXED BY t1b SET a=a+100
   787         -     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
   788         -        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
   789         -        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   790         -  }
   791         -} {0 {}}
   792         -do_test where9-6.8.4 {
   793         -  catchsql {
   794         -    DELETE FROM t1 INDEXED BY t1b
   795         -     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
   796         -        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
   797         -        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
   798         -  }
   799         -} {0 {}}
   800         -
          784  +ifcapable stat3 {
          785  +  # When STAT3 is enabled, the "b NOT NULL" terms get translated
          786  +  # into b>NULL, which can be satified by the index t1b.  It is a very
          787  +  # expensive way to do the query, but it works, and so a solution is possible.
          788  +  do_test where9-6.8.3-stat3 {
          789  +    catchsql {
          790  +      UPDATE t1 INDEXED BY t1b SET a=a+100
          791  +       WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
          792  +          OR (b NOT NULL AND c IS NULL AND d NOT NULL)
          793  +          OR (b NOT NULL AND c NOT NULL AND d IS NULL)
          794  +    }
          795  +  } {0 {}}
          796  +  do_test where9-6.8.4-stat3 {
          797  +    catchsql {
          798  +      DELETE FROM t1 INDEXED BY t1b
          799  +       WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
          800  +          OR (b NOT NULL AND c IS NULL AND d NOT NULL)
          801  +          OR (b NOT NULL AND c NOT NULL AND d IS NULL)
          802  +    }
          803  +  } {0 {}}
          804  +} else {
          805  +  do_test where9-6.8.3 {
          806  +    catchsql {
          807  +      UPDATE t1 INDEXED BY t1b SET a=a+100
          808  +       WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
          809  +          OR (b NOT NULL AND c IS NULL AND d NOT NULL)
          810  +          OR (b NOT NULL AND c NOT NULL AND d IS NULL)
          811  +    }
          812  +  } {1 {no query solution}}
          813  +  do_test where9-6.8.4 {
          814  +    catchsql {
          815  +      DELETE FROM t1 INDEXED BY t1b
          816  +       WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
          817  +          OR (b NOT NULL AND c IS NULL AND d NOT NULL)
          818  +          OR (b NOT NULL AND c NOT NULL AND d IS NULL)
          819  +    }
          820  +  } {1 {no query solution}}
          821  +}
   801    822   ############################################################################
   802    823   # Test cases where terms inside an OR series are combined with AND terms
   803    824   # external to the OR clause.  In other words, cases where
   804    825   #
   805    826   #              x AND (y OR z)
   806    827   #
   807    828   # is able to use indices on x,y and x,z, or indices y,x and z,x.