Thread: Getting sorted data from foreign server for merge join

On Thu, Nov 5, 2015 at 11:54 PM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> Hi All,
> PFA patch to get data sorted from the foreign server (postgres_fdw)
> according to the pathkeys useful for merge join.
>
> For a given base relation (extendable to join when that becomes available in
> postgres_fdw), the patch tries to find merge joinable clauses. It then adds
> paths with pathkeys extracted out of these merge joinable clauses. The merge
> joinable clauses form equivalence classes. The patch searches in
> root->eq_classes for equivalence members belonging to the given relation.
> For every such expression it creates a single member pathkey list and
> corresponding path. The test postgres_fdw.sql has an existing join which
> uses merge join. With this patch the data is sorted on the foreign server
> than locally.
>
> While mergejoinable clauses can be obtained from rel->joininfo as well. But
> rel->joininfo contains other clauses as well and we need extra efforts to
> remove duplicates if the same expression appears in multiple merge joinable
> clauses.
>
> Two joining relations can have multiple merge joinable clauses, requiring
> multi-member pathkeys so that merge join is efficient to the maximum extent.
> The order in which the expressions appears in pathkeys can change the costs
> of sorting the data according to the pathkeys, depending upon the
> expressions and the presence of indexes containing those expressions. Thus
> ideally we would need to club all the expressions appearing in all the
> clauses for given two relations and create paths with pathkeys for every
> order of these expressions.That explodes the number of possible paths. We
> may restrict the number of paths created by considering only certain orders
> like sort_inner_and_outer(). In any case, costing such paths increases the
> planning time which may not be worth it. So, this patch uses a heuristic
> approach of creating single member pathkeys path for every merge joinable
> expression.
>
> The pathkeys need to be canonicalised using make_canonical_pathkey(), which
> is a static function. I have added a TODO and comments in the patch
> explaining possible ways to avoid "extern"alization of this function.
>
> Comments/suggestions are welcome.

I think this approach is generally reasonable, but I suggested parts
of it, so may be biased.  I would be interested in hearing the
opinions of others.

Random notes:

"possibily" is a typo.

usable_pklist is confusing because it seems like it might be talking
about primary keys rather than pathkeys.  Also, I realize now, looking
at this again, that you're saying "usable" when what I really think
you mean is "useful".  Lots of pathkeys are usable, but only a few of
those are useful.  I suggest renaming usable_pathkeys to
query_pathkeys and usable_pklist to useful_pathkeys.  Similarly, let's
rename generate_pathkeys_for_relation() to
get_useful_pathkeys_for_relation().

Although I'm usually on the side of marking things as extern whenever
we find it convenient, I'm nervous about doing that to
make_canonical_pathkey(), because it has side effects.  Searching the
list of canonical pathkeys for the one we need is reasonable, but is
it really right to ever think that we might create a new one at this
stage?  Maybe it is, but if so I'd like to hear a good explanation as
to why.
Is the comment "Equivalence classes covering relations other than the
current one are of interest here" missing a "not"?

I don't find this comment illuminating:

+         * In case of child relation, we need to check that the
+         * equivalence class indicates a join to a relation other than
+         * parents, other children and itself (something similar to above).
+         * Otherwise we will end up creating useless paths. The code below is
+         * similar to generate_implied_equalities_for_column(), which might
+         * give a hint.

That basically just says that we have to do it this way because the
other way would be wrong.  But it doesn't say WHY the other way would
be wrong. Then a few lines later, you have another comment which says
the same thing again:

+                /*
+                 * Ignore equivalence members which correspond to children
+                 * or same relation or to parent relations
+                 */

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

On Friday, November 6, 2015 10:32 AM, Robert Haas <robertmhaas@gmail.com> wrote:

> I think this approach is generally reasonable, but I suggested
> parts of it, so may be biased.  I would be interested in hearing
> the opinions of others.

Has anyone taken a close look at what happens if the two sides of
the merge join have different implementations of the same collation
name?  Is there anything we should do to defend against the
problem?

We already face the issue of corrupted indexes when we have
different revisions of glibc on a primary and a standby or when the
OS on a server is updated, so this wouldn't be entirely a *new*
problem:

http://www.postgresql.org/message-id/BA6132ED-1F6B-4A0B-AC22-81278F5AB81E@tripadvisor.com

... but it would be a brand-new way to hit it, and we might be able
to spot the problem in a merge join by watching for rows being fed
to either side of the join which are not in order according to the
machine doing the join.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Nov 6, 2015 at 4:54 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> PFA patch to get data sorted from the foreign server (postgres_fdw)
> according to the pathkeys useful for merge join.


An idle thought. There are going to be a lot of cases where different
software systems actually disagree about collation rules. I wonder if
it would be valuable to have a node that just checks that each row is
in fact greater than the previous row and throws an error if not. That
can be optional or a parameter of the FDW but it's probably cheap
enough to have enabled by default. It would save a lot of difficult to
heartache since the behaviour if the inputs aren't correctly sorted
will be strangely incorrect join results. Often the results may just
be missing or duplicated rows and that can be easy to miss and lead to
corrupted databases or security problems.

-- 
greg

On Sat, Nov 7, 2015 at 12:07 PM, Corey Huinker <corey.huinker@gmail.com> wrote:
> Sorry to barge in late, but I was wondering if what we've learned with this
> patch can be applied to the case of asserting a sort order on a query
> returning from dblink().

Nope.

Sorry to the bearer of bad news, but that would be a different and
much harder development project.  Set-returning functions have no way
to indicate anything about the ordering of their return values at
present.  We could invent something, but the work involved wouldn't
have much to do with this patch.

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

On Sat, Nov 7, 2015 at 5:42 PM, Greg Stark <stark@mit.edu> wrote:
> On Fri, Nov 6, 2015 at 4:54 AM, Ashutosh Bapat
> <ashutosh.bapat@enterprisedb.com> wrote:
>> PFA patch to get data sorted from the foreign server (postgres_fdw)
>> according to the pathkeys useful for merge join.
>
> An idle thought. There are going to be a lot of cases where different
> software systems actually disagree about collation rules. I wonder if
> it would be valuable to have a node that just checks that each row is
> in fact greater than the previous row and throws an error if not. That
> can be optional or a parameter of the FDW but it's probably cheap
> enough to have enabled by default. It would save a lot of difficult to
> heartache since the behaviour if the inputs aren't correctly sorted
> will be strangely incorrect join results. Often the results may just
> be missing or duplicated rows and that can be easy to miss and lead to
> corrupted databases or security problems.

It's not a bad thought, but it could come up even locally - we've had
more than one situation where indexes have gotten corrupted by
updating glibc.  The new glibc doesn't agree with the old one on what
the collation ordering is, and so the indexes are wrong with respect
to the new glibc version.  If we were going to design something like
this, rather than making it a separate node, I'd be inclined to create
it as a C-callable function that could be invoked anywhere we want to
check that the ordering is valid.  I suspect you're wrong about the
cost, though: I bet it wouldn't be too hard to find cases where it
imposes a really noticeable penalty.

Also, to be clear, I don't think this patch needs to solve that problem.

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

On Fri, Nov 6, 2015 at 2:03 PM, Kevin Grittner <kgrittn@ymail.com> wrote:
> Has anyone taken a close look at what happens if the two sides of
> the merge join have different implementations of the same collation
> name?  Is there anything we should do to defend against the
> problem?

The issue of FDWs vs. collations has been thought about to some degree
(see FDW_COLLATE_NONE/SAFE/UNSAFE), but I don't quite understand that
stuff in detail.

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

On 2015/11/10 0:56, Robert Haas wrote:
> On Sat, Nov 7, 2015 at 12:07 PM, Corey Huinker <corey.huinker@gmail.com> wrote:
>> Sorry to barge in late, but I was wondering if what we've learned with this
>> patch can be applied to the case of asserting a sort order on a query
>> returning from dblink().
> 
> Nope.
> 
> Sorry to the bearer of bad news, but that would be a different and
> much harder development project.  Set-returning functions have no way
> to indicate anything about the ordering of their return values at
> present.  We could invent something, but the work involved wouldn't
> have much to do with this patch.

There was a patch (which, it seems, was rejected [1]) to do this sort of
thing.

Thanks,
Amit

[1] https://commitfest.postgresql.org/4/88/

On Tue, Nov 17, 2015 at 8:33 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
>> Although I'm usually on the side of marking things as extern whenever
>> we find it convenient, I'm nervous about doing that to
>> make_canonical_pathkey(), because it has side effects.  Searching the
>> list of canonical pathkeys for the one we need is reasonable, but is
>> it really right to ever think that we might create a new one at this
>> stage?  Maybe it is, but if so I'd like to hear a good explanation as
>> to why.
>
> For a foreign table no pathkeys are created before creating paths for
> individual foreign table since there are no indexes. For a regular table,
> the pathkeys get created for useful indexes.

OK.

Could some portion of the second foreach loop inside
get_useful_pathkeys_for_relation be replaced by a call to
eclass_useful_for_merging?  The logic looks very similar.

More broadly, I'm wondering about the asymmetries between this code
and pathkeys_useful_for_merging().  The latter has a
right_merge_direction() test and a case for non-EC-derivable join
clauses that aren't present in your code.  I wonder if we could just
generate pathkeys speculatively and then test which ones survive
truncate_useless_pathkeys(), or something like that.  This isn't an
enormously complicated patch, but it duplicates more of the logic in
pathkeys.c than I'd like.

I'm inclined to think that we shouldn't consider pathkeys that might
be useful for merge-joining unless we're using remote estimates.  It
seems more speculative than pushing down a toplevel sort.

This patch seems rather light on test cases.

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

On Wed, Dec 2, 2015 at 6:45 AM, Rushabh Lathia <rushabh.lathia@gmail.com> wrote:
> Thanks Ashutosh.
>
> Re-reviewed and Re-verified the patch, pg_sort_all_pd_v5.patch
> looks good to me.

This patch needs a rebase.

It's not going to work to say this is a patch proposed for commit when
it's still got a TODO comment in it that obviously needs to be
changed.   And the formatting of that long comment is pretty weird,
too, and not consistent with other functions in that same file (e.g.
get_remote_estimate, ec_member_matches_foreign, create_cursor).

Aside from that, I think before we commit this, somebody should do
some testing that demonstrates that this is actually a good idea.  Not
as part of the test case set for this patch, but just in general.
Merge joins are typically going to be relevant for large tables, but
the examples in the regression tests are necessarily tiny.  I'd like
to see some sample data and some sample queries that get appreciably
faster with this code.  If we can't find any, we don't need the code.

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

On Thu, Dec 17, 2015 at 3:32 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> On Wed, Dec 9, 2015 at 12:14 AM, Robert Haas <robertmhaas@gmail.com> wrote:
>> On Wed, Dec 2, 2015 at 6:45 AM, Rushabh Lathia <rushabh.lathia@gmail.com>
>> wrote:
>> > Thanks Ashutosh.
>> >
>> > Re-reviewed and Re-verified the patch, pg_sort_all_pd_v5.patch
>> > looks good to me.
>>
>> This patch needs a rebase.
>
> Done.

Thanks.

>> It's not going to work to say this is a patch proposed for commit when
>> it's still got a TODO comment in it that obviously needs to be
>> changed.   And the formatting of that long comment is pretty weird,
>> too, and not consistent with other functions in that same file (e.g.
>> get_remote_estimate, ec_member_matches_foreign, create_cursor).
>>
>
> The TODO was present in v4 but not in v5 and is not present in v6 attached
> here.. Formatted comment according estimate_path_cost_size(),
> convert_prep_stmt_params().

Hrm, I must have been looking at the wrong version somehow.  Sorry about that.

>> Aside from that, I think before we commit this, somebody should do
>> some testing that demonstrates that this is actually a good idea.  Not
>> as part of the test case set for this patch, but just in general.
>> Merge joins are typically going to be relevant for large tables, but
>> the examples in the regression tests are necessarily tiny.  I'd like
>> to see some sample data and some sample queries that get appreciably
>> faster with this code.  If we can't find any, we don't need the code.
>>
>
> I tested the patch on my laptop with two types of queries, a join between
> two foreign tables on different foreign servers (pointing to the same self
> server) and a join between one foreign and one local table. The foreign
> tables and servers are created using sort_pd_setup.sql attached. Foreign
> tables pointed to table with index useful for join clause. Both the joining
> tables had 10M rows. The execution time of query was measured for 100 runs
> and average and standard deviation were calculated (using function
> query_execution_stats() in script sort_pd.sql) and are presented below.

OK, cool.

I went over this patch in some detail today and did a lot of cosmetic
cleanup.  The results are attached.  I'm fairly happy with this
version, but let me know what you think.  Of course, feedback from
others is more than welcome also.

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

On Mon, Dec 21, 2015 at 6:34 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
>> I went over this patch in some detail today and did a lot of cosmetic
>> cleanup.  The results are attached.  I'm fairly happy with this
>> version, but let me know what you think.  Of course, feedback from
>> others is more than welcome also.
>>
>
> Attached patch with some cosmetic changes (listed here for your quick
> reference)
> 1. , was replaced with ; in comment "inner join, expressions in the " at one
> place, which is correct, but missed other place.
> 2. The comment "First, consider whether any each active EC is potentially"
> should use either "any" or "each". I have reworded it as "First, consider
> whether any of the active ECs is potentially ...". Or we can use "First,
> find all of the active ECs which are potentially ....".
> 3. "having the remote side due the sort generally won't be any worse ..." -
> instead of "due" we should use "do"?
> 4. Added static prototype of function get_useful_ecs_for_relation().
> 5. The comment "Extract unique EC for query, if any, so we don't consider it
> again." is too crisp. Phrase "Unique EC for query" is confusing; EC can not
> be associated with a query per say and EC's are always unique because of
> canonicalisation. May be we should reword it as "Extract single EC for
> ordering of query, if any, so we don't consider it again." Is that cryptic
> as well?

Thanks.  I committed this version with one small tweak.

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

<div dir="ltr">Thanks.<br /></div><div class="gmail_extra"><br /><div class="gmail_quote">On Wed, Dec 23, 2015 at 12:24
AM,Robert Haas <span dir="ltr"><<a href="mailto:robertmhaas@gmail.com"
target="_blank">robertmhaas@gmail.com</a>></span>wrote:<br /><blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px#ccc solid;padding-left:1ex"><span class="">On Mon, Dec 21, 2015 at 6:34 AM, Ashutosh Bapat<br />
<<ahref="mailto:ashutosh.bapat@enterprisedb.com">ashutosh.bapat@enterprisedb.com</a>> wrote:<br /> >> I
wentover this patch in some detail today and did a lot of cosmetic<br /> >> cleanup.  The results are attached. 
I'mfairly happy with this<br /> >> version, but let me know what you think.  Of course, feedback from<br />
>>others is more than welcome also.<br /> >><br /> ><br /> > Attached patch with some cosmetic
changes(listed here for your quick<br /> > reference)<br /> > 1. , was replaced with ; in comment "inner join,
expressionsin the " at one<br /> > place, which is correct, but missed other place.<br /> > 2. The comment
"First,consider whether any each active EC is potentially"<br /> > should use either "any" or "each". I have
rewordedit as "First, consider<br /> > whether any of the active ECs is potentially ...". Or we can use "First,<br
/>> find all of the active ECs which are potentially ....".<br /> > 3. "having the remote side due the sort
generallywon't be any worse ..." -<br /> > instead of "due" we should use "do"?<br /> > 4. Added static prototype
offunction get_useful_ecs_for_relation().<br /> > 5. The comment "Extract unique EC for query, if any, so we don't
considerit<br /> > again." is too crisp. Phrase "Unique EC for query" is confusing; EC can not<br /> > be
associatedwith a query per say and EC's are always unique because of<br /> > canonicalisation. May be we should
rewordit as "Extract single EC for<br /> > ordering of query, if any, so we don't consider it again." Is that
cryptic<br/> > as well?<br /><br /></span>Thanks.  I committed this version with one small tweak.<br /><div
class="HOEnZb"><divclass="h5"><br /> --<br /> Robert Haas<br /> EnterpriseDB: <a href="http://www.enterprisedb.com"
rel="noreferrer"target="_blank">http://www.enterprisedb.com</a><br /> The Enterprise PostgreSQL Company<br
/></div></div></blockquote></div><br/><br clear="all" /><br />-- <br /><div class="gmail_signature"><div dir="ltr">Best
Wishes,<br/>Ashutosh Bapat<br />EnterpriseDB Corporation<br />The Postgres Database Company<br /></div></div></div> 

On Thu, Jan 7, 2016 at 4:05 AM, Ashutosh Bapat
<ashutosh.bapat@enterprisedb.com> wrote:
> In get_useful_ecs_for_relation(), while checking whether to use left or
> right argument of a mergejoinable operator, the arguments to bms_is_subset()
> are passed in reverse order. bms_is_subset() checks whether the first
> argument in subset of the second, but in this function the subset to be
> checked is passed as the second argument. Because of this following query
> when run in contrib_regression database after "make installcheck" in
> contrib/postgres_fdw trips assertion Assert(bms_is_subset(relids,
> restrictinfo->left_ec->ec_relids));
>
> EXPLAIN (COSTS false, VERBOSE)
>     SELECT t1."C 1" FROM "S 1"."T 1" t1 left join ft1 t2 join ft2 t3 on
> (t2.c1 = t3.c1) on (t3.c1 = t1."C 1") OFFSET 100 LIMIT 10;
>
> PFA patch to fix it.

The test case failed for me, possibly because of Tom's upper planner
pathification, but the substantive part of the fix looks right to me,
so committed.

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