/ 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 Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
....
4512
4513
4514
4515
4516
4517
4518

4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
....
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
....
4820
4821
4822
4823
4824
4825
4826

4827
4828
4829
4830
4831
4832
4833
4834
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make slot[] entries point to substructure within pExpr.
**
** In the previous sentence and in the diagram, "slot[]" refers to
** the WhereClause.a[] array.  The slot[] array grows as needed to contain
** all terms of the WHERE clause.
*/
static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
  pWC->op = (u8)op;
  if( pExpr==0 ) return;
  if( pExpr->op!=op ){
    whereClauseInsert(pWC, pExpr, 0);
  }else{
    whereSplit(pWC, pExpr->pLeft, op);
    whereSplit(pWC, pExpr->pRight, op);
  }
................................................................................
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;

    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;
      pNew->nOut = rSize;
      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */
      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
................................................................................
         && pProbe->bUnordered==0
         && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
         && sqlite3GlobalConfig.bUseCis
         && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
          )
      ){
        pNew->iSortIdx = b ? iSortIdx : 0;
        pNew->nOut = rSize;
        if( m==0 ){
          /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
          **  +  The extra 2 factor is to encourage the use of indexed lookups
          **     over index scans.  A table scan uses a factor of 3 so that
          **     index scans are favored over table scans.
          **  +  If this covering index might also help satisfy the ORDER BY
          **     clause, then the cost is fudged down slightly so that this
................................................................................
      }
      assert( pNew->nLSlot>=1 );
      if( sBest.maskSelf ){
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        pNew->wsFlags = WHERE_MULTI_OR;
        pNew->rSetup = 0;

        pNew->rRun = rTotal;
        pNew->nOut = nRow;
        pNew->prereq = prereq;
        memset(&pNew->u, 0, sizeof(pNew->u));
        rc = whereLoopInsert(pBuilder, pNew);
      }
      whereLoopClear(pWInfo->pParse->db, &sBest);
    }







|
|







 







>










<







 







<







 







>
|







626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
....
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529

4530
4531
4532
4533
4534
4535
4536
....
4545
4546
4547
4548
4549
4550
4551

4552
4553
4554
4555
4556
4557
4558
....
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
4832
4833
4834
** The original WHERE clause in pExpr is unaltered.  All this routine
** does is make slot[] entries point to substructure within pExpr.
**
** In the previous sentence and in the diagram, "slot[]" refers to
** the WhereClause.a[] array.  The slot[] array grows as needed to contain
** all terms of the WHERE clause.
*/
static void whereSplit(WhereClause *pWC, Expr *pExpr, u8 op){
  pWC->op = op;
  if( pExpr==0 ) return;
  if( pExpr->op!=op ){
    whereClauseInsert(pWC, pExpr, 0);
  }else{
    whereSplit(pWC, pExpr->pLeft, op);
    whereSplit(pWC, pExpr->pRight, op);
  }
................................................................................
  */
  for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
    pNew->u.btree.nEq = 0;
    pNew->nLTerm = 0;
    pNew->iSortIdx = 0;
    pNew->rSetup = 0;
    pNew->prereq = mExtra;
    pNew->nOut = rSize;
    pNew->u.btree.pIndex = pProbe;
    b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
    /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */
    assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 );
    if( pProbe->tnum<=0 ){
      /* Integer primary key index */
      pNew->wsFlags = WHERE_IPK;

      /* Full table scan */
      pNew->iSortIdx = b ? iSortIdx : 0;

      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
      **  +  The extra 3 factor is to encourage the use of indexed lookups
      **     over full scans.  A smaller constant 2 is used for covering
      **     index scans so that a covering index scan will be favored over
      **     a table scan. */
      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
      rc = whereLoopInsert(pBuilder, pNew);
................................................................................
         && pProbe->bUnordered==0
         && (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 2*(N + log2(N)).
          **  +  The extra 2 factor is to encourage the use of indexed lookups
          **     over index scans.  A table scan uses a factor of 3 so that
          **     index scans are favored over table scans.
          **  +  If this covering index might also help satisfy the ORDER BY
          **     clause, then the cost is fudged down slightly so that this
................................................................................
      }
      assert( pNew->nLSlot>=1 );
      if( sBest.maskSelf ){
        pNew->nLTerm = 1;
        pNew->aLTerm[0] = pTerm;
        pNew->wsFlags = WHERE_MULTI_OR;
        pNew->rSetup = 0;
        /* TUNING: Multiple by 3.5 for the secondary table lookup */
        pNew->rRun = rTotal + 18; assert( 18==whereCost(7)-whereCost(2) );
        pNew->nOut = nRow;
        pNew->prereq = prereq;
        memset(&pNew->u, 0, sizeof(pNew->u));
        rc = whereLoopInsert(pBuilder, pNew);
      }
      whereLoopClear(pWInfo->pParse->db, &sBest);
    }

Changes to test/where9.test.

594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
...
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
...
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
...
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
...
777
778
779
780
781
782
783




784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799







800










801
802
803
804
805
806
807
  count_steps {
    BEGIN;
    DELETE FROM t1
     WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {scan 0 sort 0}   ;# DELETEs rows 90 91 92 97
do_test where9-6.3.6 {
  db eval {
    SELECT count(*) FROM t1 UNION ALL
    SELECT a FROM t1 WHERE a BETWEEN 85 AND 100;
    ROLLBACK;
  }
} {95 85 86 87 88 89 93 94 95 96 98 99}
................................................................................
  count_steps {
    BEGIN;
    UPDATE t1 SET a=a+100
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND +c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {scan 0 sort 0}   ;# Add 100 to rowids 90 91 92 97
do_test where9-6.3.8 {
  db eval {
    SELECT count(*) FROM t1 UNION ALL
    SELECT a FROM t1 WHERE a BETWEEN 85 AND 100;
    ROLLBACK;
  }
} {99 85 86 87 88 89 93 94 95 96 98 99}
................................................................................
  count_steps {
    BEGIN;
    DELETE FROM t1
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND +c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {scan 0 sort 0}   ;# DELETEs rows 90 91 92 97
do_test where9-6.6.2 {
  db eval {
    SELECT count(*) FROM t1 UNION ALL
    SELECT a FROM t1 WHERE a BETWEEN 85 AND 100;
    ROLLBACK;
  }
} {95 85 86 87 88 89 93 94 95 96 98 99}
................................................................................
  count_steps {
    BEGIN;
    UPDATE t1 SET a=a+100
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND +c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {scan 0 sort 0}   ;# Add 100 to rowids 90 91 92 97
do_test where9-6.6.4 {
  db eval {
    SELECT count(*) FROM t1 UNION ALL
    SELECT a FROM t1 WHERE a BETWEEN 85 AND 200;
    ROLLBACK;
  }
} {99 85 86 87 88 89 93 94 95 96 98 99 190 191 192 197}
................................................................................
  catchsql {
    UPDATE t1 INDEXED BY t1b SET a=a+100
     WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {1 {no query solution}}




do_test where9-6.8.3 {
  catchsql {
    UPDATE t1 INDEXED BY t1b SET a=a+100
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {0 {}}
do_test where9-6.8.4 {
  catchsql {
    DELETE FROM t1 INDEXED BY t1b
     WHERE (b IS NULL AND c NOT NULL AND d NOT NULL)
        OR (b NOT NULL AND c IS NULL AND d NOT NULL)
        OR (b NOT NULL AND c NOT NULL AND d IS NULL)
  }
} {0 {}}


















############################################################################
# Test cases where terms inside an OR series are combined with AND terms
# external to the OR clause.  In other words, cases where
#
#              x AND (y OR z)
#
# is able to use indices on x,y and x,z, or indices y,x and z,x.







|







 







|







 







|







 







|







 







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







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