The hidden cost of limit-offset

[孙冰 <subi.the.dream.walker@xxxxxxxxx>]

The skipped rows by an OFFSET clause have to be computed nevertheless. I am wondering if there could be any chance to improve, since the computation is on the entire rows rather than on the criterial columns.

Consider the following example.

Create a sample table and insert some random data.

create table thing (
  id int generated always as identity,
  tag float default random()
);
insert into thing select from generate_series(1,100);

Let's find the last 10 rows ordered by tag:

explain (analyze, verbose)
select id, pg_sleep(0.1) from thing
order by tag offset 90;

The execution plan is:

Limit (cost=5.77..5.92 rows=10 width=16) (actual time=9210.751..10121.411 rows=10 loops=1)
  Output: id, (pg_sleep('0.1'::double precision)), tag
  -> Result (cost=4.42..5.92 rows=100 width=16) (actual time=101.251..10121.344 rows=100 loops=1)
        Output: id, pg_sleep('0.1'::double precision), tag
        -> Sort (cost=4.42..4.67 rows=100 width=12) (actual time=0.064..0.200 rows=100 loops=1)
              Output: id, tag
              Sort Key: thing.tag
              Sort Method: quicksort Memory: 29kB
              -> Seq Scan on public.thing (cost=0.00..1.10 rows=100 width=12) (actual time=0.012..0.019 rows=100 loops=1)
                    Output: id, tag
Planning Time: 0.176 ms
Execution Time: 10121.450 ms

Obviously, all the 100 rows are computed before offsetting & limiting. But something really catches my eye:

1. the 100 rows oftagare necessary becausetagis the sort key;
2. the 100 rows ofidare not all necessary but it is fine sinceidand tagare fetched from the same relation;
3. the 100 rows of pg_sleep(0.1) cause the major performance hit unnecessarily; pg_sleep(0.1) depends on neithertagnorid.

Could we improve the situation? Maybe the Limit node could be done in advance before the Result node for id and pg_sleep(0.1)? The execution plan could be something like:

Result (cost=5.77..5.92 rows=10 width=16)
  Output: id, pg_sleep('0.1'::double precision), tag
  -> Limit (cost=4.42..5.92 rows=10 width=12)
        Output: id, tag
        -> Sort (cost=4.42..4.67 rows=100 width=12)
              Output: id, tag
              Sort Key: thing.tag
              -> Seq Scan on public.thing (cost=0.00..1.10 rows=100 width=12)
                    Output: id, tag

Generally, if the Limit process could be executed immediately after the criterial attributes are computed rather than the full output is evaluated, pagination by limit-offset could be considerably more performant for broad use cases. That is, pagination is done by several keys which is usually static, while a few dynamic but expensive attributes can be computed quite effectively since the result set is typically very small, by its (nested-)loop nature.

I don't understand the postgresql internal, but I suspect such a change may introduce significant work on the planner and executor. From my point view, skipping everything (or expensive ones) except the criteria in the target list would greatly improve the usability of OFFSET, and it is definitely worth the effort.

Best regards.

–

SUN Bing