[GNUnet-developers] Re: dropping support for SQlite from GNUnet due to bug? workaround?

[D. Richard Hipp]

On Sun, 2005-08-21 at 14:21 -0700, Christian Grothoff wrote:
> First of all, thanks for the quick response.  You suggested adding an index, 
> however we do have an index on all of the colums.  Als Nils pointed out in a 
> private E-mail to me, the index only works for equality constraints, as in 
> your suggestion:
> 
> >    SELECT * FROM tbl WHERE a=EXPR AND b=EXPR ORDER BY c, d LIMIT 1
> 
> However, our query looks like this:
> 
> SELECT * FROM tbl 
>    WHERE (e > :4 AND p == :5) OR p > :6 
>    ORDER BY p ASC e ASC h ASC 
>    LIMIT 1
> 
> The index is created with:
> 
> CREATE INDEX idx_h ON tbl (h)
> CREATE INDEX idx_p ON tbl (p)
> CREATE INDEX idx_e ON tbl (e)
> 
> Maybe something is wrong with the way we create the index? (should we create 
> one "big" index on h,p,e instead?) 

There is an enormous difference between three separate indices each on
separate fields, and a single index on all three fields.  That fact is
true for all SQL database engines, not just SQLite.  Further more, when
you have a single index with multiple columns, the order of the columns
is critical.  Again, this is true of all SQL database engines (that I
am aware of) not just SQLite.

For the query above, your index should be:

    CREATE INDEX idx1 ON tbl(p,e,h);

The order of the columns in the index should match the order
of the terms in the ORDER BY clause.

For SQLite, the performance of your query might be enhanced
if you code it as shown below.  Unlike all of the previous
advice I have given you, the following trick is SQLite-specific
and will not necessarily work or help on other database engines:

   SELECT * FROM tbl WHERE rowid IN
     (SELECT rowid FROM tbl
      WHERE (e>:4 AND p=:5) OR p>:6
      LIMIT 1)

Depending on your parameters and the data in your table,
this latter query might run in O(N) time whereas your
original seems likely to run in O(NlogN) time.
-- 
D. Richard Hipp <address@hidden>