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
0001-Consider-aggregate-target-cost-for-top-N-sorts.patch
Description: Binary data
benchmark.sql
Description: Binary data
Makefile
Description: Binary data
README.md
Description: Binary data
topnbench.c
Description: Binary data
topnbench.control
Description: Binary data
topnbench--1.0.sql
Description: Binary data
