Re: MDAM techniques and Index Skip Scan patch

Peter Geoghegan <pg(at)bowt(dot)ie> writes:
> Like many difficult patches, the skip scan patch is not so much
> troubled by problems with the implementation as it is troubled by
> *ambiguity* about the design. Particularly concerning how skip scan
> meshes with existing designs, as well as future designs --
> particularly designs for other MDAM techniques. I've started this
> thread to have a big picture conversation about how to think about
> these things.

Peter asked me off-list to spend some time thinking about the overall
direction we ought to be pursuing here. I have done that, and here
are a few modest suggestions.

1. Usually I'm in favor of doing this sort of thing in an index AM
agnostic way, but here I don't see much point. All of the ideas at
stake rely fundamentally on having a lexicographically-ordered multi
column index; but we don't have any of those except btree, nor do
I think we're likely to get any soon. This motivates the general
tenor of my remarks below, which is "do it in access/nbtree/ not in
the planner".

2. The MDAM paper Peter cited is really interesting. You can see
fragments of those ideas in our existing btree code, particularly in
the scan setup stuff that detects redundant or contradictory keys and
determines a scan start strategy. The special handling we implemented
awhile ago for ScalarArrayOp index quals is also a subset of what they
were talking about. It seems to me that if we wanted to implement more
of those ideas, the relevant work should almost all be done in nbtree
proper. The planner would need only minor adjustments: btcostestimate
would have to be fixed to understand the improvements, and there are
some rules in indxpath.c that prevent us from passing "too complicated"
sets of indexquals to the AM, which would need to be relaxed or removed
altogether.

3. "Loose" indexscan (i.e., sometimes re-descend from the tree root
to find the next index entry) is again something that seems like it's
mainly nbtree's internal problem. Loose scan is interesting if we
have index quals for columns that are after the first column that lacks
an equality qual, otherwise not. I've worried in the past that we'd
need planner/statistical support to figure out whether a loose scan
is likely to be useful compared to just plowing ahead in the index.
However, that seems to be rendered moot by the idea used in the current
patchsets, ie scan till we find that we'll have to step off the current
page, and re-descend at that point. (When and if we find that that
heuristic is inadequate, we could work on passing some statistical data
forward. But we don't need any in the v1 patch.) Again, we need some
work in btcostestimate to understand how the index scan cost will be
affected, but I still don't see any pressing need for major planner
changes or plan tree contents changes.

4. I find each of the above ideas to be far more attractive than
optimizing SELECT-DISTINCT-that-matches-an-index, so I don't really
understand why the current patchsets seem to be driven largely
by that single use-case. I wouldn't even bother with that for the
initial patch. When we do get around to it, it still doesn't need
major planner support, I think --- again fixing the cost estimation
is the bulk of the work. Munro's original 2014 patch showed that we
don't really need all that much to get the planner to build such a
plan; the problem is to convince it that that plan will be cheap.

In short: I would throw out just about all the planner infrastructure
that's been proposed so far. It looks bulky, expensive, and
drastically undercommented, and I don't think it's buying us anything
of commensurate value. The part of the planner that actually needs
serious thought is btcostestimate, which has been woefully neglected in
both of the current patchsets.

BTW, I've had a bee in my bonnet for a long time about whether some of
nbtree's scan setup work could be done once during planning, rather than
over again during each indexscan start. This issue might become more
pressing if the work becomes significantly more complicated/expensive,
which these ideas might cause. But it's a refinement that could be
left for later --- and in any case, the responsibility would still
fundamentally be nbtree's. I don't think the planner would do more
than call some AM routine that could add decoration to an IndexScan
plan node.

Now ... where did I put my flameproof vest?

regards, tom lane