Re: planner missing a trick for foreign tables w/OR conditions

From: Robert Haas <robertmhaas(at)gmail(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org>, Eric Ridge <e_ridge(at)tcdi(dot)com>
Subject: Re: planner missing a trick for foreign tables w/OR conditions
Date: 2013-12-16 21:49:22
Message-ID: CA+TgmobC8kaR4qr9=xoutaHZoCs7R0UP1Vq5SkNS9p8v0in_Kg@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Mon, Dec 16, 2013 at 2:04 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> The problem is that that optimization is a crock; see the comments
> for create_or_index_quals(). We can't just turn it loose to CNF-ify
> every OR it might find. The case that we support at the moment is
> to CNF-ify whichever single OR condition looks like the best win,
> and it's hard to see how to do that without any index knowledge.
>
> In principle, when we're using remote estimates, we could probably
> ask the remote server about each possibility ... but that could be
> expensive.

Could we get by without actually converting to CNF?

Suppose we define JOINQUAL-STRIP(P, B), where P is a join clause and B
is a truth value. Something like this:

JOINQUAL-STRIP(NOT Q, B) = NOT (JOINQUAL-STRIP(Q, NOT B))
JOINQUAL-STRIP(Q1 AND Q2 AND ... AND Qn, B) = the conjunction of
JOINQUAL-STRIP(Qi, B) for all i
JOINQUAL-STRIP(Q1 OR Q2 OR ... OR Qn, B) = the disjunction of
JOINQUAL-STRIP(Qi, B) for all i

For any join clause not of one of the above forms, JOINQUAL-STRIP(P,
B) is equal to P if there are no Vars in P referring to any table
other than the one for which we're constructing baserestrictinfo, and
to B otherwise.

Given this definition, we can take each join clause P and apply
JOINQUAL-STRIP(P, true) to it. If the result is true, forget it. If
the result is anything else, it's a simplified version of the original
AND/OR/NOT tree that we can apply on the remote side (if it's
pushdown-safe) to pre-filter the results. In plain English, we walk
down through AND, OR, and NOT nodes and inspect what's underneath.
Whenever we find something that references only the remote table under
consideration, we keep it as is. If we find something that touches
any other table, we assume it's true unless we're beneath an odd
number of negations, in which case we assume it's false.

e.g. if we start with (L1 AND R1) OR NOT(L2 OR R2), where the Li
reference local vars and the Ri only remote vars, we get (true AND R1)
OR NOT(false OR R2); after some trivial simplification, this reduces
to R1 OR NOT R2, which is indeed a suitable pre-filter.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Robert Haas 2013-12-16 21:50:30 Re: pg_rewarm status
Previous Message Andres Freund 2013-12-16 20:57:28 Re: 9.3 reference constraint regression