SQLite

Check-in [a8761a9128]
Login

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

Overview
Comment:Do not do full table scans of unordered indices.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: a8761a9128de945aa4b6196df5ffe64115d66b61
User & Date: drh 2011-04-15 14:46:27.121
References
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: 8d924e1607 user: drh tags: branch-3.7.2)
Context
2011-04-15
16:39
Changes to memory allocator usage tracking to delay the onset of integer overflow. (check-in: 4e33a0eaf8 user: drh tags: trunk)
14:46
Do not do full table scans of unordered indices. (check-in: a8761a9128 user: drh tags: trunk)
14:33
Fix #ifs involving SQLITE_ENABLE_LOCKING_STYLE so that they check the value of that macro and not whether it is defined. (check-in: 8775f159c1 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
︙︙
4234
4235
4236
4237
4238
4239
4240


4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253

        /* 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);
        }








>
>





|








4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255

        /* 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);
        }
︙︙
Changes to test/unordered.test.
︙︙
53
54
55
56
57
58
59



60
61
62
63
64
65

    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)} 0 0 0 {USE TEMP B-TREE FOR GROUP BY}}

    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)}}



  } {
    do_eqp_test 1.$idxmode.$tn $sql $r($idxmode)
  }
}

finish_test








>
>
>







53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

    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)} 0 0 0 {USE TEMP B-TREE FOR GROUP BY}}

    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