Remove useless self-joins
The Self Join Elimination (SJE) feature removes an inner join of a plain table
to itself in the query tree if is proved that the join can be replaced with
a scan without impacting the query result. Self join and inner relation are
replaced with the outer in query, equivalence classes, and planner info
structures. Also, inner restrictlist moves to the outer one with removing
duplicated clauses. Thus, this optimization reduces the length of the range
table list (this especially makes sense for partitioned relations), reduces
the number of restriction clauses === selectivity estimations, and potentially
can improve total planner prediction for the query.
The SJE proof is based on innerrel_is_unique machinery.
We can remove a self-join when for each outer row:
1. At most one inner row matches the join clause.
2. Each matched inner row must be (physically) the same row as the outer one.
In this patch we use the next approach to identify a self-join:
1. Collect all merge-joinable join quals which look like a.x = b.x
2. Add to the list above the baseretrictinfo of the inner table.
3. Check innerrel_is_unique() for the qual list. If it returns false, skip
this pair of joining tables.
4. Check uniqueness, proved by the baserestrictinfo clauses. To prove
the possibility of self-join elimination inner and outer clauses must have
an exact match.
The relation replacement procedure is not trivial and it is partly combined
with the one, used to remove useless left joins. Tests, covering this feature,
were added to join.sql. Some regression tests changed due to self-join removal
logic.
Discussion: https://postgr.es/m/flat/64486b0b-0404-e39e-322d-0801154901f3%40postgrespro.ru
Author: Andrey Lepikhov, Alexander Kuzmenkov
Reviewed-by: Tom Lane, Robert Haas, Andres Freund, Simon Riggs, Jonathan S. Katz
Reviewed-by: David Rowley, Thomas Munro, Konstantin Knizhnik, Heikki Linnakangas
Reviewed-by: Hywel Carver, Laurenz Albe, Ronan Dunklau, vignesh C, Zhihong Yu
Reviewed-by: Greg Stark, Jaime Casanova, Michał Kłeczek, Alena Rybakina
Reviewed-by: Alexander Korotkov
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/d3d55ce571369dad6e1d582f1655e5a3fbd8594a
Modified Files
--------------
doc/src/sgml/config.sgml | 16 +
src/backend/optimizer/path/indxpath.c | 39 +
src/backend/optimizer/plan/analyzejoins.c | 1211 +++++++++++++++++++++++--
src/backend/optimizer/plan/planmain.c | 5 +
src/backend/utils/misc/guc_tables.c | 10 +
src/include/optimizer/paths.h | 3 +
src/include/optimizer/planmain.h | 6 +
src/test/regress/expected/equivclass.out | 32 +
src/test/regress/expected/join.out | 805 ++++++++++++++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/expected/updatable_views.out | 17 +-
src/test/regress/sql/equivclass.sql | 16 +
src/test/regress/sql/join.sql | 359 ++++++++
src/tools/pgindent/typedefs.list | 3 +
14 files changed, 2457 insertions(+), 68 deletions(-)