Thread
Commits
Same data as JSON:
GET /api/v1/messages/:b64id/commits
the thread's linked commits as JSON, with link sources.
API reference →
-
Speed up eqjoinsel() with lots of MCV entries.
- 057012b205a0 19 (unreleased) landed
-
Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-07-21T13:55:56Z
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.
-
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.
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-03T16:53:51Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-09-03T20:26:26Z
Ilia Evdokimov <ilya.evdokimov@tantorlabs.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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-04T11:05:50Z
On 03.09.2025 23:26, Tom Lane wrote: > Ilia Evdokimov <ilya.evdokimov@tantorlabs.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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-05T14:03:02Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-08T07:11:24Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-08T10:08:59Z
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 -
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-08T10:35:50Z
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 -
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-08T10:45:06Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-08T10:56:07Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-08T11:00:10Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-08T13:45:27Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-08T14:36:35Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-09T07:29:36Z
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 -
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-09-09T09:22:32Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-10T13:56:03Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-16T15:52:47Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-09-17T09:40:01Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-10-13T10:08:02Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-10-27T15:50:33Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-10-30T10:07:22Z
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/
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-03T21:55:45Z
Ilia Evdokimov <ilya.evdokimov@tantorlabs.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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-11-10T14:20:42Z
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/
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-13T22:21:54Z
Ilia Evdokimov <ilya.evdokimov@tantorlabs.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 -
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-11-14T17:37:33Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-11-17T15:17:25Z
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/
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-11-17T15:25:35Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-11-17T15:28:23Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-11-17T15:42:38Z
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/
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-17T18:30:13Z
Ilia Evdokimov <ilya.evdokimov@tantorlabs.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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-17T18:44:33Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-11-18T17:54:16Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-18T19:16:54Z
David Geier <geidav.pg@gmail.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 -
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-19T02:19:46Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
David Geier <geidav.pg@gmail.com> — 2025-11-19T15:38:53Z
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
-
Re: Use merge-based matching for MCVs in eqjoinsel
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-11-19T15:52:08Z
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/
-
Re: Use merge-based matching for MCVs in eqjoinsel
Tom Lane <tgl@sss.pgh.pa.us> — 2025-11-19T17:05:39Z
David Geier <geidav.pg@gmail.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