v0.8.14

Built against Mojo 1.0.0 (ed45d567).

A patch release with two threads in it, one that finishes the lookaround and one that finishes the question 0.8.13 left open.

The engine that copies Python reads a lookahead and a lookbehind now, both forms of each, which are the first two constructs RE2 has not got and the last two the held out corpus of 30052 patterns was turning down. A pattern with one in it used to raise from contains, count, replace, match, fullmatch and extract and now answers, with the one refusal Python itself makes, which is a lookbehind whose body does not always read the same number of characters. The lookahead is what surfaced a wrong answer sitting underneath both of them: a pattern that prefers to match nothing where it could have matched something was losing the character after the empty match, so count("a*?") on abc said four where CPython says five. Both engines learned the rule upstream has used since 3.7.

Issue #889 asked what the decode, the byte offset table and the copy cost inside the replacing kernel, on ClickBench q28's column, and guessed the three of them were about half the work. They are about a tenth and the engine is the rest. The decode got about three times cheaper anyway, by widening a block of ASCII in one go rather than a character at a time, and every copy in the replacing scan is a run copy now, which is worth about a third on a row shape where the copy is most of the work. q28 does not move. What the issue leaves behind is six rows of the benchmark suite that split the kernel into its passes and run on every pull request, and a next question, which is the engine's step count.

Beside those, three things. SQL reads an INTERVAL literal rather than stopping at one, which was the largest single reason anything in DuckDB's corpus stopped at all, and the refusal moves to lowering where it belongs. SQL first and last report the row at the edge rather than the first value that is not null, which is what DuckDB does and what separates them from any_value. And a Parquet read assembles half a million rows at a time rather than the whole answer at once, which takes about 460 MB off the peak of a six million row read and makes it slightly faster.

Added: SQL reads an INTERVAL literal instead of stopping at one

INTERVAL '1' DAY and the spellings around it used to be refused by the transformer, and 697 statements in DuckDB's corpus stopped there, which was the largest single reason anything in it stopped at all. They parse, transform and print now, and a duration arrives at the printer with its amount and its unit intact.

The refusal moved rather than went away. Nothing here has a column type for a duration yet, so lowering is the stage that says so, and it says it with the entry it always used, which keeps sql_support() and the README's table honest. What changed is when a query hears about it: one that only has to be read gets read, and one that has to run is refused in the same words.

The unit comes off the grammar rule and not off the text, so DAYS and DAY are one unit without a table of plurals anywhere, and YEAR TO MONTH is one unit rather than three words. The amount is whatever the query wrote, which is a string in INTERVAL '1 day', a number in INTERVAL 5 DAY, and any expression at all in INTERVAL (x) DAY. The string is not read, because the text is the value and taking a duration out of it is work the type does.

The parentheses around the amount are the printer's decision rather than something the arena keeps. A string or a number goes bare, which is how nearly every interval anybody writes is written, and anything else keeps them, because the grammar takes only those three things in that position and INTERVAL x DAY without them is not a query.

Fixed: SQL first and last report the row and not the first value there is

first(x) and last(x) inside a GROUP BY skipped over a null looking for something to report, so a group whose first row was missing answered the row after it. DuckDB answers null there, because those two name a row and read whatever is in it. Issue #888.

any_value is the one that skips, and it was the one already right. That is what separated the three: they had been one fold under three names, and the case that tells them apart is a group whose first row holds nothing and whose second row holds a five. DuckDB says null for first and five for any_value, and firepanda said five for both.

So there are two new reductions rather than a flag on the old ones, FIRST_ROW and LAST_ROW, and both rules are kept because both are wanted. pandas groupby.first skips and keeps the fold it had, any_value keeps it too, and SQL's first and last are the new pair. The numeric kernel, the text kernel and the slow reference twin all grew the pair, and the plan JSON reads and writes their names.

They do not fold a chunk at a time, which is the one design decision here worth writing down. A partial answer from one chunk is a value that may itself be null, and a running slot holding a null cannot say whether it is a group whose first row was missing or a group no chunk has reached yet. That is the trap a sum fell into in the entry below, where a zero meant both nothing added and a total of zero. The way out there was a second state slot; here it is cheaper to hold the column and reduce once at the end, which is the route a median already takes, because these two copy one element per group rather than accumulating anything.

FILTER on any_value used to be refused alongside the other two and runs now. The rewrite turns a row the predicate dropped into a null, and a fold that passes over a null cannot tell that from a row that was taken away, so the CASE says what the filter said. For first and last it does not, and they are still refused by name.

Added: a lookbehind, which is the other half of the construct below

str.contains("(?<=a)b") used to raise and now answers, and so do count, replace, fullmatch and extract. Both forms are in, the positive one and the negative one, and a lookbehind may hold another or hold a lookahead. With this the whole of the lookaround is read on the engine that copies Python, and no pattern in the held out corpus is turned down for one.

The half below needed nothing from the compiler, because a lookahead starts its body where the pattern has got to. This half needs a number: the body has to end where the pattern has got to, the machine walks forwards, so the compiler has to know how many characters the body always reads and has to refuse a body that does not always read the same number. Python refuses exactly those, with look-behind requires fixed-width pattern, so (?<=a*)b raises here and raises there. That refusal is a ValueError rather than a NotImplementedError, which is the difference between a pattern nobody answers and a pattern pandas answers and this library does not.

Which bodies count as one width is a rule with several edges on it and every one was measured against a running interpreter. An alternation is fixed when its arms agree, so (?<=ab|cd)e reads and (?<=a|bc)d does not. A repeat is fixed when its two bounds are the same number, so a{2} reads and a{2,3} does not. An assertion of any kind is worth nothing, which is what makes (?<=^) and (?<=\b) ordinary rather than special.

The second machine is the one the lookahead already had and it does not know which direction it is answering, since the seed is the whole of the difference. It also stops now when no thread survives a pass, instead of walking to the end of the row to learn what it already knew, which a lookbehind would otherwise pay for on every position of every long row.

Added: a lookahead, which is the first construct RE2 has not got

str.contains("a(?=b)") used to raise and now answers, and so do count, replace, match, fullmatch and extract. Both forms are in, the positive one and the negative one, and a lookahead may hold another. This is the first piece of syntax to land that only one of the two engines reads. Everything before it on this engine was a flag, and a flag modifies syntax both engines already have.

pandas routes a pattern holding a lookaround away from Arrow and answers it with re, because RE2 has never had one. This library routed it the same way and then refused it, so 700 of the 30052 patterns in the held out corpus were a column the caller did not get, plus 13 more for (?!), which is a negative lookahead with nothing in it and so a pattern that never matches. That one now compiles to a character class with no members in it.

The instruction is a position test like the word boundary is. The thread goes on when the body matches starting exactly where the pattern has got to and dies when it does not, and either way the position does not move, so the width of a lookahead is nothing and the count says so. The body is run by a second machine over the whole row rather than over the part of it after the position, which is what keeps an anchor inside one honest: a(?=b$) matches ab and does not match abc.

Two shapes are refused rather than answered. A lookbehind is a different question, since reading one means working out the width of the body at compile time and reproducing the error Python raises when it has not got one. A capturing group inside a lookahead is refused only when the caller asked for the groups, which through the accessor means only extract, because the second machine carries no slots and reporting nothing would be a wrong answer rather than a refusal.

The cache of position sets added above refuses any pattern holding one outright, because that instruction reads text the cache has not read and will not read again, and there is nothing to fold into a state. The backtracker added below hands one back for a reason of the same kind: it follows one path with one stack and one bitmap, and a search inside a search has nowhere to go. Those rows go to the machine, which is the arrangement a row too long for the bitmap already had.

Fixed: what happens after a match of no width on Python's engine

str.count(pat, flags=...) and str.replace(pat, repl, flags=..., regex=True) gave a count that was too small and a row with text left in it for any pattern that prefers to match nothing where it could have matched something. count("a*?") on abc answered four where upstream answers five, and replace(r"(?!x)|\s", "#") on a b left the space where it was.

The rule was written down as a step one character on after a match of no width and that is what upstream did until 3.7. What it does now is look at the same position a second time with the end of the pattern refused there, so an arm of the pattern that reads a character gets a turn where an arm that reads nothing has already answered, and only then does the search move along. The two rules agree for every pattern that cannot prefer an empty match over a wider one at the same place, which is why this stood through two slices and through a sweep of 30052 patterns.

The lookahead above is what surfaced it, by making a pattern with no flags anywhere in it reach these two loops for the first time, which put it in front of the differential that compares them against pandas. Both scans and the documents that state the rule are corrected, and both engines learned the rule, the machine and the backtracker, with the test that compares the two asking it of every cursor of every row. Document 93 section 10.

Changed: the passes a regular expression kernel makes around the engine are measured, and the decode reads a block at a time

Issue #889 asked what the decode, the byte offset table and the copy cost inside the replacing kernel, on the column ClickBench q28 runs over, before changing any of them. That measurement is now six rows of benchmarks/main.mojo under regex/, over a column of URLs with q28's pattern, and each row contains the one above it so a pass comes out by subtracting.

What it says is that the engine is about nine tenths of the serial row and the three passes together are the rest. The issue guessed half and half from arithmetic stitched out of two different runs, and the guess was wrong. What is left on q28 is the engine.

The decode is the largest of the three and is the one that got cheaper. A row has at most as many characters as it has bytes, so the list is grown once and written into rather than appended to a character at a time, and a block of bytes with no top bit set in any of them is widened into place in one go. Text with a multi byte character in it drops into the old loop for that character and the block is tried again from there, so a row that is mostly ASCII still reads mostly in blocks. On the benchmark's URL column the pass goes from about 56 ns a row to about 23, and on the real Referer column of the suite's 1M ClickBench file from about 137 ms to about 48 ms over the 921225 rows q28 keeps, which is about 149 ns a row down to about 52.

The copy is the second. Every piece of a row the scan writes out is copied as a run now rather than a byte at a time, which is what it always was: both ends of a piece are known before any of it is written. On q28's column that is one host name a row and it is hard to see, so it was measured on a row shape where the copy is most of the work, a 350 byte row with eight short matches in it. Over 100000 of those, the two changes together take the scan from about 866 ms to about 562 ms.

The offset table is the third and it stays as it was, with a measurement rather than an argument. Growing it to its size first costs a fill of whatever the last row did not use, the row that empties it is the ASCII row, and most rows are ASCII, so the fill lands on every row that needs a table at all. On the same column that came out slower than the appends it would have replaced. The table is under ten nanoseconds a row where the engine is over a thousand, which is the other half of why it stays.

q28 itself does not move, and that is the honest reading rather than a disappointment. The kernel the query calls goes from about 773 ms to about 800 ms over the real column, which is the same number twice on a shared machine, and the suite is worse than that: q28 at 1M in memory mode landed anywhere between 0.57 s and 2.34 s across four paired runs the same afternoon, on both sides of the change and in both orders, tracking the load average and nothing else. A tenth of a tenth does not show up in a suite. The passes are now measured where a pull request can see them, which is the point.

regex/search_machine is in the same section and is the only row there expected to be slower than the row above it. It runs the same scan with the backtracker taken out, so the pair keeps saying what 0.8.13 bought, which on this column is about two and a half times.

Changed: a Parquet read assembles a group of chunks at a time

A read fetched every chunk out of DuckDB, described all of them as Arrow, and only then copied the lot into a frame, because the assembler sizes the buffer it allocates from every batch it is handed and cannot begin until it has them all. So the Arrow copy of the whole answer and the frame it turns into were both resident, and the peak of a read was the sum of the two.

It now assembles half a million rows at a time and lets that group's Arrow arrays go before fetching the next, then stacks the groups into one chunk a column after DuckDB's own result has been destroyed. Nothing downstream can tell: the frame comes back in one chunk the way it always did, which matters because a column with more than one chunk cannot be borrowed and most of this library borrows.

Measured on a 13900K reading sf1 lineitem, six million rows and sixteen columns, with the two builds run alternately four times each, the peak resident set goes from 3498 MB to 3037 MB and the read from 1083 to 1189 ms down to 1011 to 1129. The read gets faster rather than slower because a group that fits in cache is assembled out of cache, and that pays for the stacking step at the end.

The group size is half a million rows because the ladder flattens there. The read peaks at 2896 MB at two million rows a group, 2625 MB at half a million and 2556 MB at a hundred and twenty eight thousand, and at the last of those the read has gone back up to 1220 ms because the fixed cost of an assemble is being paid forty six times. What is left is mostly DuckDB's materialised result, about 1400 MB of it, which is not ours to release a piece at a time. Issue #427.