Re: Use merge-based matching for MCVs in eqjoinsel - Mailing list pgsql-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.

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.