Thread
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-07-29T14:07:13Z
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.