Reladynamo · the query planner

Planning a bitemporal query

Reladomo hands you an arbitrary boolean predicate. DynamoDB answers one shape of question. Everything interesting happens in the gap.

What DynamoDB will actually answer

A DynamoDB query starts from one exact partition-key value. From there it can narrow by a sort-key condition, then discard rows with a filter — but the filter runs after the read, so you pay for every row it throws away.

An ORM predicate has no such shape. ruleId in (2,3) and priority > 5 and businessDate = X is perfectly ordinary and maps onto three different mechanisms. The planner's whole job is deciding which node goes where — and refusing when nothing fits.

OPERATION TREE AND ruleId = 12 processingDate = ∞ priority > 5 ruleName startsWith "r" businessDate = 2026-06-01 WHERE IT LANDS key condition pk = … and begins_with(sk, …) filter expression read and discarded — still billed residual, in memory DynamoDB cannot express it refused no partition key ⇒ Scan ⇒ throw
Note where businessDate lands. It is an as-of predicate, yet it becomes a filter, not a key condition — the reason is the next diagram.
key condition filter expression in-memory residual refused

Why business date can't be a range scan

The sort key is processing-major: v1#P#<processing>#B#<business>. DynamoDB compares sort keys as byte strings from the left, so a prefix is queryable and a suffix is not.

THREE ROWS, SAME BUSINESS DATE P#2020030112… B#20260601000 P#2024071409… B#20260601000 P#2026091300… B#20260601000 identical business date scattered across the key space — no contiguous range holds them Processing-major buys "every version of this row, newest knowledge first" as one query. It costs the symmetric query on business date. That trade is deliberate, and stated.
Serving a business-date access pattern by index needs a secondary index, and the only GSI shape with evidence behind it today is a foreign-key index with an ALL projection — see the support contract. The planner does not pretend the base table can serve it.

The contradiction that returns nothing

An adversarial test generator found this one. ruleId in (2,3) and ruleId = 1 is unsatisfiable — but a planner that consumes ruleId = 1 as the partition key and forgets the rest will happily fetch row 1 and return it.

The fix was not to keep the dropped predicate as a filter. It was to convert the tree to disjunctive normal form, plan each conjunction independently, and give the planner a fifth outcome:

Plan kindWhenCalls issued
GET_ITEMfull key known1
QUERYone partition key1 + pages
QUERY_FAN_OUTOR across keys, capped at 100 by defaultn
SCANopt-in only, else refusedwhole table
EMPTYprovably unsatisfiable0

EMPTY issues no call at all. That is a correctness result, not an optimisation: the executor asserts it never touches DynamoDB, because sending a query anyway would suggest the verdict is advisory.

Why refusing matters more than optimising. A silent Scan does not fail — it returns correct rows, slowly, at rising cost, until the table is large enough that it doesn't. So a missing partition key throws by default, and running a Scan is a decision someone has to make in configuration and can be found later in review.

The path that actually matters

Almost every real Reladomo query is "the current row for this key": businessDate = X and processingDate = ∞. If that path is slow, nothing else about the planner matters. It gets a named fast path — FAST_PATH_CURRENT_ASOF, or FAST_PATH_POINT_GET when the whole key is known and a single GetItem will do.

Every plan also carries an explain output — chosen index, key condition, residual predicates, items scanned versus returned. Tests assert against it, so a query that quietly degrades into scanning ten thousand items to return three fails the build rather than the budget.