Re: [sqlite] Covering index scan optimization

[Roger Binns]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 15/09/12 18:23, Simon Slavin wrote:
> PRAGMA lint_mode=ON

I'm sure there is some ideal to preserve the "Lite" part of the name and a
lint mode would be quite intrusive.  I can imagine a separate compilation
mode (eg another #define), or some mechanism by which you could load a
second "hook" library into SQLite that takes over various bits of
functionality (mostly parsing).

> It might help in the testing suite too.

I doubt it.  Test suites have a lot of code running at boundary conditions
and need to provoke certain configurations and circumstances.  Providing
randomly ordered results back doesn't particularly help anything.  (You'll
note just how much test code had to be altered to keep tests functional
after adding the covering index code.)

Roger



-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAlBVUI0ACgkQmOOfHg372QTHbACfTP/8dfoa0zNbgStAeiMfFfMu
o/sAoIwX+dwIiLk+jmbOgBOQtsX7Eipb
=fNrn
-END PGP SIGNATURE-
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Covering index scan optimization

[Simon Slavin]

On 16 Sep 2012, at 2:16am, Roger Binns  wrote:

> It would be *really* helpful if there was some way to put SQLite into a
> mode by which developers using it can test and improve their own apps.  If
> their app worked in that lint/test mode they would know that the chances
> of changes like this one breaking their app would be tiny.
> 
> For the ordering case, and implicit "ORDER BY random()" could be added to
> every query that doesn't specify an order.

There is already "PRAGMA reverse_unordered_selects;":



perhaps one could add a "PRAGMA reverse_unordered_selects=RANDOM".  But it 
might be interesting to replace it with

PRAGMA lint_mode=ON

or

PRAGMA do_everything_weirdly=ON

for SQLite4 which did all sorts of things in a whacky but still compliant 
manner.  It might help in the testing suite too.

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

Re: [sqlite] Covering index scan optimization

[Roger Binns]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 15/09/12 11:57, Richard Hipp wrote:
> ... and that this change merely exposes their brokenness.  I won't
> dispute that.  Nevertheless, with this changes, those applications will
> stop working.

There is the lint mode request:

  http://www.sqlite.org/src/tktview?name=25e09aa2ab

It would be *really* helpful if there was some way to put SQLite into a
mode by which developers using it can test and improve their own apps.  If
their app worked in that lint/test mode they would know that the chances
of changes like this one breaking their app would be tiny.

For the ordering case, and implicit "ORDER BY random()" could be added to
every query that doesn't specify an order.

(Of course how to deliver such a mode is tricky ...)

Roger
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAlBVKHMACgkQmOOfHg372QQRuwCghe+HEV0pKybWOam2TkDRfxax
LJMAn3afFd0YB9uEWVii2xTTRgFmkPfz
=+tho
-END PGP SIGNATURE-
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Covering index scan optimization

[Simon Slavin]

On 15 Sep 2012, at 7:57pm, Richard Hipp  wrote:

> So my thinking now is that this optimization should not be merged to trunk
> unless it is first disabled by default and only enabled by a compile-time
> or start-time option.

How about for SQLite4 ?

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

Re: [sqlite] Covering index scan optimization

[Elefterios Stamatogiannakis]

On 15/09/12 21:57, Richard Hipp wrote:

So my thinking now is that this optimization should not be merged to trunk
unless it is first disabled by default and only enabled by a compile-time
or start-time option.



IMHO, a pragma that enables/disables it persistently on a DB would be ideal.

Many many thanks for making this a reality, the performance increase 
will be very profound.


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

Re: [sqlite] Covering index scan optimization

[Richard Hipp]

A more complete implementation of fullscan-by-covering-index can be seen
here:

   http://www.sqlite.org/src/info/cfaa7bc128

Many of the changes were the addition of an "ORDER BY rowid" clause to test
queries in the test suite.  For the previous 12 years, SQLite has always
returned content in rowid order if there was no ORDER BY clause and no
index could be used.  But with the fullscan-by-covering-index change, that
is no longer the case.  The "ORDER BY rowid" clause does not actually force
a sort, but it does disable the use of a covering index for the scan.

If the fullscan-by-covering-index change does go into the trunk, I fear it
will break many applications, because I believe many SQLite applications
are probably making the assumption that unindexed queries always return
their results in rowid order.  The documentation clearly states that this
is not necessarily the case, but who ever reads the documentation.  We have
also, for years, provided the reverse_unordered_selects pragma (see
http://www.sqlite.org/pragma.html#pragma_reverse_unordered_selects) which
an application can used to locate places where there are unwarranted
assumptions about the order of the results.  But I doubt many applications
actually use this pragma.

You can well argument that applications that depend on the order of results
when there is no ORDER BY clause are already broken, and that this change
merely exposes their brokenness.  I won't dispute that.  Nevertheless, with
this changes, those applications will stop working.

So my thinking now is that this optimization should not be merged to trunk
unless it is first disabled by default and only enabled by a compile-time
or start-time option.

-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Covering index scan optimization

[Elefterios Stamatogiannakis]

I have a question.

Will the covering index scan optimization also cover the automatically 
created indexes?


So lets say that for a certain part of a query, the optimizer decides to 
create an automatic index. Will the same index be chosen for doing a 
scan (instead of a full table scan) for another part of the query where 
the automatic index may also be useful?


Thanks,

lefteris.

On 15/09/12 18:29, Richard Hipp wrote:

On Fri, Sep 14, 2012 at 5:24 PM, Roger Binns  wrote:


-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1


Is there a chance that the change will go into SQLite mainline?


Not without a copyright release.


And it may require more especially if you are an employee.  See the bottom
section of http://www.sqlite.org/copyright.html

And of course it is more than the few lines of changes - all the test
suites have to be updated to ensure no breakage and 100% coverage.



Furthermore, the change is incomplete.  With the patch shown, EXPLAIN QUERY
PLAN gives an incorrect explanation of what is happening.  And
sqlite3_stmt_status(pStmt,
SQLITE_STMTSTATUS_FULLSCAN_STEP, ...) does not count the full-scan steps
that occur as part of a covering-index scan.  There may be other issues;
these are just the ones I have found so far.



Roger
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAlBToHQACgkQmOOfHg372QR1XgCfZvoXr2uKaVFFDo46sEQZiML6
X3UAn0qWun5ldvSJdGj4SEN/n7dVBd7V
=GQzU
-END PGP SIGNATURE-
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users







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

Re: [sqlite] Covering index scan optimization

[Elefterios Stamatogiannakis]

On 15/09/12 17:03, Simon Slavin wrote:


On 15 Sep 2012, at 12:08pm, Elefterios Stamatogiannakis  
wrote:


What i would really like to have in SQLite concerning OLAP, would be bigger 
pages,


You can set pagesize for a new database using a PRAGMA:



The maximum allowed pagesize is 65536 bytes.  Create a new database file, then 
issue the PRAGMA before any CREATE commands.  If you have an existing database 
and want to change it you have to export the data, make a new database and 
import the data again, but this can all be done in two commands to the shell 
tool.



Yes i know about the page size pragma and i actively use it. What i 
meant to say was that i would like to have even bigger pages than what 
is currently possible.



and internal page compression in a similar manner that column stores do [^]. 
This would greatly alleviate the storage pain of using denormalized DBs which 
is a must for OLAP.


This feature would indeed be suitable for a server-client database engine 
designed to run on multipurpose computers.  But SQLite is designed more in 
embedded machines in a single-processor environment.  For example, my TV 
recorder uses it to list the TV channels and meta-data about its recordings, 
and I have an extremely low-power GPS device which uses it for Positions of 
Interest.  The fact that SQLite turns out to be so useful as an embedded DBMS 
inside, for example, a web browser is just a bonus.  As the documentation says, 
if you need network-savvy client-server stuff, look elsewhere.



Could you explain why you think that compressed pages are suitable for a 
client-server database engine and not for an embedded one ? Because i 
don't see why.


From my point of view, being able to have even smaller databases than 
now, without any major overhead would be most useful for embedded 
purposes where disk and memory (pages could be kept compressed in the 
cache) space are at a premium.


Also considering that the compression i proposed doesn't have anything 
at all to do with using a block compressor on a page, but it concerns 
the way that the rows are stored in a page, there won't be any 
noticeable CPU usage increase.


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

Re: [sqlite] Covering index scan optimization

[Yuriy Kaminskiy]

Simon Slavin wrote:
> On 15 Sep 2012, at 12:08pm, Elefterios Stamatogiannakis  
> wrote:
> 
>> What i would really like to have in SQLite concerning OLAP, would be bigger 
>> pages,
> 
> You can set pagesize for a new database using a PRAGMA:
> 
> 
> 
> The maximum allowed pagesize is 65536 bytes.  Create a new database file, 
> then issue the PRAGMA before any CREATE commands.  If you have an existing 
> database and want to change it you have to export the data, make a new 
> database and import the data again, but this can all be done in two commands 
> to the shell tool.

Hint: look for VACUUM in above page (well, VACUUM is not much different from
export+import pair internally).

>> and internal page compression in a similar manner that column stores do [^]. 
>> This would greatly alleviate the storage pain of using denormalized DBs 
>> which is a must for OLAP.
> 
> This feature would indeed be suitable for a server-client database engine 
> designed to run on multipurpose computers.  But SQLite is designed more in 
> embedded machines in a single-processor environment.  For example, my TV 
> recorder uses it to list the TV channels and meta-data about its recordings, 
> and I have an extremely low-power GPS device which uses it for Positions of 
> Interest.  The fact that SQLite turns out to be so useful as an embedded DBMS 
> inside, for example, a web browser is just a bonus.  As the documentation 
> says, if you need network-savvy client-server stuff, look elsewhere.
> 
> Simon.

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

Re: [sqlite] Covering index scan optimization

[Richard Hipp]

On Fri, Sep 14, 2012 at 5:24 PM, Roger Binns  wrote:

> -BEGIN PGP SIGNED MESSAGE-
> Hash: SHA1
>
> >> Is there a chance that the change will go into SQLite mainline?
> >
> > Not without a copyright release.
>
> And it may require more especially if you are an employee.  See the bottom
> section of http://www.sqlite.org/copyright.html
>
> And of course it is more than the few lines of changes - all the test
> suites have to be updated to ensure no breakage and 100% coverage.
>

Furthermore, the change is incomplete.  With the patch shown, EXPLAIN QUERY
PLAN gives an incorrect explanation of what is happening.  And
sqlite3_stmt_status(pStmt,
SQLITE_STMTSTATUS_FULLSCAN_STEP, ...) does not count the full-scan steps
that occur as part of a covering-index scan.  There may be other issues;
these are just the ones I have found so far.

>
> Roger
> -BEGIN PGP SIGNATURE-
> Version: GnuPG v1.4.11 (GNU/Linux)
>
> iEYEARECAAYFAlBToHQACgkQmOOfHg372QR1XgCfZvoXr2uKaVFFDo46sEQZiML6
> X3UAn0qWun5ldvSJdGj4SEN/n7dVBd7V
> =GQzU
> -END PGP SIGNATURE-
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Covering index scan optimization

[Simon Slavin]

On 15 Sep 2012, at 12:08pm, Elefterios Stamatogiannakis  
wrote:

> What i would really like to have in SQLite concerning OLAP, would be bigger 
> pages,

You can set pagesize for a new database using a PRAGMA:



The maximum allowed pagesize is 65536 bytes.  Create a new database file, then 
issue the PRAGMA before any CREATE commands.  If you have an existing database 
and want to change it you have to export the data, make a new database and 
import the data again, but this can all be done in two commands to the shell 
tool.

> and internal page compression in a similar manner that column stores do [^]. 
> This would greatly alleviate the storage pain of using denormalized DBs which 
> is a must for OLAP.

This feature would indeed be suitable for a server-client database engine 
designed to run on multipurpose computers.  But SQLite is designed more in 
embedded machines in a single-processor environment.  For example, my TV 
recorder uses it to list the TV channels and meta-data about its recordings, 
and I have an extremely low-power GPS device which uses it for Positions of 
Interest.  The fact that SQLite turns out to be so useful as an embedded DBMS 
inside, for example, a web browser is just a bonus.  As the documentation says, 
if you need network-savvy client-server stuff, look elsewhere.

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

Re: [sqlite] Covering index scan optimization

[Elefterios Stamatogiannakis]

On 14/09/12 22:56, Clemens Ladisch wrote:

 But do you have any numbers (which would help deciding whether to accept this 
patch)?



I've run two queries on two different DBs:

- DB1: Size 414M, Count of recs 2999671, the table has 17 Cols
- DB2: Size 1.4G, Count of recs 1975986, the table has 28 Cols

The tables had one of the columns indexed (Column Cidx)

Queries run were:

Tablescan (Ts) query:
  select sum(Cidx) from t;
SCAN TABLE t (~100 rows)

CoveringIndexscan (CIs) query:
  select sum(Cidx) from (select Cidx from t order by Cidx);
SCAN TABLE t USING COVERING INDEX idx_Cidx (~100 rows)
SCAN SUBQUERY 1 (~100 rows)

For each DB, i've run 3 times each query (below i present an average), 
clearing the OS's caches every time.


DB1:
  Ts: ~ 4 sec 100 msec.
  CIs: ~ 2 sec 90 msec

DB2:
  Ts: ~ 4 sec 550 msec.
  CIs: ~ 1 sec 350 msec

Apart from the covering index scans being faster, another interesting 
fact that i've found is that when both table's and index's data are in 
memory (cached), the CIs query is consistently two times slower than Ts.


A rough guess is that SQLite's query execution VM has to do more work 
due to not being able to optimize:


SCAN TABLE t USING COVERING INDEX idx_Cidx (~100 rows)
SCAN SUBQUERY 1 (~100 rows)

to just:

SCAN TABLE t USING COVERING INDEX idx_Cidx (~100 rows)

Regards,

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

Re: [sqlite] Covering index scan optimization

[Elefterios Stamatogiannakis]

On 14/09/12 22:56, Clemens Ladisch wrote:

Elefterios Stamatogiannakis wrote:

On 13/09/12 23:02, Clemens Ladisch wrote:
For my main workload (OLAP) this can make an enormous difference!


OLAP isn't quite the typical SQLite use case.  But do you have any
numbers (which would help deciding whether to accept this patch)?



Concerning the "numbers", i'll run some timings.

Concerning OLAP being the typical SQLite use case. I haven't chosen 
SQLite for OLAP lightly. When the choice was made (some years ago) we 
had benchmarked other DBs too (MySQL, Postgres).


Things may have changed from when we did the benchmarks, but i suspect 
that if we ran the same tests again the final choice would remain the 
same. Some more details concerning the things that we had found follows.


MySQL's query execution engine was very fast for simple selects, counts 
etc. When the queries became more complex, MySQL tended to "explode" due 
to materializing nested queries to the disk or other query optimizer 
stupidities.


Postgres, which i hold dear in my heart, was a lot closer to SQLite's 
behaviour (it also runs single threaded for single OLAP queries). 
Nevertheless it was slower than SQLite for queries involving UDFs and on 
some complex queries it could take many times more to finish a query 
than SQLite.


In the end we didn't care that much about raw performance, but about UDF 
flexibility/speed, and to have a reliable and predictable query 
planner/optimizer.


Concerning the query optimizer, in my opinion and by watching other more 
experienced people than me writing queries. What counts more is not the 
cleverness of the query optimizer but being able to predict what a 
reliable optimizer will do.


There are a number of things that i miss from Postgres e.g. nested 
tables and the new JSON storage in 9.2. But using SQLite's UDF API (via 
exceptional APSW [*] ) i have created workarounds for them in madIS [*]. 
So i don't care that much.


What i would really like to have in SQLite concerning OLAP, would be 
bigger pages, and internal page compression in a similar manner that 
column stores do [^]. This would greatly alleviate the storage pain of 
using denormalized DBs which is a must for OLAP.


In addition, this feature would bring SQLite's engine very close to also 
being able to function as a document store while at the same time 
speeding up its relational processing (due to having smaller DBs on the 
disk).


Kind regards,

lefteris

[*] APSW: http://code.google.com/p/apsw/
madIS: http://code.google.com/p/madis/

[^] Like http://en.wikipedia.org/wiki/RCFile . Another idea would be for 
each column to have a dictionary at the start and then the column's data 
would reference the column's dictionary.

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

Re: [sqlite] Covering index scan optimization

[Roger Binns]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

>> Is there a chance that the change will go into SQLite mainline?
> 
> Not without a copyright release.

And it may require more especially if you are an employee.  See the bottom
section of http://www.sqlite.org/copyright.html

And of course it is more than the few lines of changes - all the test
suites have to be updated to ensure no breakage and 100% coverage.

Roger
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.11 (GNU/Linux)

iEYEARECAAYFAlBToHQACgkQmOOfHg372QR1XgCfZvoXr2uKaVFFDo46sEQZiML6
X3UAn0qWun5ldvSJdGj4SEN/n7dVBd7V
=GQzU
-END PGP SIGNATURE-
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Covering index scan optimization

[Clemens Ladisch]

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

Maybe because it's a special case that nobody has yet bothered to
implement ...

> 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?

Not without a copyright release.

  I dedicate any and all copyright interest in this code and any future
  SQLite contributions to the public domain.  I make this dedication for
  the benefit of the public at large and to the detriment of my heirs
  and successors.  I intend this dedication to be an overt act of
  relinquishment in perpetuity of all present and future rights to this
  code under copyright law.

And now v2 without tabstop damage and with much clarified logic:

--- 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 bIndexOnlyScan = 0;   /* True for full scan over covering index */
 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; jnColumn; j++){
@@ -3142,10 +3143,17 @@
   m &= ~(((Bitmask)1)< For my main workload (OLAP) this can make an enormous difference!

OLAP isn't quite the typical SQLite use case.  But do you have any
numbers (which would help deciding whether to accept this patch)?


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

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; jnColumn; 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

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 (~100 rows)
>
>   explain query plan select c1 from t order by c1;
> SCAN TABLE t USING COVERING INDEX idxtc1 (~100 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; jnColumn; 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

[sqlite] Covering index scan optimization

[Eleytherios Stamatogiannakis]

Hello,

I've just wanted to ask about using covering indexes for scans. A very 
rudimentary test:


create table t (c1,c2, c3, c4);
create index idxtc1 on t(c1);

The simple "select" scans the full table:

  explain query plan select c1 from t;
SCAN TABLE t (~100 rows)

A select with a dummy "order by" uses the covering index:

  explain query plan select c1 from t order by c1;
SCAN TABLE t USING COVERING INDEX idxtc1 (~100 rows)

It seems to me that using a covering index scan would always be faster 
in both cases (fewer disk page reads). Am i wrong? Is there a reason for 
SQLite to not use a covering index for scans?


Thank you in advance,

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