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/