Hash-based MCV matching for large IN-lists

Hi hackers,

When estimating selectivity for ScalarArrayOpExpr (IN, ANY, ALL) and MCV statistics are available for the column, the planner currently matches IN-list elements against the MCV array using nested loop. For large IN-list and large MCV arrays this results in O(N*M) behavior, which can become unnecessarily expensive during planning.

Thanks to David for pointing out this case [0]

This patch introduces a hash-based matching path, analogous to what is already done for MCV matching in join selectivity estimation (057012b commit). Instead of linearly scanning the MCV array for each IN-list element, we build a hash table and probe it to identify matches.

The hash table is built over the MCV values, not over the IN-list. The IN-list may contain NULLs, non-Const expressions, and duplicate values, whereas the MCV list is guaranteed to contain distinct, non-NULL values and represents the statistically meaningful domain we are matching against. Hashing the MCVs therefore avoids duplicate work and directly supports selectivity estimation.

For each IN-list element, if a matching MCV is found, we add the corresponding MCV frequency to the selectivity estimate. If no match is found, the remaining selectivity is estimated in the same way as the existing non-MCV path (similar to var_eq_const when the constant is not present in the MCV list).

The hash-based path is enabled only when both a sufficiently large IN-list and an MCV list are present, and suitable hash functions exist for the equality operator. The threshold is currently the same as the one used for join MCV hashing, since the underlying algorithmic tradeoffs are similar.

Example:

CREATE TABLE t (x int);
INSERT INTO t SELECT x % 10000 FROM generate_series(1, 3000000) x;
ALTER TABLE t ALTER COLUMN x SET STATISTICS 10000;
ANALYZE t;

Before patch:
EXPLAIN (SUMMARY) SELECT * FROM t WHERE x IN (1,2,...,2000);
Seq Scan on t  (cost=5.00..58280.00 rows=600000 width=4)
   Filter: (x = ANY ('{1,2,...,2000}'::integer[]))
 Planning Time: 57.137 ms
(3 rows)

After patch:
EXPLAIN (SUMMARY) SELECT * FROM t WHERE x IN (1,2,...,2000);
Seq Scan on t  (cost=5.00..58280.00 rows=600000 width=4)
   Filter: (x = ANY ('{1,2,...,2000}'::integer[]))
 Planning Time: 0.558 ms
(3 rows)

Comments, suggestions, and alternative approaches are welcome!

[0]: https://www.postgresql.org/message-id/b6316b99-565b-4c89-aa08-6aea51f54526%40gmail.com

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