/ Check-in [8d924e16]
Login

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

Overview
Comment:Backport check-in [9f9f32882501ac9] to provide EXPLAIN QUERY PLAN output for the count(*) optimization. Also backport check-in [a8761a9128de945aa] to prevent unordered indices from being used on a full table scan. The first backport was necessary in order to test the second.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | branch-3.7.2
Files: files | file ages | folders
SHA1:8d924e160703e02958db9c9bc1fd2c600e01e606
User & Date: drh 2011-04-15 15:18:34
Context
2011-05-01
22:57
Backport check-ins [0900e35348f4b9bf3] and [4fead8e714c7e50] to the 3.7.2 branch. These check-ins provide hints to the btree layer for when it is possible to use a hash table rather than a btree to implement an index. The SQLite BTree layer does not use these hints, but alternative btree layers might. check-in: 7155e6f3 user: drh tags: branch-3.7.2
2011-04-15
15:18
Backport check-in [9f9f32882501ac9] to provide EXPLAIN QUERY PLAN output for the count(*) optimization. Also backport check-in [a8761a9128de945aa] to prevent unordered indices from being used on a full table scan. The first backport was necessary in order to test the second. check-in: 8d924e16 user: drh tags: branch-3.7.2
2011-04-09
03:30
Back port the unordered-index-hack to the 3.7.2 branch. check-in: 80353020 user: drh tags: branch-3.7.2
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

3529
3530
3531
3532
3533
3534
3535


























3536
3537
3538
3539
3540
3541
3542
....
4108
4109
4110
4111
4112
4113
4114


4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
....
4129
4130
4131
4132
4133
4134
4135

4136
4137
4138
4139
4140
4141
4142
  for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){
    sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);
  }
  pAggInfo->directMode = 0;
  sqlite3ExprCacheClear(pParse);
}



























/*
** Generate code for the SELECT statement given in the p argument.  
**
** The results are distributed in various ways depending on the
** contents of the SelectDest structure pointed to by argument pDest
** as follows:
**
................................................................................
        /* Search for the index that has the least amount of columns. If
        ** there is such an index, and it has less columns than the table
        ** does, then we can assume that it consumes less space on disk and
        ** will therefore be cheaper to scan to determine the query result.
        ** In this case set iRoot to the root page number of the index b-tree
        ** and pKeyInfo to the KeyInfo structure required to navigate the
        ** index.


        **
        ** In practice the KeyInfo structure will not be used. It is only 
        ** passed to keep OP_OpenRead happy.
        */
        for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
          if( !pBest || pIdx->nColumn<pBest->nColumn ){
            pBest = pIdx;
          }
        }
        if( pBest && pBest->nColumn<pTab->nCol ){
          iRoot = pBest->tnum;
          pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest);
        }
................................................................................
        /* Open a read-only cursor, execute the OP_Count, close the cursor. */
        sqlite3VdbeAddOp3(v, OP_OpenRead, iCsr, iRoot, iDb);
        if( pKeyInfo ){
          sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO_HANDOFF);
        }
        sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);
        sqlite3VdbeAddOp1(v, OP_Close, iCsr);

      }else
#endif /* SQLITE_OMIT_BTREECOUNT */
      {
        /* Check if the query is of one of the following forms:
        **
        **   SELECT min(x) FROM ...
        **   SELECT max(x) FROM ...







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







 







>
>





|







 







>







3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
....
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
....
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
  for(i=0, pC=pAggInfo->aCol; i<pAggInfo->nAccumulator; i++, pC++){
    sqlite3ExprCode(pParse, pC->pExpr, pC->iMem);
  }
  pAggInfo->directMode = 0;
  sqlite3ExprCacheClear(pParse);
}

/*
** Add a single OP_Explain instruction to the VDBE to explain a simple
** count(*) query ("SELECT count(*) FROM pTab").
*/
#ifndef SQLITE_OMIT_EXPLAIN
static void explainSimpleCount(
  Parse *pParse,                  /* Parse context */
  Table *pTab,                    /* Table being queried */
  Index *pIdx                     /* Index used to optimize scan, or NULL */
){
  if( pParse->explain==2 ){
    char *zEqp = sqlite3MPrintf(pParse->db, "SCAN TABLE %s %s%s(~%d rows)",
        pTab->zName, 
        pIdx ? "USING COVERING INDEX " : "",
        pIdx ? pIdx->zName : "",
        pTab->nRowEst
    );
    sqlite3VdbeAddOp4(
        pParse->pVdbe, OP_Explain, pParse->iSelectId, 0, 0, zEqp, P4_DYNAMIC
    );
  }
}
#else
# define explainSimpleCount(a,b,c)
#endif

/*
** Generate code for the SELECT statement given in the p argument.  
**
** The results are distributed in various ways depending on the
** contents of the SelectDest structure pointed to by argument pDest
** as follows:
**
................................................................................
        /* Search for the index that has the least amount of columns. If
        ** there is such an index, and it has less columns than the table
        ** does, then we can assume that it consumes less space on disk and
        ** will therefore be cheaper to scan to determine the query result.
        ** In this case set iRoot to the root page number of the index b-tree
        ** and pKeyInfo to the KeyInfo structure required to navigate the
        ** index.
        **
        ** (2011-04-15) Do not do a full scan of an unordered index.
        **
        ** In practice the KeyInfo structure will not be used. It is only 
        ** passed to keep OP_OpenRead happy.
        */
        for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
          if( pIdx->bUnordered==0 && (!pBest || pIdx->nColumn<pBest->nColumn) ){
            pBest = pIdx;
          }
        }
        if( pBest && pBest->nColumn<pTab->nCol ){
          iRoot = pBest->tnum;
          pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest);
        }
................................................................................
        /* Open a read-only cursor, execute the OP_Count, close the cursor. */
        sqlite3VdbeAddOp3(v, OP_OpenRead, iCsr, iRoot, iDb);
        if( pKeyInfo ){
          sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO_HANDOFF);
        }
        sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);
        sqlite3VdbeAddOp1(v, OP_Close, iCsr);
        explainSimpleCount(pParse, pTab, pBest);
      }else
#endif /* SQLITE_OMIT_BTREECOUNT */
      {
        /* Check if the query is of one of the following forms:
        **
        **   SELECT min(x) FROM ...
        **   SELECT max(x) FROM ...

Added test/unordered.test.







































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# 2011 April 9
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

set testprefix unordered

do_execsql_test 1.0 {
  CREATE TABLE t1(a, b);
  CREATE INDEX i1 ON t1(a);
  INSERT INTO t1 VALUES(1, 'xxx');
  INSERT INTO t1 SELECT a+1, b FROM t1;
  INSERT INTO t1 SELECT a+2, b FROM t1;
  INSERT INTO t1 SELECT a+4, b FROM t1;
  INSERT INTO t1 SELECT a+8, b FROM t1;
  INSERT INTO t1 SELECT a+16, b FROM t1;
  INSERT INTO t1 SELECT a+32, b FROM t1;
  INSERT INTO t1 SELECT a+64, b FROM t1;
  ANALYZE;
} {}

foreach idxmode {ordered unordered} {
  if {$idxmode == "unordered"} {
    execsql { UPDATE sqlite_stat1 SET stat = stat || ' unordered' }
    db close
    sqlite3 db test.db
  }
  foreach {tn sql r(ordered) r(unordered)} {
    1   "SELECT * FROM t1 ORDER BY a"
        {0 0 0 {SCAN TABLE t1 USING INDEX i1 (~128 rows)}}
        {0 0 0 {SCAN TABLE t1 (~128 rows)}}
    2   "SELECT * FROM t1 WHERE a >?"
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?) (~32 rows)}}
        {0 0 0 {SCAN TABLE t1 (~42 rows)}}
    3   "SELECT * FROM t1 WHERE a = ? ORDER BY rowid"
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?) (~1 rows)}}
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?) (~1 rows)}}
    4   "SELECT max(a) FROM t1"
        {0 0 0 {SEARCH TABLE t1 USING COVERING INDEX i1 (~1 rows)}}
        {0 0 0 {SEARCH TABLE t1 (~1 rows)}}
    5   "SELECT group_concat(b) FROM t1 GROUP BY a"
        {0 0 0 {SCAN TABLE t1 USING INDEX i1 (~128 rows)}}
        {0 0 0 {SCAN TABLE t1 (~128 rows)}}

    6   "SELECT * FROM t1 WHERE a = ?"
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?) (~1 rows)}}
        {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?) (~1 rows)}}
    7   "SELECT count(*) FROM t1"
        {0 0 0 {SCAN TABLE t1 USING COVERING INDEX i1(~128 rows)}}
        {0 0 0 {SCAN TABLE t1 (~128 rows)}}
  } {
    do_eqp_test 1.$idxmode.$tn $sql $r($idxmode)
  }
}

finish_test