The mean describes no query

Imagine ten measured searches:

1, 1, 1, 1, 1, 100, 100, 100, 100, 100 milliseconds

The arithmetic mean is 50.5 ms. No query finished near it. The workload has two populations—perhaps warm and cold, cache hit and miss, exact settlement and fuzzy expansion. One number hid the mechanism.

Sort observations $Y_{[1]}\leq\cdots\leq Y_{[n]}$. A percentile is an order statistic or interpolation between order statistics under a declared estimator. The p50 describes the middle; p90 leaves about one in ten observations above it; p99 leaves about one in a hundred. Different standard estimators disagree slightly for small samples, so the receipt names the method.

A percentile needs observations

In $n$ independent observations, the expected number beyond p99 is $0.01n$. One hundred samples contain about one tail observation; ten thousand contain about one hundred. That arithmetic does not guarantee independence or a narrow confidence interval, but it immediately rejects a “stable p99” from a tiny run.

Nonparametric confidence intervals for a population percentile use two sample order statistics. The number of samples below the true percentile follows a binomial distribution, so choose lower and upper ranks whose binomial coverage meets the stated confidence. Report the resulting latency interval, not only a point estimate.

For comparing variants, resample or use paired order-statistic methods on interleaved observations as appropriate. “p99 improved by 8%” is unsupported when the two confidence regions are wide enough to reverse that ordering.

The maximum is usually a poor optimization target. It grows with run length and is dominated by singular host events. Preserve maxima for diagnosis; optimize a justified service objective over a declared population.

Stage tails do not add

If query latency is

$$T=T_{analyze}+T_{expand}+T_{retrieve}+T_{rank}+T_{render},$$

then generally

$$p99(T)\ne\sum_i p99(T_i).$$

The slowest one percent of each stage need not occur on the same query. Measure the end-to-end pipeline for the experience claim and record stage spans for diagnosis. A microbenchmark can explain one term; it cannot substitute for the pipeline distribution.

Prove which artifact ran

A search system is compiled into an index, dictionary, bundle, configuration, and executable. A stale artifact can return plausible results and stable timing. No statistical test detects that it came from a previous revision of the source.

Before the first sample, bind:

source revision
corpus digest and generation
analyzer and ranker versions
index-format version and artifact digest
executable or bundle digest
benchmark configuration and query-set digest
host and runtime profile

Rebuild deterministically and compare the digest expected by the current source with the artifact loaded by the harness. Fail closed on disagreement. This one line of identity evidence prevents an entire class of fluent, reproducible false measurements.

Equalize the carriers

Two implementations of the same recurrence can differ because one allocates a matrix, normalized copy, or candidate object per call while the other reuses owner-scoped scratch. A timer reports the largest difference, whether or not it is the algorithm named in the chart.

Before comparison, state per entrant:

Equalize these carriers where the claim is algorithmic. When a carrier is intrinsic to a public API, report end-to-end cost separately and do not rank it as a kernel-only result.

The sampling process can omit the stall

Suppose a closed-loop harness sends the next request only after the previous one returns. During a ten-second pause it records one slow request and sends no others. A real arrival process might have produced hundreds of waiting requests. The harness coordinated its sampling with the system's delay and omitted the latencies that would have accumulated.

Use an arrival schedule independent of completions when modeling an open workload. Record intended start time and completion time, apply backpressure as an explicit system behavior, and count refused or queued requests. HdrHistogram provides recording modes that compensate for coordinated omission when an expected sampling interval is known; the receipt says whether and how correction was applied.

A closed-loop workload is legitimate when it models a user who cannot issue the next action before seeing the answer. It is misleading when presented as a fixed-rate service workload. Name the population.

Stratify before aggregating

One aggregate query mix can hide every crossover. Report at least:

• exact hit and exact miss;
• prefix, infix, ordered subsequence, one-edit typo, and transposition;
• single-term and multi-term prose;
• path, identifier, title, and body-text candidates;
• common term, rare term, and no match;
• cold artifact, warm artifact, and warm scratch; and
• corpus-scale points derived from one deterministic semantic family.

The judged corpus answers whether ranking is useful. A scale family answers where a cost curve bends. Do not stretch synthetic repetition until it pretends to be relevance evidence, or stretch one judged corpus until it pretends to be a scale study.

Counters locate the term

A clock says the total changed. Deterministic operation counters say which term changed:

dictionary states visited
candidate strings verified
DP cells filled
postings decoded and scored
heap comparisons
bytes copied or decompressed
result rows rendered

Counters belong in tests because their values can be deterministic for a fixed artifact and query. They travel across machines more honestly than nanoseconds. They do not replace time; they connect an observed time change to the algorithmic mechanism claimed to cause it.

Take two $O(n)$ terms: scan a dictionary and rebuild a dictionary-derived lookup table on every query. Remove the scan and time barely changes because the call-invariant table construction remains. Big-O cannot separate equal-order terms. A counter for table entries rebuilt exposes the hidden coefficient and the wrong lifetime.

COMPARE(A, B, QUERIES, REPETITIONS)
Input:  equivalent variants A and B, stratified QUERIES, and REPETITIONS
Output: paired latency samples, counters, and correctness receipts

VERIFY-ARTIFACT-IDENTITY(A, B)
VERIFY-EQUAL-CARRIERS(A, B)
for r ← 1 to REPETITIONS
    for each query in QUERIES
        first ← A
        second ← B
        if r is even
            SWAP(first, second)
        x ← RUN-AND-RECEIPT(first, query)
        y ← RUN-AND-RECEIPT(second, query)
        REQUIRE-EQUAL-SEMANTICS(x, y)
        RECORD-PAIR(query.stratum, x, y)
return SUMMARIZE-PAIRS-WITH-CONFIDENCE()

Interleaving A, B, B, A across repetitions keeps slow drift from becoming the variant effect. It does not remove every confounder; it turns time-adjacent measurements into useful pairs.

Every metric advertises its exploit

A metric is a proxy. Write down how it can improve while the real goal worsens:

If the primary improves and its independent guard worsens, stop. That is not a mixed result to average; it is evidence the proxy detached from the goal.

Test at least one corpus or scale family not used to choose parameters. State what remains unmeasured—comprehensibility and perceived stability do not become zero because the harness has no column for them.

Re-profile after every fix

A profile ranks terms in one particular program. Fix the largest term and the program changes. The former second-place term may become dominant, disappear, or interact differently with caches. Never take two optimizations from one profile.

Use this loop:

1. fingerprint and verify;
2. measure by stratum with counters;
3. form one falsifiable hypothesis;
4. change one mechanism;
5. interleave old and new variants;
6. require semantic equality and paired metric agreement; and
7. profile the new program again.

The exhaustive implementation remains the result oracle. The operation counter is the mechanism oracle. The timer is the host observation. Their agreement supports a causal explanation; any one alone is weaker.

Negative results

Lessons

• Latency is a distribution; mixtures require named strata.
• Percentiles are order statistics under a declared estimator and need enough observations plus confidence.
• Pipeline p99 is measured end to end, not reconstructed from stage p99s.
• Fingerprint source, artifact, corpus, executable, query set, and configuration before timing.
• Equalize carriers before attributing a difference to an algorithm.
• Match the arrival process and account for coordinated omission.
• Pair wall time with deterministic counters and correctness receipts.
• Interleave variants and compare neighboring pairs.
• Every primary metric names its gaming strategy and independent guard.
• Re-profile after each fix because the dominant term moves.

Practice

1. Compute the expected number of observations beyond p99 for sample sizes 100, 1,000, and 100,000.
2. Construct two stage-latency distributions whose individual p99s occur on different requests. Compare the sum with pipeline p99.
3. Design an artifact-identity receipt for a browser search benchmark.
4. Convert a closed-loop harness into an open arrival schedule and specify its overload behavior.
5. Pair each of these primaries with a guard: index size, top-k accuracy, throughput, time to first result.
6. Add counters to the two-$O(n)$ example and show how they distinguish scanning from per-query table construction.

References

1. Jeffrey Dean and Luiz André Barroso. “The Tail at Scale.” Communications of the ACM 56(2), 2013.
2. Gil Tene and HdrHistogram contributors. “HdrHistogram.” Documentation for high-dynamic-range histograms and coordinated-omission correction.
3. NIST/SEMATECH. “Percentiles.” e-Handbook of Statistical Methods, definitions and order-statistic estimators.