Re: Large offset optimization and index only scan

On Tue, Nov 19, 2013 at 2:03 AM, Maxim Boguk <maxim.boguk@gmail.com> wrote:
> Case:
> SELECT * FROM very_large_table ORDER BY [some indexed column(s)]  OFFSET
> [some large value] LIMIT N;
>
> Idea:
> Use IOS (index only scan) to skip the first OFFSET values than switch to
> common index scan to fetch LIMIT N values

Interesting.  This is really a variant of an optimization that I
believe to have been originally proposed by Heikki.  His idea was to
have an Index-Only Scan node that would only ever look at the index,
and the have a Heap Fetch node which would bubble up the plan tree to
a higher level.  So, for example, if you were doing something like
this:

SELECT * FROM medium_size_table a, huge_table b WHERE a.x = b.x AND
rarely_true(a.y, b.y)

...you could implement this as:

Heap Fetch On b
-> Nested Loop   -> Seq Scan on a   -> Index-Only Scan on b

That way, we'd apply the filter condition at the nested-loop level,
using some hypothetical index on x and y, before even testing the
visibility of the rows from b (and thus incurring random I/O).  The
reason why nobody implemented this is (1) the planner challenges were
formidable and (b) if rarely_true isn't leakproof, the user (or some
other user) might find it unfortunate that it gets passed tuples not
visible to the current scan.  Thus, we stuck with a design where the
index-only scan always performs the heap fetch if that is needed to
determine visibility.

However, in your example, that wouldn't be the right thing anyway,
because you'd need to know whether the tuples were visible before
performing the limit.  So what you'd really want is to have index-only
scan work about the way it does now, except that if it does end up
fetching the heap tuple to check visibility, it somehow returns that.
If not, it returns only the index tuple, and then a Heap Fetch node
higher up the plan tree can fetch those heap tuples not yet fetched
without re-fetching those we've already got.  That seems complicated
to make work even in the executor, though, and the planning problem
makes my head hurt.  If we can sole those problems it might be neat,
though.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company