Subject: Re: Unfortunate pushing down of expressions below sort

From: Chengpeng Yan <[email-masked]>
Date: Fri, 6 Feb 2026 14:37:59 +0000

Hi,

I took a closer look at make_sort_input_target() in
src/backend/optimizer/plan/planner.c.

The current heuristics only defer targetlist expressions past a Sort
when they are: 
* volatile, or 
* set-returning (due to SRF synchronization constraints), or 
* considered “expensive” (cost > 10 * cpu_operator_cost) and there is a
LIMIT.

Functions like repeat() and acldefault() have the default procost = 1,
so they don’t meet the “expensive” threshold and therefore remain below
the Sort, which is what leads to the tuple width inflation seen in these
examples.

Grouping behaves differently: make_group_input_target() unconditionally
flattens non-grouping expressions to Vars, which is why repeat() ends up
above the Aggregate node there.

Tom mentioned the md5(widecol) counterexample, where evaluating the
expression before the sort can actually reduce memory usage. The key
distinction seems to be whether the expression depends solely on sort
keys.

The approach I’m experimenting with is to defer an expression only when
all the Vars it depends on are sort keys. That gives the desired
behavior in both cases: 
* repeat(i, 1000) ORDER BY i: i is the sort key, so we defer and keep
the sort tuples narrow. 
* md5(widecol) ORDER BY id: widecol is not a sort key, so we keep the
expression below the sort and avoid carrying the wide column.

This seems to address the cases discussed in this thread and should be
low-risk for the common case.

I’m working on a patch along these lines; any thoughts?

--
Best regards,
Chengpeng Yan

---

From: Chengpeng Yan <[email-masked]>
Date: Sat, 7 Feb 2026 12:46:15 +0000

Hi,

Following up on the discussion below, I now have a patch.

The patch extends make_sort_input_target() with a conservative rule:
defer additional non-sort targetlist expressions past Sort only when
doing so does not require carrying any additional Vars/PlaceHolderVars
through Sort. This way, Sort input width never increases.

This still allows cases like repeat(i::text, ...) ORDER BY i to be
projected above Sort, while avoiding the md5(widecol) counterexample
mentioned earlier, since such expressions are not deferred when they
would force a wide non-sort column through Sort.

One limitation remains: this can't help queries like
'SELECT repeat(i::text, ...) FROM t ORDER BY othercols;'
where the output expression depends on Vars that are not sort keys. In
that case we still have to carry i through the Sort to be able to
compute the final targetlist, so the patch cannot avoid inflating Sort's
input width (and may still evaluate repeat() before Sort, depending on
the existing projection placement rules).

The existing volatile/SRF/expensive behavior is unchanged (expensive
exprs are still postponed once a post-sort projection is needed).

I also added regression coverage (including an md5(widecol)-style case).
Some existing EXPLAIN outputs (e.g. join/groupingsets) now show a Result
above Sort, which is expected from postponing additional non-sort
outputs.

Patch attached. Comments welcome.

--
Best regards,
Chengpeng Yan

---

From: Tom Lane <[email-masked]>
Date: Tue, 07 Apr 2026 16:16:54 -0400

> through Sort. This way, Sort input width never increases.

I spent some time thinking about this.

One thing I think we need to keep in mind is that if we don't postpone
an expression past Sort, and the user doesn't like that, she can
easily rewrite the query to force it; as indeed Andres demonstrated
at the start of this thread.  But overriding an unwanted planner
decision to postpone is harder.  I think you can do it with

SELECT * FROM (SELECT x,y,f(z) FROM ... OFFSET 0) ORDER BY whatever;

but if you forget the OFFSET-0 optimization fence you may find
f(z) getting evaluated after the sort anyway.  And the fence might
foreclose some other optimization you did want.

Also, make_sort_input_target() has gone basically unchanged since
2016, without that many complaints.  So I think we need to be pretty
conservative about adding postponement choices that aren't forced by
semantic requirements.

The rule stated above seems pretty conservative, but either it's not
conservative enough or you didn't implement it right, because the
regression test changes show the v2 patch is very willing to create
Result nodes where there were none before, even when there's no LIMIT
and thus no reason to think we can save any expression evaluations.
That extra plan node has nonzero cost that I don't think you're
accounting for.  It'll still be a win if enough data volume is removed
from the Sort step, but I don't see any consideration of how much
we're actually saving before deciding to add the projection step.

So I think we need some sort of gating rule, whereby we only postpone
these expressions if (a) there was already a reason to add a
projection or (b) we can make some cost-based or at least heuristic
estimate that says we'll cut the sort data volume significantly.
Maybe (b) needs to interact with the existing heuristic about
postponing expensive expressions, not sure.

Independently of that, I don't especially like the changes in
make_sort_input_target().  They seem rather inelegant and expensive
(and underdocumented), as well as duplicative of other work already
being done in the function.  It may be time to tackle the unfinished
work mentioned in the existing comments about avoiding redundant
cost/width calculations ...

			regards, tom lane

---

From: Andres Freund <[email-masked]>
Date: Tue, 7 Apr 2026 17:01:43 -0400

Hi,

> we're actually saving before deciding to add the projection step.

A different way (compared to the heuristics you were subsequently talking
about) to deal with that could be to add projection support to sort's output,
I guess. That would have a considerably smaller cost than a separate node.

It'd add a tiny bit of cost (an if checking for projection) for the rather
common of a sort without a projection.  Although that'd not be too hard to get
rid of by generating specialized ExecSort() variants for the different cases,
like now done for ExecSeqScan, if it turned out to matter.

However it'd probably would still not be guaranteed faster than evaluating
below the sort, due to
a) startup cost of the projection machinery
b) potentially needing to deform during the expression's inputs during the
   projection in the sort (or above)

I don't know if there are realistic cases where b) matters?  You'd have to
have nodes above the sort that would require the projection to happen at the
sort (or an intermediary level) but then filter out most rows to avoid needing
to deform anyway?  In all the realistic cases I can think of the expression
evaluation should then be pulled up above that filtering out of rows?

I don't know if a) is really ever significant enough to matter compared to the
cost of sorting. It sure shows up in a sequential scan, but that has an order
of magnitude or three lower per tuple cost.

Are there cases where something like Chengpeng's logic would still trigger a
result node being injected, if sort had projection capability?

> estimate that says we'll cut the sort data volume significantly.

This reminds me: The heuristics around the cost of expression evaluation seem
like they could be improved a fair bit by taking into account the cost of
having to deform the input columns.  There's a huge difference between

  func1(col1), func2(col1)
and
  func1(col1), func2(col2)
and
  func1(col30)

Unless func* are particularly expensive, the cost will be increasingly
dominated by tuple deforming.

I think this is one thing that sometimes contributes to us wrongly choosing
sequential scans with a qual over an index scans that needs to evaluate far
fewer rows, because we just take the operator costs into account, not the
tuple deforming it requires.

Greetings,

Andres Freund