Resjunk sort columns, Heikki's index-only quals patch, and bug #5000 - Mailing list pgsql-hackers

I've been looking at bug #5000 (must be some kind of milestone), in
which the complaint was that the planner won't use an indexscan on a
functional index to satisfy an ORDER BY.  Of course it *can* do that,
it's just not being very bright about it.  Consider the following
example in the regression database, using all default settings:

regression=# create or replace function foo(int) returns int as
regression-# 'begin return $1; end' language plpgsql immutable strict     
regression-# cost 10000;
CREATE FUNCTION
regression=# create index fooi on tenk1 (foo(unique1));
CREATE INDEX
regression=# explain verbose select * from tenk1 order by foo(unique1);
                       QUERY PLAN                                                                           
 

---------------------------------------------------------------------------------------------------------------------------------------------------------------Index
Scanusing fooi on public.tenk1  (cost=0.00..251702.25 rows=10000 width=244)  Output: unique1, unique2, two, four, ten,
twenty,hundred, thousand, twothousand, fivethous, tenthous, odd, even, stringu1, stringu2, string4, foo(unique1)
 
(2 rows)

The first thing you'll notice is that the cost estimate is supposing
that the expensive function gets re-evaluated at each row.  And the
second thing you'll notice is that the cost estimate is not incorrect,
because this plan actually *is* evaluating foo(unique1) at each row.
(I am using CVS HEAD here so that you can see resjunk output columns...)
So this is hardly going to satisfy the complainant, even if the planner
chose it over the seqscan-and-sort alternative.

The reason for this behavior is that the Query representation emitted
by the parser includes the ORDER BY expressions as "resjunk" columns
in the query targetlist.  grouping_planner() faithfully includes all
such columns in the final plan's targetlist, even ones that are not
really needed because of the form of the chosen plan.  Because it always
uses the same targetlist, it also feels that it's not necessary to worry
about the evaluation cost of the targetlist while choosing the plan
--- so it settles on indexscan or seqscan before it's ever even bothered
to compute the cost of the tlist.

This isn't a horrid strategy in "normal" cases where the sort keys
are just simple columns; even if they end up not being referenced,
pulling a couple of extra datums from the heap tuples isn't all that
much extra expense.  But if you're talking about an expensive function
then it gets objectionable.

I looked into fixing the code to omit unused resjunk sort columns, and
think that it could probably be dealt with via some reasonably
straightforward changes in grouping_planner and some of its immediate
subroutines.  However, grouping_planner is already a huge pile of subtly
intertwined spaghetti, and adding yet another set of considerations to
it will make it that much harder to understand or maintain.  (If
anyone's got some ideas about refactoring it, I'm all ears.)  So I
looked around for alternatives.

It strikes me that in the cases where it wouldn't be necessary to
compute junk sort-key columns, it would be because we were scanning an
index that includes those values.  So if the plan were set up to pull
those values from the index and return them, then we'd not have to add
this extra complexity to grouping_planner --- the argument that it's not
worth it to get rid of the junk columns comes back into play.  Moreover,
such an ability would also mean that if the user *does* ask for the
sort column value as output (ie it's not resjunk), we can still satisfy
the query from the index without recomputing the expensive function.

So this is where we come to the connection to Heikki's index-only-quals
patch.  As submitted, that code is only able to use an index column in
a scan qual, it's not able to return it as part of the scan result.
This example makes it clear that that definition is missing a large
part of the potential benefit of an index value extraction capability.

To be able to do anything along that line would require some more work
in the executor and a *lot* more work in the planner, and I'm honestly
not sure what the planner part of it would look like.  The main point
at the moment is that to do something like this, we'd want the indexscan
to certainly extract the function value from the index.  Heikki's patch
views that as an optional behavior with no real penalty for failure.
I don't think that's good enough.

I'm not sure whether to go ahead with trying to fix the unused-sort-key
behavior right now, or to leave it until something gets done on the
index value extraction front.  Comments?
        regards, tom lane