Aggregation Queries

The previous lesson produced a sorted document list and discussed that list’s top ten. The questions sitting on the loan desk’s board, by contrast, do not want a document: how many books fall under each subject heading, how many times per book have this search’s results been borrowed, what does the loan curve look like across years. These questions run on the same inverted index, but their output is not a sorted list.

Three forms are distinguished. A metric aggregation produces a single number from a set of documents: count, sum, average, maximum. A bucket aggregation splits the set into parts by a key and computes a metric within each part. A pipeline aggregation takes its input not from documents but from another aggregation’s buckets: cumulative share, moving average, difference between buckets.

That aggregation ignores order is this lesson’s first observation. The query evaluator produces a sorted list; the aggregation reads that list’s set, not its order. It has its own order, but that order is bucket order. The lesson measures set and order on this plane, and counts the cost in bytes.

Corpus, Loan Record, and Three Aggregations

Code	Assumption	Value	Rationale
QR14	loan record	each book produces as many events as its loan count	the record is derived from the corpus, no separate seed needed
QR15	reader pool	40,000 readers, skewed selection	so the distinct reader count per bucket produces high cardinality
QR16	metric bucket	three numbers per bucket (count, sum, maximum)	a fixed 24-byte bucket state
QR17	aggregation input	the entire matching set	the top-N result limit does not apply to the aggregation

QR17 is quiet but decisive: even though the user is shown ten results, the aggregation sees all 325 documents; its cost grows with the size of the matching set, not the number of results shown.

// corpus.mjs — library catalog: seeded corpus, inverted index, and matching set.
export const N = 1200, SEED = 20260801, FIELDS = ["title", "summary", "subject", "author"];
let d = SEED;                                             // 32-bit generator, no overflow
export const random = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const pick = (a) => a[Math.floor(random() * a.length)];
const THEMES = [["story|tale", "literature", "short selection collection narrative fiction rural"],
  ["fable", "children's literature", "child illustrated school youth forest sleep"],
  ["history", "history", "ottoman republic archive document chronicle foundation"],
  ["ocean", "travel", "coast fisherman harbor ship island lighthouse"],
  ["mathematics", "science", "geometry number proof theory solution probability"],
  ["poetry", "poetry", "verse collected divan translation selection meter"]]
  .map(([k, subject, a]) => ({ k: k.split("|"), subject, core: a.split(" ") }));
const COMMON = "book volume edition publication review notes introduction glossary".split(" ");
const FIRST_NAMES = "James Emma Simon Nora Kevin Ocean Grace Owen Meredith Blake".split(" ");
const SURNAMES = "Stone Bishop Miller Hayes Reed Frost".split(" ");

export const documents = Array.from({ length: N }, (_, id) => {
  const t = pick(THEMES), draw = t.k[t.k.length > 1 && random() < 0.5 ? 1 : 0], sm = [draw, draw];
  const title = [...new Set([draw, pick(t.core), pick(t.core)])];
  t.core.forEach((s, j) => { if (random() < 1 / (1 + j * 0.42)) sm.push(s); });
  COMMON.forEach((s, j) => { if (random() < 0.55 / (1 + j * 0.28)) sm.push(s); });
  if (random() < 0.5) sm.push(pick(pick(THEMES).core));   // word leaking from another theme
  for (let k = sm.length - 1; k > 0; k -= 1) { const j = Math.floor(random() * (k + 1));
    [sm[k], sm[j]] = [sm[j], sm[k]]; }
  // the subject tag is a publisher decision: a quarter of documents do not match the text's theme
  return { id, title: title.join(" "), summary: sm.join(" "),
    subject: (random() < 0.25 ? pick(THEMES) : t).subject,
    author: `${pick(FIRST_NAMES)} ${pick(SURNAMES)}`, year: 1975 + Math.floor(random() ** 0.6 * 50),
    loans: Math.floor(random() ** 3 * 400) };
});

export const tokenize = (s) => s.toLocaleLowerCase("en-US").match(/[\p{L}\p{N}]+/gu) ?? [];
export function buildIndex(bs) {                          // per-field inverted index
  const idx = {};
  for (const a of FIELDS) {
    const postings = new Map();
    for (const b of bs) for (const t of new Set(tokenize(b[a]))) {
      if (!postings.has(t)) postings.set(t, []);
      postings.get(t).push(b.id);
    }
    idx[a] = postings;
  }
  return idx;
}
export function matching(idx, query) {    // documents carrying at least one query term
  const s = new Set();
  for (const a of FIELDS) for (const t of tokenize(query))
    for (const id of idx[a].get(t) ?? []) s.add(id);
  return s;
}

Bucket Count Is a Memory Decision

A bucket aggregation is determined by the question “which field do we group by,” and that is a memory decision: each bucket must keep its own state to compute its metric. Metrics like count and sum need a fixed amount of space per bucket; distinct counting does not, because knowing how many separate readers there were requires keeping a representation of those readers. The setup measures both for five bucket keys: an exact set and a cardinality estimate. The estimate’s structure was built and measured in M17/K06; here it is used as a tool, and the bytes it holds are read from its own buffer.

// aggregation.mjs — bucket count and distinct-count byte cost: exact set and estimator.
import { documents, random, N, SEED } from "./corpus.mjs";
const READERS = 40_000, events = [];                      // each book as many times as its loan count
for (const b of documents) for (let i = 0; i < b.loans; i += 1)
  events.push([b.id, 1 + Math.floor(random() ** 2 * READERS)]);  // reader selection is skewed

class ExactSet {                                          // open addressing, empty slot 0
  constructor() { this.table = new Int32Array(16); this.n = 0; }
  slot(t, x) { let i = (Math.imul(x, 2654435761) >>> 0) & (t.length - 1);
    while (t[i] !== 0 && t[i] !== x) i = (i + 1) & (t.length - 1); return i; }
  add(x) {
    if ((this.n + 1) * 2 > this.table.length) { const y = new Int32Array(this.table.length * 2);
      for (const v of this.table) if (v !== 0) y[this.slot(y, v)] = v; this.table = y; }
    const i = this.slot(this.table, x);
    if (this.table[i] === 0) { this.table[i] = x; this.n += 1; }
  }
}
class Estimator {          // cardinality estimate: structure was built in M17/K06, used here as a tool
  constructor(p) { this.p = p; this.R = new Uint8Array(1 << p); }
  add(x) { let h = Math.imul(x ^ 0x9e37, 0x85ebca6b) >>> 0;
    h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35) >>> 0; h = (h ^ (h >>> 16)) >>> 0;
    const i = h >>> (32 - this.p), w = (h << this.p) >>> 0;
    const r = w === 0 ? 33 - this.p : Math.clz32(w) + 1;
    if (r > this.R[i]) this.R[i] = r; }
  estimate() { const m = this.R.length; let z = 0, s = 0;
    for (const v of this.R) { z += 2 ** -v; if (v === 0) s += 1; }
    const e = (0.7213 / (1 + 1.079 / m)) * m * m / z;
    return e <= 2.5 * m && s > 0 ? m * Math.log(m / s) : e; }
}

const fmt = (x) => Math.round(x).toLocaleString("en-US");
const KEYS = { subject: (b) => b.subject, decade: (b) => `${Math.floor(b.year / 10) * 10}`,
  year: (b) => `${b.year}`, author: (b) => b.author, book: (b) => `${b.id}` };
console.log(`corpus ${N} documents, seed ${SEED}; loan record ${fmt(events.length)} events, ` +
  `${fmt(READERS)} reader pool\n`);
console.log("bucket field".padEnd(12) + "buckets".padStart(8) + "metric".padStart(8) +
  "exact distinct".padStart(16) + "estimate p8".padStart(13) + "error".padStart(8) +
  "estimate p12".padStart(14) + "error".padStart(8) + "largest bucket".padStart(16));
for (const [label, f] of Object.entries(KEYS)) {
  const exact = new Map(), approx = [new Map(), new Map()], P = [8, 12];
  for (const [book, reader] of events) {
    const k = f(documents[book]);
    if (!exact.has(k)) { exact.set(k, new ExactSet()); P.forEach((p, j) => approx[j].set(k, new Estimator(p))); }
    exact.get(k).add(reader); approx.forEach((m) => m.get(k).add(reader));
  }
  let exactBytes = 0, largest = 0;
  const approxBytes = [0, 0], error = [0, 0];
  for (const [k, s] of exact) {
    exactBytes += s.table.byteLength; largest = Math.max(largest, s.n);
    approx.forEach((m, j) => { approxBytes[j] += m.get(k).R.byteLength;
      error[j] = Math.max(error[j], Math.abs(m.get(k).estimate() - s.n) / s.n); });
  }
  console.log(label.padEnd(12) + fmt(exact.size).padStart(8) + fmt(exact.size * 3 * 8).padStart(8) +
    fmt(exactBytes).padStart(16) + fmt(approxBytes[0]).padStart(13) +
    `%${(error[0] * 100).toFixed(1)}`.padStart(8) +
    fmt(approxBytes[1]).padStart(14) + `%${(error[1] * 100).toFixed(1)}`.padStart(8) +
    `${fmt(largest)} distinct`.padStart(16));
}

corpus 1200 documents, seed 20260801; loan record 120,809 events, 40,000 reader pool

bucket field buckets  metric  exact distinct  estimate p8   error  estimate p12   error  largest bucket
subject            6     144         786,432        1,536   %11.1        24,576    %1.6 15,257 distinct
decade             6     144         819,200        1,536    %6.5        24,576    %2.1 20,949 distinct
year              50   1,200       1,202,176       12,800   %18.5       204,800    %2.8  4,392 distinct
author            60   1,440       1,318,912       15,360   %14.8       245,760    %3.3  3,908 distinct
book           1,045  25,080       1,401,216      267,520   %33.1     4,280,320    %8.2    394 distinct

The byte columns are read from the structures’ own buffers; the metric column is the bucket count times twenty-four.

The metric column shows why a bucket aggregation is assumed to be cheap: 25,080 bytes for 1,045 buckets. Even if the bucket count grew a thousandfold, this column would not reach a megabyte; the statement “bucket count takes memory” is nearly false for a metric aggregation.

The distinct-count column is a different world. For the same 1,045 buckets, the exact sets hold 1,401,216 bytes — fifty-five times the metric state. The exact column does not grow much with bucket count either — 786,432 at six buckets, 1,401,216 at one thousand forty-five — because what determines the cost is not the bucket count but the number of distinct readers spread across the buckets.

The estimate columns show where the decision actually sits. At six buckets, the p8 estimate wants 1,536 bytes — one five-hundred-twelfth of the exact set — for a worst-case bucket error of 11.1 percent. Moving to p12 drops the error to 1.6 percent and raises the cost to 24,576 bytes — still one thirty-second of the exact figure. But in the last row the sign reverses: for one thousand forty-five buckets, the p12 estimate wants 4,280,320 bytes, three times the exact sets. An estimator wants a fixed buffer per bucket; as buckets shrink, that fixed amount exceeds the distinct count it is meant to represent. M17/K06 measured this for a single structure; in a bucket aggregation, the same break comes with the bucket count itself.

Error also reads by bucket size: the worst deviation is 6.5 percent at six buckets and 33.1 percent at one thousand forty-five. An estimate’s error should be judged not over total cardinality but over the smallest bucket; the report will be wrong not where the buckets are large, but where they are small.

Which Set an Aggregation Runs On

The second decision is not about memory but about meaning: is the aggregation computed over the whole corpus, over the query’s matching set, or over the set left after the user’s applied filter? The three give three different numbers, and all three can be “correct.”

// buckets.mjs — which set an aggregation runs on: corpus, matched set, filtered set; and pipeline.
import { documents, buildIndex, matching } from "./corpus.mjs";
const idx = buildIndex(documents);
const matched = [...matching(idx, "ocean ship")].map((id) => documents[id]);
const filtered = matched.filter((b) => b.subject === "travel");
const fmt = (x) => Math.round(x).toLocaleString("en-US");
const bucket = (bs, f) => {                               // bucket: key -> count and loans
  const m = new Map();
  for (const b of bs) {
    const k = f(b), v = m.get(k) ?? { n: 0, loans: 0 };
    v.n += 1; v.loans += b.loans; m.set(k, v);
  }
  return [...m].sort((x, y) => y[1].n - x[1].n || (x[0] < y[0] ? -1 : 1));
};

const corpusBuckets = new Map(bucket(documents, (b) => b.subject));
console.log(`subject buckets — corpus ${documents.length}, matched ${matched.length}, ` +
  `${filtered.length} documents after the subject filter\n`);
console.log("subject".padEnd(23) + "corpus".padStart(8) + "matched".padStart(9) +
  "matched loans".padStart(15) + "per book".padStart(14));
for (const [k, v] of bucket(matched, (b) => b.subject))
  console.log(k.padEnd(23) + fmt(corpusBuckets.get(k).n).padStart(8) + fmt(v.n).padStart(9) +
    fmt(v.loans).padStart(15) + (v.loans / v.n).toFixed(1).padStart(14));
console.log("bucket count if the same aggregation runs on the filtered set: " +
  `${bucket(filtered, (b) => b.subject).length}`);

const yearBuckets = bucket(matched, (b) => `${b.year}`);
const byLoans = [...yearBuckets].sort((x, y) => y[1].loans - x[1].loans);
const total = (l) => l.reduce((s, [, v]) => s + v.loans, 0);
console.log(`\npipeline: cumulative share over the loan total of year buckets`);
console.log("bucket set".padEnd(16) + "buckets".padStart(9) + "loans".padStart(9) +
  "top three buckets' share".padStart(26) + "top bucket's share".padStart(21));
for (const [label, list] of [["full", byLoans], ["top 10 buckets", byLoans.slice(0, 10)],
  ["top 3 buckets", byLoans.slice(0, 3)]]) {
  const t = total(list);
  console.log(label.padEnd(16) + `${list.length}`.padStart(9) + fmt(t).padStart(9) +
    `%${((total(list.slice(0, 3)) / t) * 100).toFixed(1)}`.padStart(26) +
    `%${((list[0][1].loans / t) * 100).toFixed(1)}`.padStart(21));
}

subject buckets — corpus 1200, matched 325, 168 documents after the subject filter

subject                  corpus  matched  matched loans      per book
travel                      208      168         14,842          88.3
poetry                      208       35          3,761         107.5
science                     185       34          2,886          84.9
history                     206       33          2,937          89.0
literature                  220       30          3,875         129.2
children's literature       173       25          3,895         155.8
bucket count if the same aggregation runs on the filtered set: 1

pipeline: cumulative share over the loan total of year buckets
bucket set        buckets    loans  top three buckets' share   top bucket's share
full                   49   32,196                     %15.4                 %5.4
top 10 buckets         10   13,181                     %37.6                %13.1
top 3 buckets           3    4,961                    %100.0                %34.8

The first two columns are two different numbers for the same bucket. The corpus has 208 travel books; the “ocean ship” query’s matching set has 168. A surface that shows the user “travel (208)” gives information independent of the query; “travel (168)” describes navigating within the query. Mixing the two breaks the totals: the matched column sums to 325, the corpus column sums to 1,200.

The per-book loans column shows the rule for reading a metric: the highest value, 155.8, is in the children’s literature bucket, but that bucket has only 25 documents. An average drawn from twenty-five documents and one drawn from a hundred sixty-eight documents are not equally trustworthy.

The filter row turns navigation surfaces’ classic mistake into a number. When the user selects “travel,” the result set drops to 168 documents, and if the same subject aggregation runs on that set, it returns a single bucket: no other subject appears on the surface, and the selection cannot be changed. The subject aggregation must be computed on the set before its own filter is applied, and after the other filters are applied. The order between aggregation and filtering is not a display preference; it is a decision that determines the set.

The pipeline table shows the last issue. The answer to “what share of total loans do the top three years hold” is 15.4 percent when all fifty buckets are seen, 37.6 percent when only the top ten buckets are seen, and 100 percent when three buckets are seen. Because a pipeline aggregation takes its input from buckets, not documents, a truncated input produces a wrong output, and the error cannot be seen by looking at the output — all three numbers are internally consistent. Truncating buckets looks like a display decision, but it changes the pipeline’s input.

Summary

• Aggregation does not use document order; it reads the set. Its own order is bucket order, and buckets can be arranged by count, by key, or by metric.
• A metric bucket is twenty-four bytes per bucket: 25,080 bytes for 1,045 buckets. A distinct-count bucket wants 1,401,216 bytes with exact sets on the same buckets, and its cost depends on the number of distinct readers in the buckets, not the bucket count.
• Cardinality estimation gains five hundred times at few buckets (1,536 bytes against 786,432 at six buckets) and loses at many buckets: the p12 estimate for 1,045 buckets is 4,280,320 bytes, three times the exact figure.
• An estimate’s error is read at the smallest bucket: the worst deviation is 6.5 percent at six buckets, 33.1 percent at one thousand forty-five.
• The same subject aggregation gives 208 over the corpus, 168 over the matching set, and a single bucket after its own filter; the pipeline’s answer likewise ranges from 15.4 percent to 100 percent depending on the bucket count in its input.

Next Step

Aggregations produced numbers, the query evaluator produced a sorted list; neither addressed how the result appears to the reader. What sits on the screen is not a document identifier but a snippet drawn from the book’s title and summary; which part of that snippet gets picked depends on where the query’s word matches, and that information was not kept during scoring. The second question is heavier: when the reader moves to page twenty, how the same ranking is preserved, and how many candidates that requires keeping in memory, was never asked. The next lesson takes up result presentation and the cost of deep pagination.