While working on the UniqueKeys stuff, I noticed that the self-join elimination code puts its uniqueness proof logic into several places that are also used by other parts of the planner. This makes the UniqueKeys work harder than it should be, because I have to take care of SJE-specific things in places that are not related to SJE at all.
To remove a self-join, SJE needs to prove that each row of the removed relation can only match its own row in the kept relation. Currently it passes the self-join quals and all the restriction clauses of the kept relation to innerrel_is_unique(), and lets relation_has_unique_index_for() report back which restriction clauses it used. Then it checks that the removed relation also has these clauses. For this, an extra_clauses output parameter is added to innerrel_is_unique(), is_innerrel_unique_for(), rel_is_distinct_for() and relation_has_unique_index_for(). Also the UniqueRelInfo cache entries have self_join and extra_clauses fields, and the cache lookups need to handle them specially. IMHO it doesn't seem like a good design to scatter SJE-specific logic across these functions in such an ad hoc way. Another problem is that the result depends on the order of the indexes. This is the kind of plan instability users can't reason about. relation_has_unique_index_for() stops at the first unique index that it can prove, and if this index uses a restriction clause that only the kept relation has, SJE just gives up, even if another index could work. For example, with the table sj (a int unique, b int, c int unique) from join.sql, and a unique index on (a, b, c), for the query below SELECT * FROM sj j1, sj j2 WHERE j1.b = j2.b AND j1.c = 3 AND j2.a = 2 AND j2.c = 3; the join is not removed. This is because the index on (a, b, c) is tried first, and it needs j2.a = 2, which j1 does not have. However, the unique index on c together with the shared restriction c = 3 is enough to remove the join. So I'd like to propose the attached patch. With this patch, SJE first finds out the restriction clauses that both relations have, and then calls relation_has_unique_index_for() directly with the self-join quals and these shared clauses. Since SJE does not go through innerrel_is_unique() any more, we can remove the extra_clauses parameters as well as all the code around that. Also, unique_for_rels can be a plain list of Relids again, so we can remove UniqueRelInfo structure and all the special handling around it. One might worry that SJE does not use the cache any more. But within SJE, the cached entries never get hit, because each pair of relations is checked only once, and if anything is removed, we restart and rebuild all the RelOptInfos, which discards every cache entry. The only benefit of the SJE cache might be that join search may reuse the entries from the *final* SJE pass, which only happens when a table is joined to itself, and at the cost of at most one extra relation_has_unique_index_for() call. I think this is fine, as it is very cheap compared to the rest of planning. OTOH, because now more self-joins can be removed, we actually can save a lot of planning time, since join search has fewer relations to deal with. The patch also removes the requirement that the two relations must have a join clause between them. The shared restriction clauses alone can prove that the join is removable, such as "WHERE j1.a = 2 AND j2.a = 2" with a unique index on a. This enables us to remove even more self-joins than before. (This is a master-only patch.) Any thoughts? - Richard
v1-0001-Simplify-the-uniqueness-proof-for-self-join-elimi.patch
Description: Binary data
