[erlang-questions] Binary pattern matching on ETS

Ulf Wiger ulf@REDACTED
Mon Oct 27 11:06:42 CET 2014


FWIW, the kvdb database [1] allows for select operations on e.g. ets-based tables, including prefix match on binary keys.

It does this through a little trickery. Since the match syntax doesn’t support prefix notation for binaries, and kvdb keys are always some form of binary encoding, specifying a list prefix, e.g. “aa” ++ ‘_’ in the head pattern will indicate to kvdb that you want to match on prefix, and the match spec will be modified. More specifically, kvdb will derive a proper prefix and do a prefix_match using ‘next’ iteration, and then matching the objects using ets:match_spec_run/2.

Example:

Eshell V5.10.3  (abort with ^G)
1> kvdb:start().
starting kvdb
KVDB Dbs = []
ok
2> kvdb:open(db,[{backend,ets}]).
File = "db.db"
{ok,<0.53.0>}
3> kvdb:add_table(db,t,[]).
ok
4> kvdb:put(db,t,{<<"aaaaa">>,1}).
ok
5> kvdb:put(db,t,{<<"aabbb">>,2}).
ok
6> kvdb:put(db,t,{<<"aabcc">>,3}).
ok
7> kvdb:select(db,t,[{{<<"aa">>,'_'},[],['$_']}]).       
{[],#Fun<kvdb_direct.34.51139377>}
8> kvdb:select(db,t,[{{"aa" ++ '_','_'},[],['$_']}]).
{[{<<"aaaaa">>,1},{<<"aabbb">>,2},{<<"aabcc">>,3}],
 #Fun<kvdb_direct.34.51139377>}
9> kvdb:select(db,t,[{{"aab" ++ '_','_'},[],['$_']}]).
{[{<<"aabbb">>,2},{<<"aabcc">>,3}],
 #Fun<kvdb_direct.34.51139377>}

This is obviously (significantly) slower than doing a normal ets:select() or mnesia:[dirty_]select(), but it’s mainly a question of constant-factor overheads. Kvdb clearly puts semantics before performance. ;-)

BR,
Ulf W

[1] https://github.com/Feuerlabs/kvdb

On 27 Oct 2014, at 10:02, Lukas Larsson <lukas@REDACTED> wrote:

> Hello,
> 
> On Thu, Oct 23, 2014 at 11:35 AM, Eduardo Gurgel <edgurgel@REDACTED> wrote:
> Is it possible to match the prefix of a binary using ETS match spec?
> 
> It is not possible.
>  
> And if it's not, is it a limitation or just a missing implementation?
> 
> At the moment it is both :)
> 
> I've never tried to do something like that, but I would guess you work around this limitation by extracting what you have to match from the binary into a surrounding tuple before doing the insert. Right now there is afaik no plan to add the possibility to do this.
> 
> Lukas
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger, Co-founder & Developer Advocate, Feuerlabs Inc.
http://feuerlabs.com



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20141027/af94cbde/attachment.htm>


More information about the erlang-questions mailing list