Best way to get multiple keys from static ETS table

Questions / Help
1

Background

I have an ets table that has, for each key, a list of items. ETS tables have O(1) complexity when using :ets.lookup, as we all know and they are super fast, but for my specific use case, I need to ask to the ets table for more than 1 key at a time.

This means I have 2 options:

  1. Perform multiple lookups
  2. Perform a match or select on the keys

Multiple lookups

I don’t really like this approach because it would mean my operation is not atomic. This is a big no no.

Match or Select on keys

This is my preferred approach since I want the operation to be as efficient as possible. I am also not going to look for patterns in keys, I am simply going to look directly for keys that match my spec, so it should be fast.

I do have several questions about match and select though (see Questions section)

Issue

The problem here is that I don’t know how to use :ets.match or it’s select variant correctly. This is an example:

iex(27)> table = :ets.new(:table, [:public])
#Reference<0.830523521.2311716867.20185>
iex(28)> :ets.insert(table, {:a, [{:banana, :orange, 10}, {:tomato, :potato, 6}]})
true
iex(29)> :ets.insert(table, {:b, [{:car, :moto, 1}, {:plane, :heli, 60}]})        
true
iex(30)> :ets.tab2list(table) 
[
  b: [{:car, :moto, 1}, {:plane, :heli, 60}],
  a: [{:banana, :orange, 10}, {:tomato, :potato, 6}]
]
ex(32)> :ets.match(table, [:a, :b]) # I want to get the values from both keys :a :b
[]

Questions

  1. What am I doing wrong?
  2. How do I optimize my match queries so they are atomic? From the docs:

Traversals using match and select functions may not need to scan the entire table depending on how the key is specified. A match pattern with a fully bound key (without any match variables) will optimize the operation to a single key lookup without any table traversal at all.

  1. The data on my table will never change. Does it matter if I make the table an ordered_set or are the gains for match and select not worth it?
2

Looked at this yet?

http://erlang.org/doc/apps/erts/match_spec.html

3 
iex(13)> :ets.select(table, [{{:"$1", :_}, [{:or, {:==, :"$1", :a}, {:==, :"$1", :b}}], [:"$_"]}]) 
[
  b: [{:car, :moto, 1}, {:plane, :heli, 60}],
  a: [{:banana, :orange, 10}, {:tomato, :potato, 6}]
]

Boom! You can adjust the match body to what you’re interested in. Also note that the match head has to match the table format.

I have a weird fascination with match specs.

7 Likes
4

This sounds like a good use case for :persistent_term. The data will never change so there isn’t a write penalty and you get extremely fast reads.

I’m curious though, if the data doesn’t change why are you concerned about atomicity?

4 Likes
5

You can’t have a fully bound key in a match spec that checks for many keys. Either do one lookup per key and throw away atomicity (which might not be a great deal as @sorentwo already mentioned) or build a matchspec as shown by @jola (perhaps even use ex2ms and just write functions rather than weirdly nested tuples).

But you’ll need to give up either atomicity or O(1) reads…

5 Likes
6

I had no idea about persistent terms. You also make an excellent point about atomicity. What I want are extremely fast reads above all things, I thought atomicity could help with this.

7

The persistent_term module is a very recent addition. And a very useful one, too!

1 Like
8

I’m in the same situation but with lots more keys (a few hundreds) and dets. From this post http://erlang.org/pipermail/erlang-questions/2012-February/064214.html it appears that I should not use jola’s approach but somehow feed my keys into a key. I wasn’t able to do this from elixir. Any suggestion?
:dets.select( :my_dets_table,
[ { { :Key, :_ }, [], [ :"$_" ] } || :Key <- my_keys ] )
===> undefined function <-/2

9

The erlang code from that mailinglist could be translated into Elixir like this (using the sample code from the OP):

iex(5)> my_keys = [:b, :a]
[:b, :a]
iex(6)> :ets.select(table, (for key <- my_keys, do: {{key, :_}, [], [:"$_"]}))
[
  a: [{:banana, :orange, 10}, {:tomato, :potato, 6}],
  b: [{:car, :moto, 1}, {:plane, :heli, 60}]
]

Basically, it uses the comprehension to build a list of match specs, where each one has a fully bound key.

7 Likes
10

Confirmed, this works well and is indeed measurably faster than lookups in an Enum.map.
Thank you very much jola for the guidance!!

11

Having spent a few hours now on match specs, my head hurts. Very much hoping @jola is still weirdly fascinated by them :slight_smile:

Dets Table layout

My dets/ets table has a key of the format {x_min, x_max, y_min, y_max} and value of a bunch of polygons. Basically the key describes a bounding box.

Objective

Return all the records that match the key with some guards

What I’ve tried

This is what I’ve been working on - until I realised this is likely doing a match on the value, not the key.

  # Match specification, which I assumed is matching only on the key
  # but probably isn't
  defp match_spec(%{coordinates: {lng, lat}}) do
    [
      {
        {:"$1", :"$2", :"$3", :"$4"},
        [
          {:andalso, {:>=, lng, :"$1"}, {:"=<", lng, :"$2"}},
          {:andalso, {:>=, lat, :"$3"}, {:"=<", lat, :"$4"}}
        ],
        [:"$_"]
      }
    ]
  end

# All keys are a 4-tuple {x_min, x_max, y_min, y_max}
iex> :dets.first TzWorld.Backend.Dets                                            
{-92.186268, -91.750739, 20.002558, 20.420965}
iex> :dets.select TzWorld.Backend.Dets, match_spec(%{coordinates: {3.2, 45.32}})
[]

Any and all help much appreciated!

12

Match patterns/specs are a difficult DSL. Have you looked at https://github.com/ericmj/ex2ms?

13

Yes, I have, that’s where I started :grin: but I am not at all clear how to make a key search and I think that’s the main issue here.

14

Afaik there is no special keysearch in ets. If you want to sesrch by key search by the first tuple element of items in the ets table.

15

Ahhhh, thanks for that. I did not work out that {k, v} nature of the select construction. All good now, thanks.

16

Well, ETS does not need to be 2 element tuples with the key beeing the first element… When you create the table with :ets.new/2, you can specify the position of the key using the :keypos option.

You can then use :ets.lookup/2 to lookup all entries that have match your key.

1 Like
17

Thanks @NobbZ. :ets.lookup/2 appears to be an exact match, so :ets.select/2 is the right fit for my purpose but thanks for letting me know that the key isn’t necessarily the first element in the tuple.