Re: Use merge-based matching for MCVs in eqjoinsel

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