Chapter 21: Query Planning and Diagnostics

Chapter 20 focused on getting data into Datalevin quickly. Once the data is loaded, performance work shifts from the write path to the read path: which query plan will run, how many facts each clause is expected to match, whether the optimizer's cardinality estimates match the current data, and what explain shows when they do not.

Datalevin's query optimizer leverages the strengths of sorted triple indexes for cardinality estimation, one of the hardest problems in database design. With that foundation, Datalevin can choose good plans for complex joins without requiring users to hand-order clauses.

A fast query depends on both the plan Datalevin chooses and the evidence you can collect when that plan surprises you. This chapter combines optimizer mechanics, recursive rule evaluation, and the explain workflow used to diagnose real query behavior.

If you are debugging a slow or surprising query right now, start with Section 3 and run explain first. Then return to Sections 1 and 2 to interpret why the planner chose a particular join order, access path, or recursive-rule strategy.

1. Query Planning and Optimization

As discussed in Chapter 8, Datalog is declarative. You describe what you want, and Datalevin's Query Optimizer decides how to find it. This decoupling is critical for performance because even a simple change in the order of joins can make a query orders of magnitude faster or slower, even though the results are the same.

This section explores how Datalevin's Cost-Based Optimizer (CBO) uses the counted indexes and ordered storage in DLMDB to create efficient execution plans.

Before a query executes its result-producing plan, Datalevin rewrites it into a simpler execution shape. Predicate pushdown, inequality conversion, constant parameter plugging, and complex-clause dependency analysis all happen before join planning. The optimizer then chooses access paths and join methods against that rewritten query.

1.1 The Selinger-Style Optimizer

Datalevin uses a Selinger-style cost-based query optimizer, following the System R tradition [1]. It uses dynamic programming over join alternatives, in the same broad family as enterprise relational optimizers.

1.1.1 How it Works

Figure 21.1 describes the query planner pipeline.

When a query is submitted:

1. Parsing: The engine breaks down the :where clauses into individual constraints.
2. Query Graph Simplification: Star-like attributes (multiple attributes on the same entity) are handled via merge scan, defined in Section 1.4, reducing the graph to chains between stars.
3. Cardinality Estimation: The engine uses DLMDB's order statistics to estimate how many results each clause will produce.
4. Join Planning: It explores possible join orders using dynamic programming, generating left-deep join trees.
5. Bounded Search Policy: The planner keeps dynamic-programming plan tables, but shrinks the search space when the number of alternatives exceeds a cap derived from P(n, 2). This keeps planning bounded while preserving careful choice of the most important early joins.

A left-deep join tree is a plan shape where each step joins one new base relation into the intermediate result built so far. The alternative is a bushy tree, where two independently built subplans are joined together. Datalevin uses left-deep plans because its join methods are index-scan oriented: keeping one side as a base relation preserves accurate counts and keeps planning cost bounded [2,3].

P(n, 2) is permutation notation. It means the number of ordered ways to choose the first two join steps from n candidates: n * (n - 1). Datalevin uses this as a practical bound on plan-table growth. Early joins get the most careful attention because they are where exact index counts and direct samples are most reliable, and because they determine the size of every later intermediate.

1.1.2 A Concrete Join-Order Example

Join order matters because every join produces an intermediate relation. A bad plan can create millions of temporary candidates and then throw almost all of them away. A good plan starts with the most selective facts and keeps the intermediate relation small.

Suppose an e-commerce database has:

• 10,000,000 orders.
• 80,000,000 line items.
• 500,000 products priced above $100, stored as 10000 cents.
• A unique order id, so :order/id lookup returns exactly one order.
• About 12 line items per order.

The logical query is simple: "For one order, find the expensive products in its line items."

(d/q '[:find ?sku ?qty
       :in $ ?order-id
       :where
       [?order :order/id ?order-id]
       [?line :line-item/order ?order]
       [?line :line-item/product ?product]
       [?line :line-item/quantity ?qty]
       [?product :product/sku ?sku]
       [?product :product/price ?price]
       [(> ?price 10000)]]
     db
     "o-2026-000001")

Object result = conn.query("[:find ?sku ?qty " +
    " :in $ ?order-id " +
    " :where " +
    " [?order :order/id ?order-id] " +
    " [?line :line-item/order ?order] " +
    " [?line :line-item/product ?product] " +
    " [?line :line-item/quantity ?qty] " +
    " [?product :product/sku ?sku] " +
    " [?product :product/price ?price] " +
    " [(> ?price 10000)]]",
    "o-2026-000001");

result = conn.query(
    '[:find ?sku ?qty '
    ' :in $ ?order-id '
    ' :where '
    ' [?order :order/id ?order-id] '
    ' [?line :line-item/order ?order] '
    ' [?line :line-item/product ?product] '
    ' [?line :line-item/quantity ?qty] '
    ' [?product :product/sku ?sku] '
    ' [?product :product/price ?price] '
    ' [(> ?price 10000)]]',
    'o-2026-000001',
)

const result = await conn.query(
  '[:find ?sku ?qty ' +
  ' :in $ ?order-id ' +
  ' :where ' +
  ' [?order :order/id ?order-id] ' +
  ' [?line :line-item/order ?order] ' +
  ' [?line :line-item/product ?product] ' +
  ' [?line :line-item/quantity ?qty] ' +
  ' [?product :product/sku ?sku] ' +
  ' [?product :product/price ?price] ' +
  ' [(> ?price 10000)]]',
  'o-2026-000001'
);

These clauses have one logical meaning, but the physical join order can be wildly different.

The good plan does work proportional to one order.

The result is identical, but the bad plan may process millions of candidates to answer a question about one order. This is why Datalevin invests in cardinality estimation and join planning. The textual order of :where clauses does not matter; the optimizer is choosing this physical order for you.

The good plan is a left-deep tree: the optimizer starts from the single order, then folds in one base relation at a time, keeping the intermediate result small at every step. Figure 21.2 shows the tree for the example above.

1.2 Accurate Cardinality Estimation

The quality of a query plan depends on accurate cardinality estimates. Datalevin excels here because counting is cheap in its nested triple storage. The resulting join order is often similar to a hand-written join plan.

1.2.1 Direct Counting

Some counts can be obtained in O(1) time directly from the index without scanning. For example, [?e :user/city "London"] returns an exact count from the AVE index. For range queries, DLMDB's order statistics provide O(log n) counting.

1.2.2 Query-Specific Sampling

Direct counts are most useful for individual indexed clauses and range bounds. After several clauses have been joined, the next estimate depends on the size and distribution of an intermediate relation. Small errors can compound: if the planner underestimates users in one city, then underestimates how many of those users have active orders, the combined estimate can become much too small. For these plan-dependent estimates, Datalevin uses online reservoir sampling under actual query conditions. This is query-time work, not a background histogram. It:

1. Collects sample entity ids
2. Performs merge scans to get selectivity ratios
3. Uses empirical-Bayes shrinkage with priors
4. Applies skew-aware upper-bound correction for extreme data distributions

The last two steps are statistical guardrails. Empirical-Bayes shrinkage means the planner does not trust a small or noisy sample completely; it pulls the sample estimate toward a prior expectation so a few sampled entities do not dominate the whole plan [4]. Skew-aware upper-bound correction means the planner treats heavy-tailed distributions cautiously. If a few values are much more frequent than average, the estimate is adjusted upward so the optimizer does not choose a plan that only works for the average case [5]. These statistical techniques are what often prevent the edge cases that create catastrophic query slowdown incidents in production.

1.2.3 Directional Estimation

Many relational optimizers fall back to independence assumptions when they lack multi-column or join-specific statistics. Datalevin's estimation is directional because different join directions produce different estimates. This matters for :ref and :_ref joins, where starting from the source entity or the referenced value can have very different selectivity.

1.3 Predicate Push-Down

Datalevin rewrites queries to push selection predicates down to index scans.

1.3.1 Inequality Predicates

Comparison operators are converted to range boundaries in the index scan. For example:

[(> ?age 21)]  ;; Becomes a range scan with an open lower bound at 21

1.3.2 Constant Parameter Plugging

Query parameters are plugged directly into the query to avoid expensive joins with bound values.

1.4 Merge Scan

For star-like queries (multiple attributes on the same entity), Datalevin uses merge scan, a technique similar to pivot scan [6].

Instead of joining each attribute separately, an EAV-oriented merge scan can retrieve matching attributes for the same entity in one ordered pass. The optimizer can then plan over a simplified query graph whose nodes are star-shaped groups and whose edges are links between those groups, reducing the join search space [7,8,9]. For star-heavy queries, this removes a large amount of otherwise repetitive entity-local work.

1.5 Join Methods

Datalevin considers six join methods and picks the best based on cost estimation:

Sideways information passing (SIP) means passing already-known variable bindings from one part of the plan into another part that is not simply the next linear data pattern. In ordinary joins this happens naturally through shared variables: once ?user is bound, a later clause such as [?order :order/customer ?user] can use that value to do a narrow lookup. An or-join is more complicated because it contains several alternative branches. SIP lets the planner evaluate each branch with the outer bindings it is allowed to see, rather than evaluating every branch as an independent broad subquery and joining the results afterward.

For example, an or-join whose declared join variables include ?user can receive the current ?user bindings from earlier indexed clauses. Each branch then asks a bounded question such as "does this user match by email?" or "does this user match by phone?" instead of scanning all users that match either branch. The declared join-variable list matters: it is the contract that tells the optimizer which outer variables may be passed sideways into the alternatives and which branch-local variables must stay internal. If a complex clause cannot use the available bindings, it is less selective and may be planned later.

An anti-join is the negative counterpart of a join: it keeps a candidate row only when no matching row exists on the excluded side. In SQL this is the shape behind NOT EXISTS; in Datalevin it is usually expressed with not or not-join. A planned not-join is useful when the engine has already bound the declared join variables and can check the negative pattern with indexed lookups. For example, after ?start and ?person are bound, a not-join [?start ?person] can ask "is there a direct friendship edge between these two?" and discard the candidate only if that edge exists. The result is still declarative negation, but the physical plan can avoid treating the negative pattern as a late row-by-row filter.

In hash-join terminology, the build side is the input used to construct an in-memory hash table, and the probe side is the input scanned to look up matches in that table. Building on the smaller side usually saves memory and work. Datalevin considers a hash join when estimated intermediate sizes make repeated index probes expensive; for reverse-reference joins it can also combine hash joining with SIP when the target side is much larger than the current input.

1.5.1 Recency-Based Link Choice

When multiple paths exist to reach the same node, Datalevin prefers the link from the most recently resolved node, since the estimation for the recent data distribution is more accurate.

1.6 Parallel Processing

Datalevin's query engine uses parallelism at multiple levels:

• Planning: Independent counts, samples, and connected components can be processed in parallel.
• Execution: Pipelined execution can keep tuples moving across plan steps, so downstream work can begin before the whole upstream relation has been materialized. Not every query shape benefits equally, but the execution model is built for streaming intermediate results.

1.7 Complex Clauses and Rules

The optimizer handles complex clauses in stages:

1. Index access clauses produce intermediate results first
2. Heuristics and variable dependencies reorder remaining complex clauses such as and, or, not, complex predicates, and function bindings that are not pushed down.
3. Rules are handled by the specialized bottom-up evaluation machinery described later in this chapter.

or-join participates in link planning, and common not-join shapes can become anti-join steps when their join variables are bound in a single plan component. More complex negative clauses still fall back to late resolution.

1.8 Optimizer Principles

In summary, Datalevin has a sophisticated query optimizer that compiles declarative query clauses into execution steps that use index scans where they help, take advantage of cheap counts from triple storage, and often produce plans similar to a hand-written one. Users can usually write the logical query first, then use explain when a specific workload needs inspection or tuning.

• Clause order does not matter for the most part: The optimizer chooses the physical order for most clauses. Deferred :late-clauses are also re-ordered according to their binding dependencies. If two late clauses are both fully bound at the same time, their original order does matter.
• Indexes are automatic: Datalevin maintains the core EAV and AVE indexes for all attributes.
• Counts are live and samples are refreshable: DLMDB gives the planner cheap current index counts, while background sampling and explicit d/analyze calls refresh per-attribute eid samples, per-attribute cardinality counters, and default fan-out ratios. These are not histogram-style distribution statistics.
• Nested storage helps planning: The nested triple storage makes counting cheap, giving the optimizer evidence that many systems have to approximate.

1.9 Benchmarks

Datalevin's query engine has been tested against standard benchmark workloads, but the published comparisons are Datalevin project benchmarks, not independent third-party certifications. Treat the numbers as reproducible workload observations: useful for understanding design tradeoffs, but not a substitute for testing your own schema, data distribution, hardware, and database configuration.

• Join Order Benchmark (JOB): 113 complex SQL queries ported to Datalog. In the Datalevin JOB benchmark [10], the reported run used a November 2023 16-inch MacBook Pro with an Apple M3 Pro, 36GB RAM, and a 1TB SSD. PostgreSQL was Homebrew PostgreSQL@18, Datalevin was the repository version under test, and all systems used default configuration without tuning. Each system was run once for warmup and once for the reported timing. Under that setup, Datalevin finished the 113-query workload in 71 seconds versus 171 seconds for PostgreSQL, about 2.4x faster overall. SQLite was included as a second SQL comparison and was much weaker on this workload: it completed the non-timeout portion in 295 seconds, already more than 4x slower than Datalevin, and 9 queries hit the benchmark timeout. Counting those queries to completion would make the SQLite gap larger.
• LDBC SNB: The Datalevin LDBC-SNB benchmark [11] is an unofficial implementation of the Interactive workload for Datalevin and Neo4j. The reported run used scale factor 1, about 3.2M entities and 17.3M edges, on a 2023 Apple M2 Max machine with 12 cores, 32GB RAM, a 1TB SSD, macOS 15.2, OpenJDK 21, and Clojure 1.12.4. Queries were run twice and the second run was reported. In that setup, Datalevin was much faster on the Interactive Short queries, while the Interactive Complex results were closer and mixed, with Neo4j faster on several individual complex queries. Consult the benchmark page for current numbers, because release versions, tuning, JVM settings, indexes, hardware, and scale factor can change them.

Benchmark ratios are especially sensitive to scale factor, cache state, data modeling choices, query parameters, JVM settings, memory settings, and indexes. Use these results as evidence that Datalevin's optimizer is competitive on these workloads, not as a guarantee that Datalevin will show the same margin in another deployment.

2. Recursive Rules as Specialized Query Evaluation

Non-recursive rules are pulled out and planned as part of the query optimization described above. Recursive rules require specialized planning because the engine may have to derive new tuples over several rounds before the rule result is complete. This section explains the separate machinery: semi-naive evaluation, deltas, and rule-specific rewrites.

(def ancestor-rules
  '[[(ancestor ?x ?y)
     [?x :person/parent ?y]]

    [(ancestor ?x ?y)
     [?x :person/parent ?z]
     (ancestor ?z ?y)]])

Object ancestorRules = Datalevin.edn("""
    [[(ancestor ?x ?y)
      [?x :person/parent ?y]]

     [(ancestor ?x ?y)
      [?x :person/parent ?z]
      (ancestor ?z ?y)]]
    """);

ancestor_rules = interop().read_edn("""
    [[(ancestor ?x ?y)
      [?x :person/parent ?y]]

     [(ancestor ?x ?y)
      [?x :person/parent ?z]
      (ancestor ?z ?y)]]
    """)

const ancestorRules = await interop().readEdn(`
    [[(ancestor ?x ?y)
      [?x :person/parent ?y]]

     [(ancestor ?x ?y)
      [?x :person/parent ?z]
      (ancestor ?z ?y)]]
    `);

For the ancestor rule set above, a naive evaluator would repeatedly join all known ancestors against all parents. That repeats work. In the third round, for example, it may rediscover grandparent facts already found in the second round. On large graphs, this redundant computation can dominate the query.

Datalevin therefore uses semi-naive evaluation, the standard bottom-up strategy for recursive Datalog [12]. The key idea is delta tracking: each round only uses the new tuples discovered in the previous round. Evaluation continues until a fixpoint, meaning a round produces no new tuples. The engine also builds rule-dependency components and evaluates them in dependency order. A later rule component can use facts computed by an earlier component, but not the other way around. Strongly connected recursive components run to a fixpoint before dependent components consume their results.

This bottom-up model is set-oriented. Joins operate over candidate sets and iterators, so the storage layer can use sequential page scans, merge-style operations, and bulk filtering rather than tuple-at-a-time random lookup.

Bottom-up evaluation has one obvious risk: it can compute more of the world than the user asked for. If a query asks only for Alice's ancestors, the engine should not materialize every ancestor relation in the database. Datalevin uses magic-set rewriting, a classic Datalog transformation for making bottom-up evaluation goal-directed [12,13]. Magic-set rules push bound variables from the outer query into the recursive rule, pruning intermediate results to the part of the graph relevant to the question.

2.1 Semi-Naive Evaluation

Consider a small directed graph, using letters as stand-ins for entity ids. The example EDB is the following set of base edge facts:

[a :link/to b]
[b :link/to c]
[b :link/to d]
[d :link/to e]
[p :link/to q]
[q :link/to r]

In a real Datalevin database, each row above corresponds to a stored :link/to datom. These base edge facts are the EDB (extensional database): facts read from Datalevin rather than derived by the recursive rule. The rule predicate reachable is the IDB (intensional database): derived tuples produced by the rules. The EDB stays fixed during the evaluation; each round adds a delta of new IDB tuples.

The recursive rule says that ?end is reachable from ?start if there is a direct edge, or if there is an edge to ?mid and ?end is reachable from ?mid:

(def reachability-rules
  '[[(reachable ?start ?end)
     [?start :link/to ?end]]

    [(reachable ?start ?end)
     [?start :link/to ?mid]
     (reachable ?mid ?end)]])

Object reachabilityRules = Datalevin.edn("""
    [[(reachable ?start ?end)
      [?start :link/to ?end]]

     [(reachable ?start ?end)
      [?start :link/to ?mid]
      (reachable ?mid ?end)]]
    """);

reachability_rules = interop().read_edn("""
    [[(reachable ?start ?end)
      [?start :link/to ?end]]

     [(reachable ?start ?end)
      [?start :link/to ?mid]
      (reachable ?mid ?end)]]
    """)

const reachabilityRules = await interop().readEdn(`
    [[(reachable ?start ?end)
      [?start :link/to ?end]]

     [(reachable ?start ?end)
      [?start :link/to ?mid]
      (reachable ?mid ?end)]]
    `);

Semi-naive evaluation tracks a delta, the new IDB tuples from the previous round, and joins only against that delta in the recursive step. The base rule derives round 1 directly from the EDB; later rounds join the previous IDB delta against the same EDB edge facts. For this graph:

Figure 21.3 shows the delta flow for this example. Each round consumes only the previous round's delta; the fixpoint is reached when the next delta is empty.

A naive bottom-up evaluator would keep rejoining all known reachable tuples in every round, rediscovering many results it already had. Semi-naive evaluation uses only the previous round's delta to produce the next delta, then unions the deltas into the final IDB relation. Chapter 9 shows the same idea with a longer reports-to example.

2.2 Magic-Set Rewrite

Now suppose the query asks only for nodes reachable from one bound start node, represented as a in the graph trace:

(def reachable-from-query
  '[:find [?end ...]
    :in $ % ?start
    :where (reachable ?start ?end)])

(d/q reachable-from-query db reachability-rules start-id)

import java.util.List;

Object reachableFromQuery = Datalevin.edn("""
    [:find [?end ...]
     :in $ % ?start
     :where (reachable ?start ?end)]
    """);

Object ends = conn.queryForm(reachableFromQuery,
    List.of(reachabilityRules, startId));

reachable_from_query = interop().read_edn("""
    [:find [?end ...]
     :in $ % ?start
     :where (reachable ?start ?end)]
    """)

ends = conn.query(reachable_from_query, reachability_rules, start_id)

const reachableFromQuery = await interop().readEdn(`
    [:find [?end ...]
     :in $ % ?start
     :where (reachable ?start ?end)]
    `);

const ends = await conn.query(reachableFromQuery, reachabilityRules, startId);

Plain bottom-up evaluation of reachable would also derive the disconnected p -> q -> r portion of the graph, even though it cannot affect the answer. A magic-set rewrite adds a temporary predicate that carries the bound arguments from the query into recursive evaluation. In this example, magic-reachable means "this start node can still contribute to the answer for the original query." Conceptually, the engine seeds that relation with the bound start node and threads it through the recursive rule:

;; Seed the temporary relation from the query binding:
;; only a is initially relevant.
(magic-reachable a)

;; If a relevant start has an outgoing edge, its neighbor can
;; become the start of a relevant recursive subcall.
[(magic-reachable ?mid)
 (magic-reachable ?start)
 [?start :link/to ?mid]]

;; Guard the original base rule so it only derives rows for relevant starts.
[(reachable ?start ?end)
 (magic-reachable ?start)
 [?start :link/to ?end]]

;; Guard the original recursive rule the same way.
[(reachable ?start ?end)
 (magic-reachable ?start)
 [?start :link/to ?mid]
 (reachable ?mid ?end)]

This is a conceptual rewrite, not Datalevin's literal internal representation, and magic-reachable is not a stored attribute, datom, or user-visible rule. It is an internal, temporary relation that marks which ?start values are worth expanding. Starting from a, the propagation rule discovers b, c, d, and e as relevant starts. The disconnected p, q, and r component is never marked, so the guarded reachable rules never derive rows for that component. The answers for the original query are still b, c, d, and e; the rewrite only avoids recursive work that cannot feed those answers.

Datalevin applies magic-set rewriting when a recursive rule call has bound arguments that can actually restrict recursive branches. If those bindings would not filter the recursive work, or if the magic relations grow beyond the optimizer's guardrail, the engine falls back to ordinary dependency-ordered recursive evaluation.

Figure 21.4 visually compares plain bottom-up evaluation with magic-set rewriting.

2.3 Rule Evaluation Refinements

Datalevin also connects rule evaluation back to the cost-based optimizer:

1. Seeding tuples: Rule evaluation can receive bindings from earlier indexed query clauses. These seeds prevent unnecessary tuple generation and give recursion a warm start.
2. Inlining non-recursive clauses: Clauses not involved in recursion can be pulled back into the ordinary query plan, where the cost-based optimizer can use indexes and join estimates.
3. Temporal elimination: Recursive rules that meet T-stratification criteria can keep only the last iteration's results, reducing memory use for long chains [14].
4. Conservative complex clauses: not, not-join, or, and function clauses obey the same binding discipline as ordinary queries. Recursive rules with negative or complex clauses use conservative planning paths rather than the positive-recursion magic-set path.

The practical takeaway is that rules are not interpreted as repeated application callbacks. They are compiled into set-oriented recursive evaluation, constrained by outer query bindings, and integrated with the same storage and planning principles used by ordinary Datalog queries.

3. Inspecting Query Plans with explain

Datalevin's query optimizer has good evidence, but it is still making estimates. Sometimes a query that should be fast takes longer than expected. To debug those cases, inspect the execution plan instead of guessing from the query text.

Datalevin's public diagnostic API for Datalog queries is explain. By default, explain plans the query without running it. When called with {:run? true}, it executes the query as well and adds measured result-size and timing information to the explain output.

3.1 Plan-Only Explain

Use plan-only explain when you want to inspect join order, access paths, and estimated cardinalities without running the query itself.

(def query
  '[:find ?name
    :where [?e :user/name ?name]
           [?e :user/age ?age]
           [(> ?age 30)]])

(d/explain {} query (d/db conn))

String query =
    "[:find ?name " +
    " :where [?e :user/name ?name] " +
    "        [?e :user/age ?age] " +
    "        [(> ?age 30)]]";

Object plan = conn.explain(query);

query = """[:find ?name
           :where [?e :user/name ?name]
                  [?e :user/age ?age]
                  [(> ?age 30)]]"""

plan = conn.explain(query)

const query = `[:find ?name
               :where [?e :user/name ?name]
                      [?e :user/age ?age]
                      [(> ?age 30)]]`;

const plan = await conn.explain(query);

Plan-only output includes:

• :query-graph: The optimizer's graph of clauses and estimated counts
• :plan: Planned steps, access paths, join methods, estimated :cost, and estimated :size. The order of the :steps is the chosen join order, and the text of each step describes the join method or index access path.
• :opt-clauses / :late-clauses: Clauses handled by the optimizer versus clauses processed after the optimized plan
• Planning times: :parsing-time, :building-time, :planning-time, and :prepare-time

The actual value returned by explain is ordinary structured data and is much larger than what is useful to print inline. It includes the query graph, plan steps, rewritten clauses, timing fields, and many implementation details that are useful when debugging a specific query. The following is an abbreviated, human-friendly excerpt from the small query above:

{:planning-time "3.217",
 :opt-clauses
 [[?e :user/name ?name]
  [?e :user/age ?age]
  [(> ?age 30)]],
 :query-graph
 {$
  {?e
   {:free
    [{:attr :user/name, :var ?name}
     {:attr :user/age,
      :var ?age,
      :range [[[:open 30] [:closed :db.value/sysMax]]]}]}}},
 :plan
 {$
  [[{:steps
     ["Initialize [?e ?age] by range ... on :user/age."
      "Merge [?name] by scanning [:user/name]."],
     :cost nil,
     :size nil}]]},
 :late-clauses ()}

Read this in three parts. :late-clauses is empty, so the optimizer handled all clauses in the main plan. The predicate [(> ?age 30)] has been converted into a range bound on :user/age; it is not a separate row-by-row filter. The plan starts from that bounded age scan and then merges :user/name for the same entity. The :cost and :size fields can be nil for a single star-shaped component because there is no join-order competition to cost. In multi-component joins, :cost and :size are usually the main plan fields to inspect; in every case, the :query-graph count fields show the optimizer's estimated clause cardinalities.

Use plan-only explain to verify that a query is using the expected indexes and join strategies before running it on large data.

3.2 Explain with Execution Measurements

Use {:run? true} when you also need measured execution information. This runs the query and augments the explain map with fields such as :execution-time, :actual-result-size, :result, and per-plan :actual-size where available.

(d/explain {:run? true} query (d/db conn))

import java.util.List;

Object measuredPlan = conn.explain("{:run? true}", query, List.of());

measured_plan = conn.explain(query, opts_edn="{:run? true}")

const measuredPlan = await conn.explain(query, {
  optsEdn: '{:run? true}'
});

{:run? true} is the runtime diagnostics mode of explain. It does not produce a separate clause-by-clause trace, but it lets you compare estimated sizes against actual sizes and distinguish planning cost from runtime cost.

In either mode, start with the :plan section. Each planned component contains :steps, estimated :cost, and estimated :size; with {:run? true}, the engine also reports actual sizes where available. Use the count fields in :query-graph and :size in the plan for estimated cardinalities, :actual-size and :actual-result-size for measured cardinalities, and :prepare-time versus :execution-time to separate planning overhead from execution time.

The key comparison is estimated :size versus measured :actual-size for each planned component. :size is the optimizer's cardinality estimate; :actual-size is what the plan actually produced when the query ran. When those values are close, the planner's model matched the current data. Datalevin is normally very accurate in the first few plan steps because it can combine exact index counts with query-specific sampling, and those early steps matter most for keeping intermediate results small.

If :size and :actual-size differ by orders of magnitude, cardinality estimation was wrong for that part of the plan. The cause may be a predicate or a join whose selectivity is hard to estimate, but it can also be stale or sparse attribute metadata: Datalevin refreshes per-attribute eid samples, attribute cardinality counters, and default fan-out ratios in the background, and a very fast load or major reshaping of data may outrun that process. Background sampling is enabled by default, but explicit analyze is useful when you need those statistics refreshed before judging a plan. After a bulk load or major reshaping of data, refresh statistics for the affected attribute, or for the database as a whole:

(d/analyze (d/db conn) :user/age)
(d/analyze (d/db conn))

conn.analyze(":user/age");
conn.analyze();

conn.analyze(":user/age")
conn.analyze()

await conn.analyze(':user/age');
await conn.analyze();

3.3 Understanding Join Orders

The :plan section shows the join order chosen by the optimizer.

1. Leading Clause: This is the first clause the engine used to find the initial set of entities.
2. Sequential Joins: The order in which subsequent clauses were applied.

If you see that the engine is starting with a non-selective clause (e.g., searching for :user/active? true), it might be because the selective filter you expect is hidden inside a complex predicate or rule.

A common join-order bottleneck is a large intermediate result set. If the first join returns 1,000,000 entities, but the second join filters them down to 10, the engine still had to process 1,000,000 records.

The fix is to ask whether the query can express a more selective indexed constraint earlier in the plan. The optimizer tries to do this automatically, but a complex predicate or rule may hide the selective condition from estimation.

3.4 Diagnosing Slow Predicates

Some custom predicates are visible to the optimizer. A predicate that can be pushed down, typically one involving a single free variable and no source expression, is executed during query-specific sampling, so Datalevin can estimate its selectivity from the current data. For example, a predicate such as [(my-ns/is-complex? ?x)] can be planned differently from a late filter when ?x is attached to a sampled value path.

The harder cases are predicates that cannot be pushed down, such as predicates over several variables, predicates that depend on an explicit source, or functions whose own runtime cost dominates even when selectivity is estimated well. explain can show whether the predicate became part of the optimized plan or remained in :late-clauses, but it does not time each predicate call separately. If a query becomes slow only after adding a predicate, isolate that predicate by comparing explain output and query runtime before and after adding it.

Summary: The Explain Workflow

The chapter has three layers: optimizer mechanics, recursive-rule evaluation, and the practical diagnostics workflow. When a query is slow, follow this workflow:

1. Use plan-only explain: Inspect join methods, index usage, and estimated cardinalities.
2. Use explain with {:run? true}: Compare estimates with actual result sizes and total execution time.
3. Check cardinality gaps: Large gaps between estimated :size and measured :actual-size are a strong hint that a predicate, rule, stale per-attribute sample, or rapidly changed data is hiding selectivity from the optimizer. If the data changed quickly, run d/analyze before drawing conclusions from the plan.
4. Simplify and isolate: Remove clauses one by one to find the specific part of the query that is slow.
5. Refine the logic: Prefer more selective indexed attributes to expensive custom predicates.

By using explain well, you gain the transparency needed to understand how Datalevin plans a query and why a query may be slower than expected.

References

[1] Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price, "Access Path Selection in a Relational Database Management System," SIGMOD 1979, pp. 23-34. URL: https://research.ibm.com/publications/access-path-selection-in-a-relational-database-management-system. DOI: https://doi.org/10.1145/582095.582099.

[2] Guido Moerkotte and Thomas Neumann, "Dynamic Programming Strikes Back," SIGMOD 2008, pp. 539-552.

[3] Hai Lan, Zhifeng Bao, and Yuwei Peng, "A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration," Data Science and Engineering, 2021.

[4] Max Heimel, Volker Markl, and Keshava Murthy, "A Bayesian Approach to Estimating the Selectivity of Conjunctive Predicates," BTW 2009, pp. 47-56.

[5] Peter J. Haas and Arun N. Swami, "Sampling-Based Selectivity Estimation for Joins Using Augmented Frequent Value Statistics," ICDE 1995.

[6] Andreas Brodt, Oliver Schiller, and Bernhard Mitschang, "Efficient Resource Attribute Retrieval in RDF Triple Stores," CIKM 2011, pp. 1445-1454.

[7] Andrey Gubichev and Thomas Neumann, "Exploiting the Query Structure for Efficient Join Ordering in SPARQL Queries," EDBT 2014.

[8] Marios Meimaris et al., "Extended Characteristic Sets: Graph Indexing for SPARQL Query Optimization," ICDE 2017.

[9] Thomas Neumann and Guido Moerkotte, "Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins," ICDE 2011.

[10] Datalevin project, "Join Order Benchmark," benchmark writeup and implementation. URL: https://github.com/datalevin/datalevin/tree/master/benchmarks/JOB-bench.

[11] Datalevin project, "LDBC Social Network Benchmark," benchmark writeup and implementation. URL: https://github.com/datalevin/datalevin/tree/master/benchmarks/LDBC-SNB-bench.

[12] Todd J. Green, Shan Shan Huang, Boon Thau Loo, and Wenchao Zhou, "Datalog and Recursive Query Processing," Foundations and Trends in Databases 5(2):105-195, 2013. URL: https://www.nowpublishers.com/article/Details/DBS-017. DOI: https://doi.org/10.1561/1900000017.

[13] Francois Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman, "Magic Sets and Other Strange Ways to Implement Logic Programs," PODS 1986, pp. 1-15. DOI: https://doi.org/10.1145/6012.15399.

[14] Amir Shaikhha et al., "Optimizing Nested Recursive Queries," Proceedings of the ACM on Management of Data 2(1), SIGMOD 2024, pp. 1-27.