Avoid computing ORDER BY junk columns unnecessarily

Problem
-------

We are using junk columns for (at least) two slightly different purposes:

1. For passing row IDs and other such data from lower plan nodes to 
LockRows / ModifyTable.

2. To represent ORDER BY and GROUP BY columns that don't appear in the 
SELECT list. For example, in a query like:

     SELECT foo FROM mytable ORDER BY bar;

The parser adds 'bar' to the target list as a junk column. You can see 
that with EXPLAIN VERBOSE:

explain (verbose, costs off)
   select foo from mytable order by bar;

             QUERY PLAN
----------------------------------
  Sort
    Output: foo, bar
    Sort Key: mytable.bar
    ->  Seq Scan on public.mytable
          Output: foo, bar
(5 rows)

The 'bar' column get filtered away in the executor, by the so-called 
junk filter. That's fine for simple cases like the above, but in some 
cases, that causes the ORDER BY value to be computed unnecessarily. For 
example:

create table mytable (foo text, bar text);
insert into mytable select g, g from generate_series(1, 10000) g;
create index on mytable (sha256(bar::bytea));
explain verbose
  select foo from mytable order by sha256(bar::bytea);

                                            QUERY PLAN 

------------------------------------------------------------------------------------------------
  Index Scan using mytable_sha256_idx on public.mytable 
(cost=0.29..737.28 rows=10000 width=64)
    Output: foo, sha256((bar)::bytea)
(2 rows)

The index is used to satisfy the ORDER BY, but the expensive ORDER BY 
expression is still computed for every row, just to be thrown away by 
the junk filter.

This came up with pgvector, as the vector distance functions are pretty 
expensive. All vector operations are expensive, so one extra distance 
function call per row doesn't necessarily make that much difference, but 
it sure looks silly. See 
https://github.com/pgvector/pgvector/issues/359#issuecomment-1840786021 
(thanks Matthias for the investigation!).

Solution
--------

The obvious solution is that the planner should not include those junk 
columns in the plan. But how exactly to implement that is a different 
matter.

I came up with the attached patch set, which adds a projection to all 
the paths at the end of planning in grouping_planner(). The projection 
filters out the unnecessary junk columns. With that, the plan for the 
above example:

postgres=# explain verbose select foo from mytable order by 
sha256(bar::bytea);
                                           QUERY PLAN 

-----------------------------------------------------------------------------------------------
  Index Scan using mytable_sha256_idx on public.mytable 
(cost=0.29..662.24 rows=10000 width=4)
    Output: foo
(2 rows)


Problems with the solution
--------------------------

So this seems to work, but I have a few doubts:

1. Because Sort cannot project, this adds an extra Result node on top of 
Sort nodes when the the ORDER BY is implemented by sorting:

postgres=# explain verbose select foo from mytable order by bar;
                                    QUERY PLAN 

--------------------------------------------------------------------------------
  Result  (cost=818.39..843.39 rows=10000 width=4)
    Output: foo
    ->  Sort  (cost=818.39..843.39 rows=10000 width=8)
          Output: foo, bar
          Sort Key: mytable.bar
          ->  Seq Scan on public.mytable  (cost=0.00..154.00 rows=10000 
width=8)
                Output: foo, bar
(7 rows)

 From a performance point of view, I think that's not as bad as it 
sounds. Remember that without this patch, the executor needs to execute 
the junk filter to filter out the extra column instead. It's not clear 
that an extra Result is worse than that, although I haven't tried 
benchmarking it though.

This makes plans for queries like above more verbose though. Perhaps we 
should teach Sort (and MergeAppend) to do projection, just to avoid that?

Another solution would be to continue relying on the junk filter, if 
adding the projection in the planner leads to an extra Result node. 
That's a bit ugly, because then the final target list of a (sub)query 
depends on the Path that's chosen.

2. Instead of tacking on the projection to the paths at the end, I first 
tried modifying the code earlier in grouping_planner() that computes the 
target lists for the different plan stages. That still feels like a 
cleaner approach to me, although I don't think there's any difference in 
the generated plans in practice. However I ran into some problems with 
that approach and gave up.

I basically tried to remove the junk columns from 'final_target', and 
have create_ordered_paths() create paths with the filtered target list 
directly. And if there is no ORDER BY, leave out the junk columns from 
'grouping_target' too, and have create_grouping_paths() generate the 
final target list directly. However, create_grouping_paths() assumes 
that the grouping columns are included in 'grouping_target'. And 
similarly in create_ordered_paths(), some partial planning stages assume 
that the ordering columns are included in 'final_target'. Those 
assumptions could probably be fixed, but I ran out of steam trying to do 
that.

3. I also considered if we should stop using junk columns to represent 
ORDER BY / GROUP BY columns like this in the first place. Perhaps we 
should have a separate list for those and not stash them in the target 
list. But that seems like a much bigger change.

4. It would be nice to get rid of the junk filter in the executor 
altogether. With this patch, the junk columns used for RowLocks and 
ModifyTable are still included in the final target list, and are still 
filtered out by the junk filter. But we could add similar projections 
between the RowLocks and ModifyTable stages, to eliminate all the junk 
columns at the top of the plan. ExecFilterJunk() isn't a lot of code, 
but it would feel cleaner to me. I didn't try to implement that.

5. I'm not sure the categorization of junk columns that I implemented 
here is the best one. It might make sense to have more categories, and 
distinguish row-id columns from others for example. And ORDER BY columns 
from GROUP BY columns.

Patches
-------

So the attached patches implement that idea, with the above-mentioned 
problems. I think this approach is fine as it is, despite those 
problems, but my planner-fu is a rusty so I really need review and a 
second opinion on this.

v1-0001-Add-test-for-Min-Max-optimization-with-kNN-index-.patch
v1-0002-Show-how-ORDER-BY-expression-is-computed-unnecess.patch

These patches just add to existing tests to demonstrate the problem.

v1-0003-Turn-resjunk-into-an-enum.patch

Replace 'resjunk' boolean with an enum, so that we can distinguish 
between different junk columns. The next patch uses that information to 
identify junk columns that can be filtered out. It's is a separate patch 
for easier review.

v1-0004-Omit-columns-from-final-tlist-that-were-only-need.patch

The main patch in this series.

v1-0005-Fix-regression-tests-caused-by-additional-Result-.patch

Regression test output changes, for all the plans with Sort that now 
have Sort + Result. See "Problem with the solution" #1.

-- 
Heikki Linnakangas
Neon (https://neon.tech)