match_trie

An Erlang trie (prefix tree) implementation using ETS for efficient MQTT-style topic matching with wildcard support.

Used in barrel_docdb.

Features

• Fast topic matching using ETS ordered sets
• MQTT-style wildcard support (+ and #)
• System topic protection ($SYS/...)
• Concurrent read access
• Topic validation

Installation

Add match_trie to your rebar.config dependencies:

{deps, [
    {match_trie, "1.0.0"}
]}.

Quick Start

%% Create a new trie
Trie = match_trie:new(),

%% Insert topic patterns
ok = match_trie:insert(Trie, <<"sensors/+/temperature">>),
ok = match_trie:insert(Trie, <<"sensors/#">>),
ok = match_trie:insert(Trie, <<"alerts/critical">>),

%% Find matching patterns for a topic
Matches = match_trie:match(Trie, <<"sensors/room1/temperature">>),
%% Returns: [<<"sensors/+/temperature">>, <<"sensors/#">>]

%% Delete a pattern
ok = match_trie:delete(Trie, <<"sensors/#">>),

%% Clean up when done
ok = match_trie:delete(Trie).

Wildcards

Two wildcards are supported following MQTT conventions:

+ (single-level): Matches exactly one topic segment.

%% "sensors/+/temperature" matches:
%%   - "sensors/room1/temperature"
%%   - "sensors/kitchen/temperature"
%% Does NOT match:
%%   - "sensors/floor1/room1/temperature"

# (multi-level): Matches zero or more segments. Must be the last segment.

%% "sensors/#" matches:
%%   - "sensors"
%%   - "sensors/temperature"
%%   - "sensors/room1/temperature"

System Topics

Topics starting with $ (like $SYS/...) are not matched by + or # wildcards at the root level:

false = match_trie:is_match(<<"$SYS/broker/clients">>, <<"#">>),
false = match_trie:is_match(<<"$SYS/broker/clients">>, <<"+/broker/clients">>),
true = match_trie:is_match(<<"$SYS/broker/clients">>, <<"$SYS/#">>).

API

Function	Description
new/0, new/1	Create a new trie (with optional ETS access mode)
insert/2	Insert a topic pattern
match/2	Find all patterns matching a topic
delete/1	Delete the entire trie
delete/2	Remove a pattern from the trie
validate/1	Validate a topic name or filter
is_match/2	Check if a topic matches a filter
is_wildcard/1	Check if a topic contains wildcards

Concurrency

The trie uses ETS tables internally. By default, tables are created with protected access, allowing concurrent reads from any process while writes are restricted to the owner.

%% Private: only owner can read/write
Trie1 = match_trie:new(private),

%% Protected (default): any process can read, owner writes
Trie2 = match_trie:new(protected),

%% Public: any process can read/write
Trie3 = match_trie:new(public).

Benchmark

Run the benchmark:

rebar3 as bench compile
erl -pa _build/bench/lib/match_trie/ebin -pa _build/bench/lib/match_trie/bench \
    -noshell -eval "match_trie_bench:run(100000), halt()."

Example output (Apple MacBook Pro M4 Pro, 48GB RAM, March 2026):

=== match_trie benchmark ===
Iterations: 100000

--- Insert ---
  Total: 8.61 ms
  Per op: 0.09 us
  Ops/sec: 11609009

--- Match (exact topics) ---
  Total: 112.88 ms
  Per op: 1.13 us
  Ops/sec: 885928

--- Match (with wildcards) ---
  Total: 25.30 ms
  Per op: 2.53 us
  Ops/sec: 395241

--- Delete ---
  Total: 8.33 ms
  Per op: 0.08 us
  Ops/sec: 12004802

License

This project is licensed under the Mozilla Public License 2.0. See LICENSE for details.