Home › Hard problems › Data and computer systems

Data and computer systems

Estimating query sizes (the 40-year database problem)

Solo: possibleOne person can test a narrow slice of it.

A queryjoin three tablesThe planner guesses"about 10 rows"(say)Picks a planbuilt for 10 rowsThen it runs10,000 rows arrive:1,000 times more"10, I think"a plan fora cupfulrowsthe slow plan was pickedbefore anything ran
A query planner guesses row counts before it runs anything. When the guess is off by 1,000 times, it picks a plan built for the wrong size.

Why it is still open

Query planners guess how many rows each step returns. Guesses can be off by 1,000 times and pick slow plans; learned estimators haven't replaced the old ones.

An experiment one person can run in 8 weeks

On the public JOB benchmark, compare the default planner's guesses with a small learned model. Measure the time lost to bad guesses.

Verdict: Solo: possible

Well studied, so a gain must be clean and real.

The solo test behind the verdict

  1. Can it be measured? There is a number that shows you did better, such as an error rate, a catch rate or a cost per answer.
  2. Is it cheap to try? It runs on a laptop, free open models and open data, or under about ₹50,000 of rented GPU time.
  3. Is there a public yardstick? A benchmark or dataset others use, so your result can be compared and believed.
  4. Would a small win get noticed? A lab, a funder or a customer would care about a 10% improvement, not only a full solution.

Four yeses means Solo: strong. Two or three means Solo: possible. Fewer means Follow, don't build.

NextKeeping thousands of GPUs busy

All 79 hard problems · Working on this, or know of a result we missed? basant@cleandataengineering.ai