THE FOLD / RESPAWN / THE PHOENIX / THE HALLOWEEN PROBLEM
THE HALLOWEEN PROBLEM
the rows keep coming back
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Give everyone under twenty-five thousand a ten percent rise. Run it down an index ordered by salary, and each row you raise moves further along the index — into the part you have not reached yet. You meet it again. And again.
LIT verified live. eight salaries, six of them below the threshold. With the qualifying set decided before any row is touched, the statement performs exactly 6 updates and the lowest earner finishes on 11,000. Running the same statement down a live index instead performs 30 updates — 5× as many — with one row raised 10 separate times, and the lowest earner finishes on 25,937. Afterwards 0 rows remain below the threshold, which is the tell: the statement did not do too little, it ran until its own
LIT verified live. eight salaries, six of them below the threshold. With the qualifying set decided before any row is touched, the statement performs exactly 6 updates and the lowest earner finishes on 11,000. Running the same statement down a live index instead performs 30 updates — 5× as many — with one row raised 10 separate times, and the lowest earner finishes on 25,937. Afterwards 0 rows remain below the threshold, which is the tell: the statement did not do too little, it ran until its own
WHERE clause stopped being true of anybody.2 HOW IT WAS WEAVED · AI + HUMAN
Named at IBM Research on Halloween 1976, when Don Chamberlin, Pat Selinger and Morton Astrahan hit it and could not explain it by the end of the day. The fix — separate reading from writing — is called Halloween protection and every serious optimiser has one.
AVAN (AI) reports the final salaries rather than only the update count, because the count alone reads like a performance problem. It is not: the answer is wrong, deterministically and reproducibly, and 25,937 against 11,000 is a payroll. The 0 rows remaining below is the clean statement of what went wrong — the query reached a fixed point instead of a result.
AVAN (AI) reports the final salaries rather than only the update count, because the count alone reads like a performance problem. It is not: the answer is wrong, deterministically and reproducibly, and 25,937 against 11,000 is a payroll. The 0 rows remaining below is the clean statement of what went wrong — the query reached a fixed point instead of a result.
3 ONE DIMENSION
6 updates, or 30. Same statement, same data.
4 TWO DIMENSIONS · INTERACTIVE
Step the cursor and watch a row you already raised come back.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that the scan must not see its own writes. The inverse is that the statement was never wrong — it was read as a command when it was written as a description.
WHERE salary < 25000 describes a set; executing it row by row against a moving index turns it into a loop with a termination condition, and a loop that raises anyone it finds below the line terminates only when nobody is below the line. Read backwards, declarative languages are exactly the ones where the order of evaluation is invisible in the source, which means the difference between a set and a fixed point is invisible too.LIT eight salaries, six below the threshold: with the qualifying set decided before any row is touched the statement performs exactly 6 updates and the lowest earner finishes on 11,000, while running the same statement down a live index performs 30 updates - 5x as many - with one row raised 10 separate times and the lowest earner finishing on 25,937; afterwards 0 rows remain below the threshold, which is the tell, because the statement did not do too little, it ran until its own WHERE clause stopped being true of anybody
FIG Named at IBM Research on Halloween 1976, when Don Chamberlin, Pat Selinger and Morton Astrahan hit it and could not explain it by the end of the day. The fix - separating reading from writing - is called Halloween protection and every serious optimiser has one. AVAN reports the final salaries rather than only the update count, because the count alone reads like a performance problem and it is not: the answer is wrong, deterministically, and 25,937 against 11,000 is a payroll. The 0 rows remaining below is the clean statement of what went wrong - the query reached a fixed point instead of a result.
FIG Named at IBM Research on Halloween 1976, when Don Chamberlin, Pat Selinger and Morton Astrahan hit it and could not explain it by the end of the day. The fix - separating reading from writing - is called Halloween protection and every serious optimiser has one. AVAN reports the final salaries rather than only the update count, because the count alone reads like a performance problem and it is not: the answer is wrong, deterministically, and 25,937 against 11,000 is a payroll. The 0 rows remaining below is the clean statement of what went wrong - the query reached a fixed point instead of a result.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PHOENIX · David Lee Wise (ROOT0), with AVAN