v0.8.13

Built against Mojo 1.0.0 (ed45d567).

A patch release that finishes the regular expression thread 0.8.12 started, and closes issue #863 with it.

0.8.12 taught the engine to remember what it did, which answered the scans that ask whether a row matched. The three that ask where each group matched, which are replace, extract and count, could not use that, because a cache of position sets knows that a row matched and not where. This release adds the engine that answers those. It backtracks, which is the thing this library refuses to do, and it is safe because it writes down every pair of an instruction and a position it has already tried and never tries one twice. That is RE2's BitState, the bound is the same one the machine has, and the machine is still underneath it for any row long enough that the bitmap would not fit.

All three scans run it now. On a million URLs replace with the ClickBench q28 pattern goes from about 2.11 s to about 0.75 s and count on the same pattern from about 0.94 s to about 0.39 s. On the suite itself, q28 at 1M in memory mode goes from 2.33 s to 0.82 s measured back to back on the same loaded machine, with q27 unmoved beside it and DuckDB at 0.20 s in the same run. That is about four times DuckDB rather than the eight this started at, and what is left of it is the decode and the copy the kernel does around the engine rather than the engine, which is issue #889.

The counting scans moved out of Machine while that happened, so a caller that used Machine.counts or counts_text from the kernel now calls counted or counted_text from firepanda/kernel/regex/count.mojo. Nothing pandas-facing changes.

Beside it, two wrong answers about nothing. A sum over values that are every one null answered zero and now answers null, which is what DuckDB does and what SQL says, and so does a window sum over a partition of nothing but nulls. And a group by on several keys now factorizes them one per worker, which is worth the one TPC-H query firepanda was behind a rival on.

Changed: count runs the backtracker, and the two counting scans move out of the machine

The last of the three scans that were still on the machine alone. Counting over a million URLs goes from about 0.94 s to about 0.39 s on the ClickBench q28 pattern, from about 1.62 s to about 0.94 s on a two group pattern, and from about 0.28 s to about 0.19 s on a short one.

Both counting loops moved to a new file, firepanda/kernel/regex/count.mojo, and they are no longer methods on the machine. A scan is a loop that runs the pattern, does something with the match and looks again, and both halves of that are Arrow's rules or Python's rather than the engine's. Now that a scan also picks between two engines, it cannot be written inside one of them. The replacing scan was already arranged that way and this is the counting scan catching up, so Machine is the machine and nothing else.

counts and counts_python are gone from Machine and counts_text and counts_python_text are gone from firepanda/kernel/regex/pike.mojo. The replacements are counted, counted_python, counted_text and counted_python_text in the new file, and the two one shot forms take the same arguments they took before. Nothing pandas-facing changes and no answer moves.

The count differential now runs the whole generated corpus through both engines, which was the last of the three that did not.

Changed: replace and extract run the backtracker

The backtracker in the entry below is wired under the two kernels that read the groups out of a match. Every search goes through one function that asks it first and asks the machine for the rows it hands back, so a caller never learns which of the two answered and there is one place in the library where that is decided.

On a million URLs with four threads, replace with the ClickBench q28 pattern goes from about 2.11 s to about 0.75 s, a two group pattern that matches nothing in most rows from about 6.40 s to about 3.14 s, and a short two group pattern from about 0.85 s to about 0.45 s. Those are smaller multiples than the engine on its own gets, which is the honest shape of it: the kernel also decodes the row, builds a byte offset table for it and copies the pieces out, and none of that got faster.

The replace differential now runs the pattern corpus through both engines, since it calls the same kernel function the column does. extract is the same change in one line, and the counting scan is still the machine because its loop cuts the row down after every match and hands the engine a different text rather than a cursor.

Fixed: a window sum over a partition of nothing but nulls answers null

sum(x) OVER (PARTITION BY k) answered zero for a partition whose values were all missing, where DuckDB answers null. It is the last operator holding the disagreement the entry below closed everywhere else, and it is now closed too. Issue #877.

A window never folds no rows, because a partition is a partition on account of a row being in it, so the only thing the mark can decide here is whether the rows it held had anything in them. That made the flag worth carrying on a window at all, which it was not before: Expressions.window takes empty_is_null the way aggregate already did, the JSON writes it and reads it back, and lowering hands it to the operator.

The operator pays more for it than a group by does, in shape if not in time. A group carries the count as a second state slot and fills it in the pass it was already making. A window has no running state to add a slot to, since it holds every row and reduces once at the end, so the count is a second reduction over the flattened column. The grouping pass itself is still done once and the gather is unchanged. group/pipeline_window and group/pipeline_window_marked are a new pair of benchmark rows that isolate the count, beside the pair the entry below added. No number is quoted here, because the machine these were run on was not quiet enough to produce one worth writing down, and the rows are what the next quiet run reads.

It is not paid where it cannot buy anything, on the same two gates as a fold: a column the schema says cannot hold a null had a value in every row it has, and a float column is asked about separately because a NaN is not a value here either.

A count window is unmarked, as a counting fold is, so a partition of nothing but nulls still counts zero rather than answering null. That is what both front ends say.

Fixed: a sum over values that are every one null answers null

SELECT sum(x) FROM t where every x is null answered zero, and so did a group inside a GROUP BY whose values were all null. DuckDB answers null to both, because a total of nothing is not a total, and so does firepanda now. Issue #836.

The neighbouring case, a fold over no rows at all, was fixed in 0.8.7 and cost nothing, because the operator already knew that no chunk with rows in it had ever arrived. This one is not free. A group is a group because a row made it, so a group whose values were all missing and a group whose values added to zero leave the kernel as the same zero. A grouped sum reads no validity at all: a null holds a zero and a NaN is made to hold one, so both spellings of missing add nothing and neither has to be looked up, which is the invariant that makes the sum as fast as it is. Telling the two groups apart means counting what was really added.

So a sum that has to answer null now carries a count beside it, which is the second state slot and the second scatter a mean has always carried for its divisor. The sum keeps the accumulator a sum gets, since this one is the answer and not a numerator, so the number it reports does not move. group/pipeline_stream_marked is a new benchmark row that says what the pair costs, against group/pipeline_stream beside it, which is the same query without the mark: sixteen million rows in a thousand groups through the streaming operator, 1.009 nanoseconds a row unmarked and 1.745 marked.

Nothing pandas-facing pays it. The count is allocated only for a fold the plan marked and the mark is the one the SQL front end sets, so DataFrame.group_by sums the way it always did and firepanda/frame/groupby.mojo still describes what it does. It is not allocated where it cannot buy anything either. A column the schema says cannot hold a null has a value in every row it has, so a group that exists held one, and a float column is asked about on its own because a NaN is not a value here and a column of them holds nothing even where the schema allows no null.

One registered divergence closes with it. A FILTER does not take rows away, it turns the ones it does not want into nulls, so sum(qty) FILTER (WHERE price > 500) over rows where the predicate never holds was a fold that saw rows and found nothing in them. It answered zero and it answers null.

A window aggregate still answers zero. sum(x) OVER () over a partition of nothing but nulls is the same disagreement in the one operator this does not reach, because a window carries no mark to read, and that is issue #877.

Added: a backtracker with a bitmap, for the scans that have to say where every group matched

The state cache answers whether a row matched and cannot say where, so the three scans that read the groups out of a match, which are replace, extract and the counting loop, are all still on the machine. This is the engine for those. It follows one path through the program at a time the way an ordinary backtracking engine does, and it writes down every pair of an instruction and a position it has already been to. Arriving at a pair it has already been to means the rest of that path has already been tried and has already failed, because whether a match can be found from an instruction and a position does not depend on how the search got there. So the pair is dropped, and the work is held to one visit per instruction per position, which is the same bound the machine has. It is RE2's BitState and the name is the bitmap.

What that buys is the constants rather than the bound. There are no thread lists, no stamp array to refill per row, and no copy of the slots per thread: one set of slots is written as the path goes forward and put back as it comes out. Over two hundred thousand URLs, a search with the groups of the ClickBench q28 pattern goes from about 1.47 s on the machine to about 0.33 s, and a shorter pattern with two groups in it from about 0.46 s to about 0.12 s. A pattern that matches nothing is about the same on both, since the character set added in 0.8.11 is what answers those and it answers them for either engine.

What it costs is the bitmap, which is one bit per instruction per position and so grows with the row. A row needing more than a quarter of a million bits is handed back, and the caller runs the machine on it. That is the same arrangement the state cache has: an accelerator with an engine underneath rather than a second engine a caller has to choose between. There is no pattern shape it refuses, which is the difference from the cache, since it answers the assertions and the captures exactly as the machine does.

The order is the correctness argument. A split pushes its second arm and then its first, so the first arm comes off the stack first and the path the pattern prefers is the path that is followed. Attempts start at one position after another from the cursor, and the first position that matches wins. Those two together are leftmost first, which is what the machine does and what both RE2 and Python do. The bitmap is deliberately not cleared between attempts at different positions, which is what keeps the whole scan linear and is sound for the same reason the memo is: nothing in the program reads where the attempt began.

The scans that call it are the entry above, and issue #863 has the order the rest go in.

Changed: a group by on several keys factorizes them one per worker

A group by on more than one key gives each key its own dense ordinals and then folds them into one number per row. Those factorizes are independent of each other, they were run one after another, and each is a serial pass until the column is tall enough to be worth splitting on its own. So a group by under those heights ran on one core however many keys it had.

TPC-H q10 is what found it, and it was the one query in that suite firepanda was measurably behind a rival on. It groups a four way join on seven columns, five of them text, and at sf1 the intermediate is 114,705 rows, which is under the height any one of those factorizes splits at. On a 13900K with 32 workers the seven keys cost 15.3 ms of the 17.9 ms the whole step spent, and one key per worker brings that to 7.0 ms. End to end q10 goes from 0.065 s to 0.055 s and q3, which goes through the same function on two keys and is the control, does not move.

The route is taken only when no key would have gone parallel inside its own factorize, since a split inside a split is the same cores twice and neither split knows about the other, and only when there is enough work to pay for the fork. Issue #878 has the sweep the threshold was fitted on.