Why is there no ordered_bag type ETS table?

Questions / Help
1

It looks like ordered_bag is also very useful. For example, to record the persons with the max score, then the persons with the next max score etc. I wonder why such a type is not introduced in ETS. Or this kind of use case can be mimic using other types of ETS?

1 Like
2

I probably would suggest just a simple set with {Key,gb_trees:tree({Score,...}) | list({Score, ...})}; if you use a list() then manually sort it using lists:keysort(1, List).

Two problems though:

  1. slower as you have to read in the whole object, update it, and then write it out
  2. you will need to marshal updates through a single process as ets:select_replace/2 uses a matchspec, not an arbitrary function

This should be fine up to a couple of 100->1000 updates per second per ETS table though so depends on your use case…so unless you are doing a pachinko simulator…

1 Like
3

Oh, as I am an idiot (I blame pre-coffee and not having had my breakfast sausage roll) you will not be able to use gb_trees as you cannot have duplicate keys; so use list() instead with lists:keysort/2.

Sorry if that sent you off on a wild goose chase!

2 Likes
4

Usually it’s done by storing a “list of people with the same score” in an ordered_set table.

1 Like
5

That solution may have some performance issue: To add a member, the list of people with the same score need to be serialized and read out from ETS into the current process, add the member to the list, then the new list will have to be serialized and copied back into ETS. If ETS can support some kind of update_spec (similar to match_spec but for updating) which can be used to precisely update the terms within ETS that will greatly help.

1 Like
6

You thinking of ets:select_replace/2 ?

1 Like
7

Didn’t notice this method. Yes it looks quite promising. I played around with it and find that it doesn’t support updating map in place.
For example, the change to a list works:
ets:fun2ms(fun({K, L}) when is_list(L) → {K, [marker | L]} end).
Output: [{{‘$1’,‘$2’},[{is_list,‘$2’}],[{{‘$1’,[marker|‘$2’]}}]}]
But for something similar with map:
ets:fun2ms(fun({K, Map}) when is_map(Map) → {K, Map#{marker => true}} end).
Error: the language element map (in body) cannot be translated into match_spec
{error,transform_error}

1 Like
8

Let’s say you have a bag with primary key K and attribute A. If you have frequent updates (insert or delete {K,A}) or membership tests (is {K,A} present?) and less frequent “get all with key K”, then you may want to emulate the bag as an ordered_set with {K,A} keys. Of course, if the list of As always are short then don’t bother.

It’s perhaps less of an issue for plain ETS, but we’ve had write-amplification issues with Mnesia tables using the naive key-plus-list approach. Before we migrated off Mnesia we tended use a mix of emulated bags as above, and tables where the “set of As” were represented as a B-tree.

1 Like
9

Not sure if I’m just repeating what @mikpe was saying, but using an order_set with ‘Score’ being part of the key should give you fast, sorted access.

Pseudo-code

-define(OPS, #{eq => '=:=',
               lt => '<',
               gt => '>',
               lte => '=<',
               gte => '>='}).
-type name() :: binary().
-type key() :: {number(), name()}.
-record(person, {key :: key(), dob :: calendar:date()}).

find_by_score(Score, Comp) when is_map_key(Comp, ?OPS) ->
  #{Comp := Operator} = ?OPS,
  Match = [{#person{key = {'$1', '_'}, dob = '_'},
           [{Operator, '$1', {const, Score}}],
           ['$_']}],
  ets:select(scores, Match).
1 Like
10

Thank you for providing such a detailed code snippet. That helps a lot to clarify things. This topic also leads me to open a proposal to add some support to in place add/remove key/values of map in ets:select_replace with match spec:

1 Like