Обсуждение: Extending constraint exclusion for implied constraints/conditions

Ashutosh Bapat <ashutosh.bapat@enterprisedb.com> writes:
> Right now, constraint exclusion code looks only at the provided conditions.
> If we want avoid table scan based on constraints in the above example, it
> will need to look at the implied conditions as well. E.g. val2 < 30 AND val
> = val2 => val < 30. Then the constraint exclusion can see that val < 30 AND
> val > 30 are contradictory and infer that the result is going to be empty.
> We will need to add information about the transitive inferences between
> operators. Can we do that in PostgreSQL? Will the benefits be worth the
> code, that needs to be added?

I doubt it.  The extra code isn't the problem so much, it's the extra
planning cycles spent trying to make proofs that will usually fail.
What you propose will create a combinatorial explosion in the number
of proof paths to be considered.

> I can see some more benefits. We can use it to eliminate joins where the
> constraints on joining relations may cause the join to be empty e.g.

... and applying constraint exclusion to join relations would make that
problem even worse.
        regards, tom lane

On Mon, Jul 7, 2014 at 3:07 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I doubt it.  The extra code isn't the problem so much, it's the extra
> planning cycles spent trying to make proofs that will usually fail.
> What you propose will create a combinatorial explosion in the number
> of proof paths to be considered.

Well, not necessarily. You only need to consider constraints on
matching columns and only when there's a join column on those columns.
So you could imagine, for example, sorting all the constraints by the
eclass for the non-const side of their expression, then going through
them linearly to see where you have multiple constraints on the same
eclass.

For what it's worth I think there is a case where this is a common
optimization. When you have multiple tables partitioned the same way.
Then you ideally want to be able to turn that from an join of multiple
appends into an append of multiple joins. This is even more important
when it comes to a parallelizing executor since it lets you do the
joins in parallel.

However to get from here to there I guess you would need to turn the
join of the appends into NxM joins of every pair of subscans and then
figure out which ones to exclude. That would be pretty nuts. To do it
reasonably we probably need the partitioning infrastructure we've been
talking about where Postgres would know what the partitioning key is
and the order and range of the partitions so it can directly generate
the matching subjoins in less than n^2 time.

-- 
greg

Ashutosh Bapat <ashutosh.bapat@enterprisedb.com> writes:
> On Mon, Jul 7, 2014 at 7:37 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I doubt it.  The extra code isn't the problem so much, it's the extra
>> planning cycles spent trying to make proofs that will usually fail.
>> What you propose will create a combinatorial explosion in the number
>> of proof paths to be considered.

> I can understand that it will create combinatorial explosion in the number
> of predicates that need to be examined by the constraint exclusion. I do
> not understand where come the paths gets involved here. The constraint
> exclusion kicks in before paths are created

Perhaps I should not have used the term "path" here, because I wasn't
referring to what the planner calls Paths.  I just meant that there will
be many more ways to perhaps prove a constraint-exclusion result, and the
planner will have to go through them all.  (Usually to no avail, because
how often do people write queries that are guaranteed to produce no rows?)

An example of what I meant by combinatorial explosion is that if a clause
mentions K variables, and each of those variables has been equated to M
other variables, there are (M+1)^K possible derived clauses, and it looks
to me like we'd have to consider them all to catch the sort of situation
you're talking about.

I think this is going to require a *lot* of additional planner cycles,
and TBH you've not provided any very compelling example of why it's
worthwhile.  Yeah, if you can exclude a large partition it's a win,
but how often is that going to happen in real-world queries?  The one
example you gave seemed pretty artificial to me, ie unrelated to typical
partitioning constraints.
        regards, tom lane