Further refinements to table order selection on join query planning.

FossilOrigin-Name: defaf0d99a807027f8883bf821b6482025f9f54e

8 files changed, 78 insertions, 56 deletions

diff --git a/manifest b/manifest
index 552af6097..00193d386 100644
--- a/manifest
+++ b/manifest
@@ -1,8 +1,8 @@
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA1
 
-C The\squery\splanner\suses\snon-indexable\sWHERE\sclause\sterms\sto\sreduce\sthe\nestimated\snumber\sof\soutput\srows,\sthen\suses\sthe\sestimated\snumber\sof\soutput\nrows\sas\sa\stie-breaker\swhen\schoosing\stable\sorder.
-D 2010-04-14T19:01:45
+C Further\srefinements\sto\stable\sorder\sselection\son\sjoin\squery\splanning.
+D 2010-04-15T01:04:54
 F Makefile.arm-wince-mingw32ce-gcc fcd5e9cd67fe88836360bb4f9ef4cb7f8e2fb5a0
 F Makefile.in 4f2f967b7e58a35bb74fb7ec8ae90e0f4ca7868b
 F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654
@@ -225,7 +225,7 @@ F src/vdbemem.c 2a82f455f6ca6f78b59fb312f96054c04ae0ead1
 F src/vdbetrace.c 864cef96919323482ebd9986f2132435115e9cc2
 F src/vtab.c a0f8a40274e4261696ef57aa806de2776ab72cda
 F src/walker.c 3112bb3afe1d85dc52317cb1d752055e9a781f8f
-F src/where.c 458b6e0d5e3e4eaaf75e352a88641ab2d7e21cad
+F src/where.c 74ff6f0d96b3190f8abe2ceaa09858441749e8ff
 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2
 F test/alias.test 4529fbc152f190268a15f9384a5651bbbabc9d87
 F test/all.test 14165b3e32715b700b5f0cbf8f6e3833dda0be45
@@ -558,7 +558,7 @@ F test/schema.test 8f7999be894260f151adf15c2c7540f1c6d6a481
 F test/schema2.test 906408621ea881fdb496d878b1822572a34e32c5
 F test/securedel.test 328d2921c0ca49bdd3352e516b0377fc07143254
 F test/select1.test f67ca2dfc05df41c7b86eb32ca409b427a5f43b0
-F test/select2.test 9735da20ccd41e42bf2b4c19fd939141b591adae
+F test/select2.test 352480e0e9c66eda9c3044e412abdf5be0215b56
 F test/select3.test 2ce595f8fb8e2ac10071d3b4e424cadd4634a054
 F test/select4.test 44aa6e7110592e18110b0b9cf5c024d37d23be17
 F test/select5.test e758b8ef94f69b111df4cb819008856655dcd535
@@ -723,7 +723,7 @@ F test/trigger6.test 0e411654f122552da6590f0b4e6f781048a4a9b9
 F test/trigger7.test 72feaf8dbc52cea84de0c3e6ce7559ff19c479af
 F test/trigger8.test 30cb0530bd7c4728055420e3f739aa00412eafa4
 F test/trigger9.test 5b0789f1c5c4600961f8e68511b825b87be53e31
-F test/triggerA.test 0718ad2d9bfef27c7af00e636df79bee6b988da7
+F test/triggerA.test eaf11a29db2a11967d2d4b49d37f92bce598194e
 F test/triggerB.test 56780c031b454abac2340dbb3b71ac5c56c3d7fe
 F test/triggerC.test cac41fe31adc1abb9fa08532762fc2b4f662ab03
 F test/triggerD.test c6add3817351451e419f6ff9e9a259b02b6e2de7
@@ -759,12 +759,12 @@ F test/vtab_err.test 0d4d8eb4def1d053ac7c5050df3024fd47a3fbd8
 F test/vtab_shared.test 0eff9ce4f19facbe0a3e693f6c14b80711a4222d
 F test/where.test de337a3fe0a459ec7c93db16a519657a90552330
 F test/where2.test 45eacc126aabb37959a387aa83e59ce1f1f03820
-F test/where3.test 97d3936e6a443b968f1a61cdcc0f673252000e94
+F test/where3.test aa44a9b29e8c9f3d7bb94a3bb3a95b31627d520d
 F test/where4.test e9b9e2f2f98f00379e6031db6a6fca29bae782a2
 F test/where5.test fdf66f96d29a064b63eb543e28da4dfdccd81ad2
 F test/where6.test 5da5a98cec820d488e82708301b96cb8c18a258b
-F test/where7.test fdd58ab9dec9f97679e65d4414bf5e07d725d79f
-F test/where8.test 2bb8ea44b745fcc93db150fac9ce33d12e499760
+F test/where7.test a0a92b8ce48d9c027fbdd7b764c7de1e1213575a
+F test/where8.test a6c740fd286d7883e274e17b6230a9d672a7ab1f
 F test/where8m.test da346596e19d54f0aba35ebade032a7c47d79739
 F test/where9.test be19e1a92f80985c1a121b4678bf7d2123eaa623
 F test/whereA.test 24c234263c8fe358f079d5e57d884fb569d2da0a
@@ -800,14 +800,14 @@ F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff
 F tool/speedtest8.c 2902c46588c40b55661e471d7a86e4dd71a18224
 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e
 F tool/vdbe-compress.tcl d70ea6d8a19e3571d7ab8c9b75cba86d1173ff0f
-P 012cf101bf8be9e39c138786ea5a5039b8131e55
-R e6913462c9fc35ffdd8fb296dee81dc4
+P b87cb0c2bd9c52a938795a974e101879b81210e3
+R ac19ec910df4152a1528b71c1365be54
 U drh
-Z b112ddd6d5441568434e7011a246cd66
+Z 406deb0be8ed4b7e4bb6e640f59e7f15
 -----BEGIN PGP SIGNATURE-----
 Version: GnuPG v1.4.6 (GNU/Linux)
 
-iD8DBQFLxhEcoxKgR168RlERAr4AAJ4o9PzYb8/4qM3TXJMcn3pTohzAyQCeOO2/
-T96saJ5mGiq/UIbcA3uQVL0=
-=Qkym
+iD8DBQFLxmY4oxKgR168RlERAsvwAJ4tlJVE6cdAiLgjUGC8Snj86Xjm4ACeIy59
+w6HyVplE+rrSW13BtidRydE=
+=uibN
 -----END PGP SIGNATURE-----
diff --git a/manifest.uuid b/manifest.uuid
index 4577d98b8..ddeecd995 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-b87cb0c2bd9c52a938795a974e101879b81210e3
\ No newline at end of file
+defaf0d99a807027f8883bf821b6482025f9f54e
\ No newline at end of file
diff --git a/src/where.c b/src/where.c
index f9fc47777..77ecdfef4 100644
--- a/src/where.c
+++ b/src/where.c
@@ -1575,6 +1575,11 @@ static void bestOrClauseIndex(
   WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
   WhereTerm *pTerm;                 /* A single term of the WHERE clause */
 
+  /* No OR-clause optimization allowed if the NOT INDEXED clause is used */
+  if( pSrc->notIndexed ){
+    return;
+  }
+
   /* Search the WHERE clause terms for a usable WO_OR term. */
   for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
     if( pTerm->eOperator==WO_OR 
@@ -1617,8 +1622,9 @@ static void bestOrClauseIndex(
       /* If there is an ORDER BY clause, increase the scan cost to account 
       ** for the cost of the sort. */
       if( pOrderBy!=0 ){
+        WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
+                    rTotal, rTotal+nRow*estLog(nRow)));
         rTotal += nRow*estLog(nRow);
-        WHERETRACE(("... sorting increases OR cost to %.9g\n", rTotal));
       }
 
       /* If the cost of scanning using this OR term for optimization is
@@ -2569,14 +2575,14 @@ static void bestBtreeIndex(
     **    Set to true if there was at least one "x IN (SELECT ...)" term used 
     **    in determining the value of nInMul.
     **
-    **  nBound:
+    **  estBound:
     **    An estimate on the amount of the table that must be searched.  A
     **    value of 100 means the entire table is searched.  Range constraints
     **    might reduce this to a value less than 100 to indicate that only
     **    a fraction of the table needs searching.  In the absence of
     **    sqlite_stat2 ANALYZE data, a single inequality reduces the search
     **    space to 1/3rd its original size.  So an x>? constraint reduces
-    **    nBound to 33.  Two constraints (x>? AND x<?) reduce nBound to 11.
+    **    estBound to 33.  Two constraints (x>? AND x<?) reduce estBound to 11.
     **
     **  bSort:   
     **    Boolean. True if there is an ORDER BY clause that will require an 
@@ -2598,7 +2604,8 @@ static void bestBtreeIndex(
     int nEq;
     int bInEst = 0;
     int nInMul = 1;
-    int nBound = 100;
+    int estBound = 100;
+    int nBound = 0;             /* Number of range constraints seen */
     int bSort = 0;
     int bLookup = 0;
     WhereTerm *pTerm;           /* A single term of the WHERE clause */
@@ -2624,18 +2631,20 @@ static void bestBtreeIndex(
       used |= pTerm->prereqRight;
     }
 
-    /* Determine the value of nBound. */
+    /* Determine the value of estBound. */
     if( nEq<pProbe->nColumn ){
       int j = pProbe->aiColumn[nEq];
       if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
         WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
         WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
-        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &nBound);
+        whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &estBound);
         if( pTop ){
+          nBound = 1;
           wsFlags |= WHERE_TOP_LIMIT;
           used |= pTop->prereqRight;
         }
         if( pBtm ){
+          nBound++;
           wsFlags |= WHERE_BTM_LIMIT;
           used |= pBtm->prereqRight;
         }
@@ -2704,8 +2713,8 @@ static void bestBtreeIndex(
     /* Adjust the number of rows and the cost downward to reflect rows
     ** that are excluded by range constraints.
     */
-    nRow = (nRow * (double)nBound) / (double)100;
-    cost = (cost * (double)nBound) / (double)100;
+    nRow = (nRow * (double)estBound) / (double)100;
+    cost = (cost * (double)estBound) / (double)100;
 
     /* Add in the estimated cost of sorting the result
     */
@@ -2727,24 +2736,36 @@ static void bestBtreeIndex(
     ** 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.
+    ** Also, never reduce the output row count below 2 using this step.
     */
     if( nRow>2 && cost<=pCost->rCost ){
       int k;
-      int nSkip = nEq;
+      int nSkipEq = nEq;
+      int nSkipRange = nBound;
       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 ){
+          if( nSkipEq ){
             /* Ignore the first nEq equality matches since the index
             ** has already accounted for these */
-            nSkip--;
+            nSkipEq--;
           }else{
             /* Assume each additional equality match reduces the result
             ** set size by a factor of 10 */
             nRow /= 10;
           }
+        }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
+          if( nSkipRange ){
+            /* Ignore the first nBound range constraints since the index
+            ** has already accounted for these */
+            nSkipRange--;
+          }else{
+            /* Assume each additional range constraint reduces the result
+            ** set size by a factor of 3 */
+            nRow /= 3;
+          }
         }else{
           /* Any other expression lowers the output row count by half */
           nRow /= 2;
@@ -2755,17 +2776,18 @@ static void bestBtreeIndex(
 
 
     WHERETRACE((
-      "%s(%s): nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
+      "%s(%s): nEq=%d nInMul=%d estBound=%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
+      nEq, nInMul, estBound, 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))
+     && (cost<pCost->rCost || (cost<=pCost->rCost && nRow<pCost->nRow))
     ){
       pCost->rCost = cost;
       pCost->nRow = nRow;
@@ -4015,20 +4037,25 @@ WhereInfo *sqlite3WhereBegin(
     bestPlan.rCost = SQLITE_BIG_DBL;
 
     /* Loop through the remaining entries in the FROM clause to find the
-    ** next nested loop. The FROM clause entries may be iterated through
+    ** next nested loop. The loop tests all FROM clause entries
     ** either once or twice. 
     **
-    ** The first iteration, which is always performed, searches for the
-    ** FROM clause entry that permits the lowest-cost, "optimal" scan. In
+    ** The first test is always performed if there are two or more entries
+    ** remaining and never performed if there is only one FROM clause entry
+    ** to choose from.  The first test looks for an "optimal" scan.  In
     ** this context an optimal scan is one that uses the same strategy
     ** for the given FROM clause entry as would be selected if the entry
     ** were used as the innermost nested loop.  In other words, a table
     ** is chosen such that the cost of running that table cannot be reduced
-    ** by waiting for other tables to run first.
+    ** by waiting for other tables to run first.  This "optimal" test works
+    ** by first assuming that the FROM clause is on the inner loop and finding
+    ** its query plan, then checking to see if that query plan uses any
+    ** other FROM clause terms that are notReady.  If no notReady terms are
+    ** used then the "optimal" query plan works.
     **
-    ** The second iteration is only performed if no optimal scan strategies
-    ** were found by the first. This iteration is used to search for the
-    ** lowest cost scan overall.
+    ** The second loop iteration is only performed if no optimal scan
+    ** strategies were found by the first loop. This 2nd iteration is used to
+    ** search for the lowest cost scan overall.
     **
     ** Previous versions of SQLite performed only the second iteration -
     ** the next outermost loop was always that with the lowest overall
@@ -4046,9 +4073,8 @@ WhereInfo *sqlite3WhereBegin(
     ** algorithm may choose to use t2 for the outer loop, which is a much
     ** costlier approach.
     */
-    for(isOptimal=1; isOptimal>=0 && bestJ<0; isOptimal--){
-      Bitmask mask = (isOptimal ? 0 : notReady);
-      assert( (nTabList-iFrom)>1 || isOptimal );
+    for(isOptimal=(iFrom<nTabList-1); isOptimal>=0; isOptimal--){
+      Bitmask mask;  /* Mask of tables not yet ready */
       for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
         int doNotReorder;    /* True if this table should not be reordered */
         WhereCost sCost;     /* Cost information from best[Virtual]Index() */
@@ -4061,6 +4087,7 @@ WhereInfo *sqlite3WhereBegin(
           if( j==iFrom ) iFrom++;
           continue;
         }
+        mask = (isOptimal ? m : notReady);
         pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
   
         assert( pTabItem->pTab );
@@ -4076,9 +4103,11 @@ WhereInfo *sqlite3WhereBegin(
         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))
+         && (bestJ<0 || sCost.rCost<bestPlan.rCost
+             || (sCost.rCost<=bestPlan.rCost && sCost.nRow<bestPlan.nRow))
         ){
+          WHERETRACE(("... best so far with cost=%g and nRow=%g\n",
+                      sCost.rCost, sCost.nRow));
           bestPlan = sCost;
           bestJ = j;
         }
diff --git a/test/select2.test b/test/select2.test
index 25a552de1..35f8dd587 100644
--- a/test/select2.test
+++ b/test/select2.test
@@ -153,12 +153,12 @@ do_test select2-4.1 {
 do_test select2-4.2 {
   execsql {
     INSERT INTO bb VALUES(0);
-    SELECT * FROM aa, bb WHERE b;
+    SELECT * FROM aa CROSS JOIN bb WHERE b;
   }
 } {1 2 1 4 3 2 3 4}
 do_test select2-4.3 {
   execsql {
-    SELECT * FROM aa, bb WHERE NOT b;
+    SELECT * FROM aa CROSS JOIN bb WHERE NOT b;
   }
 } {1 0 3 0}
 do_test select2-4.4 {
diff --git a/test/triggerA.test b/test/triggerA.test
index 1a0055f3a..9f93db5c9 100644
--- a/test/triggerA.test
+++ b/test/triggerA.test
@@ -77,7 +77,7 @@ do_test triggerA-1.5 {
 do_test triggerA-1.6 {
   db eval {
      CREATE VIEW v5 AS SELECT x, b FROM t1, t2 WHERE y=c;
-     SELECT * FROM v5;
+     SELECT * FROM v5 ORDER BY x DESC;
   }
 } {10 1003 9 904 8 805 7 705 6 603 5 504 4 404 3 305 2 203 1 103}
 
diff --git a/test/where3.test b/test/where3.test
index c395d0ac1..13f947329 100644
--- a/test/where3.test
+++ b/test/where3.test
@@ -199,13 +199,13 @@ do_test where3-2.5 {
      WHERE cpk=ax AND bpk=cx
   }
 } {tA {} tC * tB * tD *}
-do_test where3-2.5 {
+do_test where3-2.6 {
   queryplan {
     SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
      WHERE bpk=cx AND apk=bx
   }
 } {tC {} tB * tA * tD *}
-do_test where3-2.6 {
+do_test where3-2.7 {
   queryplan {
     SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
      WHERE cpk=bx AND apk=cx
diff --git a/test/where7.test b/test/where7.test
index 10a94c137..dbb9bc6b6 100644
--- a/test/where7.test
+++ b/test/where7.test
@@ -90,12 +90,10 @@ do_test where7-1.9 {
   }
 } {2 4 5 scan 0 sort 0}
 do_test where7-1.10 {
-breakpoint
   count_steps {
     SELECT a FROM t1 WHERE (b=3 OR c>=10 OR c=4 OR b>10)
   }
 } {2 4 5 scan 0 sort 0}
-breakpoint
 do_test where7-1.11 {
   count_steps {
     SELECT a FROM t1 WHERE (d=5 AND b=3) OR c==100 ORDER BY a;
@@ -106,13 +104,7 @@ do_test where7-1.12 {
     SELECT a FROM t1 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a
   }
 } {1 2 3 5 scan 0 sort 1}
-do_test where7-1.13.1 {
-  count_steps {
-    SELECT a FROM t1 WHERE (b BETWEEN 0 AND 2) OR (c BETWEEN 9 AND 999)
-    ORDER BY a DESC
-  }
-} {5 4 1 scan 4 sort 0}
-do_test where7-1.13.2 {
+do_test where7-1.13 {
   count_steps {
     SELECT a FROM t1 WHERE (b BETWEEN 0 AND 2) OR (c BETWEEN 9 AND 999)
     ORDER BY +a DESC
diff --git a/test/where8.test b/test/where8.test
index 04657c047..a7d5edb3f 100644
--- a/test/where8.test
+++ b/test/where8.test
@@ -286,8 +286,9 @@ do_test where8-3.15 {
     SELECT c FROM t1, t2 WHERE a BETWEEN 1 AND 2 OR a = (
       SELECT sum(e IS NULL) FROM t2 AS inner WHERE t2.d>inner.d
     )
+    ORDER BY c
   }
-} {I II I II I II I II I II I II III I II III I II III I II III I II III 9 0}
+} {I I I I I I I I I I II II II II II II II II II II III III III III III 9 1}
 
 #-----------------------------------------------------------------------
 # The following tests - where8-4.* - verify that adding or removing