v0.8.18

Built against Mojo 1.0.0 (ed45d567).

A patch release with two entries in it, both about reading a column once where it was being read twice. One is the last of the ClickBench q29 regression, a reduction that built a folded operation once per state slot instead of once per column, which on ninety marked sums over one column was ninety extra passes down a million rows. The other is sortedness, which was asked of a column a row at a time and is now asked a block at a time.

Nothing in the API moves and no answer changes.

Fixed: a reduction builds a folded operation once per column rather than once per slot

Reduce.partial applied an aggregate's folded operation inside the loop over state slots, so a reduction that owns two slots over one column under one operation built that column twice and walked it twice. Two reductions own two slots. A mean is a sum and a count, and since #882 so is a sum marked to answer null over a column that held nothing, which is what the SQL front end builds for every SUM. bind gives both halves the same source column and the same operation, so the second pass produced a column identical to the first one and threw it away.

ClickBench q29 is ninety marked sums over one column under ninety constants, so it was paying ninety extra passes down a million rows. Paired, two drivers built from the same bench source and run back to back, thirteen rounds at loads between thirty and eighty: the fixed driver is faster in every round, and CPU time per run, which is the column that holds still while this machine's load swings, is 583 milliseconds against 380, a factor of 1.53. The two drivers answer q29 identically, ninety columns and one row, checked on the sum of every one of them.

That is the rest of #922, which was the part of the q29 regression #921 did not explain. #921 does not cut this line at all, since a reduction is a breaker and there is no prefix over it, so the morsel fix could not have been the whole of it and this is the other half.

The count itself is not what costs. It is a popcount over the validity bitmap and it stays. What is gone is building the column it counts a second time.

exec/reduce_ninety_marked is the new row in benchmarks/main.mojo, the same ninety sums as exec/reduce_ninety_fused with the mark SQL puts on them. The gap between the two is what a marked sum costs, and while partial built the column once per slot the marked row was about twice the unmarked one with nothing in either file moving.

Changed: a column's sortedness is read a block at a time instead of a row at a time

Several places ask whether a column is already sorted, and the answer decides whether a whole pass of work can be skipped. A group by on a sorted key walks it instead of building a hash table. A semi or anti join whose two key columns are both sorted walks them instead of factorizing both sides. The chunked array, the series and the index each have a gate that asks the same question. All of them went through one function that read the column one row at a time, comparing each sort key against the previous one held in a variable, which is a loop the machine cannot run ahead in because the next comparison needs the value the last iteration wrote.

That cost showed up as a measurable tax rather than as theory. While measuring an unrelated change I built a branch that performs both sortedness scans on a join and then deliberately takes the ordinary route, so the scan is paid and nothing else changes, and it reproduced a regression I had been blaming on the new code. The scan was the cost. On TPC-H q3 the gates rescan about seven and a half million rows a run and get the same answer every time.

The reading is now a block of sort keys against the same block shifted by one row. Two overlapping loads, the same bit twiddle that the sort itself uses to put floats and signed integers into an order a plain comparison gets right, one compare and one reduce, and the loop carries nothing from one block to the next. A column past a quarter of a million rows splits its pairs across the workers, and each worker checks a run of blocks and then asks a shared flag whether somebody has already found a break, so a column that is out of order in its first hundred rows still stops almost at once rather than reading to the end on every core. A column holding nulls keeps the row at a time walk, because there the question is not only whether each pair is in order but whether the run of nulls has been passed yet, and that is state the blocks do not carry.

Measured on a 13900K, TPC-H sf1 in memory, ABBA order with nine runs a side. q21 goes from 0.041 to 0.032 seconds on the medians and q18 from 0.023 to 0.016, which is 1.28 and 1.44 times. q20 reads 0.039 against 0.038 and q4 0.021 against 0.021. q16 and q22 are the useful controls because both are turned away at the sortedness check and go down the ordinary route, so they pay the scan and get nothing back from it, and both are flat at 0.018 and 0.022, which says the faster reading does not cost anything on the queries it cannot help.

What this does not do is spread the answer around. A chunked array does carry a sortedness flag and does remember what it is told, but the flag is set by a sort and by a reader and by almost nothing else, and the two gates that matter most cannot reach it. A group by holds the frame by reference while it reads the key column, so it has nowhere to write the answer and calls the scan that deliberately does not cache. A join works on the array below the level the flag lives at and has no flag to ask at all. Both of them rescan on every call, so what changed here is that the rescan is cheap, not that it is gone.