ETS queries with keys which look like meta-variables

Questions / Help
, ,
1

ETS match patterns have some meta-variables, like '$1' , '_' etc., but I am not aware of a way to escape them (at least in the guard and body, you can do {const, '_'}, but that doesn’t seem to be a thing in patterns), so if you have an entry in your ETS table whose key is the atom '_' , searching for it seems difficult, since you need to resort to less-efficient queries, or manually escape these names (which can be hard if you’re working with a legacy system).

Is there a built-in way in ETS to make using ets:select etc., easier to work with if you have keys which overlap with the ETS meta-variables, such as a way to escape them in match specs?

2

One quick way would be to do an equality check in the guard, but I don’t know if this is the best way. ets:fun2ms does the following:

3> ets:fun2ms(fun ({X,Y}) when X =:= ‘$1’ → [‘$2’,Y] end).
[{{‘$1’,‘$2’},
[{‘=:=’,‘$1’,{const,‘$1’}}],
[[{const,‘$2’},‘$2’]]}]

3

The main issue is that this will perform a full table scan vs having the key in the pattern can do a fast lookup.

4

Yep, I am keen to continue to make good use of the index.

5

The problem here is that ets:match and ets:select both interpret their input pattern or match spec as some form of code which is why there is this specific syntax for a variable, the '$1'. This is because there is no way to give an unbound variable as an argument to a call.

The only way I can think of to get past this is to use ets:lookup which you give the exact key you want to find. That will do a fast lookup. The downside is you will get all the whole objects with that key.

Pest eller kolera (plague or cholera) as we would say in swedish.

6

{const,Term} is allowed in matches everywhere except MatchHeads.
Is there a reason it could not be allowed, at least in the form
{const, MatchVariable | ‘_’ | const}, in MatchHeads as well?

Would it be worth writing up an EEP about this?

7

Is there a reason it could not be allowed

I suspect the main one would be backward compatibility, or the noise/complexity of adding a new set of options/overloads. Otherwise, in principle, it does feel like an odd restriction at the moment, and has bitten me in practice.

1 Like
8

I don’t know why {const,Term} was not allowed in MatchHead from the start. A problem to introduce it now is backward compatibility.

1 Like
9

I’ve checked what qlc module does under the hood. It falls back to filtering the results via list comprehensions when a meta-variable is found in place of a constant:

17> qlc:info(qlc:q([K || {K, '$1'} <- ets:table(foo)])).   
"qlc:q([ \n       K ||\n           {K, '$1'} <- ets:table(foo)\n      ])"

Changing '$1' to a regular atom allows qlc to employ ets:select, as one would expect:

18> qlc:info(qlc:q([K || {K, foo} <- ets:table(foo)])). 
"ets:table(foo, [{traverse, {select, [{{'$1', foo}, [true], ['$1']}]}}])"

Based on that, I’d say there’s no way to escape meta-variables in the match specification. In conclusion, use qlc and maybe some day your query will magically become optimized.

10

It’s funny you say that, because one of the reasons I was asking this was for my ets:fun2ms optimisation pass. qlc is a bit more complicated though, so I am not looking to optimise that at the moment, but maybe someone will be inspired by my work.