/ Check-in [e3fe8400]
Login

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

Overview
Comment:Fix the STAT4 range scan estimates for DESC indexes.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e3fe84005259ef9a6027d25793514cebb2d4e7e0
User & Date: drh 2014-10-08 02:53:25
Context
2014-10-08
11:11
Remove some temporary code in mallocA.test that was accidentally checked in. check-in: dedd15f7 user: dan tags: trunk
02:53
Fix the STAT4 range scan estimates for DESC indexes. check-in: e3fe8400 user: drh tags: trunk
00:08
More intuitive labels on ".wheretrace" output. check-in: adcb3fed user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  2202   2202         }else{
  2203   2203           /* Note: this call could be optimized away - since the same values must 
  2204   2204           ** have been requested when testing key $P in whereEqualScanEst().  */
  2205   2205           whereKeyStats(pParse, p, pRec, 0, a);
  2206   2206           iLower = a[0];
  2207   2207           iUpper = a[0] + a[1];
  2208   2208         }
         2209  +
         2210  +      assert( pLower==0 || (pLower->eOperator & (WO_GT|WO_GE))!=0 );
         2211  +      assert( pUpper==0 || (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
         2212  +      if( p->pKeyInfo && p->pKeyInfo->aSortOrder[nEq] ){
         2213  +        /* The roles of pLower and pUpper are swapped for a DESC index */
         2214  +        SWAP(WhereTerm*, pLower, pUpper);
         2215  +      }
  2209   2216   
  2210   2217         /* If possible, improve on the iLower estimate using ($P:$L). */
  2211   2218         if( pLower ){
  2212   2219           int bOk;                    /* True if value is extracted from pExpr */
  2213   2220           Expr *pExpr = pLower->pExpr->pRight;
  2214         -        assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
  2215   2221           rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
  2216   2222           if( rc==SQLITE_OK && bOk ){
  2217   2223             tRowcnt iNew;
  2218   2224             whereKeyStats(pParse, p, pRec, 0, a);
  2219         -          iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0);
         2225  +          iNew = a[0] + ((pLower->eOperator & (WO_GT|WO_LE)) ? a[1] : 0);
  2220   2226             if( iNew>iLower ) iLower = iNew;
  2221   2227             nOut--;
  2222   2228             pLower = 0;
  2223   2229           }
  2224   2230         }
  2225   2231   
  2226   2232         /* If possible, improve on the iUpper estimate using ($P:$U). */
  2227   2233         if( pUpper ){
  2228   2234           int bOk;                    /* True if value is extracted from pExpr */
  2229   2235           Expr *pExpr = pUpper->pExpr->pRight;
  2230         -        assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
  2231   2236           rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
  2232   2237           if( rc==SQLITE_OK && bOk ){
  2233   2238             tRowcnt iNew;
  2234   2239             whereKeyStats(pParse, p, pRec, 1, a);
  2235         -          iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0);
         2240  +          iNew = a[0] + ((pUpper->eOperator & (WO_GT|WO_LE)) ? a[1] : 0);
  2236   2241             if( iNew<iUpper ) iUpper = iNew;
  2237   2242             nOut--;
  2238   2243             pUpper = 0;
  2239   2244           }
  2240   2245         }
  2241   2246   
  2242   2247         pBuilder->pRec = pRec;

Added test/analyzeE.test.

            1  +# 2014-10-08
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file implements tests for using STAT4 information
           12  +# on a descending index in a range query.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +set ::testprefix analyzeE
           18  +
           19  +ifcapable {!stat4} {
           20  +  finish_test
           21  +  return
           22  +}
           23  +
           24  +# Verify that range queries on an ASCENDING index will use the
           25  +# index only if the range covers only a small fraction of the
           26  +# entries.
           27  +#
           28  +do_execsql_test analyzeE-1.0 {
           29  +  CREATE TABLE t1(a,b);
           30  +  WITH RECURSIVE
           31  +    cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000)
           32  +  INSERT INTO t1(a,b) SELECT x, x FROM cnt;
           33  +  CREATE INDEX t1a ON t1(a);
           34  +  ANALYZE;
           35  +} {}
           36  +do_execsql_test analyzeE-1.1 {
           37  +  EXPLAIN QUERY PLAN
           38  +  SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500;
           39  +} {/SCAN TABLE t1/}
           40  +do_execsql_test analyzeE-1.2 {
           41  +  EXPLAIN QUERY PLAN
           42  +  SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000;
           43  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           44  +do_execsql_test analyzeE-1.3 {
           45  +  EXPLAIN QUERY PLAN
           46  +  SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750;
           47  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           48  +do_execsql_test analyzeE-1.4 {
           49  +  EXPLAIN QUERY PLAN
           50  +  SELECT * FROM t1 WHERE a BETWEEN 1 AND 500
           51  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           52  +do_execsql_test analyzeE-1.5 {
           53  +  EXPLAIN QUERY PLAN
           54  +  SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000
           55  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           56  +do_execsql_test analyzeE-1.6 {
           57  +  EXPLAIN QUERY PLAN
           58  +  SELECT * FROM t1 WHERE a<500
           59  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           60  +do_execsql_test analyzeE-1.7 {
           61  +  EXPLAIN QUERY PLAN
           62  +  SELECT * FROM t1 WHERE a>2500
           63  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           64  +do_execsql_test analyzeE-1.8 {
           65  +  EXPLAIN QUERY PLAN
           66  +  SELECT * FROM t1 WHERE a>1900
           67  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           68  +do_execsql_test analyzeE-1.9 {
           69  +  EXPLAIN QUERY PLAN
           70  +  SELECT * FROM t1 WHERE a>1100
           71  +} {/SCAN TABLE t1/}
           72  +do_execsql_test analyzeE-1.10 {
           73  +  EXPLAIN QUERY PLAN
           74  +  SELECT * FROM t1 WHERE a<1100
           75  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           76  +do_execsql_test analyzeE-1.11 {
           77  +  EXPLAIN QUERY PLAN
           78  +  SELECT * FROM t1 WHERE a<1900
           79  +} {/SCAN TABLE t1/}
           80  +
           81  +# Verify that everything works the same on a DESCENDING index.
           82  +#
           83  +do_execsql_test analyzeE-2.0 {
           84  +  DROP INDEX t1a;
           85  +  CREATE INDEX t1a ON t1(a DESC);
           86  +  ANALYZE;
           87  +} {}
           88  +do_execsql_test analyzeE-2.1 {
           89  +  EXPLAIN QUERY PLAN
           90  +  SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500;
           91  +} {/SCAN TABLE t1/}
           92  +do_execsql_test analyzeE-2.2 {
           93  +  EXPLAIN QUERY PLAN
           94  +  SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000;
           95  +} {/SEARCH TABLE t1 USING INDEX t1a/}
           96  +do_execsql_test analyzeE-2.3 {
           97  +  EXPLAIN QUERY PLAN
           98  +  SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750;
           99  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          100  +do_execsql_test analyzeE-2.4 {
          101  +  EXPLAIN QUERY PLAN
          102  +  SELECT * FROM t1 WHERE a BETWEEN 1 AND 500
          103  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          104  +do_execsql_test analyzeE-2.5 {
          105  +  EXPLAIN QUERY PLAN
          106  +  SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000
          107  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          108  +do_execsql_test analyzeE-2.6 {
          109  +  EXPLAIN QUERY PLAN
          110  +  SELECT * FROM t1 WHERE a<500
          111  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          112  +do_execsql_test analyzeE-2.7 {
          113  +  EXPLAIN QUERY PLAN
          114  +  SELECT * FROM t1 WHERE a>2500
          115  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          116  +do_execsql_test analyzeE-2.8 {
          117  +  EXPLAIN QUERY PLAN
          118  +  SELECT * FROM t1 WHERE a>1900
          119  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          120  +do_execsql_test analyzeE-2.9 {
          121  +  EXPLAIN QUERY PLAN
          122  +  SELECT * FROM t1 WHERE a>1100
          123  +} {/SCAN TABLE t1/}
          124  +do_execsql_test analyzeE-2.10 {
          125  +  EXPLAIN QUERY PLAN
          126  +  SELECT * FROM t1 WHERE a<1100
          127  +} {/SEARCH TABLE t1 USING INDEX t1a/}
          128  +do_execsql_test analyzeE-2.11 {
          129  +  EXPLAIN QUERY PLAN
          130  +  SELECT * FROM t1 WHERE a<1900
          131  +} {/SCAN TABLE t1/}
          132  +
          133  +# Now do a range query on the second term of an ASCENDING index
          134  +# where the first term is constrained by equality.
          135  +#
          136  +do_execsql_test analyzeE-3.0 {
          137  +  DROP TABLE t1;
          138  +  CREATE TABLE t1(a,b,c);
          139  +  WITH RECURSIVE
          140  +    cnt(x) AS (VALUES(1000) UNION ALL SELECT x+1 FROM cnt WHERE x<2000)
          141  +  INSERT INTO t1(a,b,c) SELECT x, x, 123 FROM cnt;
          142  +  CREATE INDEX t1ca ON t1(c,a);
          143  +  ANALYZE;
          144  +} {}
          145  +do_execsql_test analyzeE-3.1 {
          146  +  EXPLAIN QUERY PLAN
          147  +  SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500 AND c=123;
          148  +} {/SCAN TABLE t1/}
          149  +do_execsql_test analyzeE-3.2 {
          150  +  EXPLAIN QUERY PLAN
          151  +  SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000 AND c=123;
          152  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          153  +do_execsql_test analyzeE-3.3 {
          154  +  EXPLAIN QUERY PLAN
          155  +  SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750 AND c=123;
          156  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          157  +do_execsql_test analyzeE-3.4 {
          158  +  EXPLAIN QUERY PLAN
          159  +  SELECT * FROM t1 WHERE a BETWEEN 1 AND 500 AND c=123
          160  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          161  +do_execsql_test analyzeE-3.5 {
          162  +  EXPLAIN QUERY PLAN
          163  +  SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000 AND c=123
          164  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          165  +do_execsql_test analyzeE-3.6 {
          166  +  EXPLAIN QUERY PLAN
          167  +  SELECT * FROM t1 WHERE a<500 AND c=123
          168  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          169  +do_execsql_test analyzeE-3.7 {
          170  +  EXPLAIN QUERY PLAN
          171  +  SELECT * FROM t1 WHERE a>2500 AND c=123
          172  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          173  +do_execsql_test analyzeE-3.8 {
          174  +  EXPLAIN QUERY PLAN
          175  +  SELECT * FROM t1 WHERE a>1900 AND c=123
          176  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          177  +do_execsql_test analyzeE-3.9 {
          178  +  EXPLAIN QUERY PLAN
          179  +  SELECT * FROM t1 WHERE a>1100 AND c=123
          180  +} {/SCAN TABLE t1/}
          181  +do_execsql_test analyzeE-3.10 {
          182  +  EXPLAIN QUERY PLAN
          183  +  SELECT * FROM t1 WHERE a<1100 AND c=123
          184  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          185  +do_execsql_test analyzeE-3.11 {
          186  +  EXPLAIN QUERY PLAN
          187  +  SELECT * FROM t1 WHERE a<1900 AND c=123
          188  +} {/SCAN TABLE t1/}
          189  +
          190  +# Repeat the 3.x tests using a DESCENDING index
          191  +#
          192  +do_execsql_test analyzeE-4.0 {
          193  +  DROP INDEX t1ca;
          194  +  CREATE INDEX t1ca ON t1(c ASC,a DESC);
          195  +  ANALYZE;
          196  +} {}
          197  +do_execsql_test analyzeE-4.1 {
          198  +  EXPLAIN QUERY PLAN
          199  +  SELECT * FROM t1 WHERE a BETWEEN 500 AND 2500 AND c=123;
          200  +} {/SCAN TABLE t1/}
          201  +do_execsql_test analyzeE-4.2 {
          202  +  EXPLAIN QUERY PLAN
          203  +  SELECT * FROM t1 WHERE a BETWEEN 2900 AND 3000 AND c=123;
          204  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          205  +do_execsql_test analyzeE-4.3 {
          206  +  EXPLAIN QUERY PLAN
          207  +  SELECT * FROM t1 WHERE a BETWEEN 1700 AND 1750 AND c=123;
          208  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          209  +do_execsql_test analyzeE-4.4 {
          210  +  EXPLAIN QUERY PLAN
          211  +  SELECT * FROM t1 WHERE a BETWEEN 1 AND 500 AND c=123
          212  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          213  +do_execsql_test analyzeE-4.5 {
          214  +  EXPLAIN QUERY PLAN
          215  +  SELECT * FROM t1 WHERE a BETWEEN 3000 AND 3000000 AND c=123
          216  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          217  +do_execsql_test analyzeE-4.6 {
          218  +  EXPLAIN QUERY PLAN
          219  +  SELECT * FROM t1 WHERE a<500 AND c=123
          220  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          221  +do_execsql_test analyzeE-4.7 {
          222  +  EXPLAIN QUERY PLAN
          223  +  SELECT * FROM t1 WHERE a>2500 AND c=123
          224  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          225  +do_execsql_test analyzeE-4.8 {
          226  +  EXPLAIN QUERY PLAN
          227  +  SELECT * FROM t1 WHERE a>1900 AND c=123
          228  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          229  +do_execsql_test analyzeE-4.9 {
          230  +  EXPLAIN QUERY PLAN
          231  +  SELECT * FROM t1 WHERE a>1100 AND c=123
          232  +} {/SCAN TABLE t1/}
          233  +do_execsql_test analyzeE-4.10 {
          234  +  EXPLAIN QUERY PLAN
          235  +  SELECT * FROM t1 WHERE a<1100 AND c=123
          236  +} {/SEARCH TABLE t1 USING INDEX t1ca/}
          237  +do_execsql_test analyzeE-4.11 {
          238  +  EXPLAIN QUERY PLAN
          239  +  SELECT * FROM t1 WHERE a<1900 AND c=123
          240  +} {/SCAN TABLE t1/}
          241  +
          242  +finish_test