Re: Tracking per-RelOptInfo uniqueness during planning

Richard Guo <guofenglinux(at)gmail(dot)com> wrote:

> Thanks. Fixed in v4. v4 also drops the costsize.c changes from 0003,
> as the costing issue has been fixed on master.

A few more comments:

* populate_joinrel_uniquekeys()

Shouldn't we care about the number of unique keys created by the combination
technique? If most / all relations do have the unique keys, the list of keys
can grow exponentially as we keep adding relations to the join.

* uniquekeys_match_join_clauses()

/*
* Nullable keys are fine here: rows with NULL key values cannot match any
* outer row through these strict clauses.
*/

I'm not able to find where the callers check the strictness of the clauses.

Also, "Nullable" => "null-unaware" ?

* strengthen_uniquekeys_for_join()

In the header comment:

"The caller must have established that every clause holds of every output" =>
"...holds for ..." ?

I also tried to adjust one comment regarding "strengthening" of the unique
keys - see the attached diff. The original wording was hard form me to
understand, so I elaborated it more in detail. (Of course it's possible that I
missed the point altogether.)

Comments on regression tests:

v4-0001
-------

* The following

+-- a key column equated to a constant drops out of the key
+explain (costs off) select distinct b from uk_pk2 where a = 5;
+ QUERY PLAN
+----------------------------------------
+ Bitmap Heap Scan on uk_pk2
+ Recheck Cond: (a = 5)
+ -> Bitmap Index Scan on uk_pk2_pkey
+ Index Cond: (a = 5)
+(4 rows)

does not seem prove what the comment claims because explicit grouping is (for
different reason, probably due to the unique key not being a subset of the
DISTINCT clause) needed even without the WHERE clause:

explain (costs off) select distinct b from uk_pk2;
QUERY PLAN
--------------------------
HashAggregate
Group Key: b
-> Seq Scan on uk_pk2
(3 rows)

* To test the translation of the unique keys into the outer query,

+--
+-- Subquery-in-FROM keys
+--
+-- a DISTINCT inside is translated into the outer query
+explain (costs off) select distinct a, b from (select distinct a, b from uk_pk2) s;
+ QUERY PLAN
+--------------------
+ Seq Scan on uk_pk2
+(1 row)
+
+-- likewise a GROUP BY
+explain (costs off) select distinct a, b from (select a, b from uk_pk2 group by a, b) s;
+ QUERY PLAN
+--------------------
+ Seq Scan on uk_pk2
+(1 row)

I think neither DISTINCT nor GROUP BY is needed in the subquery. The subquery should have the appropriate unique keys anyway:

explain (costs off) select distinct a, b from (select a, b from uk_pk2) s;
QUERY PLAN
--------------------
Seq Scan on uk_pk2
(1 row)

* What's the point of the OFFSET clause here?

+-- a key deduced inside the subquery's own join search
+explain (costs off)
+select distinct x from
+ (select uk_p.id as x from uk_p join uk_q on uk_p.id = uk_q.id offset 0) s;
+ QUERY PLAN
+----------------------------------
+ Hash Join
+ Hash Cond: (uk_p.id = uk_q.id)
+ -> Seq Scan on uk_p
+ -> Hash
+ -> Seq Scan on uk_q
+(5 rows)

I'm getting the same plan w/o that.

* I was wondering what's specific about CROSS JOIN (v03-0001)

+-- one side's key alone is not a key of a cross join
+explain (costs off) select distinct uk_p.id from uk_p cross join uk_q;
+ QUERY PLAN
+-----------------------------------------------------
+ Unique
+ -> Nested Loop
+ -> Index Only Scan using uk_p_pkey on uk_p
+ -> Materialize
+ -> Seq Scan on uk_q
+(5 rows)

but debugger session revealed that populate_plain_rel_uniquekeys() does not
find the ECs for uk_q. I think it's because the table is not mentioned in the
DISTINCT clause. Once I added it, the appropriate unique key seems to exist,
even when the join is CROSS JOIN:

explain (costs off) select distinct uk_p.id, uk_q.id from uk_p cross join uk_q;
QUERY PLAN
------------------------------
Nested Loop
-> Seq Scan on uk_p
-> Materialize
-> Seq Scan on uk_q
(4 rows)

* Regarding FULL JOIN

+-- a full join null-extends both sides, so nothing survives
+explain (costs off)
+select distinct uk_p.id from uk_p full join uk_q on uk_p.id = uk_q.id;

don't we also need a query whith "DISTINCT uk_q.id" clause?

* I'm not sure the unique keys are tested here

+-- the RHS of this semijoin is already distinct, so it is not unique-ified
+explain (costs off)
+select * from uk_p, uk_q where (uk_p.id, uk_q.id) in (select a, b from uk_pk2);
+ QUERY PLAN
+-----------------------------------------
+ Hash Join
+ Hash Cond: (uk_pk2.b = uk_q.id)
+ -> Hash Join
+ Hash Cond: (uk_pk2.a = uk_p.id)
+ -> Seq Scan on uk_pk2
+ -> Hash
+ -> Seq Scan on uk_p
+ -> Hash
+ -> Seq Scan on uk_q
+(9 rows)

I'm getting the same plan even if I comment out the fast path (i.e. the use of
the unique keys) in rel_is_distinct_for().

* Is this comment

+-- across a left join the RHS key covers only the matched rows
+explain (costs off) select distinct uk_d1.u from uk_d2 left join uk_d1 on uk_d2.id = uk_d1.u;

saying that the RHS "loses its NULL-awareness", as tested earlier in the
script, or is it a different problem?

v4-0002
-------

* Maybe

"A partitioned table's unique index must include ..."
=>
"A partitioned table's unique index key must include ..."

* " ... an inheritance parent has none"

Does that mean " ... an inheritance parent has no unique indexes", because
inheritance parent is treated as if it had no indexes at all, per
get_relation_info()?

/*
* Make list of indexes. Ignore indexes on system catalogs if told to.
* Don't bother with indexes from traditional inheritance parents. For
* partitioned tables, we need a list of at least unique indexes as these
* serve as unique proofs for certain planner optimizations. However,
* let's not discriminate here and just record all partitioned indexes
* whether they're unique indexes or not.
*/

v4-0003
-------

* The patch seems to handle grouped child relation, so it'd make sense to have
a test for that.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com