Re: Index-only scan for "f(x)" without "x"

Malthe <mborch(at)gmail(dot)com> writes:
> Referencing the example given in the documentation for index-only
> scans [0], we consider an index:
> CREATE INDEX tab_f_x ON tab (f(x));
> This index currently will not be used for an index-scan for the
> following query since the planner isn't smart enough to know that "x"
> is not needed:
> SELECT f(x) FROM tab WHERE f(x) < 1;
> However, any function applied to a column for an index expression is
> required to be immutable so as far as I can tell the planner doesn't
> have to be very smart to know that the index can indeed be used for an
> index-only scan (without having "x" included).

The problem is that the planner's initial analysis of the query tree
concludes that the scan of "tab" has to return "x", because it looks
through the tree for plain Vars, and "x" is what it's going to find.
This conclusion is in fact true for any plan that doesn't involve
scanning a suitable index on f(x), so it's not something we can just
dispense with.

To back up from that and conclude that the indexscan doesn't really
need to return "x" because every use of it is in the context "f(x)"
seems like a pretty expensive proposition, especially once you start
considering index expressions that are more complex than a single
function call. A brute-force matching search could easily be O(N^2)
or worse in the size of the query tree, which is a lot to pay when
there's a pretty high chance of failure. (IOW, we have to expect
that most queries on "tab" are in fact not going to be able to use
that index, so we can't afford to spend a lot of planning time just
because the index exists.)

> What's required in order to move forward on these capabilities?

Some non-brute-force solution to the above problem.

regards, tom lane