Horton

Re: Removing unneeded self joins

Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>

View thread
From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
To: David Rowley <david.rowley@2ndquadrant.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, PostgreSQL-development <pgsql-hackers@postgresql.org>
Date: 2019-03-22T14:39:40Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Remove GUC_NOT_IN_SAMPLE from enable_self_join_elimination

  2. Put enable_self_join_elimination into postgresql.conf.sample

  3. Get rid of ojrelid local variable in remove_rel_from_query()

  4. Implement Self-Join Elimination

  5. Revert: Remove useless self-joins

  6. Replace lateral references to removed rels in subqueries

  7. Replace relids in lateral subquery parse tree during SJE

  8. Forbid SJE with result relation

  9. Fix misuse of RelOptInfo.unique_for_rels cache by SJE

  10. Replace the relid in some missing fields during SJE

  11. Revert 56-bit relfilenode change and follow-up commits.

  12. Stabilize timetz test across DST transitions.

  13. Speed up finding EquivalenceClasses for a given set of rels

  14. Fix mark-and-restore-skipping test case to not be a self-join.

Attachments

On 3/21/19 01:54, David Rowley wrote:
> I really just don't think checking the unique indexes match is going
> to cut it. You should be looking for a unique index where the join
> clauses match on either side of the join, not looking independently
> and then checking the indexes are the same ones.


The bug you mention later is an implementation bug that can be fixed (I 
will expand on that below). Besides this, do you think current self-join 
detection algorithm has fundamental correctness problems? I am not aware 
of such problems and this algorithm reflects my understanding of what 
constitutes a removable self-join, so it would be helpful if you could 
explain what exactly is wrong with it.

Your alternative idea sounds plausible, but I won't know it's correct 
for sure until I implement it, which is a nontrivial amount of work. I 
am also concerned that we will have to redo calculations similar to 
innerrel_is_unique(), because having near-zero overhead is a hard 
prerequisite for this patch, as was discussed upthread.

In short, I am reluctant to implement a new approach to detection until 
I understand why the current one is fundamentally broken.


> Here's an example of what can go wrong with your current code:


This is a bug indeed. Unique index search is not exhaustive, so if many 
indexes match the join quals, we might not find the same index for both 
sides. I think this can be overcome if we switch to exhaustive search in 
relation_has_unique_index_for, and then try to find matching indexes in 
is_unique_self_join. Please see the new patch for the fix.


> I also think this way would give you the subquery GROUP BY / DISTINCT
> self join removal for just about free.


Could you explain how exactly we can generalize join removal to the 
DISTINCT/GROUP BY case? I understand the removable self-joins as having 
the same row on both sides of join, as identified by ctid, but I'm not 
sure how to apply this to subqueries. Your earlier DISTINCT example 
looked like it needed a different kind of join removal, with different 
conditions for when it applies (please see my previous letter for details).


Another thing I'd like to mention is that this patch splits in two 
independent parts, the detection of self-joins and their removal. While 
we are looking for agreement on the detection part, could you also 
review the removal part? I'm sure it has its own share of problems.

-- 
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company