Re: [sqlite] Covering index scan optimization

[Elefterios Stamatogiannakis]

On 13/09/12 23:02, Clemens Ladisch wrote:
Eleytherios Stamatogiannakis wrote:
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.


In my experience, the most frequent case is for an index to have less 
columns than the table it indexes.

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:

Do you know if there is a reason for this?


   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;



Thank you for the patch!! With a three line change you replicated the 
new index-only scan feature of PostgreSQL 9.2!

Is there a chance that the change will go into SQLite mainline? For my 
main workload (OLAP) this can make an enormous difference!

Thanks again.

lefteris.

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