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: PostgreSQL-development <pgsql-hackers@postgresql.org>
Date: 2018-06-25T15:26:28Z
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

David,

I tried to implement your suggestions, here are the patches.

The first patch mostly moves some code around without changing 
functionality. It modifies innerrel_is_unique to not only cache the fact 
that the relation is unique, but also
cache the index that guarantees uniqueness.

The second patch adds the unique self join removal code. It goes along 
the lines of your plan. I didn't even have to examine join clauses 
because the constraints imposed by innerrel_is_unique are strong enough 
to guarantee that when it finds the same unique index for both 
relations, the join can be removed. Namely, it requires mergejoinable 
equality clauses for all columns of a unique index.

As a simple benchmark, I measured the duration of query_planner and 
remove_useless_self_joins with clock_gettime() on the regression tests. 
The following table shows average times in microseconds, median over 11 
runs. First row is with this patch, and the second row doesn't call 
remove_useless_self_joins and just calls clock_gettime to measure its 
overhead.

               query_planner  remove_useless_self_joins

with removal       39.61            0.61

no removal         39.45            0.38


So, on this workload, unique self join removal adds about 0.2 mcs, or 
0.6% of total time, to query_planner. I also tried a query that joins 26 
relations, remove_useless_self_joins takes about 40 mcs. Still, this 
time grows quadratically with number of relations we have to process, so 
in the final patch I limit it to join_collapse_limit, which brings the 
time down to 15 mcs. This is negligible compared to the total 
query_planner time, which for 8 relations is about 3 ms, that is, 3 
orders of magnitude higher.

These benchmarks mostly measure the path where we don't remove any 
joins. I didn't time the join removal itself, because it wins quite some 
time by allowing to plan one relation and one join less.

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