Re: BUG #19408: Bad plan for UNION ALL subquery with outer WHERE, ORDER BY, LIMIT, and separate indexes

PG Bug reporting form <noreply(at)postgresql(dot)org> writes:
> The query planner generates a very suboptimal plan under the following
> circumstances:
> - Each table has an index supporting the WHERE clause
> - Each table has a different index supporting the ORDER BY clause
> - WHERE clause has a very low selectivity for some but not all of the tables
> involved

I poked into this a little bit, because as you say it seems like we
ought to be able to do better. I found that the blame seems to attach
to generate_orderedappend_paths(), which is being very blinkered about
which combinations of subpaths it will consider for a MergeAppend.
Basically, for each relevant sort ordering (here, only ORDER BY y),
it wants to consider:

1. A MergeAppend in which every subpath returns a presorted result,
and each is the best on startup cost.

2. A MergeAppend in which every subpath returns a presorted result,
and each is the best on total cost.

3. A MergeAppend in which every subpath returns a presorted result,
and each is the best on fractional cost (i.e., estimated cost after
stopping early thanks to LIMIT).

It will consider sorting an unsorted subpath too, but only if there
is no presorted path, no matter how bad that path is.

In this example we need a combination of sorting one non-ordered
input and using one presorted input, and it won't consider that
because it sees a (bad) presorted path for the first input.

I experimented with the attached quick hack. It arrives at the right
solution for your example, but it's still feeling rather blinkered.
It's not clear to me that the above rule always finds the best
combinations of subpaths. I wonder if we should tear this code up and
devise some other organizing principle for selecting the subpaths to
consider. (I can't say that I love the way in which partitioned-input
considerations have been shoved into it, either; maybe a rewrite could
factor that better.)

Another reason why this is only WIP quality is that it causes a bunch
of plan changes in the regression tests. I haven't looked to see if
they're all reasonable. Even if they're nominally better plans, some
of them may be defeating the point of the particular test by causing
it to test a different scenario.

regards, tom lane