Re: Use merge-based matching for MCVs in eqjoinsel

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.