(Sorry it took me so long to get back to this work.) While working through Antonin's review of v4, I became less and less happy with keeping UniqueKeys on join relations.
The number of keys on a join relation grows quickly, as Antonin pointed out, because the union of a key from each side is a key of the join. v4 caps the list at 8, but then which keys survive depends on the order they are added in. Worse, a join relation's keys are derived from whichever pair of input relations that the join search tries first, and a different pair can give different keys. And we build all these keys for every join relation in every query, though most of them are ever looked at. I've been trying a new idea on this. The idea is that we keep UniqueKeys for base relations only. For a join relation, we work out whether it is distinct for a given set of ECs at the time the question is asked. If some base relation in the join has a UniqueKey within that set, only one of its rows is possible, so the ECs of all its columns can be added to the set, which may in turn cover a key of another relation. We repeat that until every base relation is accounted for or we get stuck. For example, in SELECT * FROM a LEFT JOIN (b JOIN c ON b.x = c.id) ON a.x = b.id; with unique indexes on b.id and c.id, the clause "a.x = b.id" fixes b.id, that leaves one row of b, which fixes b.x and so c.id, and that leaves one row of c. So the join of b and c is unique for a. There is nothing to cap, the answer doesn't depend on the join order, and a query that never asks pays nothing. The loop is just bitmapset operations on the keys of the base relations, so it should be cheap. I've split the implementation into small steps. Attached are the first three I've got so far. 0001 detects unique inner sides of joins when the inner side is a join, for plain tables and inner joins only. 0002 skips DISTINCT and GROUP BY steps whose input is already distinct. A UniqueKey is marked null_aware if it also holds with NULLs considered equal. 0003 skips a DISTINCT step that follows grouping or window functions. There is still a lot of work to do, including outer joins, semi/anti joins, child relations, partially aggregated relations and subqueries. But I'd like to hear what people think of the approach first. - Richard
v5-0001-Detect-unique-inner-sides-of-joins-when-the-inner.patch
Description: Binary data
v5-0002-Skip-DISTINCT-and-GROUP-BY-steps-when-the-input-i.patch
Description: Binary data
v5-0003-Skip-DISTINCT-steps-over-grouped-or-windowed-inpu.patch
Description: Binary data
