[RFC PATCH] Cost-based delayed projection for ORDER BY ... LIMIT

Hi,

While testing a query of the following form, I noticed that several individually cheap target expressions were evaluated for every input row, even though only one row survived the top-N sort:

SELECT a,
a / (a * -1),
a::numeric AS b,
abs(a::numeric) / 12345.345632
FROM t
ORDER BY a
LIMIT 1;

With one million rows, rewriting it manually so that the non-sort expressions are evaluated after the top-N operation:

SELECT s.a,
s.a / (s.a * -1),
s.a::numeric AS b,
abs(s.a::numeric) / 12345.345632
FROM (
SELECT a
FROM t
ORDER BY a
LIMIT 1
) AS s
ORDER BY s.a;

made a large difference. On my first test system, current master took about 95 ms for the original query, while the manually delayed version took about 15 ms.

I looked at make_sort_input_target() and found that PostgreSQL already postpones an expression when its individual cost is greater than:

10 * cpu_operator_cost

and a LIMIT or tuple fraction makes postponing useful. However, this does not consider a target list containing several expressions that are cheap individually but expensive in aggregate.

For a top-N query, I think there are three relevant factors:

the total per-tuple cost of postponable target expressions;
the estimated number of input rows;
the number of rows that need to survive the Sort, including OFFSET.

The attached POC therefore also postpones individually cheap expressions when:

total_expression_cost * (input_rows - limit_tuples)
>
10 * cpu_operator_cost * limit_tuples

This roughly compares the expression work avoided on discarded rows with a conservative threshold proportional to the rows that survive the Sort.

The factor of 10 is retained from the existing per-expression heuristic. I do not intend to claim that it is the best factor; this is one of the parts on which I would particularly appreciate feedback.

For parallel plans, simply postponing the target expressions was not enough, because apply_projection_to_path() could push the projection below Gather or Gather Merge. The POC keeps projections selected by the new rule on the non-partial path, so that they are evaluated by the leader rather than independently for each worker's top-N candidates.

I wrote a small benchmark extension to compare the three query forms, verify their results, and record the automatic plan shape. It compares three strategies:

auto

The normal query, allowing the planner to choose the projection position.

manual-late

A subquery that performs ORDER BY/LIMIT before evaluating the target expressions, with the required ordering also specified by the outer query.

forced-early

A query that adds the deterministic projected expressions as secondary sort keys. This forces them below Sort while preserving the same serial or parallel Sort/Gather Merge topology. The benchmark data uses a unique leading key, and the added expressions are deterministic functions of that key.

Before timing, the benchmark uses EXCEPT ALL in both directions to verify that the three strategies return equivalent multisets. It then runs them in rotating order to reduce cache-order bias and reports the minimum execution time from repeated runs. The test matrix varies LIMIT selectivity, the number of expressions, the declared per-expression cost, and whether parallel query is enabled.

Here are selected results from an Intel Core i5-13500H system with 32 GB LPDDR5. Times are executor times in milliseconds reported by EXPLAIN ANALYZE with TIMING disabled.

case master auto patched auto speedup
serial, 4 x COST 1, LIMIT 1 103.189 33.299 3.10x
serial, 4 x COST 1, LIMIT 1% 107.690 36.228 2.97x
serial, 4 x COST 1, LIMIT 10% 180.063 67.149 2.68x
serial, 4 x COST 1, LIMIT 25% 184.370 80.680 2.29x
serial, 8 x COST 1, LIMIT 10% 244.155 86.155 2.83x
serial, 16 x COST 1, LIMIT 10% 358.287 74.293 4.82x
parallel, 4 x COST 1, LIMIT 1 45.060 15.700 2.87x
parallel, 4 x COST 1, LIMIT 1% 49.642 19.240 2.58x
numeric example above 95.162 17.142 5.55x

The speedup column is master auto time divided by patched auto time.

For the numeric example, the three strategies behaved as follows:

auto manual-late forced-early
master 95.162 15.294 96.118
patched 17.142 17.130 108.338

In this case, master auto was close to forced-early, while patched auto was close to manual-late.

I also repeated the patched benchmark on a second system, an Intel Core i9-12900H with 64 GB DDR5. The absolute times were different, but the relative results were similar:

case first system second system
serial, 4 x COST 1, LIMIT 1 3.07x 2.72x
serial, 4 x COST 1, LIMIT 1% 2.90x 3.02x
serial, 4 x COST 1, LIMIT 25% 2.32x 2.30x
serial, 4 x COST 1, LIMIT 50% 1.97x 1.91x
parallel, 4 x COST 1, LIMIT 1 2.91x 2.59x
parallel, 4 x COST 1, LIMIT 25% 1.29x 1.24x
numeric example 6.32x 6.89x

These values are forced-early time divided by manual-late time.

The POC is deliberately conservative and still chooses early projection in some cases where manual-late happens to be faster in this benchmark. For example, four COST 1 expressions with a 50% LIMIT remain early. The actual CPU work performed by the synthetic functions is only approximately related to their declared procost, so I do not think these cases alone establish a better threshold.

I am mainly interested in feedback on the approach:

Is aggregate target expression cost the right quantity to consider?
Is comparing avoided expression work on discarded rows against work on surviving rows a reasonable model?
Are current_rel->rows and root->limit_tuples appropriate estimates at this point in grouping_planner()?
Should a projection selected this way stay above Gather/Gather Merge, or are there cases where evaluating it in workers would be preferable?
Should this eventually be represented as competing paths and decided by ordinary path costing instead of another heuristic in make_sort_input_target()?
Is retaining the existing factor of 10 a reasonable conservative starting point?

The attached patch is intended as a POC for design discussion, not yet as a commit-ready patch. I have also attached the benchmark extension; selected results from the tested builds are included above.

I have not registered this in a CommitFest, since I would first like to get feedback on the costing and parallel-placement approach.

Thanks,
ChenHui Mo