Fetch

The fetch operation computes the value of a query. It prefers to reuse memoized values when it can.

Input queries

Input queries simply load the result from the table.

Interned queries

Interned queries map the input into a hashmap to find an existing integer. If none is present, a new value is created.

Derived queries

The logic for derived queries is more complex. We summarize the high-level ideas here, but you may find the flowchart useful to dig deeper. The terminology section may also be useful; in some cases, we link to that section on the first usage of a word.

• If an existing memo is found, then we check if the memo was verified in the current revision. If so, we can directly return the memoized value.
• Otherwise, if the memo contains a memoized value, we must check whether dependencies have been modified:
  • Let R be the revision in which the memo was last verified; we wish to know if any of the dependencies have changed since revision R.
  • First, we check the durability. For each memo, we track the minimum durability of the memo's dependencies. If the memo has durability D, and there have been no changes to an input with durability D since the last time the memo was verified, then we can consider the memo verified without any further work.
  • If the durability check is not sufficient, then we must check the dependencies individually. For this, we iterate over each dependency D and invoke the maybe changed after operation to check whether D has changed since the revision R.
  • If no dependency was modified:
    • We can mark the memo as verified and return its memoized value.
• Assuming dependencies have been modified or the memo does not contain a memoized value:
  • Then we execute the user's query function.
  • Next, we compute the revision in which the memoized value last changed:
    • Backdate: If there was a previous memoized value, and the new value is equal to that old value, then we can backdate the memo, which means to use the 'changed at' revision from before.
      • Thanks to backdating, it is possible for a dependency of the query to have changed in some revision R1 but for the output of the query to have changed in some revision R2 where R2 predates R1.
    • Otherwise, we use the current revision.
  • Construct a memo for the new value and return it.