Performance regression for ets:select/3 with a map in the keys

[sorentwo]

Describe the bug
There is a severe performance regression for ets:select/3 when keys contain a map.

To Reproduce
This benchmark (in Elixir, sorry) reproduces the issue and demonstrates the difference between OTP 26.2.4 and 26.2.5.

Here's the relevant portion of the benchmark for OTP 26.2.5:

Name                     ips        average  deviation         median         99th %
lookup                1.62 M      616.07 ns  ±1798.74%         584 ns         791 ns
select_reverse        1.21 M      823.61 ns  ±1503.76%         667 ns         958 ns
select             0.00100 M   995660.57 ns     ±2.84%      982750 ns  1058731.74 ns

Comparison:
lookup                1.62 M
select_reverse        1.21 M - 1.34x slower +207.54 ns
select             0.00100 M - 1616.16x slower +995044.50 ns

Removing the map portion of the key alleviates the issue, and adds a nice speed boost for all operations:

Name                     ips        average  deviation         median         99th %
lookup                3.61 M      276.76 ns  ±9550.30%         250 ns         333 ns
select_reverse        2.21 M      452.09 ns  ±2259.09%         458 ns         583 ns
select                2.20 M      454.81 ns  ±2213.31%         458 ns         583 ns

Comparison:
lookup                3.61 M
select_reverse        2.21 M - 1.63x slower +175.33 ns
select                2.20 M - 1.64x slower +178.05 ns

Expected behavior
There shouldn't be such an extreme difference in performance.

Affected versions
OTP 26.2.5

Additional context
Originally reported in this oban issue.

[jhogberg]

Thanks for your report, I hate to say it but this is roughly the performance difference I’d expect.

The partially matching nature of maps (#{ a := b } matching all maps with that pair) makes it impossible to bind keys which turns your query into a linear scan, completely tanking performance.

I will look into adding a way to match maps exactly, but that will not make it in before OTP 27.1 at the earliest.

[sorentwo]

Thanks for the quick reply. The performance difference makes sense when you consider that it's a linear scan, which also explains the difference between select and select_reverse.

I've worked around the issue on my side for now, but I suspect this could trip up other applications.

[michalmuskala]

I think this somewhat comes from the ETS interface completely intertwining access by patterns and access by key. In my opinion the proper, long-term solution would be to separate the two. They have very different performance characteristics where a difference between key lookup vs linear scan can be very subtle and unexpected - they should be separate APIs.

[jhogberg]

Aren't they separated already? lookup and friends access by key, whereas select and friends access by pattern.

[tsloughter]

@jhogberg right, but with no lookup_replace and such we lose a lot of functionality when wanting to lookup on a key -- being unable to do atomic and isolated actions on elements based on a key lookup.

In OpenTelemetry we, for now, not sure what long term will look like, do binary_to_term on the map to keep it from using variable matching.

[sorentwo]

In OpenTelemetry we, for now, not sure what long term will look like, do binary_to_term on the map to keep it from using variable matching.

For the metrics mentioned above I switched to phash2 to hash the map, then stored the map outside of the key. Thankfully it was a simple change.

[tsloughter]

@ferd had a similar idea. Though his was to still have the map in the key and use an ordered set. Since wouldn't you need to use a bag if you are using phash2 with the map outside of the key? That wouldn't work for us particularly since we use select_replace which doesn't support bag.

But I guess if you are already using bag there is no question that phash2 with guard makes the most sense :)

[tsloughter]

Oh I missed this:

I will look into adding a way to match maps exactly, but that will not make it in before OTP 27.1 at the earliest.

Yaya! Solves my request for lookup_replace :)

[sorentwo]

Since wouldn't you need to use a bag if you are using phash2 with the map outside of the key? That wouldn't work for us particularly since we use select_replace which doesn't support bag.

The key is itself a tuple of a series name, a hash of the labels, and a timestamp. The table is an ordered_set, but we have to use lookup followed by insert because it's merging values and not replacing them.