Re: [sqlite] Covering index scan optimization

[Clemens Ladisch]

Eleytherios Stamatogiannakis wrote:
> create table t (c1,c2, c3, c4);
> create index idxtc1 on t(c1);
>
>   explain query plan select c1 from t;
>     SCAN TABLE t (~1000000 rows)
>
>   explain query plan select c1 from t order by c1;
>     SCAN TABLE t USING COVERING INDEX idxtc1 (~1000000 rows)
>
> It seems to me that using a covering index scan would always be faster
> in both cases (fewer disk page reads).

Yes, if the index has fewer columns than the table.

> Is there a reason for SQLite to not use a covering index for scans?

The query optimizer does not allow indexes that are not needed for some
DISTINCT, WHERE, or ORDER BY clause:

  select c1 from t indexed by idxtc1;
  Error: cannot use index: idxtc1

However, it doesn't appear to be too difficult to allow this case:

--- src/where.c
+++ src/where.c
@@ -3037,6 +3037,7 @@
     int bSort = !!pOrderBy;       /* True if external sort required */
     int bDist = !!pDistinct;      /* True if index cannot help with DISTINCT */
     int bLookup = 0;              /* True if not a covering index */
+    int bFullCovIdxScan = 0;      /* True if full covering index scan */
     WhereTerm *pTerm;             /* A single term of the WHERE clause */
 #ifdef SQLITE_ENABLE_STAT3
     WhereTerm *pFirstTerm = 0;    /* First term matching the index */
@@ -3133,7 +3134,7 @@
     ** using the main table (i.e. if the index is a covering
     ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
     ** wsFlags. Otherwise, set the bLookup variable to true.  */
-    if( pIdx && wsFlags ){
+    if( pIdx ){
       Bitmask m = pSrc->colUsed;
       int j;
       for(j=0; j<pIdx->nColumn; j++){
@@ -3143,9 +3144,16 @@
         }
       }
       if( m==0 ){
-        wsFlags |= WHERE_IDX_ONLY;
+        if( wsFlags ){
+          wsFlags |= WHERE_IDX_ONLY;
+       }else{
+          wsFlags = WHERE_COLUMN_RANGE|WHERE_IDX_ONLY;
+          bFullCovIdxScan = 1;
+       }
       }else{
-        bLookup = 1;
+        if( wsFlags ){
+          bLookup = 1;
+       }
       }
     }

@@ -3209,6 +3217,8 @@
       ** it seems to be working well enough at the moment.
       */
       cost = aiRowEst[0]*4;
+    }else if(bFullCovIdxScan){
+      cost = aiRowEst[0]*2;
     }else{
       log10N = estLog(aiRowEst[0]);
       cost = nRow;


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users