Search code examples
erlangets

What is the ordering in tab2list for bag ETS?


I was playing with bag table a bit:

30> W = ets:new(w, [bag]).
#Ref<0.616284823.3413770252.143386>
31> ets:insert(W, [{1, a}, {2, a}, {1, b}, {2, b}, {a}, {b}]).
true
32> ets:tab2list(W).
[{1,a},{1,b},{b},{a},{2,a},{2,b}]

I totally don't understand how does the ordering work here. Why are the smallest tuples in the middle? How are they greater than {1,_} but smaller than {2,_}?


EDIT: the results in the example come from OTP21


Solution

  • According to the docs for ets:lookup/2:

    The time order of object insertions is preserved.

    That means that when two tuples with the same key are inserted, their ordering is determined by the time of insertion. I don't know if that also holds true for ets:tab2list/1. In any case, that is the ONLY guarantee. And, your results seem to behave consistently with that ONE guarantee.

    I looked at the source code for ets:tab2list/1, and it calls ets:first/1--not ets:lookup/2. The docs for ets:first/1 say:

    For an ordered_set table, the first key in Erlang term order is returned. For other table types, the first key according to the internal order of the table is returned.

    Because the order of the returned keys from an ordered_set is mentioned, but the order of the returned keys from a bag is said to be "according to the internal order of the table", I don't think you can count on ets:first/1 to return the keys in ANY order. Therefore, you must treat the list returned by tab2list/1 as unordered.

    And, straight from rvirding himself:

    With a set, bag or duplicate_bag the order in which you get the keys is internal. This irrespective of whether you use match, select or first and next. I was referring to the ordering of elements of one key in a bag or duplicate_bag returned when doing a lookup, match or select [where the time order of object insertions is preserved; the first object inserted with the specified key is the first in the resulting list, and so on.]

    [Otherwise,] the internal ordering of keys is not defined and you can never depend on it because as you say it can change between releases. Except of course for type ordered_set where the ordering is defined.

    https://elixirforum.com/t/retrieval-in-ets/10413/2