Prefer using the ORDER BY index if LIMIT is used

[GoogleCodeExporter]

What steps will reproduce the problem?
(simple SQL scripts or simple standalone applications are preferred)
When trying to paging through a resultset that includes selection criteria,
the query performance is extremely slow. Here is an example:

SELECT * FROM table WHERE id > 100 AND status = 100 ORDER BY id LIMIT 10

The query takes multi-second to execute, despite the fact there are indices
on both id and status.

What is the expected output? What do you see instead?
I expected that the pagination would execute within a normal amount of time
on a table with proper indices; instead, the query appears to run in a time
frame more typical of a full table scan, despite the presence of indices on
all selection criteria columns.

What version of the product are you using? On what operating system, file
system, and virtual machine?
H2 1.1.7 on Windows and Mac. The problem does not appear to be
environmentally-specific.

Do you know a workaround?
A workaround is to use negation to selective turn off the use of index on
those columns (e.g. SELECT * FROM tables WHERE id > 100 AND (-status =
-100) ORDER BY id).

How important/urgent is the problem for you?
This problem is somewhat important and urgent, as the query needed is very
difficult to workaround.

In your view, is this a defect or a feature request?
This is a feature request.

Please provide any additional information below.

Original issue reported on code.google.com by peterkwa...@gmail.com on 3 Aug 2009 at 8:50

[GoogleCodeExporter]

Here is the link to a previous group discussion:

http://groups.google.com/group/h2-database/browse_thread/thread/6e1a88a535e54c4a

Please also see the emails and sample database that I sent to the H2 support 
email,
from April to June of 2009, with the subject of "Odd H2 Ordering Performance 
Issue"

Original comment by peterkwa...@gmail.com on 3 Aug 2009 at 8:55

[GoogleCodeExporter]

I made a mistake on the version number. The affected version should be 1.1.113.

Original comment by peterkwa...@gmail.com on 3 Aug 2009 at 9:16

[GoogleCodeExporter]

I agree, the optimizer should be smarter here.
A complete test case:

drop table test;
create table test(id int primary key, status int);
create index idx_status on test(status);
insert into test select x, mod(x, 10) from system_range(1, 10000);
analyze;
explain SELECT * FROM test WHERE id > 100 AND status = 5 ORDER BY id LIMIT 10;

Original comment by thomas.t...@gmail.com on 9 Aug 2009 at 11:06

[GoogleCodeExporter]

I will add this to the feature request list at
http://www.h2database.com/html/roadmap.html where it will be prioritized. 
Currently
it is at 
the bottom of the list, but of more people run into this problem it will move 
higher.

Original comment by thomas.t...@gmail.com on 4 Sep 2009 at 1:59

• Changed title: Prefer using the ORDER BY index if LIMIT is used
• Changed state: InRoadmap

[GoogleCodeExporter]

Good to know that this feature is being added to the roadmap!

When this feature is implemented, would it allow H2 to process this query:

SELECT * FROM test WHERE id > 100 AND status = 5 ORDER BY id LIMIT 10;

more efficiently than:

SELECT * FROM test WHERE id > 100 AND (-status = -5) ORDER BY id LIMIT 10;

which is the current manually-worked-around version?

In other words, would this feature allows H2 to use both the ORDER BY index 
(ORDER BY
id) and the selection index (status = 5) at the same time?

Original comment by peterkwa...@gmail.com on 5 Sep 2009 at 8:05

[GoogleCodeExporter]

When this feature is implemented, would it allow H2 to process this query:
... more efficiently than ...: No, it would be the same.

> In other words, would this feature allows H2 to use both the 
> ORDER BY index (ORDER BY id) and the selection index 
> (status = 5) at the same time?

No, that's not the plan, sorry.

Original comment by thomas.t...@gmail.com on 22 Sep 2009 at 4:26