CONCEPT Cited by 1 source
Rule-set O(1) rule matching¶
Definition¶
A rule set is a data structure that maps a <key, value> pair to the rules that reference it, enabling O(1)-per-query-metadata-field rule-candidate identification regardless of how many rules are configured in the system. Given a query carrying a metadata bag like { username: postgres, app: commerce, controller: api }, the rule set returns candidate rules with exactly three hash-map lookups — one per field on the query — not N lookups over the N configured rules.
Why it matters¶
Rule matching is on the hot path of every admission-controlled query, so its cost must be decoupled from the size of the rule space. "One important goal for Traffic Control is that it can efficiently decide when not to block a query. After all, Traffic Control has to make that decision before each query is even allowed to begin execution. So the budget here is measured in microseconds. But we also want developers and database administrators to be able to configure as many rules as it takes to manage traffic to their application. So it's crucial that we can evaluate many rules quickly." (Source: sources/2026-04-21-planetscale-behind-the-scenes-how-database-traffic-control-works.)
The data structure flips the cost model from "one check per rule" to "one check per query-metadata-field" — number of rules grows unboundedly; number of metadata fields on a single query is bounded small.
Structure¶
- Each configured rule with form
key=valueregisters itself under(key, value). - Matching a query: for every field on the query, look up the
(key, value)pair and union the resulting rule lists.
Three exceptions to O(1)¶
Per the source, three rule shapes relax the O(1) bound:
1. CIDR-masked remote_address rules — O(mask-count)¶
"Rules for the remote_address key check for a match for each mask length. So if you have rules for ten different mask lengths, the rule set has to do as many as ten lookups to find the rule with the longest matching prefix."
remote_address rules are longest-prefix-match, not exact-match. The rule set must try each configured mask length against the query's IP. Cost: O(distinct-mask-lengths-configured), not O(rules).
2. Conjunction rules — O(matching-<k,v>-pairs)¶
"Any conjunction rule — that is, a rule with multiple <key, value> pairs ANDed together — may be identified as a candidate for queries that match any one of the <key, value> pairs in the rule. So if you have conjunction rules with overlapping <key, value> pairs, the rule set may identify several or all of them as candidates for each query."
A rule app=commerce AND controller=api registers under both (app, commerce) and (controller, api). A query matching either field surfaces the rule as a candidate — final match must check all the rule's conditions against the query (phase 2, below).
3. Duplicate-key rules — O(duplicates)¶
"It is possible to add multiple rules for the exact same <key, value> pair. If you do that, any query with that exact <key, value> pair will get checked against all of those rules."
The rule-set entry for (key, value) is a list, not a single rule. All entries in that list are candidates.
Three-phase dispatch¶
The O(1) property is phase-1 only. Full rule application is three phases:
- Lookup. Rule set returns a candidate list — O(query-metadata-fields) for exact-match rules, plus the three exceptions above.
- Filter. Each candidate rule's full predicate is evaluated against the query (e.g. for conjunction rules, all
<k,v>pairs must match). - Budget check. For surviving rules, evaluate their budget against reverse leaky bucket state and concurrency counters.
The phase-1 lookup is the one bounded independently of rule count. Phase 2 is bounded by the candidate list length. Phase 3 is bounded by the surviving rule count.
Comparison: rule set vs. naive scan¶
| Naive (check every rule) | Rule set | |
|---|---|---|
| Cost per query | O(N rules) | O(query-fields) |
| Rule-count scaling | Linear | Flat |
| CIDR rules | O(N CIDR rules) | O(mask-lengths) |
| Conjunction rules | O(N conjunction rules) | O(overlapping <k,v> pairs) |
Seen in¶
- sources/2026-04-21-planetscale-behind-the-scenes-how-database-traffic-control-works — canonical wiki source. Reynolds canonicalises the rule-set data structure as the answer to "how does Traffic Control evaluate many rules inside a microsecond per-query budget?". The three named exceptions (CIDR, conjunction, duplicate-key) are the operator-visible rule shapes that move a rule off the O(1) fast path; worth surfacing to users who are configuring many complex rules.