Horton

Thread

Commits

  1. Refactor the representation of indexable clauses in IndexPaths.

  1. Refactoring IndexPath representation of index conditions

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-02-02T16:29:10Z

    I've been poking at the problem discussed in a couple of recent threads
of letting extensions in on the ability to create "lossy index conditions"
for complex operators/functions.  The current design for that in
indxpath.c is frankly just a pile of kluges of varying ages.  In the
initial pass, the code merely decides that a given clause is or is not
capable of being used with an index (match_clause_to_indexcol), and
then later it generates an actual indexqual for some lossy cases
(expand_indexqual_conditions), and then still later it generates an actual
indexqual for some other cases (in particular, commutation of reversed
clauses doesn't happen until fix_indexqual_references in createplan.c).
Both the second and third passes have to expensively rediscover some
things the first pass knew already, like which side of the operator the
index column is on.  In between, still other places like costsize.c
and selfuncs.c also expensively rediscover that.  And, because the
IndexPath's representation of original and derived index clauses doesn't
keep a clear association between an original clause and what was derived
from it, we also fail to handle some cases where we don't really need to
re-test an original clause, see for instance
https://www.postgresql.org/message-id/27810.1547651110@sss.pgh.pa.us

I think that the original idea here was that we should do as little
work as possible "up front", since most index paths will get discarded
before we reach createplan.c.  But to the extent that that was valid
at all, it's gotten overtaken by circumstances.  In particular,
postponing work to expand_indexqual_conditions (which is called by
create_index_path) is just stupid, because these days we typically
call that several times with the same index conditions.  It's really
dubious that postponing commutation to createplan.c is a net win either,
considering that it complicates intermediate costing steps.

What finally drove me to the breaking point on this was seeing that
if we keep this design, we'd have to look up and call an extension
operator's planner support function twice, once during
match_clause_to_indexcol (to ask whether a lossy conversion is possible)
and again in expand_indexqual_conditions (to actually do it).  That's
just silly.  But thinking about how to fix that led me to the conclusion
that we need a more wide-ranging refactoring that will also eliminate
the inefficiencies cited above.

Hence, I propose the attached, which replaces the separate "indexclauses",
"indexquals" and "indexqualcols" lists of IndexPaths with a single list
of IndexClause nodes.  That allows us to keep a clear association between
original and derived clauses, and provides us a place to put additional
data as needed.  In this version I added a "lossy" flag to tell whether
the derived clauses are an exact implementation of the original or not,
which is enough to fix the boolean-index problem mentioned above.
I also added a field to allow storing the index column list for an
indexable RowCompareExpr, avoiding the need to re-do creation of that
list at createplan time.

In this patch I also legislate that commutation of a clause is a form
of making a derived clause, and it has to be done up-front and stored
explicitly.  That's a debatable choice, but I think it's a win because
it allows code such as the index cost estimators to not have to deal
with un-commuted index clauses, and (after some more refactoring)
we'll be able to avoid looking up the commutator operator twice.

As best I can tell from microbenchmarking the planner, this
patch is about a wash as it stands for simple index clauses.
I expect it will come out ahead after I've refactored 
match_clause_to_indexcol and expand_indexqual_conditions to avoid
duplication of effort in the latter.  It is already a measurable
and very significant win for RowCompareExpr cases, eg planning
time for "select * from tenk1 where (thousand, tenthous) < (10,100)"
drops by 30%.

An interesting side effect, visible in the regression tests, is
that EXPLAIN now always shows index clauses with the index column
on the left, since commutation happens before we create the
"indexqualorig" component of the Plan.  This seems all to the
good IMO; the old output always struck me as confusing.

The next step is to actually do that refactoring inside indxpath.c,
but I felt this patch was large enough already, so I'm putting
it up for comment as-is.  (There's more cleanup and elimination
of duplicate work that could happen in the index cost estimators
too, I think.)

Thoughts?  If there's not objections I'd like to push this soon.

			regards, tom lane

  2. Re: Refactoring IndexPath representation of index conditions

    Andres Freund <andres@anarazel.de> — 2019-02-02T20:02:32Z

    Hi,

On 2019-02-02 11:29:10 -0500, Tom Lane wrote:
> I think that the original idea here was that we should do as little
> work as possible "up front", since most index paths will get discarded
> before we reach createplan.c.  But to the extent that that was valid
> at all, it's gotten overtaken by circumstances.  In particular,
> postponing work to expand_indexqual_conditions (which is called by
> create_index_path) is just stupid, because these days we typically
> call that several times with the same index conditions.  It's really
> dubious that postponing commutation to createplan.c is a net win either,

It seems your approach isn't particularly in contradiction to the
stated historical goal. We could create the new struct, but just not
populate it eagerly, right?



> Thoughts?  If there's not objections I'd like to push this soon.

Seems reasonable from a very very quick skim.

Andres

  3. Re: Refactoring IndexPath representation of index conditions

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-02-02T20:48:41Z

    Andres Freund <andres@anarazel.de> writes:
> On 2019-02-02 11:29:10 -0500, Tom Lane wrote:
>> I think that the original idea here was that we should do as little
>> work as possible "up front", since most index paths will get discarded
>> before we reach createplan.c.  But to the extent that that was valid
>> at all, it's gotten overtaken by circumstances.  In particular,
>> postponing work to expand_indexqual_conditions (which is called by
>> create_index_path) is just stupid, because these days we typically
>> call that several times with the same index conditions.  It's really
>> dubious that postponing commutation to createplan.c is a net win either,

> It seems your approach isn't particularly in contradiction to the
> stated historical goal. We could create the new struct, but just not
> populate it eagerly, right?

Not really.  A large part of the point here is to record what
match_clause_to_indexcol has found out rather than have to rediscover
it later (perhaps repeatedly).

Concretely, the main extra cost that I've added in this patch
(that wouldn't have been paid anyway by the time we've finished
create_index_path) is creation of a commuted OpExpr and a
RestrictInfo for it, in cases where we have an operator that
matches the index but the index column is on the right.  I was
able to reduce that cost quite a bit by adding a bespoke
"commute_restrictinfo" function, but it's still a few palloc's
more than we did before.  However, I think the benefits are
substantial: subsequent code can uniformly assume that indexquals
have indexcol-on-left, rather than having to figure that out repeatedly,
and we can avoid repeated syscache lookups to find out the OID of
the commutator operator.  The patch as posted is still doing
one more commutator lookup than it needs to, but that'll be fixed
by folding expand_indexqual_conditions and match_clause_to_indexcol
into one step.  Also I'm not sure if I've found all the places that
are expending now-useless effort for indexcol-on-right or not;
I've not looked exhaustively.  So at the worst this choice seems to
be a wash in terms of cycles, but I have hopes that it'll be a win
before all the dust settles.  In any case I think it makes things
simpler and clearer, which is worth a good deal.

Another idea that I looked into is to not create RestrictInfos for
derived indexqual clauses, with the hope that that would further
reduce the added overhead for the commuted-clause case.  However
that crashed and burned when I found out that the extended-stats
machinery punts when given a bare clause rather than a RestrictInfo.
It could possibly be fixed to not do that, but it looks like the
consequences would be extra lookups that'd probably cost more than
we saved by omitting the RestrictInfo.  Also, having RestrictInfos
means that we can cache selectivity estimates across multiple
calls.  I'm not entirely sure how much that matters in this
context, but it's probably not negligible.

			regards, tom lane

  4. Re: Refactoring IndexPath representation of index conditions

    Alvaro Herrera <alvherre@2ndquadrant.com> — 2019-02-06T01:35:12Z

    On 2019-Feb-02, Tom Lane wrote:

> In any case I think it makes things simpler and clearer, which is
> worth a good deal.

Looking at the patch, I agree -- this is clearer than what was there
before.

> Another idea that I looked into is to not create RestrictInfos for
> derived indexqual clauses, with the hope that that would further
> reduce the added overhead for the commuted-clause case.  However
> that crashed and burned when I found out that the extended-stats
> machinery punts when given a bare clause rather than a RestrictInfo.
> It could possibly be fixed to not do that, but it looks like the
> consequences would be extra lookups that'd probably cost more than
> we saved by omitting the RestrictInfo.  Also, having RestrictInfos
> means that we can cache selectivity estimates across multiple
> calls.  I'm not entirely sure how much that matters in this
> context, but it's probably not negligible.

Is it reasonable to give ext-stats the option to receive either a
"plain" clause or a RestrictInfo, and if the former have it construct
the RestrictInfo and return it?  It seems a pity to waste effort to
cater for ext-stats, only to be used in the rare case where any
ext-stats actually exist ... most of the time, it'd be wasted effort.

-- 
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  5. Re: Refactoring IndexPath representation of index conditions

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-02-06T16:04:26Z

    Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> On 2019-Feb-02, Tom Lane wrote:
>> Another idea that I looked into is to not create RestrictInfos for
>> derived indexqual clauses, with the hope that that would further
>> reduce the added overhead for the commuted-clause case.  However
>> that crashed and burned when I found out that the extended-stats
>> machinery punts when given a bare clause rather than a RestrictInfo.
>> It could possibly be fixed to not do that, but it looks like the
>> consequences would be extra lookups that'd probably cost more than
>> we saved by omitting the RestrictInfo.  Also, having RestrictInfos
>> means that we can cache selectivity estimates across multiple
>> calls.  I'm not entirely sure how much that matters in this
>> context, but it's probably not negligible.

> Is it reasonable to give ext-stats the option to receive either a
> "plain" clause or a RestrictInfo, and if the former have it construct
> the RestrictInfo and return it?

No, I don't think it'd be sane to have ext-stats modify that data
structure after-the-fact.  Too much risk of trouble (he says while
eyeing the GEQO machinery warily); plus, if we did it like that,
we'd *definitely* be giving up the ability to cache and share
cost/selectivity numbers between ext-stats and other places.

> It seems a pity to waste effort to
> cater for ext-stats, only to be used in the rare case where any
> ext-stats actually exist ... most of the time, it'd be wasted effort.

I'm not sure it's a good idea to design on the assumption that ext-stats
are rare.  I think they'll get more common over time.  Right now that
machinery is hardly built out at all, but it's coming.

			regards, tom lane