/ Check-in [8daf6e1b]
Login

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

Overview
Comment:Here is an attempted enhancement to the query planner that didn't work out. But it seems good to save this change for historical reference, even if it does not belong on the trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | query-planner-deadend
Files: files | file ages | folders
SHA1:8daf6e1b425e65d7ee2f23b45a3258979e5242f3
User & Date: drh 2011-07-11 15:52:45
Original Comment: Here is an attempted enhancement to the query planner that didn't work out. But it seems good to save this change for historical reference, even if it does not belong on the trunk.
Context
2011-07-11
15:52
Here is an attempted enhancement to the query planner that didn't work out. But it seems good to save this change for historical reference, even if it does not belong on the trunk. Closed-Leaf check-in: 8daf6e1b user: drh tags: query-planner-deadend
2011-07-09
16:17
Fix harmless compiler warnings on unix. check-in: 90b1aea1 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4708
4709
4710
4711
4712
4713
4714

4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
....
4809
4810
4811
4812
4813
4814
4815
4816
4817


4818
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
4832
4833

4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846






4847
4848
4849
4850
4851
4852
4853
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int j;                      /* For looping over FROM tables */
    int bestJ = -1;             /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int nUnconstrained;         /* Number tables without INDEXED BY */
    Bitmask notIndexed;         /* Mask of tables that cannot use an index */


    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = SQLITE_BIG_DBL;
    WHERETRACE(("*** Begin search for loop %d ***\n", i));

    /* Loop through the remaining entries in the FROM clause to find the
    ** next nested loop. The loop tests all FROM clause entries
    ** either once or twice. 
    **
    ** The first test is always performed if there are two or more entries
................................................................................
        }

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.
        **
        **   (2) A full-table-scan plan cannot supercede indexed plan unless
        **       the full-table-scan is an "optimal" plan as defined above.


        **
        **   (3) All tables have an INDEXED BY clause or this table lacks an
        **       INDEXED BY clause or this table uses the specific
        **       index specified by its INDEXED BY clause.  This rule ensures
        **       that a best-so-far is always selected even if an impossible
        **       combination of INDEXED BY clauses are given.  The error
        **       will be detected and relayed back to the application later.
        **       The NEVER() comes about because rule (2) above prevents
        **       An indexable full-table-scan from reaching rule (3).
        **
        **   (4) The plan cost must be lower than prior plans or else the
        **       cost must be the same and the number of rows must be lower.
        */
        if( (sCost.used&notReady)==0                       /* (1) */
            && (bestJ<0 || (notIndexed&m)!=0               /* (2) */
                || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0

                || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
            && (nUnconstrained==0 || pTabItem->pIndex==0   /* (3) */
                || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
            && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (4) */
                || (sCost.rCost<=bestPlan.rCost 
                 && sCost.plan.nRow<bestPlan.plan.nRow))
        ){
          WHERETRACE(("=== table %d is best so far"
                      " with cost=%g and nRow=%g\n",
                      j, sCost.rCost, sCost.plan.nRow));
          bestPlan = sCost;
          bestJ = j;
        }






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







>


|







 







|
|
>
>







<
<




|
|
|
>
|
|
|
|
|








>
>
>
>
>
>







4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
....
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
4826
4827


4828
4829
4830
4831
4832
4833
4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
    Index *pIdx;                /* Index for FROM table at pTabItem */
    int j;                      /* For looping over FROM tables */
    int bestJ = -1;             /* The value of j */
    Bitmask m;                  /* Bitmask value for j or bestJ */
    int isOptimal;              /* Iterator for optimal/non-optimal search */
    int nUnconstrained;         /* Number tables without INDEXED BY */
    Bitmask notIndexed;         /* Mask of tables that cannot use an index */
    double rBestOptimalIdx;     /* Cost of best optimal index plan */

    memset(&bestPlan, 0, sizeof(bestPlan));
    bestPlan.rCost = rBestOptimalIdx = SQLITE_BIG_DBL;
    WHERETRACE(("*** Begin search for loop %d ***\n", i));

    /* Loop through the remaining entries in the FROM clause to find the
    ** next nested loop. The loop tests all FROM clause entries
    ** either once or twice. 
    **
    ** The first test is always performed if there are two or more entries
................................................................................
        }

        /* Conditions under which this table becomes the best so far:
        **
        **   (1) The table must not depend on other tables that have not
        **       yet run.
        **
        **   (2) A full-table-scan cannot supercede an indexed plan unless
        **       (a) the full-table-scan is an "optimal" plan as defined above
        **       or (b) the cost of the full-table-scan is less than the cost
        **       of the best optimal index plan.
        **
        **   (3) All tables have an INDEXED BY clause or this table lacks an
        **       INDEXED BY clause or this table uses the specific
        **       index specified by its INDEXED BY clause.  This rule ensures
        **       that a best-so-far is always selected even if an impossible
        **       combination of INDEXED BY clauses are given.  The error
        **       will be detected and relayed back to the application later.


        **
        **   (4) The plan cost must be lower than prior plans or else the
        **       cost must be the same and the number of rows must be lower.
        */
        if( (sCost.used&notReady)==0                                  /* (1) */
         && (bestJ<0 || (notIndexed&m)!=0                             /* (2) */
             || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
             || sCost.rCost<rBestOptimalIdx
             || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
         && (nUnconstrained==0 || pTabItem->pIndex==0                 /* (3) */
             || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
         && (bestJ<0 || sCost.rCost<bestPlan.rCost                    /* (4) */
             || (sCost.rCost<=bestPlan.rCost 
                 && sCost.plan.nRow<bestPlan.plan.nRow))
        ){
          WHERETRACE(("=== table %d is best so far"
                      " with cost=%g and nRow=%g\n",
                      j, sCost.rCost, sCost.plan.nRow));
          bestPlan = sCost;
          bestJ = j;
        }
        if( isOptimal
         && (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0
         && sCost.rCost<rBestOptimalIdx
        ){
          rBestOptimalIdx = bestPlan.rCost;
        }
        if( doNotReorder ) break;
      }
    }
    assert( bestJ>=0 );
    assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
    WHERETRACE(("*** Optimizer selects table %d for loop %d"
                " with cost=%g and nRow=%g\n",