/ Check-in [53efc10a]
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:Further tweaks to the query planner logic in preparation for adding ORDER BY opt-out for joins.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | qp-enhancements
Files: files | file ages | folders
SHA1: 53efc10af990d3f293551f3cd8ef2f8be2d9d716
User & Date: drh 2012-09-27 12:05:09
Context
2012-09-27
14:11
Enable ORDER BY clauses that span joins to be optimized out. check-in: c29538f9 user: drh tags: qp-enhancements
12:05
Further tweaks to the query planner logic in preparation for adding ORDER BY opt-out for joins. check-in: 53efc10a user: drh tags: qp-enhancements
2012-09-26
23:17
Further refactoring of the ORDER BY related query-planning logic in order to make it easier to extend to support optimizing out ORDER BY on joins. No actual behavior changes, yet. check-in: 96496dda user: drh tags: qp-enhancements
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
....
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
....
5020
5021
5022
5023
5024
5025
5026
5027
5028

5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039

5040
5041
5042
5043
5044
5045
5046
    int nOrderBy;                 /* Number of ORDER BY terms */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif

    nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0;
    if( (p->i) > 0 ){
      bSort = 0;
      bDist = 0;
    }else{
      bSort = p->pOrderBy!=0;
      bDist = p->pDistinct!=0;
    }

    /* Determine the values of nEq and nInMul */
    for(nEq=nOrdered=0; nEq<pProbe->nColumn; nEq++){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
................................................................................
      }
      if( nRow<2 ) nRow = 2;
    }


    WHERETRACE((
      "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
      "         notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n"
      "         nOrdered=%d nOBSat=%d\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
      nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
      p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the pCost structure.
................................................................................
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || sWBI.cost.rCost<bestPlan.rCost        /* (4) */
                || (sWBI.cost.rCost<=bestPlan.rCost 
                 && sWBI.cost.plan.nRow<bestPlan.plan.nRow))
        ){
          WHERETRACE(("=== table %d is best so far"
                      " with cost=%g and nRow=%g\n",
                      j, sWBI.cost.rCost, sWBI.cost.plan.nRow));

          bestPlan = sWBI.cost;
          bestJ = j;
        }
        if( doNotReorder ) break;
      }
    }
    assert( bestJ>=0 );
    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    WHERETRACE(("*** Optimizer selects table %d for loop %d"
                " with cost=%g and nRow=%g\n",
                bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow));

    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
      pWInfo->nOBSat = pOrderBy->nExpr;
    }
    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
      assert( pWInfo->eDistinct==0 );
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }







|
<
<
<
<
|
<







 







|
|







 







|
|
>









|
|
>







3063
3064
3065
3066
3067
3068
3069
3070




3071

3072
3073
3074
3075
3076
3077
3078
....
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
....
5015
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
    int nOrderBy;                 /* Number of ORDER BY terms */
    WhereTerm *pTerm;             /* A single term of the WHERE clause */
#ifdef SQLITE_ENABLE_STAT3
    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
#endif

    nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0;
    bSort = nOrderBy>0 && (p->i==0 || p->aLevel[p->i-1].plan.nOBSat<nOrderBy);




    bDist = p->i==0 && p->pDistinct!=0;


    /* Determine the values of nEq and nInMul */
    for(nEq=nOrdered=0; nEq<pProbe->nColumn; nEq++){
      int j = pProbe->aiColumn[nEq];
      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
      if( pTerm==0 ) break;
      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
................................................................................
      }
      if( nRow<2 ) nRow = 2;
    }


    WHERETRACE((
      "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
      "         notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
      "         used=0x%llx nOrdered=%d nOBSat=%d\n",
      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
      nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
      p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat
    ));

    /* If this index is the best we have seen so far, then record this
    ** index and its cost in the pCost structure.
................................................................................
            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || sWBI.cost.rCost<bestPlan.rCost        /* (4) */
                || (sWBI.cost.rCost<=bestPlan.rCost 
                 && sWBI.cost.plan.nRow<bestPlan.plan.nRow))
        ){
          WHERETRACE(("=== table %d is best so far"
                      " with cost=%.1f, nRow=%.1f, nOBSat=%d\n",
                      j, sWBI.cost.rCost, sWBI.cost.plan.nRow,
                      sWBI.cost.plan.nOBSat));
          bestPlan = sWBI.cost;
          bestJ = j;
        }
        if( doNotReorder ) break;
      }
    }
    assert( bestJ>=0 );
    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    WHERETRACE(("*** Optimizer selects table %d for loop %d"
                " with cost=%.1f, nRow=%.1f, nOBSat=%d\n",
                bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
                bestPlan.plan.nOBSat));
    if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
      pWInfo->nOBSat = pOrderBy->nExpr;
    }
    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
      assert( pWInfo->eDistinct==0 );
      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
    }