Fl4m3Ph03n1x

Fl4m3Ph03n1x

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?

Showing Posts 1 to 10

jola

jola

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.

sorentwo

sorentwo

Oban Core Team

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?

NobbZ

NobbZ

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…

Fl4m3Ph03n1x

Fl4m3Ph03n1x OP

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.

dimitarvp

dimitarvp

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

mguilmineau

mguilmineau

I’m in the same situation but with lots more keys (a few hundreds) and dets. From this post [erlang-questions] Fetching several ets keys 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

jola

jola

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.

mguilmineau

mguilmineau

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

kip

kip

ex_cldr Core Team

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!

Where Next? Top

Trending in Questions Top

RSP87
I’m working on a project that simulates the bumbl example in the programming phoenix book. It acts almost like an email client. We have a...
New
nseaSeb
Hello, I know there is an approach for handling lists that allows for optimized traversal, but I can’t recall the specific method (somet...
New
RemyXRenard
I’m seeing that a list inside a Kino.DataTable will be interpreted as a charlist, even if the Kino.configure() is set to charlists: :as_l...
New
velrest
So my question is quite simple and i have found no conclusive answer on forum, google or AI. Should we use :erlang.float for Integer to ...
New
samoloth
Hi, I’ve just set up an application with ash_authentication. There is only magic link strategy for now, so there is no confirmation add o...
New
brecabral
Documentation While reading the Scoped Routes section, I noticed that the documentation currently refers to a problem without explainin...
New
FlyingNoodle
If a change or preparation module uses Ash.Changeset.get_argument/2 or Ash.Query.get_argument/2 (or any of the other get_argument functio...
New

Other Trending Topics Top

mudasobwa
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
New
marciok
Hi there! We created Gust: A task orchestrator inspired by Airflow. For those who have never heard about Aiflow, it’s a Python-based wor...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Dmk
Xamal is a deployment tool for Elixir apps that deploys native releases to bare metal servers over SSH. It’s a port of GitHub - basecamp/...
New
netoum
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
webofbits
With AI doing more of the implementation work, I’ve been wondering how much coding I should deliberately keep doing myself. My main conc...
#ai
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews