Use merge-based matching for MCVs in eqjoinsel

Hi hackers,

While analyzing planner performance on JOB with
default_statistics_target = 1000, I noticed that a significant portion
of planning time is spent inside the eqjoinsel() function. According to
perf, in most JOB queries at default_statistics_target = 1000,
eqjoinsel() is the most expensive function during planning, accounting
for approximately 8% of total CPU time. At default_statistics_target =
10000, the planner spend up to 75% of its time inside eqjoinsel(),
making it one of the primary bottlenecks.

Еhis overhead is caused by the O(N^2) nested-loop comparison of MCVs in
var1 = var2 clauses.

I propose an optimization: when the column datatype supports
ordering(i.e., has < and >), we can sort both MCV lists and apply
mege-style algorithm to detect matches. This reduces runtime from O(N^2)
to O(NlogN), where N is the number of MCV entries. The patch also
applies the same optimization to semi-join clauses, which show similar
performance behavior.

On JOB, this changes reduce planner time in most queries with complex
joins and large MCVs with no observable effect on plan quality. I’ve
also attached bar charts showing per-query planner time before and after
the patch for default_statistics_target = 100, 1000, 10000 along with
query numbers for reference.

Any feedback or suggestions are welcome!

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC.

On 21.07.2025 16:55, Ilia Evdokimov wrote:
>
> While analyzing planner performance on JOB with
> default_statistics_target = 1000, I noticed that a significant portion
> of planning time is spent inside the eqjoinsel() function. According
> to perf, in most JOB queries at default_statistics_target = 1000,
> eqjoinsel() is the most expensive function during planning, accounting
> for approximately 8% of total CPU time. At default_statistics_target =
> 10000, the planner spend up to 75% of its time inside eqjoinsel(),
> making it one of the primary bottlenecks.
>
> This overhead is caused by the O(N^2) nested-loop comparison of MCVs
> in var1 = var2 clauses.
>
> I propose an optimization: when the column datatype supports
> ordering(i.e., has < and >), we can sort both MCV lists and apply
> mege-style algorithm to detect matches. This reduces runtime from
> O(N^2) to O(NlogN), where N is the number of MCV entries. The patch
> also applies the same optimization to semi-join clauses, which show
> similar performance behavior.
>

Following up on my previous message about optimizing eqjoinsel() for
Var1 = Var2 and semijoin clauses, I’d like to share more detailed
performance results across different values of default_statistics_target
on the JOB benchmark.

The performance improvement grows as the number of MCV entries increases
(i.e., with higher default_statistics_target). The table below shows
total planner time summed over all 113 queries in JOB for each setting
of default_statistics_target, before and after applying patch:

Total planner time across all JOB queries
=========================================
default_statistics_target | Before Patch (ms) | After Patch (ms)
--------------------------+-------------------+------------------
                      100 |          1828.433 |         1820.556
                     1000 |          2194.282 |         1963.110
                     2500 |          4606.705 |         2140.126
                     5000 |         16661.581 |         2616.109
                     7500 |         35988.569 |         3061.161
                    10000 |         66616.620 |         3504.144

For default_statistics_target < 1000, the planning time remains the same
before and after the patch. The optimization reduces planner
time substantially - by up to *13X *at default_statistics_target = 10000
- while the generated plans and selectivity calculations remain
unchanged. To illustrate this, the table below shows the 10 slowest JOB
queries (by planning time), along with their planning times before and
after applying the patch.

Top 10 slowest queries at default_statistics_target = 10000
===========================================================
Query | Before Patch (ms) | After Patch (ms)
------+--------------------+-------------------
  29c |           1939.282 |           111.219
  29b |           1939.237 |           100.109
  29a |           1931.870 |           100.224
  31c |           1622.255 |            67.609
  30c |           1602.156 |            70.942
  28b |           1521.026 |            84.058
  30b |           1519.972 |            68.777
  30a |           1518.014 |            70.529
  28a |           1514.908 |            86.662
  31a |           1507.303 |            63.579

As shown, the total planner time for these top 10 queries drops
substantially with the optimization.

I’ve identified and fixed two issues in the original v1 patch: In
'eqjoinsel_semi' the second MCV array was allocated with an incorrect
size. And the initialization of FunctionCallInfoData was moved outside
the comparator compare_mcv_items() to avoid repeated setup during
sorting. I've attached the updated v2 patch with changes.

Any suggestions?

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC.

Following up on my previous messages about optimizing eqjoinsel() and
eqjoinsel_semi() for Var1 = Var2 clauses, I’d like to share detailed
profiling results showing the effect of the patch on JOB for different
values of default_statistics_target.

The first table shows the total planner time (summed over all 113
queries) before and after applying the patch, along with the speedup
achieved:

default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------+---------------------+---------------------+--------------------
                     100  | *1.00x*       | 1828.433     |        1820.556
                    1000  | *1.12x*       | 2194.282     |        1963.110
                    2500  | *2.15x*       | 4606.705     |        2140.126
                    5000  | *6.37x*       | 16661.581     |        2616.109
                    7500  | *11.76x*       | 35988.569     |       
3061.161
                   10000  | *19.01x*       | 66616.620     |       
3504.144

The second table shows the profiling of eqjoinsel() using *perf*,
demonstrating that the function, which dominates planning at high
statistics targets, becomes essentially negligible after the patch:

default_statistics_target | eqjoinsel() Before (perf) | eqjoinsel()
After (perf)
--------------------------+---------------------------+--------------------------
                     100  |                     0.01%
|                     0.04%
                    1000  |                     6.23%
|                     0.06%
                    2500  |                    35.45%
|                     0.23%
                    5000  |                    66.14%
|                     0.53%
                    7500  |                    72.70%
|                     0.97%
                   10000  |                    75.42%
|                     1.25%

I’ve attached v3 of the patch. This version adds a check for NULL values
when comparing MCV entries, ensuring correctness in edge cases.

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

Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com> writes:
> I’ve attached v3 of the patch. This version adds a check for NULL values
> when comparing MCV entries, ensuring correctness in edge cases.

Um ... what edge cases would those be? We do not put NULL into
MCV arrays.

regards, tom lane

On 03.09.2025 23:26, Tom Lane wrote:
> Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com> writes:
>> I’ve attached v3 of the patch. This version adds a check for NULL values
>> when comparing MCV entries, ensuring correctness in edge cases.
> Um ... what edge cases would those be? We do not put NULL into
> MCV arrays.

You're right - MCV arrays never contain NULLs. However, comparing two
MCV values could theoretically return NULL, even though this is very
unlikely. This check existed even before my changes, and similar checks
are used in other selectivity-estimation functions in 'selfuncs.c'.

...
fcinfo->isnull = false;
fresult = FunctionCallInvoke(fcinfo);
if (!fcinfo->isnull && DatumGetBool(fresult))
...

By "edge cases" I was referring to this situation; I probably did not
choose the best wording.

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

Hi Ilia!

On 29.07.2025 16:07, Ilia Evdokimov wrote:
>
> On 21.07.2025 16:55, Ilia Evdokimov wrote:
>>
>> While analyzing planner performance on JOB with
>> default_statistics_target = 1000, I noticed that a significant portion
>> of planning time is spent inside the eqjoinsel() function. According
>> to perf, in most JOB queries at default_statistics_target = 1000,
>> eqjoinsel() is the most expensive function during planning, accounting
>> for approximately 8% of total CPU time. At default_statistics_target =
>> 10000, the planner spend up to 75% of its time inside eqjoinsel(),
>> making it one of the primary bottlenecks.
>>
>> This overhead is caused by the O(N^2) nested-loop comparison of MCVs
>> in var1 = var2 clauses.

Thanks for working on this. I've wanted to submit a patch for the very
same issue for a while. I've come across this issue multiple times in
the field.

>> I propose an optimization: when the column datatype supports
>> ordering(i.e., has < and >), we can sort both MCV lists and apply
>> mege-style algorithm to detect matches. This reduces runtime from
>> O(N^2) to O(NlogN), where N is the number of MCV entries. The patch
>> also applies the same optimization to semi-join clauses, which show
>> similar performance behavior.

Why do you sort both lists and then merge instead of putting the smaller
list into a hash map and then doing hash lookups (if the type is hashable)?

There are more problems like this in the planner. For example col IN
(many values) is also quadratic because for every value in the IN list
all MCVs are checked. It would be great to fix this as well.

--
David Geier

Hi!

On 03.09.2025 18:53, Ilia Evdokimov wrote:
> Following up on my previous messages about optimizing eqjoinsel() and
> eqjoinsel_semi() for Var1 = Var2 clauses, I’d like to share detailed
> profiling results showing the effect of the patch on JOB for different
> values of default_statistics_target.
>
> The first table shows the total planner time (summed over all 113
> queries) before and after applying the patch, along with the speedup
> achieved:
>
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------+---------------------+---------------------
> +--------------------
> 100 | *1.00x* | 1828.433 | 1820.556
> 1000 | *1.12x* | 2194.282 | 1963.110
> 2500 | *2.15x* | 4606.705 | 2140.126
> 5000 | *6.37x* | 16661.581 |
2616.109
> 7500 | *11.76x* | 35988.569 |
> 3061.161
> 10000 | *19.01x* | 66616.620 |
> 3504.144
>

It looks to me like these results are with optimizations disabled?

Can you share the SQL script you used for testing?

--
David Geier

Hi Ilia!

On 05.09.2025 16:03, David Geier wrote:
>>> I propose an optimization: when the column datatype supports
>>> ordering(i.e., has < and >), we can sort both MCV lists and apply
>>> mege-style algorithm to detect matches. This reduces runtime from
>>> O(N^2) to O(NlogN), where N is the number of MCV entries. The patch
>>> also applies the same optimization to semi-join clauses, which show
>>> similar performance behavior.
>
> Why do you sort both lists and then merge instead of putting the smaller
> list into a hash map and then doing hash lookups (if the type is hashable)?

I've tested your and my code with the following script:

CREATE TABLE foo(col TEXT);
CREATE TABLE bar(col TEXT);
SET default_statistics_target = 10000;

-- Generate MCV values. PostgreSQL doesn't store MCVs if the table has
-- only a single value or every value has exactly the same cardinality.
DO $$
BEGIN
FOR i IN 1..10000 LOOP
FOR j IN 1..least(i, 50) LOOP
INSERT INTO foo VALUES ('aaaaaaaaaaaaaaaaaaaa' || i::TEXT);
INSERT INTO bar VALUES ('aaaaaaaaaaaaaaaaaaaa' || (i + 100000)::TEXT);
END LOOP;
END LOOP;
END;
$$;

ANALYZE foo, bar;
\timing on
EXPLAIN SELECT * FROM foo f, bar b WHERE f.col = b.col;

Results are:

- master: 433 ms
- Order+Merge: 11 ms
- Hash map: 4 ms

I've attached my draft patch.

--
David Geier

On 08.09.2025 13:08, David Geier wrote:
> Hi Ilia!
>
> On 05.09.2025 16:03, David Geier wrote:
>>>> I propose an optimization: when the column datatype supports
>>>> ordering(i.e., has < and >), we can sort both MCV lists and apply
>>>> mege-style algorithm to detect matches. This reduces runtime from
>>>> O(N^2) to O(NlogN), where N is the number of MCV entries. The patch
>>>> also applies the same optimization to semi-join clauses, which show
>>>> similar performance behavior.
>> Why do you sort both lists and then merge instead of putting the smaller
>> list into a hash map and then doing hash lookups (if the type is hashable)?
> I've tested your and my code with the following script:
>
> CREATE TABLE foo(col TEXT);
> CREATE TABLE bar(col TEXT);
> SET default_statistics_target = 10000;
>
> -- Generate MCV values. PostgreSQL doesn't store MCVs if the table has
> -- only a single value or every value has exactly the same cardinality.
> DO $$
> BEGIN
> FOR i IN 1..10000 LOOP
> FOR j IN 1..least(i, 50) LOOP
> INSERT INTO foo VALUES ('aaaaaaaaaaaaaaaaaaaa' || i::TEXT);
> INSERT INTO bar VALUES ('aaaaaaaaaaaaaaaaaaaa' || (i + 100000)::TEXT);
> END LOOP;
> END LOOP;
> END;
> $$;
>
> ANALYZE foo, bar;
> \timing on
> EXPLAIN SELECT * FROM foo f, bar b WHERE f.col = b.col;
>
> Results are:
>
> - master: 433 ms
> - Order+Merge: 11 ms
> - Hash map: 4 ms
>
> I've attached my draft patch.
>
> --
> David Geier

Hi David,

Thank you for reviewing.

I have read all the previous messages - and yes, you are right. I don’t
know why I didn’t consider using a hash table approach initially. Your
idea makes a lot of sense.

To evaluate it, I ran benchmarks on JOB with three variants:

$ ./benchmark.sh master
$ ./benchmark.sh merge
$ ./benchmark.sh hash

I compared total planning time across all 113 queries.

$ python3 planning_time.py master hash
default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
100                       | 1.00                | 1892.627            |
1886.969
1000                      | 1.09                | 2286.922            |
2100.099
2500                      | 1.94                | 4647.167            |
2400.711
5000                      | 6.15                | 17964.779           |
2919.914
7500                      | 10.58               | 38622.443           |
3650.375
10000                     | 16.33               | 69538.085           |
4257.864

$ python3 planning_time.py master merge
default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
100                       | 1.00                | 1892.627            |
1898.622
1000                      | 1.12                | 2286.922            |
2033.553
2500                      | 1.92                | 4647.167            |
2423.552
5000                      | 5.94                | 17964.779           |
3025.739
7500                      | 10.48               | 38622.443           |
3684.262
10000                     | 16.72               | 69538.085           |
4159.418

Based on these results, I’d prefer the hash lookup implementation, so I
think it makes sense to improve your patch further and bring it into
good shape. Shall I take care of that, or would you prefer to do it
yourself?

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

On 08.09.2025 13:35, Ilia Evdokimov wrote:
> Based on these results, I’d prefer the hash lookup implementation, so
> I think it makes sense to improve your patch further and bring it into
> good shape. Shall I take care of that, or would you prefer to do it
> yourself?

I realized I mistakenly copied the wrong results for the hash-map
version in my previous draft. Sorry about that. Here are the correct
benchmark results:

Merge

default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
100                       | 1.00                | 1892.627            |
1898.622
1000                      | 1.12                | 2286.922            |
2033.553
2500                      | 1.92                | 4647.167            |
2423.552
5000                      | 5.94                | 17964.779           |
3025.739
7500                      | 10.48               | 38622.443           |
3684.262
10000                     | 16.72               | 69538.085           |
4159.418

Hash-Map

default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
100                       | 1.00                | 1892.627            |
1886.969
1000                      | 1.09                | 2286.922            |
2100.099
2500                      | 1.94                | 4647.167            |
2400.711
5000                      | 6.15                | 17964.779           |
2919.914
7500                      | 10.58               | 38622.443           |
3650.375
10000                     | 16.33               | 69538.085           |
4257.864

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

Hi Ilia!

> I have read all the previous messages - and yes, you are right. I don’t
> know why I didn’t consider using a hash table approach initially. Your
> idea makes a lot of sense.

Your solution would be beneficial on top, for cases where the data type
is not hashable. But I think that's overkill for a v1. I would start
with the hash-based version.

> To evaluate it, I ran benchmarks on JOB with three variants:
>
> $ ./benchmark.sh master
> $ ./benchmark.sh merge
> $ ./benchmark.sh hash
>
> I compared total planning time across all 113 queries.

Was this running with optimizations? How did you extract the planning time?

>
> $ python3 planning_time.py master hash
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------------------------------------------------------------
> 100                       | 1.00                | 1892.627            |
> 1886.969
> 1000                      | 1.09                | 2286.922            |
> 2100.099
> 2500                      | 1.94                | 4647.167            |
> 2400.711
> 5000                      | 6.15                | 17964.779           |
> 2919.914
> 7500                      | 10.58               | 38622.443           |
> 3650.375
> 10000                     | 16.33               | 69538.085           |
> 4257.864
>
> $ python3 planning_time.py master merge
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------------------------------------------------------------
> 100                       | 1.00                | 1892.627            |
> 1898.622
> 1000                      | 1.12                | 2286.922            |
> 2033.553
> 2500                      | 1.92                | 4647.167            |
> 2423.552
> 5000                      | 5.94                | 17964.779           |
> 3025.739
> 7500                      | 10.48               | 38622.443           |
> 3684.262
> 10000                     | 16.72               | 69538.085           |
> 4159.418

I would have expected the delta between the "merge" and "hash" variant
to be bigger, especially for default_statistics_target=10000. My small
test also showed that. Any idea why this is not showing in your results?

> Based on these results, I’d prefer the hash lookup implementation, so I
> think it makes sense to improve your patch further and bring it into
> good shape. Shall I take care of that, or would you prefer to do it
> yourself?

I think process-wise it's best if you review my code and I do the changes.

Could you as part of your review test tables with just a few MCVs to
make sure we're not regressing "small" cases? For now I'm only bailing
if one of the two MCV lists has just a single value. I'm expecting the
gains from fine tuning this value to be not measurable but let's double
check.

--
David Geier

On 08.09.2025 12:45, Ilia Evdokimov wrote:
>
> I realized I mistakenly copied the wrong results for the hash-map
> version in my previous draft. Sorry about that. Here are the correct
> benchmark results:
>
> Merge
>
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------------------------------------------------------------
> 100                       | 1.00                | 1892.627            |
> 1898.622
> 1000                      | 1.12                | 2286.922            |
> 2033.553
> 2500                      | 1.92                | 4647.167            |
> 2423.552
> 5000                      | 5.94                | 17964.779           |
> 3025.739
> 7500                      | 10.48               | 38622.443           |
> 3684.262
> 10000                     | 16.72               | 69538.085           |
> 4159.418
>
>
> Hash-Map
>
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------------------------------------------------------------
> 100                       | 1.00                | 1892.627            |
> 1886.969
> 1000                      | 1.09                | 2286.922            |
> 2100.099
> 2500                      | 1.94                | 4647.167            |
> 2400.711
> 5000                      | 6.15                | 17964.779           |
> 2919.914
> 7500                      | 10.58               | 38622.443           |
> 3650.375
> 10000                     | 16.33               | 69538.085           |
> 4257.864
>

It still seems to me like something is fishy with the numbers or
something in the benchmark adds a lot over overhead so that small
differences in eqjoinsel_inner() don't show here.

The delta between "hash" and "merge" for default_statistics_target=10000
should be the biggest but it's actually slower.

--
David Geier

On 08.09.2025 13:56, David Geier wrote:
>> To evaluate it, I ran benchmarks on JOB with three variants:
>>
>> $ ./benchmark.sh master
>> $ ./benchmark.sh merge
>> $ ./benchmark.sh hash
>>
>> I compared total planning time across all 113 queries.
> Was this running with optimizations? How did you extract the planning time?

I save all query plans using EXPLAIN SUMMARY, then go through all the
plans, read the 'Planning Time' for each, and sum them up.

> I would have expected the delta between the "merge" and "hash" variant
> to be bigger, especially for default_statistics_target=10000. My small
> test also showed that. Any idea why this is not showing in your results?

So would I. With default_statistics_target = 10000 and the selectivity
in the JOB queries being close to zero, the difference should be
noticeable. I can only explain the previous results by cache-related
effects on my machine.

I reran the benchmark on a clean cluster and collected the top slowest
JOB queries — now the effect is clearly visible.

Merge (sum of all JOB queries)
==================
default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
100                       | *1.00*                | 1888.105           
| 1879.431
1000                      | *1.14*                | 2282.239           
| 2009.114
2500                      | *2.10*                | 5595.030           
| 2668.530
5000                      | *5.56*                | 18544.933          
| 3333.252
7500                      | *9.17*                | 37390.956          
| 4076.390
10000                     | *16.10*               | 69319.479          
| 4306.417

HashMap (sum of all JOB queries)
==================
default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
100                     | *1.03*                | 1888.105            |
1828.088
1000                    | *1.18*                | 2282.239            |
1939.884
2500                    | *2.64*                | 5595.030            |
2117.872
5000                    | *7.80*                | 18544.933           |
2377.206
7500                    | *13.80*               | 37390.956           |
2709.973
10000                   | *23.32*               | 69319.479           |
2973.073

Top 10 slowest JOB queries (default_statistics_target = 10000)
Query | master (ms) | merge (ms) | Hash (ms)
------+-------------+------------+-----------
29c   | 1904.586    | 144.135    | 100.473
29b   | 1881.392    | 117.891    | 89.028
29a   | 1868.805    | 112.242    | 83.913
31c   | 1867.234    | 76.498     | 56.140
30c   | 1646.630    | 88.494     | 62.549
30b   | 1608.820    | 84.821     | 64.603
31a   | 1573.964    | 75.978     | 56.140
28a   | 1457.738    | 95.939     | 77.309
28b   | 1455.052    | 99.383     | 73.065
30a   | 1416.699    | 91.057     | 62.549

BTW, the hashmap from your patch could also be applied to
eqjoinsel_semi() function.

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

Hi!

On 08.09.2025 15:45, Ilia Evdokimov wrote:
> I reran the benchmark on a clean cluster and collected the top slowest
> JOB queries — now the effect is clearly visible.
>
> Merge (sum of all JOB queries)
> ==================
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------------------------------------------------------------
> 100                       | *1.00*                | 1888.105           
> | 1879.431
> 1000                      | *1.14*                | 2282.239           
> | 2009.114
> 2500                      | *2.10*                | 5595.030           
> | 2668.530
> 5000                      | *5.56*                | 18544.933          
> | 3333.252
> 7500                      | *9.17*                | 37390.956          
> | 4076.390
> 10000                     | *16.10*               | 69319.479          
> | 4306.417
>
> HashMap (sum of all JOB queries)
> ==================
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> --------------------------------------------------------------------------------
> 100                     | *1.03*                | 1888.105            |
> 1828.088
> 1000                    | *1.18*                | 2282.239            |
> 1939.884
> 2500                    | *2.64*                | 5595.030            |
> 2117.872
> 5000                    | *7.80*                | 18544.933           |
> 2377.206
> 7500                    | *13.80*               | 37390.956           |
> 2709.973
> 10000                   | *23.32*               | 69319.479           |
> 2973.073
>
> Top 10 slowest JOB queries (default_statistics_target = 10000)
> Query | master (ms) | merge (ms) | Hash (ms)
> ------+-------------+------------+-----------
> 29c   | 1904.586    | 144.135    | 100.473
> 29b   | 1881.392    | 117.891    | 89.028
> 29a   | 1868.805    | 112.242    | 83.913
> 31c   | 1867.234    | 76.498     | 56.140
> 30c   | 1646.630    | 88.494     | 62.549
> 30b   | 1608.820    | 84.821     | 64.603
> 31a   | 1573.964    | 75.978     | 56.140
> 28a   | 1457.738    | 95.939     | 77.309
> 28b   | 1455.052    | 99.383     | 73.065
> 30a   | 1416.699    | 91.057     | 62.549

This looks much better. Very nice!

>
> BTW, the hashmap from your patch could also be applied to
> eqjoinsel_semi() function.
>

Yep. The inner loop only runs until clamped_nvalues2 and it doesn't
compute matchprodfreq. I'll try to modify the patch such that it
accounts for these differences without being too hard to read.

Do you think anything else needs changes in the patch? Did you have a
chance to check tables with just few MCVs or are there any queries in
the JOB which regress with very small default_statistics_target?

--
David Geier

Hi David,

On 08.09.2025 17:36, David Geier wrote:
> Do you think anything else needs changes in the patch?

From an architectural perspective, I think the patch is already in good
shape. However, I have some suggestions regarding code style:

1. I would move McvHashEntry, McvHashContext, he new hash table
definition, hash_mcv and are_mcvs_equal to the top.
2. I’m not sure get_hash_func_oid() is needed at all – it seems we
could do without it.
3. It would be better to name the parameters matchProductFrequencies ->
matchprodfreq, nMatches -> nmatches, hasMatch1 -> hasmatch1,
hasMatch2 -> hasmatch2 in eqjoinsel_inner_with_hashtable().
4. As I wrote earlier, since we now have a dedicated function
eqjoinsel_inner_with_hashtable(), perhaps it could be used in both
eqjoinsel_inner() and eqjoinsel_semi(). And since the hash-based
search was factored out, maybe it would make sense to also factor
out the O(N^2) nested loop implementation?
5. I think it would be helpful to add a comment explaining that using a
hash table is not efficient when the MCV array length equals 1:

if (Min(statsSlot1->nvalues, statsSlot2->nvalues) == 1)
    return false;

> Did you have a
> chance to check tables with just few MCVs or are there any queries in
> the JOB which regress with very small default_statistics_target?

Sure. I need some time to check this.

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

Hi!

Thanks for the review.

On 09.09.2025 09:29, Ilia Evdokimov wrote:
> From an architectural perspective, I think the patch is already in good
> shape. However, I have some suggestions regarding code style:
>
> 1. I would move McvHashEntry, McvHashContext, he new hash table
>    definition, hash_mcv and are_mcvs_equal to the top.
Done. I've also moved up try_eqjoinsel_with_hashtable().

> 2. I’m not sure get_hash_func_oid() is needed at all – it seems we
>    could do without it.
Removed.

> 3. It would be better to name the parameters matchProductFrequencies ->
>    matchprodfreq, nMatches -> nmatches, hasMatch1 -> hasmatch1,
>    hasMatch2 -> hasmatch2 in eqjoinsel_inner_with_hashtable().
Done.

> 4. As I wrote earlier, since we now have a dedicated function
>    eqjoinsel_inner_with_hashtable(), perhaps it could be used in both
>    eqjoinsel_inner() and eqjoinsel_semi(). And since the hash-based
Done.

The gains for SEMI join are even bigger because the function is called 3
times for e.g. EXPLAIN SELECT * FROM foo f WHERE EXISTS (SELECT 1 FROM
bar b where f.col = b.col); For that query the planning time for me goes
from ~1300 ms -> 12 ms.

>    search was factored out, maybe it would make sense to also factor
>    out the O(N^2) nested loop implementation?
Generally agreed and while tempting, I've refrained from doing the
refactoring. Let's better do this in a separate patch to keep things simple.

> 5. I think it would be helpful to add a comment explaining that using a
>    hash table is not efficient when the MCV array length equals 1:
>
> if (Min(statsSlot1->nvalues, statsSlot2->nvalues) == 1)
>     return false;
Done.
>> Did you have a
>> chance to check tables with just few MCVs or are there any queries in
>> the JOB which regress with very small default_statistics_target?
>
>
> Sure. I need some time to check this.
>
Could you please do that with the latest attached patch so that we test
it once more?

Could you also run once more the JOB benchmark to get some test coverage
on the SEMI join code (assuming it also uses SEMI joins)?

Once we've concluded on above and there are no objections, I will
register this patch in the commit fest.

--
David Geier

Hi!

On 09.09.2025 12:22, David Geier wrote:
> Could you please do that with the latest attached patch so that we test
> it once more?

LGTM. Yes, I'll test this patch.

>
> Could you also run once more the JOB benchmark to get some test coverage
> on the SEMI join code (assuming it also uses SEMI joins)?

Unfortunately, the JOB benchmark does not contain semi join nodes.
However, TPC-DS does. I'll look for the queries with slowest planner
times there and check them.

I'll need some time to check both join and semi join cases with small
and large default_statistics_target. I'll share the results later.

>
> Once we've concluded on above and there are no objections, I will
> register this patch in the commit fest.

Sure. No problem.

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

Hi hackers,

On 10.09.2025 16:56, Ilia Evdokimov wrote:
> Unfortunately, the JOB benchmark does not contain semi join nodes.
> However, TPC-DS does. I'll look for the queries with slowest planner
> times there and check them.
>
> I'll need some time to check both join and semi join cases with small
> and large default_statistics_target. I'll share the results later.

JOIN
==============================

I’ve benchmarked the new implementation of eqjoinsel() with different
values of default_statistics_target. On small targets (1, 5, 10, 25, 50,
75, 100) the results are all within statistical noise, and I did not
observe any regressions. In my view, it’s reasonable to keep the current
condition that the hash table is not used for default_statistics_target
= 1. Raising that threshold does not seem useful.

Here are the results for JOB queries (where the effect of semi join is
not visible due to different data distributions):

default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
------------------------------------------------------------------------------------------
1                         | 1.00                | 1846.643            |
1847.409
5                         | 1.00                | 1836.391            |
1828.318
10                        | 0.95                | 1841.750            |
1929.722
25                        | 0.99                | 1873.172            |
1890.741
50                        | 0.98                | 1869.897            |
1898.470
75                        | 1.02                | 1969.368            |
1929.521
100                       | 0.97                | 1857.890            |
1921.207
1000                      | 1.14                | 2279.700            |
1997.102
2500                      | 1.78                | 4682.658            |
2636.202
5000                      | 6.45                | 15943.696           |
2471.242
7500                      | 12.45               | 34350.855           |
2758.565
10000                     | 20.52               | 62519.342           |
3046.819

SEMI JOIN
==============================

Unfortunately, in TPC-DS it is not possible to clearly see improvements
for semi joins. To address this, I designed a synthetic example where
the data distribution forces the loop to run fully, without exiting
early, which makes the effect on semi joins more visible. In this setup,
I also ensured that the length of the MCV array is equal to the chosen
default_statistics_target.

CREATE TABLE t1 AS
SELECT CASE
         WHEN g <= 3000000 * 0.9 THEN (g % 10000) + 1
         ELSE (g % 1000000) + 10000
       END AS id
FROM generate_series(1, 3000000) g;

CREATE TABLE t2 AS
SELECT CASE
         WHEN g <= 3000000 * 0.9 THEN (g % 10000) + 10001
         ELSE (g % 1000000) + 20000
       END AS id
FROM generate_series(1, 3000000) g;

ANALYZE t1, t2;

The results of the query are:

SELECT * FROM t1
WHERE id IN (SELECT id FROM t2);

default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
------------------------------------------------------------------------------------------
1                         | 1.12                | 1.191               |
1.062
5                         | 1.02                | 0.493               |
0.481
10                        | 0.92                | 0.431               |
0.471
25                        | 1.27                | 0.393               |
0.309
50                        | 1.04                | 0.432               |
0.416
75                        | 0.96                | 0.398               |
0.415
100                       | 0.95                | 0.450               |
0.473
1000                      | 9.42                | 6.742               |
0.716
2500                      | 19.15               | 21.621              |
1.129
5000                      | 46.74               | 85.667              |
1.833
7500                      | 73.26               | 194.806             |
2.659
10000                     | 107.95              | 349.981             |
3.242

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

Hi David,

In v2 patch, when the join is reversed we pass the commutator operator
Oid to eqjoinsel_semi(), and inside that function we immediately call
get_opcode(<commutator operator Oid>). Did you mean for the function to
take an operator Oid instead of an here?

If that was unintentional, perhaps the cleanest fix is to add a new
'operator' parameter to eqjoinsel_semi() so we can keep passing
'opfuncoid' as before and avoid changing the behavior.

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

On 17.09.2025 12:40, Ilia Evdokimov wrote:
> Hi David,
>
> In v2 patch, when the join is reversed we pass the commutator operator
> Oid to eqjoinsel_semi(), and inside that function we immediately call
> get_opcode(<commutator operator Oid>). Did you mean for the function
> to take an operator Oid instead of an here?
>
> If that was unintentional, perhaps the cleanest fix is to add a new
> 'operator' parameter to eqjoinsel_semi() so we can keep passing
> 'opfuncoid' as before and avoid changing the behavior.
>

This v3 patch fixes the confusion between operator and function Oids in
eqjoinsel_semi(). This version restores the previous behavior by keeping
the function Oid as before and adds an explicit 'operator' parameter so
both values are available without extra behavior changes.

Do you have any further comments or suggestions on this version?

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

Hi Ilia!

On 10.09.2025 15:56, Ilia Evdokimov wrote:
>
> LGTM. Yes, I'll test this patch.
>
>
>
> Unfortunately, the JOB benchmark does not contain semi join nodes.
> However, TPC-DS does. I'll look for the queries with slowest planner
> times there and check them.
>
> I'll need some time to check both join and semi join cases with small
> and large default_statistics_target. I'll share the results later.
>

Have you had a chance to test above things?

I've seen that there's already a commit fest entry. I've adapted the
entry (changed the title and added myself as author). Do you want to add
yourself as reviewer?

--
David Geier

Hi David,

On 27.10.2025 18:50, David Geier wrote:
> Hi Ilia!
>
> On 10.09.2025 15:56, Ilia Evdokimov wrote:
>> LGTM. Yes, I'll test this patch.
>>
>>
>>
>> Unfortunately, the JOB benchmark does not contain semi join nodes.
>> However, TPC-DS does. I'll look for the queries with slowest planner
>> times there and check them.
>>
>> I'll need some time to check both join and semi join cases with small
>> and large default_statistics_target. I'll share the results later.
>>
> Have you had a chance to test above things?

Yes, I wrote about this here:
https://www.postgresql.org/message-id/c3dbf2ab-d72d-4033-822a-60ad8023f499%40tantorlabs.com

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

Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com> writes:
> On 27.10.2025 18:50, David Geier wrote:
>> On 10.09.2025 15:56, Ilia Evdokimov wrote:
>>> I'll need some time to check both join and semi join cases with small
>>> and large default_statistics_target. I'll share the results later.

>> Have you had a chance to test above things?

> Yes, I wrote about this here:
> https://www.postgresql.org/message-id/c3dbf2ab-d72d-4033-822a-60ad8023f499%40tantorlabs.com

Hmm. Those results sure look like there is a performance regression
up to at least 100 MCVs ... not a large one, but consistently a few
percent. That's a bit sad for a patch purporting to improve
performance. It looks to me like perhaps we should stick to the old
algorithm up to 100 or possibly even more MCVs. Certainly the
threshold needs to be higher than 1, as you have it now.

I eyeballed the patch itself very briefly, and have a couple
quick comments:

* Is hash_msv a typo for hash_mcv? If not, maybe spell out what
it's supposed to mean.

* The patch would be easier to read if it didn't reindent a couple
large chunks of existing code. Can we change the factorization
to avoid that? If not, I'd recommend submitting without that
reindentation, and reminding the committer to reindent at the last
moment.

* The calculation loops in eqjoinsel_inner and eqjoinsel_semi
are not identical, which makes it look quite weird to be
writing just one function that conditionally replaces both.
I wonder if we should refactor to have just one copy (and
just eat the extra cycles of calculating matchprodfreq).

* In fact ... I wonder if we should try harder to not do essentially
identical calculations twice, remembering that eqjoinsel_semi is
always used alongside eqjoinsel_inner. (Of course, we could only do
that if clamped_nvalues2 is the same as sslot2->nvalues, but that's
frequently true.) I think the reason it's duplicative right now
is that we regarded this semijoin calculation as an experiment and
so didn't want to invest a lot of effort in it ... but this patch
is exactly a lot of effort, so maybe it's time to deal with that
unfinished business.

regards, tom lane

Thanks for the detailed feedback!

On 04.11.2025 00:55, Tom Lane wrote:

> Hmm. Those results sure look like there is a performance regression
> up to at least 100 MCVs ... not a large one, but consistently a few
> percent. That's a bit sad for a patch purporting to improve
> performance. It looks to me like perhaps we should stick to the old
> algorithm up to 100 or possibly even more MCVs. Certainly the
> threshold needs to be higher than 1, as you have it now.

I re-ran the benchmark on JOB with a threshold of 100.Here are the
updated results:

default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
Planner After (ms)
--------------------------------------------------------------------------------
1                         | 1.00                | 2320.412            |
2318.377
5                         | 0.99                | 2335.894            |
2360.890
10                        | 1.00                | 2350.612            |
2347.154
25                        | 1.01                | 2365.977            |
2342.312
50                        | 0.99                | 2381.554            |
2405.262
75                        | 1.00                | 2396.481            |
2399.828
100                       | 1.00                | 2410.367            |
2412.456
1000                      | 1.11                | 2850.853            |
2564.303
2500                      | 2.04                | 5571.688            |
2731.545
5000                      | 6.05                | 18850.084           |
3114.692
7500                      | 11.96               | 39160.898           |
3273.688
10000                     | 19.04               | 71334.113           |
3745.955

> I eyeballed the patch itself very briefly, and have a couple
> quick comments:
>
> * Is hash_msv a typo for hash_mcv? If not, maybe spell out what
> it's supposed to mean.

Yes, that was a typo — fixed.

> * The patch would be easier to read if it didn't reindent a couple
> large chunks of existing code. Can we change the factorization
> to avoid that? If not, I'd recommend submitting without that
> reindentation, and reminding the committer to reindent at the last
> moment.

Fixed as well. I’ve removed all reindentation changes. I will keep that
in mind for future submissions.

> * The calculation loops in eqjoinsel_inner and eqjoinsel_semi
> are not identical, which makes it look quite weird to be
> writing just one function that conditionally replaces both.
> I wonder if we should refactor to have just one copy (and
> just eat the extra cycles of calculating matchprodfreq).

Agreed. I’ve dropped the attempt to merge them into a single function.

>
> * In fact ... I wonder if we should try harder to not do essentially
> identical calculations twice, remembering that eqjoinsel_semi is
> always used alongside eqjoinsel_inner. (Of course, we could only do
> that if clamped_nvalues2 is the same as sslot2->nvalues, but that's
> frequently true.) I think the reason it's duplicative right now
> is that we regarded this semijoin calculation as an experiment and
> so didn't want to invest a lot of effort in it ... but this patch
> is exactly a lot of effort, so maybe it's time to deal with that
> unfinished business.
>
> regards, tom lane

Good point. I addressed this in a separate patch: eqjoinsel_inner() now
saves matchfreq1, matchfreq2, nmatches so that eqjoinsel_semi() can
reuse them when (clamped_nvalues2 == sslot2->nvalues). If the MCV list
on the RHS is clamped, we still recompute locally. If you have a cleaner
idea for how to share these values between the two functions without
passing them explicitly, I’d be happy to consider it.

I’m attaching two patches:
1. v4-0001-Avoid-duplicate-MCV-matching-in-eqjoinsel_semi-an.patch -
removes redundant MCV matching for semi/anti joins;
2. v4-0002-Optimize-MCV-matching-in-eqjoinsel_inner-and-eqjo.patch -
adds hash-based MCV matching with a configurable threshold and includes
fixes based on your comments.

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

Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com> writes:
> Good point. I addressed this in a separate patch: eqjoinsel_inner() now
> saves matchfreq1, matchfreq2, nmatches so that eqjoinsel_semi() can
> reuse them when (clamped_nvalues2 == sslot2->nvalues). If the MCV list
> on the RHS is clamped, we still recompute locally. If you have a cleaner
> idea for how to share these values between the two functions without
> passing them explicitly, I’d be happy to consider it.

This didn't look very much like the refactorization that I had in
mind: I thought we should have one copy of the matching code, not two.
Also, after looking closer at your patch I realized you were just
punting for cross-type comparison operators, which I felt was kind
of sad. It's a little bit tricky to get simplehash.h to go along
with cross-type hashing, because it wants to use just one hash and
one equality function. But since those are interface routines we
are going to supply anyway, we can make them deal with the insert
and lookup cases differently.

So after a bit of hacking I ended up with the attached. I split up
the refactorization into several steps to make it easier to review.
(But I'd anticipate squashing these into one commit in the end,
so I didn't spend a lot of time on the commit messages.)

Also, 0001 in this series is not meant to be committed; what it
does is to add some debug logging to ease comparing runtimes of
different versions of eqjoinsel. I was able to use that to
convince myself that the refactoring steps didn't cost anything
meaningful in performance. Perhaps we could use it to investigate
the right hashing threshold more carefully, too.

There are still a couple of XXX comments in the attached, denoting
loose ends to look at. In particular, I wondered whether the
hash threshold check

if (Min(sslot1.nvalues, sslot2.nvalues) >= EQJOINSEL_MCV_HASH_THRESHOLD)

should use Max() instead --- that is, it might be safer to hash
if either MCV list is long. Or, holding one's head at a different
angle, perhaps the sum of the list lengths should be what's checked?

regards, tom lane

Hi Ilia!

On 13.10.2025 12:08, Ilia Evdokimov wrote:
>
> On 17.09.2025 12:40, Ilia Evdokimov wrote:
>> Hi David,
>>
>> In v2 patch, when the join is reversed we pass the commutator operator
>> Oid to eqjoinsel_semi(), and inside that function we immediately call
>> get_opcode(<commutator operator Oid>). Did you mean for the function
>> to take an operator Oid instead of an here?
>>
>> If that was unintentional, perhaps the cleanest fix is to add a new
>> 'operator' parameter to eqjoinsel_semi() so we can keep passing
>> 'opfuncoid' as before and avoid changing the behavior.
>>
>
> This v3 patch fixes the confusion between operator and function Oids in
> eqjoinsel_semi(). This version restores the previous behavior by keeping
> the function Oid as before and adds an explicit 'operator' parameter so
> both values are available without extra behavior changes.
>
> Do you have any further comments or suggestions on this version?
>

I'm sorry for missing your email with the test results. I'll read up on
it as well as the v3 patch early next week and reply.

--
David Geier

On 14.11.2025 01:21, Tom Lane wrote:
> This didn't look very much like the refactorization that I had in
> mind: I thought we should have one copy of the matching code, not two.
> Also, after looking closer at your patch I realized you were just
> punting for cross-type comparison operators, which I felt was kind
> of sad. It's a little bit tricky to get simplehash.h to go along
> with cross-type hashing, because it wants to use just one hash and
> one equality function. But since those are interface routines we
> are going to supply anyway, we can make them deal with the insert
> and lookup cases differently.

I had considered the cross-type comparison operators and I didn’t see a
clean way to support them, so I intentionally excluded cross-type cases
from hash probing. Your suggestion to switch the hash function in probe
mode is clearly a more correct approach than simply rejecting those
cases. Thanks for the explanation.

>
> So after a bit of hacking I ended up with the attached. I split up
> the refactorization into several steps to make it easier to review.
> (But I'd anticipate squashing these into one commit in the end,
> so I didn't spend a lot of time on the commit messages.)

I reviewed patches 0002-0004 with the refactoring, and I think the
overall approach is excellent. However, I noticed one issue: in
eqjoinsel_semi() the variable 'nmatches' is not initialized and can lead
to undefined behavior when clamped_nvalues2 == sslot2->nvalues. Before
the refactoring it was initialized by zero.

> Also, 0001 in this series is not meant to be committed; what it
> does is to add some debug logging to ease comparing runtimes of
> different versions of eqjoinsel. I was able to use that to
> convince myself that the refactoring steps didn't cost anything
> meaningful in performance. Perhaps we could use it to investigate
> the right hashing threshold more carefully, too.

With 0001 patch I tested the selectivity calculation time for SEMI JOIN
after applying patches 0002-0004, and the time was cut in half. Thank
you for the work on that.

>
> There are still a couple of XXX comments in the attached, denoting
> loose ends to look at. In particular, I wondered whether the
> hash threshold check
>
> if (Min(sslot1.nvalues, sslot2.nvalues) >= EQJOINSEL_MCV_HASH_THRESHOLD)
>
> should use Max() instead --- that is, it might be safer to hash
> if either MCV list is long. Or, holding one's head at a different
> angle, perhaps the sum of the list lengths should be what's checked?
>
> regards, tom lane
>

Hmm… using the sum actually seems like a good idea for me. It may
provide a smoother switch-over point between the two MCV-scanning
algorithms when both list lengths are below the threshold. But this
definitely needs to be validated by measuring different MCV lengths
below the threshold using the 0001 patch.

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

Hi Ilia!

On 13.10.2025 12:08, Ilia Evdokimov wrote:
>
> On 17.09.2025 12:40, Ilia Evdokimov wrote:
>> In v2 patch, when the join is reversed we pass the commutator operator
>> Oid to eqjoinsel_semi(), and inside that function we immediately call
>> get_opcode(<commutator operator Oid>). Did you mean for the function
>> to take an operator Oid instead of an here?
>>
>> If that was unintentional, perhaps the cleanest fix is to add a new
>> 'operator' parameter to eqjoinsel_semi() so we can keep passing
>> 'opfuncoid' as before and avoid changing the behavior.
>>
>
> This v3 patch fixes the confusion between operator and function Oids in
> eqjoinsel_semi(). This version restores the previous behavior by keeping
> the function Oid as before and adds an explicit 'operator' parameter so
> both values are available without extra behavior changes.
>
> Do you have any further comments or suggestions on this version?

I believe it doesn't matter. Because in try_eqjoinsel_with_hashtable()
we bail if the hash function of the LHS and the RHS of the equality
operator is not the same. Hence, if we use the commutator operator or
not doesn't matter.

But maybe I'm overlooking something. Can you provide an example that
fails without your change? If you can, we could add that also to the
regression tests.

Beyond that everything looks good to me. The regression tests also
passed for me.

--
David Geier

Hi Ilia!

On 16.09.2025 17:52, Ilia Evdokimov wrote:
> Hi hackers,
>
> On 10.09.2025 16:56, Ilia Evdokimov wrote:
>> Unfortunately, the JOB benchmark does not contain semi join nodes.
>> However, TPC-DS does. I'll look for the queries with slowest planner
>> times there and check them.
>>
>> I'll need some time to check both join and semi join cases with small
>> and large default_statistics_target. I'll share the results later.
>
> JOIN
> ==============================
>
> I’ve benchmarked the new implementation of eqjoinsel() with different
> values of default_statistics_target. On small targets (1, 5, 10, 25, 50,
> 75, 100) the results are all within statistical noise, and I did not
> observe any regressions. In my view, it’s reasonable to keep the current
> condition that the hash table is not used for default_statistics_target
> = 1. Raising that threshold does not seem useful.
>
> Here are the results for JOB queries (where the effect of semi join is
> not visible due to different data distributions):
>
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> ------------------------------------------------------------------------------------------
> 1                         | 1.00                | 1846.643            |
> 1847.409
> 5                         | 1.00                | 1836.391            |
> 1828.318
> 10                        | 0.95                | 1841.750            |
> 1929.722
> 25                        | 0.99                | 1873.172            |
> 1890.741
> 50                        | 0.98                | 1869.897            |
> 1898.470
> 75                        | 1.02                | 1969.368            |
> 1929.521
> 100                       | 0.97                | 1857.890            |
> 1921.207
> 1000                      | 1.14                | 2279.700            |
> 1997.102
> 2500                      | 1.78                | 4682.658            |
> 2636.202
> 5000                      | 6.45                | 15943.696           |
> 2471.242
> 7500                      | 12.45               | 34350.855           |
> 2758.565
> 10000                     | 20.52               | 62519.342           |
> 3046.819
>

Good that we've confirmed that.

> SEMI JOIN
> ==============================
>
> Unfortunately, in TPC-DS it is not possible to clearly see improvements
> for semi joins. To address this, I designed a synthetic example where
> the data distribution forces the loop to run fully, without exiting
> early, which makes the effect on semi joins more visible. In this setup,
> I also ensured that the length of the MCV array is equal to the chosen
> default_statistics_target.
>
> CREATE TABLE t1 AS
> SELECT CASE
>          WHEN g <= 3000000 * 0.9 THEN (g % 10000) + 1
>          ELSE (g % 1000000) + 10000
>        END AS id
> FROM generate_series(1, 3000000) g;
>
> CREATE TABLE t2 AS
> SELECT CASE
>          WHEN g <= 3000000 * 0.9 THEN (g % 10000) + 10001
>          ELSE (g % 1000000) + 20000
>        END AS id
> FROM generate_series(1, 3000000) g;
>
> ANALYZE t1, t2;
>
> The results of the query are:
>
> SELECT * FROM t1
> WHERE id IN (SELECT id FROM t2);
>
> default_statistics_target | Planner Speedup (×) | Planner Before (ms) |
> Planner After (ms)
> ------------------------------------------------------------------------------------------
> 1                         | 1.12                | 1.191               |
> 1.062
> 5                         | 1.02                | 0.493               |
> 0.481
> 10                        | 0.92                | 0.431               |
> 0.471
> 25                        | 1.27                | 0.393               |
> 0.309
> 50                        | 1.04                | 0.432               |
> 0.416
> 75                        | 0.96                | 0.398               |
> 0.415
> 100                       | 0.95                | 0.450               |
> 0.473
> 1000                      | 9.42                | 6.742               |
> 0.716
> 2500                      | 19.15               | 21.621              |
> 1.129
> 5000                      | 46.74               | 85.667              |
> 1.833
> 7500                      | 73.26               | 194.806             |
> 2.659
> 10000                     | 107.95              | 349.981             |
> 3.242
>

That's some decent speedups, considering that it's planning time.

Thanks for testing the code!

--
David Geier

Hi David,

It looks like there are some technical issues, but Tom and I are
currently discussing version 5 of the patches. Here is the link to the
ongoing discussion [0]. If you have any suggestions or feedback about
the patches, feel free to share them.

[0]:
https://www.postgresql.org/message-id/3026409.1763072514%40sss.pgh.pa.us

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

Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com> writes:
> On 14.11.2025 01:21, Tom Lane wrote:
>> So after a bit of hacking I ended up with the attached. I split up
>> the refactorization into several steps to make it easier to review.

> I reviewed patches 0002-0004 with the refactoring, and I think the
> overall approach is excellent. However, I noticed one issue: in
> eqjoinsel_semi() the variable 'nmatches' is not initialized and can lead
> to undefined behavior when clamped_nvalues2 == sslot2->nvalues. Before
> the refactoring it was initialized by zero.

Argh! Can't believe I missed that.

I experimented with combining all of eqjoinsel_find_matches' outputs
into one struct, but decided that that was uglier than just adding one
more pass-by-reference argument to eqjoinsel_inner/semi.

>> There are still a couple of XXX comments in the attached, denoting
>> loose ends to look at.

In the attached v6, I cleaned up one of the XXX items, deciding that
duplicate entries in the hash table should be coped with not asserted
against. The reason is that we might be working with a comparison
operator that is not exactly the one used to build the MCV list:
the planner is usually pretty cavalier about applying stats that are
only fuzzy matches to what it needs. So it seems possible that we
could find entries that are equal according to the operator we're
using, even though they're unequal according to what ANALYZE used to
compute the MCV list. I didn't actively try to hit that Assert, but
I think a counterexample could be built by using a case-insensitive
collation in a join query.

>> In particular, I wondered whether the
>> hash threshold check
>> if (Min(sslot1.nvalues, sslot2.nvalues) >= EQJOINSEL_MCV_HASH_THRESHOLD)
>> should use Max() instead --- that is, it might be safer to hash
>> if either MCV list is long. Or, holding one's head at a different
>> angle, perhaps the sum of the list lengths should be what's checked?

> Hmm… using the sum actually seems like a good idea for me.

Actually, after sleeping on it it seems like the obvious thing is
to test "sslot1.nvalues * sslot2.nvalues", since the work we are
thinking about saving scales as that product. But I'm not sure
what threshold value to use if we do that. Maybe around 10000?

regards, tom lane

I wrote:
> Actually, after sleeping on it it seems like the obvious thing is
> to test "sslot1.nvalues * sslot2.nvalues", since the work we are
> thinking about saving scales as that product. But I'm not sure
> what threshold value to use if we do that. Maybe around 10000?

Or maybe better, since we are considering an O(m*n) algorithm
versus an O(m+n) one, we could check whether

sslot1.nvalues * sslot2.nvalues - (sslot1.nvalues + sslot2.nvalues)

exceeds some threshold. But that doesn't offer any insight into
just what the threshold should be, either.

regards, tom lane

Hi Tom!

On 17.11.2025 19:44, Tom Lane wrote:
> I wrote:
>> Actually, after sleeping on it it seems like the obvious thing is
>> to test "sslot1.nvalues * sslot2.nvalues", since the work we are
>> thinking about saving scales as that product. But I'm not sure
>> what threshold value to use if we do that. Maybe around 10000?
>
> Or maybe better, since we are considering an O(m*n) algorithm
> versus an O(m+n) one, we could check whether
>
> sslot1.nvalues * sslot2.nvalues - (sslot1.nvalues + sslot2.nvalues)
>
> exceeds some threshold. But that doesn't offer any insight into
> just what the threshold should be, either.

Good idea. How about using that formula and then determining the
threshold with a few experiments? Could be the JOB benchmark Ilia has
already set up or some synthetic test-cases.

Given that there's no one-size-fits-all constant anyways, that seems
good enough to me. Looking at [1], determining to set
MIN_ARRAY_SIZE_FOR_HASHED_SAOP to 9 was done the same way.

We could also include the operator costs for hashing and equality
comparison to make it more precise, in case they're easily accessible
at this point.

--
David Geier

[1]
https://www.postgresql.org/message-id/flat/CAAaqYe8x62%2B%3Dwn0zvNKCj55tPpg-JBHzhZFFc6ANovdqFw7-dA%40mail.gmail.com

David Geier <geidav(dot)pg(at)gmail(dot)com> writes:
> On 17.11.2025 19:44, Tom Lane wrote:
>> Or maybe better, since we are considering an O(m*n) algorithm
>> versus an O(m+n) one, we could check whether
>> sslot1.nvalues * sslot2.nvalues - (sslot1.nvalues + sslot2.nvalues)
>> exceeds some threshold. But that doesn't offer any insight into
>> just what the threshold should be, either.

> Good idea. How about using that formula and then determining the
> threshold with a few experiments? Could be the JOB benchmark Ilia has
> already set up or some synthetic test-cases.

Thinking a bit harder, we are comparing these costs:

1. The old code does m*n comparisons, with next-to-no other overhead.
Sometimes the inner loop will stop early, resulting in fewer
comparisons; but I don't think we have any good handle on how often
that's likely to happen. Let's just consider worst-case numbers.

2. The hash code will do m+n hash-value computations, n hashtable
insertions, and m hashtable searches. (We can assume m >= n.)
The hashtable insertions might sometimes do datum_image_eq
comparisons, but only in the event of a hash value collision,
which is probably rare. The hashtable searches will do comparisons
in the event of a hash match. Unlike the old code, the worst case
is where everything has a match not where nothing has a match, but
we're considering the worst case so let's suppose that the m
searches do n comparisons on the way to finding n matches. (They
could do more comparisons in the event of hash value collisions,
but I'm still supposing those are rare.) So altogether we have
m+n hash-value computations
n comparisons
n hashtable insertions (exclusive of above costs)
m hashtable searches (exclusive of above costs)
1 hashtable creation/destruction, with O(n)+constant cost

What we lack here is a solid idea of the relative costs of those
primitive operations. I think though that it's reasonable to assume
that hash-value computations are about as expensive as comparisons:
data types with expensive comparisons must also have expensive hashing
methods to ensure the hashing gets the right answers for "equal"
values. Hashtable insertions and searches are probably about equally
expensive too, though it's not clear that that's in the same league as
the datatype-dependent operations. And the hashtable creation
certainly has an O(n) cost just from initial zeroing of the array,
though the constant factor in that is likely small.

However, if we fuzz things tremendously and just assume all these
costs are equal, we get 2m + 4n operations altogether, which is
probably not so far off for datatypes with cheap hashing and
comparison (like integers). At the other end of the scale, for
datatypes with expensive operations, we could disregard the hashtable
operations and conclude that there are m + 2n interesting operations.

I'm a little inclined to split the difference and take the hashing
cost as 2m + 2n, which leads to the conclusion that we should switch
to hashing when m*n > 2*(m+n), maybe with a little extra added to
account for the constant-time aspects of the hashtable setup.

It'd be good to validate this model with some tests of course.

> We could also include the operator costs for hashing and equality
> comparison to make it more precise, in case they're easily accessible
> at this point.

Well, we could look those up, but sadly it'd just be
garbage-in-garbage-out. We don't have good estimates for the relative
costs of different hash or equality functions.

regression=# select procost from pg_proc where proname = 'int4eq';
procost
---------
1
(1 row)

regression=# select procost from pg_proc where proname = 'texteq';
procost
---------
1
(1 row)

As long as you are willing to concede that 1 hash operation
should be of comparable cost to 1 comparison, I think it'd
mostly come out in the wash anyway.

regards, tom lane

I wrote:
> Thinking a bit harder, we are comparing these costs:
> [ theoretical arguments trimmed ]

I spent some effort on actually measuring timings of the v6 patch,
and concluded that this is all splitting hairs that we don't need
to split. The actual crossover between hash-loses and hash-wins
is more than what my theoretical argument suggested, but still
probably less than 100 MCVs on each side. I think we should go with

(sslot1.nvalues + sslot2.nvalues) >= 200

and call it good.

To arrive at this result, I built the v6 patchset with
EQJOINSEL_MCV_HASH_THRESHOLD changed to either 0 (to force hashing)
or 1000000 (to prevent it). I then ran the attached scripts with
different values of "nstats" and collected timings from the postmaster
log output produced by the 0001 patch.

The scripts are designed to test both the cheap-comparisons scenario
(integer columns) and the expensive-comparisons scenario (text columns
with a case-insensitive ICU collation). My motivation for splitting
them into a setup and a test step was to allow the tests to be run
repeatedly against the same underlying data. (Although I soon realized
that because VACUUM ANALYZE takes a random sample each time, the stats
we're working from aren't totally the same each time anyway.) Also
you'll notice that the test data is based on log(random()), which
I did to roughly approximate a zipfian distribution. If you remove
the log() call you'll get a flat distribution instead, but it didn't
seem to change the conclusions much.

regards, tom lane

On 19.11.2025 03:19, Tom Lane wrote:
> I wrote:
>> Thinking a bit harder, we are comparing these costs:
>> [ theoretical arguments trimmed ]
>
> I spent some effort on actually measuring timings of the v6 patch,
> and concluded that this is all splitting hairs that we don't need
> to split. The actual crossover between hash-loses and hash-wins
> is more than what my theoretical argument suggested, but still
> probably less than 100 MCVs on each side. I think we should go with
>
> (sslot1.nvalues + sslot2.nvalues) >= 200
>
> and call it good.
>
> To arrive at this result, I built the v6 patchset with
> EQJOINSEL_MCV_HASH_THRESHOLD changed to either 0 (to force hashing)
> or 1000000 (to prevent it). I then ran the attached scripts with
> different values of "nstats" and collected timings from the postmaster
> log output produced by the 0001 patch.
>
> The scripts are designed to test both the cheap-comparisons scenario
> (integer columns) and the expensive-comparisons scenario (text columns
> with a case-insensitive ICU collation). My motivation for splitting
> them into a setup and a test step was to allow the tests to be run
> repeatedly against the same underlying data. (Although I soon realized
> that because VACUUM ANALYZE takes a random sample each time, the stats
> we're working from aren't totally the same each time anyway.) Also
> you'll notice that the test data is based on log(random()), which
> I did to roughly approximate a zipfian distribution. If you remove
> the log() call you'll get a flat distribution instead, but it didn't
> seem to change the conclusions much.
Thanks for working out the details!

I've ran your script on my development machine with 1000, 100 and 50
MCVs with the following results. As the runtimes had quite some variance
I didn't bother trying more variations. I think your proposal to go with
200 is fine.

nstats | off INT | off TEXT | on INT | on TEXT
-------------------------------------|------
1000 | 697 | 8907 | 14 | 2417
100 | 13.7 | 213 | 2.3 | 239
50 | 1.4 | 7.6 | 1.5 | 49

The results suggest that the hash function for the non-deterministic
collation is really slow. If we could properly include the operator
cost, we could enable the optimization earlier in the case of simple
data types such as INT. That can be future work.

--
David Geier

On 19.11.2025 18:38, David Geier wrote:
> On 19.11.2025 03:19, Tom Lane wrote:
>
>> I spent some effort on actually measuring timings of the v6 patch,
>> and concluded that this is all splitting hairs that we don't need
>> to split. The actual crossover between hash-loses and hash-wins
>> is more than what my theoretical argument suggested, but still
>> probably less than 100 MCVs on each side. I think we should go with
>>
>> (sslot1.nvalues + sslot2.nvalues) >= 200
>>
>> and call it good.
>>
>> To arrive at this result, I built the v6 patchset with
>> EQJOINSEL_MCV_HASH_THRESHOLD changed to either 0 (to force hashing)
>> or 1000000 (to prevent it). I then ran the attached scripts with
>> different values of "nstats" and collected timings from the postmaster
>> log output produced by the 0001 patch.
> Thanks for working out the details!
>
> I've ran your script on my development machine with 1000, 100 and 50
> MCVs with the following results. As the runtimes had quite some variance
> I didn't bother trying more variations. I think your proposal to go with
> 200 is fine.
>
> nstats | off INT | off TEXT | on INT | on TEXT
> -------------------------------------|------
> 1000 | 697 | 8907 | 14 | 2417
> 100 | 13.7 | 213 | 2.3 | 239
> 50 | 1.4 | 7.6 | 1.5 | 49
>
> The results suggest that the hash function for the non-deterministic
> collation is really slow. If we could properly include the operator
> cost, we could enable the optimization earlier in the case of simple
> data types such as INT. That can be future work.

LGTM

For simple types (integer columns), both algorithms finish in a couple
milliseconds when the MCV counts are under 100, and the difference
between them is very small (JOB results show the same trend). For text
types, the planning time shifts gradually from one algorithm to the
other around that range, without any sharp transition. And it seems to
me that the current criterion is a reasonable compromise, without
requiring us to complicate the threshold any further.

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

David Geier <geidav(dot)pg(at)gmail(dot)com> writes:
> On 19.11.2025 03:19, Tom Lane wrote:
>> I spent some effort on actually measuring timings of the v6 patch,
>> and concluded that this is all splitting hairs that we don't need
>> to split. The actual crossover between hash-loses and hash-wins
>> is more than what my theoretical argument suggested, but still
>> probably less than 100 MCVs on each side. I think we should go with
>> (sslot1.nvalues + sslot2.nvalues) >= 200
>> and call it good.

> I've ran your script on my development machine with 1000, 100 and 50
> MCVs with the following results. As the runtimes had quite some variance
> I didn't bother trying more variations. I think your proposal to go with
> 200 is fine.

Thanks for double-checking it!

> nstats | off INT | off TEXT | on INT | on TEXT
> -------------------------------------|------
> 1000 | 697 | 8907 | 14 | 2417
> 100 | 13.7 | 213 | 2.3 | 239
> 50 | 1.4 | 7.6 | 1.5 | 49

These numbers look pretty similar to what I got. One thing I don't
really understand is that the crossover point where hash is faster
than loop seemed much lower for integers than text. In your above,
hash is already competitive at nstats=50 and winning by a good margin
at 100 for integer, but it's still behind for text at 100. This
makes little sense to me, as the hash-algorithm overhead ought to be
the same in both cases so you'd expect that overhead to make less
difference for text. I suspect that my initial guess that hash-value
computation is about as expensive as a comparison is wrong --- if you
look at hashint4, it's not super expensive, but for sure it's slower
than int4eq. But still, if you suppose hash-value is more expensive
than comparisons, that still doesn't lead to the conclusion that
integers should have a lower crossover point. So there's some effect
here that we're not accounting for, and I'm not sure what.

FTR, the results I got were (in microseconds per selectivity call)

--- looping --- --- hashing ---
nstats int4 text int4 text

25 0.52241 0.54468 0.19544 10.1506
50 1.35082 20.9971 1.04862 80.5282
100 19.8381 288.855 2.74378 274.799
200 64.7243 1129.51 5.3543 543.265
500 320.178 5229.23 13.3851 1366.19
1000 934.281 12774.6 29.1749 2740.84
2000 2569.61 23840.3 64.7265 5491.69
5000 11280.2 63883.0 191.85 13800.4
10000 41249.3 187174 395.337 27642.7

The integer results might lead one to want a lower threshold,
but on the other hand those numbers are small enough in absolute
terms that I think it doesn't matter. It's more pressing to not
regress the results with an expensive datatype, so I'm content
with using 200 as the cutoff.

> The results suggest that the hash function for the non-deterministic
> collation is really slow. If we could properly include the operator
> cost, we could enable the optimization earlier in the case of simple
> data types such as INT. That can be future work.

I think there's other factors here we'd have to figure out :-(.

Anyway, I'll go ahead and push this with the
(sslot1.nvalues + sslot2.nvalues) >= 200
rule. Thanks for working on it!

regards, tom lane