`Store::queryMissing`¶

Source: src/libstore/misc.cc:102-315

Purpose¶

Given a set of top-level derived paths (derivations + output names, or opaque store paths), determines what will need to be built vs substituted vs is unknown. Called by:

nix build --dry-run via printMissing(store, pathsToBuild) at src/libcmd/installables.cc:628
The Worker at the start of every build to pre-populate substitute info (src/libstore/build/worker.cc:339-340):
```
/* Call queryMissing() to efficiently query substitutes. */
store.queryMissing(topPaths);
```

Return type¶

struct MissingPaths {
    StorePathSet willBuild;        // derivations that must be built locally
    StorePathSet willSubstitute;   // output paths that can be fetched from substituters
    StorePathSet unknown;          // paths no one has
    uint64_t downloadSize;         // total bytes to download for willSubstitute
    uint64_t narSize;              // total uncompressed NAR size
};

Algorithm¶

Walks the transitive dependency closure of the given targets using a ThreadPool.

`DerivedPath::Built` handling (a derivation with specific wanted outputs)¶

doPath(Built{drvPath, outputs}):
  if already seen → return

  if !isValidPath(drvPath):
    → mark drvPath as "unknown"
    → return

  // Check which outputs are known and which are valid
  for each output in queryPartialDerivationOutputMap(drvPath):
    if outputPath is null → knownOutputPaths = false
    if output is wanted AND !isValidPath(outputPath) → add to invalid set

  if knownOutputPaths AND invalid is empty → return (all good)

  // Read the derivation to check allowSubstitutes
  drv = derivationFromPath(drvPath)
  drvOptions = derivationOptionsFromStructuredAttrs(drv)

  if CA derivation with unknown outputs AND useSubstitutes:
    → check each output's Realisation against every substituter
    → if any output has no realisation → knownOutputPaths = false

  if knownOutputPaths AND useSubstitutes AND substitutesAllowed:
    → for each invalid output, query ALL substituters via querySubstitutablePathInfos
    → if substituter has it: account downloadSize/narSize, mark willSubstitute
    → if no substituter has it: mark willBuild, recursively enqueue all inputDrvs
  else:
    → mark willBuild, recursively enqueue all inputDrvs

`DerivedPath::Opaque` handling (a concrete store path)¶

doPath(Opaque{path}):
  if already seen → return
  if isValidPath(path) → return

  query all substituters via querySubstitutablePathInfos
  if any has it: → mark willSubstitute, account sizes, enqueue references
  else: → mark unknown

Recursive expansion¶

When a derivation is marked willBuild, all its inputDrvs are enqueued (line 146-148):

for (const auto & [inputDrv, inputNode] : drv.inputDrvs.map) {
    enqueueDerivedPaths(makeConstantStorePathRef(inputDrv), inputNode);
}

`querySubstitutablePathInfos` (called for each invalid output)¶

In src/libstore/store-api.cc:444-493:

void Store::querySubstitutablePathInfos(const StorePathCAMap & paths, SubstitutablePathInfos & infos) {
    if (!useSubstitutes) return;

    for (auto & path : paths) {
        for (auto & sub : getDefaultSubstituters()) {
            auto info = sub->queryPathInfo(subPath);
            // record downloadSize, narSize, references
        }
    }
}

Iterates every configured substituter per path, calling queryPathInfo on each.

Daemon protocol path¶

Client calls RemoteStore::queryMissing (src/libstore/remote-store.cc:751-772):

Sends WorkerProto::Op::QueryMissing to the daemon

Daemon handler (src/libstore/daemon.cc:946-956):

case WorkerProto::Op::QueryMissing: {
    auto targets = WorkerProto::Serialise<DerivedPaths>::read(*store, rconn);
    logger->startWork();
    auto missing = store->queryMissing(targets);  // calls LocalStore::queryMissing
    logger->stopWork();
    WorkerProto::write(*store, wconn, missing.willBuild);
    WorkerProto::write(*store, wconn, missing.willSubstitute);
    WorkerProto::write(*store, wconn, missing.unknown);
    conn.to << missing.downloadSize << missing.narSize;
    break;
}

The daemon runs Store::queryMissing (the default implementation from misc.cc) — there is no LocalStore override.
If the daemon is too old (protocol < 1.19), RemoteStore::queryMissing falls back to the default implementation which runs locally over the connection.

Why it can take 30+ seconds¶

Factor	Detail
Walks the full dependency closure	For a derivation like `hello` from nixpkgs, it walks every transitive dependency — hundreds to thousands of derivations, each visited exactly once
N+1 substituter queries per output	Every invalid output path triggers `querySubstitutablePathInfos`, which iterates all configured substituters (`getDefaultSubstituters()`) calling `queryPathInfo` on each. With 500 invalid outputs and 2 substituters, that's 1000 HTTP requests
`queryPartialDerivationOutputMap` per drv	Reads the `.drv` file (from daemon or disk) for each derivation to resolve output paths
`derivationFromPath` per drv marked willBuild	Full deserialization of the derivation to check structured attrs and `allowSubstitutes`
Daemon is synchronous	The daemon handler holds the connection for the entire duration — one `QueryMissing` blocks all other clients on that daemon connection
No caching across invocations	Every `nix build` call re-walks the entire graph from scratch. The result is thrown away after use
No substituter-level batching	`queryPathInfo` is called one path at a time per substituter. Many substituters (like cache.nixos.org) support narinfo batch lookups, but `queryMissing` doesn't use them here
ThreadPool parallelism is limited	The thread pool only parallelizes checking multiple invalid outputs of the same derivation against substituters (`misc.cc:274-275`). Different derivations are processed sequentially by the `doPath` queue

A realised output, and a sibling that is not¶

queryMissing reads every output of a derivation to decide knownOutputPaths, and it ignores the outputs that the caller wants. The loop is at misc.cc:217-225:

for (auto & [outputName, pathOpt] : queryPartialDerivationOutputMap(drvPath)) {
    if (!pathOpt) {
        knownOutputPaths = false;
        break;
    }
    if (bfd.outputs.contains(outputName) && !isValidPath(*pathOpt))
        invalid.insert(*pathOpt);
}

The break runs for an output that the caller did not ask for. The next line reads bfd.outputs, and the substituter loop at misc.cc:250 reads bfd.outputs as well. So two of the three tests honour the wanted outputs and the first one does not. The comment above the loop states the intent that the code misses: "CA derivations for which we have a trust mapping for all wanted outputs".

A content-addressed derivation reaches this state after one ordinary build. DerivationGoal holds one wantedOutput, and it registers a realisation for that output alone, at derivation-goal.cc:228-236. The build of the resolved derivation makes every output, and Nix maps one of them back to the original derivation.

The measurement¶

ca/content-addressed.nix gives rootCA the outputs out, dev and foo. This runs against Nix 2.34.8, with no daemon and no pynixd:

$ nix build -f content-addressed.nix rootCA^out
$ sqlite3 db.sqlite 'select drvPath, outputName from Realisations'
sha256:e76acd40...|out            # the original rootCA.drv, one output
sha256:39850e18...|dev
sha256:39850e18...|foo            # the resolved derivation, all three
sha256:39850e18...|out

$ nix build -f content-addressed.nix rootCA^out --dry-run
this derivation will be built:
  .../gfzi77x6b81brl6b3lmpgmi2vrn6wp1f-rootCA.drv

The output out is realised, and its path is valid. Nix still names the derivation. After nix build -f content-addressed.nix 'rootCA^*' registers dev and foo as well, the same --dry-run command names nothing. So the siblings are the cause.

What pynixd does¶

QueryMissingPlanGoal._classify_derivation reads the wanted outputs alone, through selected_output_paths. pynixd also registers a realisation for every output that the build made, in _register_realisations, and not for the wanted one alone. Each half makes the answer of pynixd complete where the answer of Nix is not, so pynixd leaves rootCA.drv out of willBuild and nix-daemon puts it in.

pynixd keeps its answer. Issue #26 holds the difference, and issue #23 holds the convention for a defect of Nix that pynixd copies. This is not one of those: pynixd does not copy this defect.

Lillecarl/nix#312 reports the defect, and it gives the correction: read bfd.outputs in the first test as well, which makes the three tests of the function agree.

Store::queryMissing¶