Re: Use merge-based matching for MCVs in eqjoinsel

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/