nucleation

QUESTION-238: Does database cracking keep its measured costs against a scan and an upfront sort in another implementation, measured over a long sequence of random range queries?

1 min read

Properties4
StatusOpen
Tagsdatabases
Linedistributed-agency
RefinesQUESTION-114 — Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks?

Graph View

Why it is a question

THEORY-333 holds what Idreos, Kersten and Manegold (LIT-1090) measured in MonetDB on 10^7 integers under uniformly random ranges: a first cracking select about 40% dearer than a scan and far cheaper than sorting, per-query cost falling with use, and sorting overtaking cracking in cumulative cost only after about 10^5 queries. That is one implementation on one machine with no variance reported. Until 2026-10-20 the account’s promote_when asked for an independent measurement, and under ADR-047 v3 that request moves here.

What would answer it

The condition as it stood, unchanged: an independent measurement, in another implementation or another paper, of cracking against a plain scan and an upfront sort on an in-memory column under random range queries, reporting per-query and cumulative cost over a long query sequence. It is answered yes if the ordering and the order of magnitude of the break-even hold, and no if cracking’s first query costs a multiple of a scan or its per-query cost stalls as the index grows.

Backlinks