/ Check-in [b87cb0c2]
Login
Home Timeline Branches Tags Tickets Wiki More...

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

Overview
Comment:The query planner uses non-indexable WHERE clause terms to reduce the estimated number of output rows, then uses the estimated number of output rows as a tie-breaker when choosing table order.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b87cb0c2bd9c52a938795a974e101879b81210e3
User & Date: drh 2010-04-14 19:01:45
Context
2010-04-15
01:04
Further refinements to table order selection on join query planning. check-in: defaf0d9 user: drh tags: trunk
2010-04-14
19:01
The query planner uses non-indexable WHERE clause terms to reduce the estimated number of output rows, then uses the estimated number of output rows as a tie-breaker when choosing table order. check-in: b87cb0c2 user: drh tags: trunk
2010-04-13
06:18
Test that the rollback-hook is invoked if a commit-hook implementation returns non-zero (causing a rollback). Remove documentation comment that says otherwise from sqlite.h.in. check-in: 012cf101 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c. 

2597
2598
2599
2600
2601
2602
2603

2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
....
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
....
2718
2719
2720
2721
2722
2723
2724
































2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736


2737
2738
2739
2740
2741
2742
2743
....
2764
2765
2766
2767
2768
2769
2770

2771
2772
2773
2774
2775
2776
2777
2778
....
4038
4039
4040
4041
4042
4043
4044
4045

4046
4047
4048
4049
4050
4051
4052

    */
    int nEq;
    int bInEst = 0;
    int nInMul = 1;
    int nBound = 100;
    int bSort = 0;
    int bLookup = 0;


    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){
      WhereTerm *pTerm;           /* A single term of the WHERE clause */
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
................................................................................
      if( m==0 ){
        wsFlags |= WHERE_IDX_ONLY;
      }else{
        bLookup = 1;
      }
    }

    /**** Begin adding up the cost of using this index (Needs improvements)
    **
    ** Estimate the number of rows of output.  For an IN operator,
    ** do not let the estimate exceed half the rows in the table.
    */
    nRow = (double)(aiRowEst[nEq] * nInMul);
    if( bInEst && nRow*2>aiRowEst[0] ){
      nRow = aiRowEst[0]/2;
      nInMul = (int)(nRow / aiRowEst[nEq]);
................................................................................
    ** doing table lookups.  This reduces the cost by half.  (Not really -
    ** this needs to be fixed.)
    */
    if( pIdx && bLookup==0 ){
      cost /= (double)2;
    }
    /**** Cost of using this index has now been computed ****/

































    WHERETRACE((
      "%s(%s): nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
      "         notReady=0x%llx nRow=%.2f cost=%.2f used=0x%llx\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
      nEq, nInMul, nBound, bSort, bLookup, wsFlags, notReady, nRow, cost, used
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the pCost structure.
    */
    if( (!pIdx || wsFlags) && cost<pCost->rCost ){


      pCost->rCost = cost;
      pCost->nRow = nRow;
      pCost->used = used;
      pCost->plan.wsFlags = (wsFlags&wsFlagMask);
      pCost->plan.nEq = nEq;
      pCost->plan.u.pIdx = pIdx;
    }
................................................................................
  assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || pCost->plan.u.pIdx==0 
       || pCost->plan.u.pIdx==pSrc->pIndex 
  );

  WHERETRACE(("best index is: %s\n", 

    (pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
  ));
  
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
  bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
  pCost->plan.wsFlags |= eqTermMask;
}

................................................................................
#endif
        {
          bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);
        }
        assert( isOptimal || (sCost.used&notReady)==0 );

        if( (sCost.used&notReady)==0
         && (j==iFrom || sCost.rCost<bestPlan.rCost) 

        ){
          bestPlan = sCost;
          bestJ = j;
        }
        if( doNotReorder ) break;
      }
    }








>



<







 







|
<







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>











|
>
>







 







>
|







 







|
>








2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607

2608
2609
2610
2611
2612
2613
2614
....
2681
2682
2683
2684
2685
2686
2687
2688

2689
2690
2691
2692
2693
2694
2695
....
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
....
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
....
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087

    */
    int nEq;
    int bInEst = 0;
    int nInMul = 1;
    int nBound = 100;
    int bSort = 0;
    int bLookup = 0;
    WhereTerm *pTerm;           /* A single term of the WHERE clause */

    /* Determine the values of nEq and nInMul */
    for(nEq=0; nEq<pProbe->nColumn; nEq++){

      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        wsFlags |= WHERE_COLUMN_IN;
................................................................................
      if( m==0 ){
        wsFlags |= WHERE_IDX_ONLY;
      }else{
        bLookup = 1;
      }
    }

    /*

    ** Estimate the number of rows of output.  For an IN operator,
    ** do not let the estimate exceed half the rows in the table.
    */
    nRow = (double)(aiRowEst[nEq] * nInMul);
    if( bInEst && nRow*2>aiRowEst[0] ){
      nRow = aiRowEst[0]/2;
      nInMul = (int)(nRow / aiRowEst[nEq]);
................................................................................
    ** doing table lookups.  This reduces the cost by half.  (Not really -
    ** this needs to be fixed.)
    */
    if( pIdx && bLookup==0 ){
      cost /= (double)2;
    }
    /**** Cost of using this index has now been computed ****/

    /* If there are additional constraints on this table that cannot
    ** be used with the current index, but which might lower the number
    ** of output rows, adjust the nRow value accordingly.  This only 
    ** matters if the current index is the least costly, so do not bother
    ** with this step if we already know this index will not be chosen.
    */
    if( nRow>2 && cost<=pCost->rCost ){
      int k;
      int nSkip = nEq;
      Bitmask thisTab = getMask(pWC->pMaskSet, iCur);
      for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
        if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
        if( (pTerm->prereqAll & notReady)!=thisTab ) continue;
        if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
          if( nSkip ){
            /* Ignore the first nEq equality matches since the index
            ** has already accounted for these */
            nSkip--;
          }else{
            /* Assume each additional equality match reduces the result
            ** set size by a factor of 10 */
            nRow /= 10;
          }
        }else{
          /* Any other expression lowers the output row count by half */
          nRow /= 2;
        }
      }
      if( nRow<2 ) nRow = 2;
    }


    WHERETRACE((
      "%s(%s): nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
      "         notReady=0x%llx nRow=%.2f cost=%.2f used=0x%llx\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
      nEq, nInMul, nBound, bSort, bLookup, wsFlags, notReady, nRow, cost, used
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the pCost structure.
    */
    if( (!pIdx || wsFlags)
     && (cost<pCost->rCost || (cost==pCost->rCost && nRow<pCost->nRow))
    ){
      pCost->rCost = cost;
      pCost->nRow = nRow;
      pCost->used = used;
      pCost->plan.wsFlags = (wsFlags&wsFlagMask);
      pCost->plan.nEq = nEq;
      pCost->plan.u.pIdx = pIdx;
    }
................................................................................
  assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
  assert( pSrc->pIndex==0 
       || pCost->plan.u.pIdx==0 
       || pCost->plan.u.pIdx==pSrc->pIndex 
  );

  WHERETRACE(("best index is: %s\n", 
    ((pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" : 
         pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
  ));
  
  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
  bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
  pCost->plan.wsFlags |= eqTermMask;
}

................................................................................
#endif
        {
          bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);
        }
        assert( isOptimal || (sCost.used&notReady)==0 );

        if( (sCost.used&notReady)==0
         && (j==iFrom || sCost.rCost<bestPlan.rCost
             || (sCost.rCost==bestPlan.rCost && sCost.nRow<bestPlan.nRow))
        ){
          bestPlan = sCost;
          bestJ = j;
        }
        if( doNotReorder ) break;
      }
    }

This page was generated in about 0.032s by Fossil 2.10 [b94e15cff7] 2019-09-13 13:54:36