Bad planner decision in Postgres

Good afternoon. I think I may have found a bad planner decision in
Postgres. In essence, I have a table that is well-sorted, and has an index
on the sort column. I wish to retrieve all rows from the table that have a
column value greater than X, or some other condition (which is also
indexed and won't return many rows - I'm using "(column IS NULL)" for my
application).

So I run the query:

SELECT * FROM table WHERE column > 42 OR column IS NULL;

The table "table" is completely sorted on the column "column", and there
is a b-tree index on column and an index on "((column IS NULL))". Firstly,
I have to alter the query in order for the second index to be used:

SELECT * FROM table WHERE column > 42 OR (column IS NULL) = true;

Let us say that the values of column range from zero to 50, and they are
reasonably evenly spread, and there are a few thousand rows. Let us also
say that we only require the first ten rows of the results:

SELECT * FROM table WHERE column > 42 OR (column IS NULL) = true LIMIT 10;

The resulting query plan goes as follows:

Limit (cost=0.00..17.74 rows=10 width=14)
-> Index Scan using index_a on table (cost=0.00..264.38 rows=149 width=14)
Filter: ((column > 42) OR ((column IS NULL) = true))

If we remove the limit, then the planner switches to this query plan:

Limit (cost=156.24..156.26 rows=10 width=14)
-> Sort (cost=156.04..156.41 rows=149 width=14)
Sort Key: column
-> Index Scan using index_a, index_b on table (cost=0.00..150.66 rows=149 width=14)
Index Cond: ((column > 42) OR ((column IS NULL) = true))

However, this is quicker than the plan used when the LIMIT is set!

The first query plan performs a full sequential scan of the entire table,
using the b-tree index to scan it in ascending order of column. It filters
these rows with the predicate of the query, and returns the rows to the
user on a stream, which can be cut short by the LIMIT operation.

The second query fetches the rows that are relevant from the indexes,
sorts the lot, and presents them in bulk to the user.

The fallacy of the query planner in the first plan is assuming that the
rows that will pass the filter are scattered randomly across the stream of
rows returned by the index scan. It therefore assumes that it will receive
ten rows very quickly. However, the actual case is that all the rows that
will pass the filter are right at the end of the stream generated by the
index scan, so it will not return any rows until the whole index scan is
almost complete. This could be a big problem with large tables.

I'm not entirely sure how much work it would be to make the planner notice
this kind of arrangement. Noticing "column > 42" would undoubtedly be
easy, but noticing "column IS NULL" or even "(column IS NULL) = true" may
not. In any case, it may make it easier if the index for nulls could match
against the "column IS NULL" predicate in the query, so one would not need
to use "(column IS NULL) = true", which may make it easier for the planner
to notice that the predicate affects what portion of the index scan stream
will pass the filter.

In any case, the perfect solution for my particular application would be a
"sorts after X" predicate, so I could rewrite the query:

SELECT * FROM table WHERE column <sorts after> 42;

I don't know what sort of faff implementing such a predicate would
involve, and how many feathers would be ruffled by it. However it would
make it much easier for the planner to just magically make it work without
requiring the extra index to cope with nulls.

Anyway, I hope that was interesting.

Matthew

--
Picard: I was just paid a visit from Q.
Riker: Q! Any idea what he's up to?
Picard: No. He said he wanted to be "nice" to me.
Riker: I'll alert the crew.