SQLite

Check-in [52d5268864]
Login

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

Overview
Comment:Tweaks to the index selection logic.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | unlikely-func
Files: files | file ages | folders
SHA1: 52d52688644f635a50a60ff17b160f3affa8fa6c
User & Date: drh 2013-09-11 03:53:22.579
Context
2013-09-11
11:38
Change the name of the two-argument unlikely() function to likelihood(). Add test cases. (check-in: 29a359b8d7 user: drh tags: unlikely-func)
03:53
Tweaks to the index selection logic. (check-in: 52d5268864 user: drh tags: unlikely-func)
2013-09-10
01:53
Merge trunk fixes into the unlikely-func branch. (check-in: a51d751553 user: drh tags: unlikely-func)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/resolve.c.
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
            pExpr->iTable = exprProbability(pList->a[1].pExpr);
            if( pExpr->iTable<0 ){
              sqlite3ErrorMsg(pParse, "second parameter to unlikely() must be "
                                      "between 0.0 and 1.0");
              pNC->nErr++;
            }
          }else{
            pExpr->iTable = 75;  /* TUNING:  Default 2nd arg to unlikely() is 0.075 */
          }             
        }
      }
#ifndef SQLITE_OMIT_AUTHORIZATION
      if( pDef ){
        auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0, pDef->zName, 0);
        if( auth!=SQLITE_OK ){







|







701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
            pExpr->iTable = exprProbability(pList->a[1].pExpr);
            if( pExpr->iTable<0 ){
              sqlite3ErrorMsg(pParse, "second parameter to unlikely() must be "
                                      "between 0.0 and 1.0");
              pNC->nErr++;
            }
          }else{
            pExpr->iTable = 62;  /* TUNING:  Default 2nd arg to unlikely() is 0.0625 */
          }             
        }
      }
#ifndef SQLITE_OMIT_AUTHORIZATION
      if( pDef ){
        auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0, pDef->zName, 0);
        if( auth!=SQLITE_OK ){
Changes to src/where.c.
2553
2554
2555
2556
2557
2558
2559

2560
2561
2562
2563
2564
2565
2566
  WhereLoopBuilder *pBuilder,
  WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  WhereCost *pnOut     /* IN/OUT: Number of rows visited */
){
  int rc = SQLITE_OK;
  int nOut = (int)*pnOut;


#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  Index *p = pBuilder->pNew->u.btree.pIndex;
  int nEq = pBuilder->pNew->u.btree.nEq;

  if( p->nSample>0
   && nEq==pBuilder->nRecValid







>







2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
  WhereLoopBuilder *pBuilder,
  WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  WhereCost *pnOut     /* IN/OUT: Number of rows visited */
){
  int rc = SQLITE_OK;
  int nOut = (int)*pnOut;
  WhereCost nNew;

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  Index *p = pBuilder->pNew->u.btree.pIndex;
  int nEq = pBuilder->pNew->u.btree.nEq;

  if( p->nSample>0
   && nEq==pBuilder->nRecValid
2615
2616
2617
2618
2619
2620
2621

2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635

2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
      rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
      if( rc==SQLITE_OK && bOk ){
        tRowcnt iNew;
        whereKeyStats(pParse, p, pRec, 0, a);
        iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0);
        if( iNew>iLower ) iLower = iNew;

      }
    }

    /* If possible, improve on the iUpper estimate using ($P:$U). */
    if( pUpper ){
      int bOk;                    /* True if value is extracted from pExpr */
      Expr *pExpr = pUpper->pExpr->pRight;
      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
      rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
      if( rc==SQLITE_OK && bOk ){
        tRowcnt iNew;
        whereKeyStats(pParse, p, pRec, 1, a);
        iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0);
        if( iNew<iUpper ) iUpper = iNew;

      }
    }

    pBuilder->pRec = pRec;
    if( rc==SQLITE_OK ){
      WhereCost nNew;
      if( iUpper>iLower ){
        nNew = whereCost(iUpper - iLower);
      }else{
        nNew = 10;        assert( 10==whereCost(2) );
      }
      if( nNew<nOut ){
        nOut = nNew;







>














>





<







2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643

2644
2645
2646
2647
2648
2649
2650
      assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
      rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
      if( rc==SQLITE_OK && bOk ){
        tRowcnt iNew;
        whereKeyStats(pParse, p, pRec, 0, a);
        iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0);
        if( iNew>iLower ) iLower = iNew;
        nOut--;
      }
    }

    /* If possible, improve on the iUpper estimate using ($P:$U). */
    if( pUpper ){
      int bOk;                    /* True if value is extracted from pExpr */
      Expr *pExpr = pUpper->pExpr->pRight;
      assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
      rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
      if( rc==SQLITE_OK && bOk ){
        tRowcnt iNew;
        whereKeyStats(pParse, p, pRec, 1, a);
        iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0);
        if( iNew<iUpper ) iUpper = iNew;
        nOut--;
      }
    }

    pBuilder->pRec = pRec;
    if( rc==SQLITE_OK ){

      if( iUpper>iLower ){
        nNew = whereCost(iUpper - iLower);
      }else{
        nNew = 10;        assert( 10==whereCost(2) );
      }
      if( nNew<nOut ){
        nOut = nNew;
2656
2657
2658
2659
2660
2661
2662

2663
2664

2665
2666
2667

2668

2669
2670
2671
2672
2673
2674
2675
2676
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(pBuilder);
#endif
  assert( pLower || pUpper );
  /* TUNING:  Each inequality constraint reduces the search space 4-fold.
  ** A BETWEEN operator, therefore, reduces the search space 16-fold */

  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
    nOut -= 20;        assert( 20==whereCost(4) );

  }
  if( pUpper ){
    nOut -= 20;        assert( 20==whereCost(4) );

  }

  if( nOut<10 ) nOut = 10;
  *pnOut = (WhereCost)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Estimate the number of rows that will be returned based on







>

|
>


|
>

>
|







2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
#else
  UNUSED_PARAMETER(pParse);
  UNUSED_PARAMETER(pBuilder);
#endif
  assert( pLower || pUpper );
  /* TUNING:  Each inequality constraint reduces the search space 4-fold.
  ** A BETWEEN operator, therefore, reduces the search space 16-fold */
  nNew = nOut;
  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
    nNew -= 20;        assert( 20==whereCost(4) );
    nOut--;
  }
  if( pUpper ){
    nNew -= 20;        assert( 20==whereCost(4) );
    nOut--;
  }
  if( nNew<10 ) nNew = 10;
  if( nNew<nOut ) nOut = nNew;
  *pnOut = (WhereCost)nOut;
  return rc;
}

#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
/*
** Estimate the number of rows that will be returned based on
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
      ** all of (1) dependencies (2) setup-cost, (3) run-cost, and
      ** (4) number of output rows. */
      assert( p->rSetup==pTemplate->rSetup );
      if( p->prereq==pTemplate->prereq
       && p->nLTerm<pTemplate->nLTerm
       && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0
       && (p->u.btree.pIndex==pTemplate->u.btree.pIndex
           || p->u.btree.pIndex->nColumn>=pTemplate->u.btree.pIndex->nColumn)
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;
      }else{
        /* pTemplate is not helpful.







|







4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
      ** all of (1) dependencies (2) setup-cost, (3) run-cost, and
      ** (4) number of output rows. */
      assert( p->rSetup==pTemplate->rSetup );
      if( p->prereq==pTemplate->prereq
       && p->nLTerm<pTemplate->nLTerm
       && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0
       && (p->u.btree.pIndex==pTemplate->u.btree.pIndex
          || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm)
      ){
        /* Overwrite an existing WhereLoop with an similar one that uses
        ** more terms of the index */
        pNext = p->pNextLoop;
        break;
      }else{
        /* pTemplate is not helpful.
Changes to test/analyze9.test.
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
  reset_db
  execsql {
    CREATE TABLE t1(a, UNIQUE(a));
    INSERT INTO t1 VALUES($two);
    ANALYZE;
  }
  set nByte2 [lindex [sqlite3_db_status db SCHEMA_USED 0] 1]
puts "$nByte $nByte2"

  expr {$nByte2 > $nByte+900 && $nByte2 < $nByte+1050}
} {1}

#-------------------------------------------------------------------------
# Test that stat4 data may be used with partial indexes.
#







<







801
802
803
804
805
806
807

808
809
810
811
812
813
814
  reset_db
  execsql {
    CREATE TABLE t1(a, UNIQUE(a));
    INSERT INTO t1 VALUES($two);
    ANALYZE;
  }
  set nByte2 [lindex [sqlite3_db_status db SCHEMA_USED 0] 1]


  expr {$nByte2 > $nByte+900 && $nByte2 < $nByte+1050}
} {1}

#-------------------------------------------------------------------------
# Test that stat4 data may be used with partial indexes.
#
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=10 AND c=10;
} {/USING INDEX i1/}
do_eqp_test 17.3 {
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=0 AND c=10;
} {/USING INDEX i1/}

do_execsql_test 17.4 {
  CREATE INDEX i2 ON t1(c);
  ANALYZE main.i2;
}
do_eqp_test 17.5 {
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=10 AND c=10;
} {/USING INDEX i1/}
do_eqp_test 17.6 {
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=0 AND c=10;







|







841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=10 AND c=10;
} {/USING INDEX i1/}
do_eqp_test 17.3 {
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=0 AND c=10;
} {/USING INDEX i1/}

do_execsql_test 17.4 {
  CREATE INDEX i2 ON t1(c, d);
  ANALYZE main.i2;
}
do_eqp_test 17.5 {
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=10 AND c=10;
} {/USING INDEX i1/}
do_eqp_test 17.6 {
  SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=0 AND c=10;