Re: Remove redundant DISTINCT when GROUP BY already guarantees uniqueness

Hi everyone,

Thanks a lot for detailed review.

Since there's already patch work on the UniqueKeys approach, I think it
make sense to keep building on that rather than staring over. Thanks for
rebase onto master. I attached 0001-patch with it.

CC: Antonin, Andy

0002: I've included fixes for the compiler warnings that were present.

While testing the 0001-patch I found a handful of bugs.

0003. convert_unique_keys_for_rel() marks a subquery-derived output
column NOT NULL just because it's covered by a unique key, without
checking whether that key can still contain NULLs. A unique index
permits multiple NULLS, so produces wrong query results:

CREATE TABLE t (a INT, b INT);
CREATE UNIQUE INDEX ON t(a);
INSERT INTO t VALUES (NULL,1), (NULL, 2), (1,3);
SELECT DISTINCT a FROM (SELECT a, b FROM t OFFSET 0) s;
-- returns 3 rows instead of 2 -- DISTINCT gets silently dropped.

0004. Chasing that same code path down, var_is_nullable() dereferences
root->simple_rel_array[var_varno] unguarded. That's reachable with a
special varno (OUTER_VAR) or a varno that simply has no RelOptInfo un
that particular root -- e.g. a Var coming out of a set operation's own
targetlist, whose member queries are planned via their own subroots.
Segfaults on copyselect.sql's UNION-in-a-subquery case once the above is
exercised.

0005. The JoinDomain built on the fly in find_ec_postion_mathcing_expr()
is never appended to root->join_domains, unlike every other JoinDomain
construction site in the tree.

0006. The JOIN_SEMI/JOIN_ANTI branch of populate_joinrel_uniquekeys()
copies the outer side's uniquekeys through unfiltered, skipping the
is_uniquekey_useful_afterjoin() interestingness check that every other
join type goes through a few lines below.

0007. populate_joinrel_uniquekeys() is called unconditionally from
make_join_rel() on every call, including when build_join_rel() returns
an already-built joinrel from a different join-order decomposition of
the same relid set. Keys get appended again each time, so wide join
queries accumulate duplicate/redundant entries. I moved the call inside
build_join_rel()'s "build a new one" branch instaed, alongside the rest
of the one-time joinrel setup (tlist, direct_lateral_relids, etc) --
it's now called exaclty once per distinct joinrel, same as everything
else there.

0008. The collate.icu.utf8 regression test caught this by itself once
run: any case-insensitive join against a column with a case-sensitive
unique index started losing rows and showing a spurious "Inner Unique:
true". A plain join (test1cs x test3cs), a self-join (test3cs x
test3cs), and a join against a DISTINCT subquery (test1cs x (SELECT
DISTINCT x FROM test3cs)) were all affected the same way, each dropping
exaclty the rows that are duplicates under case-insensitive comparison
but distinct under the case-sensitive collation the unique index was
actually built with ('abc', 'ABC'). Root cause was
find_ec_position_mathcing_expr() matching an EC to a unique index by
opfamily alone, so an EC built under a different collation override
could still be accepted as the index's uniqueness proof; fixed by also
requiring ec->ec_collation to match.

0009. Regarding redundant distinct: DISTINCT is now recognised as
redundant whenever GROUP BY already covers it, by having GROUP BY
populate rel->uniquekeys `populate_uniquekeys_from_pathkeys()` and
letting the existing
`relation_is_distinct_for()`/`create_distinct_paths()` machinery skip
the Sort+Unique step, the same way it already does for unique indexes
and joins. Because that machinery is EC-based rather than a
query_is_distinct_for()-style clause comparison, the SRF, opclass, and
collation gaps are all closed without any extra checks. SRFs via the
existing hasTargetSRFs guard, opclass/collation because two pathkeys
only share a canonical EC when their operators and collations already agree

I'll get back to the open questions in previous email a bit later. Sorry
for long email. I wanted to split all of the above into separated
patches, so each can be reviewed independently rather than as one large
diff.

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/