DagQL E-Graph Cache

This document describes the current dagql cache implementation centered on the e-graph in dagql/cache.go and dagql/cache_egraph.go.

The code is the source of truth. This doc is meant to make the current model faster to load into your head, not replace reading the code.

For test-running and debugging workflow, see debugging.md. This doc is about how the cache is structured and how it behaves.

What This "E-Graph" Is Here

This is not a full rewrite engine or a generic academic e-graph implementation. In practice, the important pieces are:

• a union-find over digest equivalence classes
• symbolic terms keyed by operation shape plus canonical input eq-classes
• congruence repair when eq-classes merge
• separate materialized results attached to terms and digest indexes

The useful mental model is:

1. A call has a recipe identity.
2. Some different recipes can still be known equivalent because they produce the same output.
3. The cache stores those equivalences as digest eq-classes.
4. Structural lookup uses a term: selfDigest + canonical input eq-classes -> output eq-class.
5. Actual cached payloads are sharedResults hanging off the graph, not nodes in the graph itself.

So the "e-graph" part is mostly the union-find + congruence closure over terms. The cache behavior around ownership, sessions, persistence, and lazy payloads lives around it.

Identity Layers

There are four distinct identity layers worth keeping separate in your head:

1. Recipe digest

   • The authoritative identity of a specific call recipe.
   • Derived from ResultCall / call.ID.
   • Used for exact request lookup first.

2. Extra digests

   • Additional equivalence evidence attached to a result or request.
   • The most important one is content digest.
   • They do not replace recipe identity; they enlarge equivalence.

3. Structural term

   • A symbolic cache lookup key made from:
     • self digest
     • canonicalized input eq-classes
   • This is the real "e-graph lookup" key.

4. Shared result ID

   • A local cache identity for one materialized result payload.
   • This is not semantic identity. It is ownership/lifecycle identity inside the current cache instance.

The Core Invariant

The most important invariant is:

• recipe digests identify specific calls
• eq-classes identify interchangeable outputs
• terms express congruence over equivalent inputs
• sharedResults hold real payloads and lifecycle state

That separation is why the implementation works as well as it does:

• lookup can stay symbolic and cheap
• ownership does not depend on the e-graph shape
• multiple materialized results can share one output eq-class
• a hit can preserve request-facing recipe shape while still reusing an equivalent output

Main Data Structures

Cache Lock Domains

dagql/cache.go splits the cache into three main lock domains:

• callsMu

  • in-flight call bookkeeping
  • arbitrary in-memory call maps

• sessionMu

  • per-session result ownership tracking
  • per-session resource handles
  • per-session lazy span tracking

• egraphMu

  • eq-classes
  • terms
  • result indexes
  • dependency ownership graph
  • persisted edges

This split matters both for correctness and performance. In particular, recent fixes deliberately avoid cross-locking callsMu and egraphMu in observational paths.

Eq-Classes

Eq-class state lives in Cache:

• egraphDigestToClass
• eqClassToDigests
• eqClassExtraDigests
• egraphParents
• egraphRanks

This is a standard union-find setup:

• every known digest belongs to at most one eq-class
• merging two digests means merging their classes
• path compression and ranks keep lookup cheap

The main entry points are:

• ensureEqClassForDigestLocked
• findEqClassLocked
• mergeEqClassesLocked
• repairClassTermsLocked

eqClassExtraDigests is worth calling out separately: it stores labeled class-level digest facts known for an output eq-class. It is not the main direct-hit index. Direct digest hits come from egraphResultsByDigest.

Terms

Terms live in dagql/cache_egraph.go as egraphTerm:

• selfDigest
• inputEqIDs
• termDigest
• outputEqID

Important detail: terms are symbolic only. They do not hold payloads.

termDigest is the digest of:

• self digest
• canonical input eq-class IDs

That means if input eq-classes merge later, the term may need to move to a new termDigest. That is what congruence repair does.

Term indexes:

• egraphTerms
• egraphTermsByTermDigest
• inputEqClassToTerms
• outputEqClassToTerms
• termInputProvenance

Materialized Results

Materialized results are sharedResults in dagql/cache.go.

These hold:

• payload (self, hasValue, isObject)
• authoritative ResultCall
• dependency edges (deps)
• session resource requirements
• snapshot ownership links
• TTL / prune metadata
• persisted envelope for imported lazy payloads
• ownership count (incomingOwnershipCount)
• dependency-attachment barrier state
• lazy-evaluation state

This is a major design point: the e-graph decides equivalence, but the sharedResult owns the payload and lifecycle.

Result-to-Graph Associations

The bridge between symbolic graph and concrete payload is:

• resultOutputEqClasses
• termResults
• resultTerms
• egraphResultsByDigest

These let the cache answer questions like:

• which results are known for this output eq-class?
• which results were directly observed for this exact term?
• which results are indexed under this digest?

That distinction matters for hit selection.

Why Terms And Results Are Separate

One output eq-class can have multiple materialized results.

For example:

• different sessions may have compatible but not identical attached resources
• a result may be imported from persistence and later re-materialized
• the cache may know several digests are equivalent before it has canonicalized down to one surviving payload

Because of that, lookup prefers:

1. results explicitly associated with the matching term
2. then results found by output eq-class / digest equivalence

That behavior lives mainly in:

• appendTermSetResultsLocked
• firstResultForTermSetDeterministicallyAtLocked
• firstResultForOutputEqClassDeterministicallyAtLocked

How Call Identity Feeds The E-Graph

The e-graph consumes structural identity produced upstream by ResultCall / call.ID.

The key functions are in dagql/call/id.go:

• SelfDigestAndInputRefs
• SelfDigestAndInputs

The shape is:

• receiver contributes as an ordered structural input
• ID-valued literals contribute as structural inputs, not self bytes
• implicit inputs contribute to self digest
• module contributes as an input, not self

That distinction is why structural equivalence works: the cache can say "same operation over equivalent inputs" without flattening the whole call into one undifferentiated digest.

Content-preferred digest is related but separate. In dagql/call/id_content.go, it expresses "if outputs are interchangeable by content, what digest should we prefer?" It is used as equivalence evidence, not as the authoritative recipe.

Main Entry Points Into The E-Graph

These are the functions that really matter when reading the system.

1. lookupCacheForRequest

This is the normal lookup path for a new call.

High-level flow:

1. Derive recipe digest.
2. Derive structural self digest and structural input refs.
3. Try exact digest lookup first.
4. If that misses, do structural term lookup.
5. Filter candidates by session resource requirements.
6. Bind session ownership before returning.
7. Normalize imported payloads before the hit escapes.

The actual structural lookup is in lookupMatchForCallLocked.

2. lookupCacheForDigests

This is a digest-only lookup path.

It does not compute a structural term. It looks up by:

• recipe digest
• then extra digests

This is useful when the caller already has digest evidence and does not need the full request-term path.

3. indexWaitResultInEgraphLocked

This is the main publication path for a newly completed result.

It:

• gathers request and response digests
• creates or merges output eq-classes
• ensures the result has a sharedResultID
• associates the result with request term and, when different, response term
• indexes request/response digests onto the result
• accumulates extra-digest evidence on the output eq-class

This is the main place where fresh execution results become lookup-visible.

4. teachResultIdentityLocked

This is the "we got a hit, now teach the graph more about what this result is" path.

This matters because a cache hit may arrive through one route, but we still want future requests for the new recipe shape to resolve directly.

Typical uses:

• a structurally equivalent hit should become addressable by the new request digest too
• new extra digests learned later should merge into the same equivalence set

5. TeachCallEquivalentToResult

This is an externalized way to say:

"this call frame is equivalent to this existing result"

It attaches the result if needed, derives the structural identity for the call, and then teaches that identity onto the result.

6. TeachContentDigest

This is the path for late output-equivalence evidence.

It updates the result call frame with a content digest and teaches that new digest into the e-graph without replacing recipe identity.

7. AttachResult

This is a big one conceptually even though it is not "e-graph logic" in the narrow sense.

It takes a detached result, normalizes any pending ResultCallRefs, tries to resolve it against the cache, and if necessary publishes it as a new sharedResult.

This is one of the main ways semantic attachment and result-call references get bridged into the e-graph world.

8. importPersistedState

On engine startup, persisted mirror tables are read back into memory.

This reconstructs:

• eq-classes
• digests
• results
• terms
• result/term associations
• persisted edges
• snapshot ownership links

This is how the in-memory e-graph is restored after restart.

9. removeResultFromEgraphLocked

This removes a materialized result from the graph when ownership drains to zero.

It:

• removes result-term associations
• removes digest indexes for the result
• removes terms that no longer have any live results in their output eq-class
• possibly resets the whole e-graph if nothing remains

10. compactEqClassesLocked

This is maintenance rather than hot-path lookup, but it matters.

Union-find IDs only grow. After lots of merges and pruning, the class ID space can get sparse. Compaction rebuilds the live eq-class space to keep it smaller and more coherent.

Today this runs after prune when needed.

Lookup In Detail

Exact Digest Hits Come First

lookupMatchForDigestsLocked does:

1. recipe digest lookup
2. if that misses, extra-digest lookup

If the request is a simple pure recipe hit:

• no extra digests
• no TTL
• not persistable

then lookupCacheForRequestLocked takes a fast path and skips teaching the graph anything new. This keeps exact-hit overhead down.

The direct-hit index here is egraphResultsByDigest, which indexes request and response recipe digests plus extra digests for concrete results.

Structural Term Hits Are The Fallback

If exact digest lookup misses, lookupMatchForCallLocked:

1. resolves each input digest to its current eq-class root
2. aborts primary structural lookup if any input digest is still unknown
3. computes termDigest = hash(selfDigest, canonical input eq IDs)
4. looks up terms under that digest
5. gathers candidate results from those terms

Candidate gathering has an intentional preference order:

1. results explicitly associated with the matching term
2. if none exist, results found through the output eq-class

That means the cache prefers "we have seen this exact structural shape produce this result" over "something equivalent exists somewhere in the same output class."

Session Resource Filtering

Even if a result is structurally equivalent, it may depend on session-scoped resources the current session does not have.

selectLookupCandidateForSessionLocked filters candidates using:

• requiredSessionResources on the result
• sessionHandlesBySession for the current session

So the e-graph gives you semantic candidates, then session/resource filtering chooses a result that is actually usable.

Canonical Equivalent Selection

Some paths do not start from a fresh request lookup. They start from an already attached result or a specific result ID and need the best reusable equivalent for the current session.

That is what canonicalEquivalentSharedResultLocked does.

This matters because one output eq-class can have multiple materialized results. The cache can legitimately canonicalize from one sharedResult onto another session-compatible sibling in the same equivalence region.

Publication In Detail

GetOrInitCall / wait

Normal execution goes:

1. lookup miss
2. maybe singleflight via ongoingCall
3. underlying function runs
4. wait() calls initCompletedResult

initCompletedResult

This is the center of fresh result publication.

Important work done here:

• materialize a sharedResult
• preserve existing attached result when the returned value is already cache-backed
• derive request and response structural terms
• collect result-call dependency refs embedded in the authoritative ResultCall
• index the result into the e-graph
• add exact dependency ownership edges
• recompute required session resources
• install persisted edge if needed
• take a temporary handoff ownership hold
• set up the dependency-attachment barrier
• run attachDependencyResults
• sync snapshot owner leases
• register lazy evaluation

That temporary handoff hold is important. It prevents publication races where a freshly published result becomes unowned before the producing waiters or direct attach path have claimed the real session ownership.

Why There Is A Dependency-Attachment Barrier

The current publication order intentionally publishes before attachment is fully complete, because semantic module object attachment needs the parent result to already exist in the cache.

That creates a visibility race: another reader could otherwise observe the payload while AttachDependencyResults is still rewriting it.

The fix is not "publish later." The fix is:

• publish
• keep an attachment barrier on sharedResult
• make hit-return paths wait for that barrier in ensurePersistedHitValueLoaded

That preserves the required publication order for semantic attachment while blocking readers from seeing partially rewritten payloads.

Congruence Repair

The most e-graph-specific logic lives in mergeEqClassesLocked and repairClassTermsLocked.

When output digests or extra digests are merged:

1. union-find