Binary pattern matching on ETS

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Binary pattern matching on ETS

Eduardo Gurgel-2
Is it possible to match the prefix of a binary using ETS match spec?

And if it's not, is it a limitation or just a missing implementation?

Thanks in advance,

--
Eduardo

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Binary pattern matching on ETS

Lukas Larsson-8
Hello,

On Thu, Oct 23, 2014 at 11:35 AM, Eduardo Gurgel <[hidden email]> 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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Binary pattern matching on ETS

Ulf Wiger-6

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


On 27 Oct 2014, at 10:02, Lukas Larsson <[hidden email]> wrote:

Hello,

On Thu, Oct 23, 2014 at 11:35 AM, Eduardo Gurgel <[hidden email]> 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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger, Co-founder & Developer Advocate, Feuerlabs Inc.




_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Binary pattern matching on ETS

Eduardo Gurgel-2
Thank you, Lukas and Ulf. I'll check out both proposed solutions.

I needed this prefix matching on gproc, so I don't think kvdb will be a possible solution for me in this case .I will probably need to see if I can use a simple string instead of a binary to tag my processes.

Regards,

--

Eduardo

On 27 October 2014 23:06, Ulf Wiger <[hidden email]> wrote:

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


On 27 Oct 2014, at 10:02, Lukas Larsson <[hidden email]> wrote:

Hello,

On Thu, Oct 23, 2014 at 11:35 AM, Eduardo Gurgel <[hidden email]> 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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger, Co-founder & Developer Advocate, Feuerlabs Inc.






--
Eduardo

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Binary pattern matching on ETS

dmkolesnikov
Hello,

I needed this prefix matching on gproc

You should mentioned that earlier. Use tuples as keys as Lukas said.

- Dmitry

On 28 Oct 2014, at 03:20, Eduardo Gurgel <[hidden email]> wrote:

Thank you, Lukas and Ulf. I'll check out both proposed solutions.

I needed this prefix matching on gproc, so I don't think kvdb will be a possible solution for me in this case .I will probably need to see if I can use a simple string instead of a binary to tag my processes.

Regards,

--

Eduardo

On 27 October 2014 23:06, Ulf Wiger <[hidden email]> wrote:

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


On 27 Oct 2014, at 10:02, Lukas Larsson <[hidden email]> wrote:

Hello,

On Thu, Oct 23, 2014 at 11:35 AM, Eduardo Gurgel <[hidden email]>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
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger, Co-founder & Developer Advocate, Feuerlabs Inc.






-- 
Eduardo
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions