Source
Idreos, Kersten and Manegold (2007), LIT-1090, CIDR, read in full in NOTE-892: the mechanism (§§3–5, Algorithms 1–2), Figures 2(a)–(c), 3, 4 and 5, and the research agenda of §8.
What was actually shown
The mechanism. The first range query on an attribute copies the column. Each select then finds, in a cracker index, the pieces that hold its bounds, swaps values within those pieces so that values below, inside and above the range are contiguous, records the new boundaries, and returns the result as a slice. Pieces wholly inside the range are not touched. The paper’s aim: “index maintenance should be a byproduct of query processing, not of updates.”
The measurements (MonetDB 5.0alpha, 2.4 GHz Athlon 64, 2 GB, in memory; 10^7 distinct integers; ranges v1 < A < v2 chosen at random):
- First query: “The sort loads the first query with an extra cost of 3 seconds, while a simple scan-select needs 0.27 seconds, and the first cracking operation costs 0.38 seconds.”
- Later queries: per-query cost “highly depends on the size of the piece that is being physically reorganized”, 10 to 100 microseconds over the run, against a few microseconds by binary search on a sorted column. Tuples touched fall by an order of magnitude within about ten queries.
- Break-even: for 10^7 values, sorting’s cumulative cost drops below cracking’s “at around 10^5 queries in our current implementation”. On 4 × 10^7 values the advantage to cracking at 10^5 queries is larger.
- With appended batches and the cracker index discarded, cost rises after each batch and falls back within some hundreds of queries.
What could have come out otherwise. The first query could have cost a multiple of a scan, or per-query cost could have stalled while the index grew; the paper itself notes index upkeep grows with the number of pieces. Neither happened in these runs. The authors confine the comparison: with a known workload, time to prepare and no updates, “then sorting is a superior strategy.”
What this does not say
- That organization follows the workload. The paper claims “Only database portions of past interest are easily localized.” Every experiment uses uniformly random ranges (or TPC-H query 6, parameters undescribed), so every region is eventually queried. That an unqueried region stays unsplit follows from the mechanism; how much stays unorganized under a skewed or shifting workload is not measured.
- That there is a cost model. No expression for per-query or total cost is given, and no rule for when a reorganization is worth making; the authors say one “is needed”.
- That reorganizing is free. The first query costs about 30–40% over a scan and a full copy of the column per cracked attribute.
- That it generalizes beyond this setting. Range selections on an ordered key, in memory, one system. Updates, concurrency and out-of-memory data are open problems in the paper, and downstream operators had to be changed because cracking destroys row order.
- That it is selective. It reorganizes on every query whatever the chance of reuse, and it splits everything it searched, not only what it found.
Connections
- For QUESTION-114 this is sorting as amortized search in a literal sense, with a measured break-even against sorting up front; it does not price the terms the question needs in units that carry over.
- CASE-094: the analogy holds for organizing as a by-product of retrieval and fails on the mechanism, as NOTE-892 sets out.
- LIT-1085 (THEORY-344) places cracking among adaptive methods that trade read overhead against index-building over time.
- THEORY-332 prices the decision this paper leaves open: when to build and when to drop, against a build cost.
Note of 2026-10-20: promoted
The promotion audit (batch 073) promoted this account on the one study it rests on, under ADR-047 v3. LIT-1090 was read in full in NOTE-892, with its figures checked against page images, and each clause of the title carries a number from the paper’s text: 0.38 s for the first cracking select against 0.27 s for a scan and about 3 s more for sorting; 10 to 100 microseconds for later selects; break-even with sort-then-search at about 10^5 queries. The title already confines the claim to the measured setting and keeps the paper’s untested premise as untested, so nothing is dropped. The former promote_when, which asked for an independent measurement in another implementation, moves unchanged to QUESTION-238.