ExDatalog.Storage.ETS (ExDatalog v0.2.0)

Copy Markdown View Source

ETS-based storage implementation using per-relation tables.

This backend stores facts in ETS tables (one per relation), providing off-heap storage that reduces GC pressure for large fact sets (>100K tuples) and enables concurrent read access. Tables are named ex_datalog_<relation> for observability in :observer and iex.

Key design: wrapped tuples

ETS :set tables use the first element of a tuple as the key. For Datalog facts like {:alice, :bob} and {:alice, :carol}, the key :alice would collide — the second would overwrite the first. To avoid this, the ETS backend wraps every fact tuple in a 1-element tuple: {{:alice, :bob}}. The wrapped tuple's sole element — the entire original tuple — becomes the ETS key, guaranteeing set semantics matching Storage.Map.

Choice of :set table type

This backend uses :set ETS tables rather than :ordered_set. Although :ordered_set would provide sorted traversal for free, it imposes a total ordering using term comparison that differs from Elixir's Enum.sort/1. Using :set with explicit Enum.sort/1 in stream/2 guarantees the same deterministic ordering as Storage.Map, which is essential for the cross-backend conformance guarantee.

Trade-offs vs Storage.Map

  • Memory: Data lives off-heap, avoiding costly copying of large fact sets during the semi-naive fixpoint loop.
  • Read performance: :ets.member/2 and :ets.info/2 are O(1) for size. Concurrent reads are supported via :read_concurrency when configured.
  • Write performance: :ets.insert/2 is O(1) for :set tables.
  • Iteration: stream/2 returns a deterministically sorted list via Enum.sort(:ets.tab2list(table)), ensuring consistent output across runs.
  • Lifecycle: ETS tables are owned by the creating process. Call teardown/1 to delete all tables when evaluation completes.

Determinism

ETS table iteration order is not guaranteed. This backend normalizes output by sorting the result of stream/2 and relations/1, ensuring identical programs produce identical results regardless of backend choice.

Options

The init/2 function accepts an optional keyword list:

  • :access — ETS access mode, :private (default) or :public. :public enables :read_concurrency for concurrent read workloads.

Summary

Types

t()
table_ref()

Functions

build_index(state, relation, columns)

Builds a hash index on the specified columns for a relation.

capabilities(ets)

Returns the capabilities of this storage backend.

get_indexed(state, relation, columns, key)

Retrieves tuples matching an indexed key.

init(schemas)

Initializes ETS storage for the given relation schemas.

init(schemas, opts)
insert(state, relation, tuple)

Inserts a single tuple into a relation.

insert_many(state, relation, tuples)

Inserts an enumerable of tuples into a relation.

member?(state, relation, tuple)

Checks whether a tuple exists in a relation.

relations(ets)

Returns a sorted list of all relation names in the storage.

size(state, relation)

Returns the number of tuples stored in a relation.

stream(state, relation)

Returns all tuples in a relation as a deterministically sorted list.

teardown(ets)

Deletes all ETS tables owned by this storage backend.

update_index(state, relation, columns, delta)

Incrementally merges delta tuples into an existing index.

Types

t()

@type t() :: %ExDatalog.Storage.ETS{
  indexes: %{
    required({ExDatalog.Storage.relation_name(), ExDatalog.Storage.index_key()}) =>
      table_ref()
  },
  options: keyword(),
  schemas: ExDatalog.Storage.schemas(),
  tables: %{required(ExDatalog.Storage.relation_name()) => table_ref()}
}

table_ref()

@type table_ref() :: :ets.table()

Functions

build_index(state, relation, columns)

@spec build_index(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.index_key()
) :: t()

Builds a hash index on the specified columns for a relation.

Creates a new ETS table mapping projected column values to lists of tuples. Raises ArgumentError if relation is not in the schema.

capabilities(ets)

@spec capabilities(t()) :: ExDatalog.Capabilities.t()

Returns the capabilities of this storage backend.

The ETS backend supports arithmetic and comparison constraints, provenance, and indexed lookup. concurrent_reads reflects the configured access mode.

get_indexed(state, relation, columns, key)

@spec get_indexed(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.index_key(),
  ExDatalog.Storage.key_values()
) :: Enumerable.t()

Retrieves tuples matching an indexed key.

Returns tuples from a pre-built index that match the given key on the specified columns. Returns [] if the index or key does not exist.

Must call build_index/3 before calling get_indexed/4 for the same relation and columns. Results are sorted for deterministic ordering.

init(schemas)

@spec init(ExDatalog.Storage.schemas()) :: t()

Initializes ETS storage for the given relation schemas.

Creates one ETS table per relation with :set type and wrapped-tuple keys for correct multi-arity fact storage. Tables are created with the configured access mode (default: :private).

Options

  • :access — :private (default) or :public. When :public, :read_concurrency is enabled for concurrent read workloads.
  • :write_concurrency — boolean (default: false). When true, :write_concurrency is enabled on each ETS table.

init(schemas, opts)

@spec init(
  ExDatalog.Storage.schemas(),
  keyword()
) :: t()

insert(state, relation, tuple)

@spec insert(t(), ExDatalog.Storage.relation_name(), ExDatalog.Storage.tuple_values()) ::
  t()

Inserts a single tuple into a relation.

The tuple is wrapped as {tuple} before insertion so the entire tuple becomes the ETS key. Idempotent: inserting a tuple that already exists is a no-op (:set semantics with whole-tuple key).

Raises ArgumentError if relation is not in the schema.

insert_many(state, relation, tuples)

@spec insert_many(t(), ExDatalog.Storage.relation_name(), Enumerable.t()) :: t()

Inserts an enumerable of tuples into a relation.

More efficient than repeated insert/3 calls for bulk loading. Idempotent for individual tuples.

Raises ArgumentError if relation is not in the schema.

member?(state, relation, tuple)

@spec member?(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.tuple_values()
) :: boolean()

Checks whether a tuple exists in a relation.

Uses :ets.member/2 for O(1) lookup by the wrapped tuple key. Returns true if the exact tuple is present, false otherwise. Returns false if relation is unknown.

relations(ets)

@spec relations(t()) :: [ExDatalog.Storage.relation_name()]

Returns a sorted list of all relation names in the storage.

size(state, relation)

@spec size(t(), ExDatalog.Storage.relation_name()) :: non_neg_integer()

Returns the number of tuples stored in a relation.

Returns 0 if relation is unknown.

stream(state, relation)

@spec stream(t(), ExDatalog.Storage.relation_name()) :: Enumerable.t()

Returns all tuples in a relation as a deterministically sorted list.

Unwraps the stored {tuple} entries back to plain tuples and sorts them via Enum.sort/1 to guarantee deterministic iteration order. Returns [] if relation is unknown.

teardown(ets)

@spec teardown(t()) :: :ok

Deletes all ETS tables owned by this storage backend.

Must be called when evaluation completes to release ETS table resources. After teardown/1, the state is tombstoned — subsequent operations will raise ArgumentError with a clear message rather than crashing with opaque :badarg from the deleted ETS tables.

This function is idempotent — calling it twice does not raise an error.

update_index(state, relation, columns, delta)

@spec update_index(
  t(),
  ExDatalog.Storage.relation_name(),
  ExDatalog.Storage.index_key(),
  Enumerable.t()
) :: t()

Incrementally merges delta tuples into an existing index.

If no index exists for the given relation and columns, one is built from the current relation data first, then the delta is merged in.

Raises ArgumentError if relation is not in the schema.