v0.8.16

Built against Mojo 1.0.0 (ed45d567).

A patch release with two threads in it. The SQL transformer reads three more shapes of syntax, which clears the largest entries that were left in the refusal histogram, and two things that were running slower than they had to are not any more.

The three shapes are a lambda, a list comprehension and a field access. Between them 531 statements in DuckDB's corpus used to stop at the transformer and 514 of them round trip now, with the rest holding something else that is still turned down. All three moved their refusal to lowering, where the sentence is about what firepanda can run rather than about what it can read, and that is the right place for it.

The two speedups are both a route being chosen badly rather than a route being slow. A query with a limit on the end ran everything under the limit on one core, including the cases where a sort or a group by under it meant the limit could not have stopped the scan, which is twenty two of the 43 ClickBench statements. And a group by on a key that happened to be in order built a hash table anyway, because being in order was something a column had to be told rather than something anybody checked, which is TPC-H q21 twice over.

Added: SQL reads a field access

(a).b and f(x).b used to be refused by the transformer, and 114 statements in DuckDB's corpus stopped there. All 114 round trip now and none of them moved to another refusal. The refusal moved to lowering, where the sentence it says is that a field belongs to a struct and a firepanda column holds one scalar, so there is nothing here with a field in it to reach into.

The transformer was already making the split this needed. A dot on a name is one longer name, because which part of a.b is the schema and which is the table and which is the column is the binder's question and a dotted name is how that question is carried. What was left over is a dot on something that cannot be a name at all, a call or a subscript or a struct literal or a value in parentheses, and a dot there can only be reaching into a field. So the new node is the other half of a decision already being made rather than a new decision.

The name after the dot is a ColLabel, which is the widest identifier class in the language and takes every keyword, so columns[1].type comes back with type bare even though the same word as a column name would be quoted. That took splitting the quoting rule in two. Whether text would read back as one bare identifier is a property of the text, and which keywords may stand bare is a property of the position, and those were one function before. The shape half is its own function now and the label position is the one caller that wants it on its own.

Added: SQL reads a list comprehension

[x + 1 FOR x IN l] used to be refused by the transformer, and 68 statements in DuckDB's corpus stopped there. 67 of them round trip now and the other one holds something else the transformer still turns down. The refusal moved to lowering and kept the sentence it already had.

The node holds four things: the element written before FOR, a run of interned names, the source written after IN, and the condition an IF put on the end when one was written. The names are read as text the way a lambda's parameters are and for the same reason, which is that a name in that position is being bound rather than looked up, and the element and the condition both refer to it the way they refer to a column.

DuckDB reads this as calls. [x + 1 FOR x IN l] is list_apply(l, lambda x: x + 1) in its own parse tree, and the form with a condition grows a list_filter and a pair of struct_pack calls under that. That is what a comprehension means rather than what it says, and this keeps what it says, so the printer hands back the brackets the query wrote instead of a nest of calls a reader would have to turn back into brackets.

Changed: a limit above a sort no longer takes the query off the cores

The pipeline driver runs the leading row local operators on every core, and it gave that up for the whole line when there was a limit anywhere in it. The reason was right: the parallel route reads a batch of chunks before it pushes any of them, and reading ahead on behalf of ten cores is reading rows a limit was about to make unnecessary.

It asks a narrower question now. A breaker holds every row it is given and emits nothing until its input has run out, so a limit with a sort or a group by under it counts its first row after the last chunk has already been read, and the batch the parallel route reads ahead is a batch the breaker was going to be handed anyway. The search for a limit therefore stops at the first breaker. A limit with nothing holding rows under it still puts the line on the calling thread, and a join is not a breaker for this, because rows flow through it while the source is being read.

ClickBench q23 is what found it. SELECT * FROM hits WHERE URL LIKE '%google%' ORDER BY EventTime LIMIT 10 at 1M was 23.8 milliseconds through the planner and the same statement without the LIMIT 10 was 11.5, on the same rows through the same operators, because the limit was running a search down a million rows on one core. It is 13.6 with this, and q22, which is the same shape with a narrower projection, goes from 21.5 to 12.0. Nothing without a limit above a breaker moves: q20, q24 and the two variants of q23 that drop the limit are all within a few tenths of where they were. Twenty two of the 43 ClickBench statements end in a limit and almost all of them have a group by or an order by under it. Issue #682, document 98.

Added: a backreference under the ignore case flag, which is a second case table

str.contains(r"(\w)\1", case=False) used to raise and now answers, which is one of the two things the backreference entry in 0.8.15 left refused.

It wanted a table because (?i) means two different things and upstream implements it twice. A literal under the flag is widened while the pattern is compiled, into the set of everything that folds onto it, so (?i)s becomes s, S and the long s. A backreference cannot be widened that way, because what it is going to be compared against is not known until the row is being walked, so upstream compares the two characters at run time by lowering each of them and asking whether the results are equal. Those two relations disagree: (?i)ss matches sſ and (?i)(s)\1 does not, and the sigma pair goes the same way. It is measured against a running CPython rather than reasoned about, and it is upstream's arrangement rather than a defect in it.

So there are two case tables now. folddata.mojo is the orbits and lowerdata.mojo is the simple lowercase, written by tools/gen_regexlower.py beside the fold generator and against the same interpreter, CPython 3.13.12 with Unicode 15.1.0. 1433 code points move, in 214 runs, which takes a marker of its own: the fold table's says a run alternates up and down because folding is a cycle, and this one says the even code point steps up and the odd one stays, because lowering is not. Without it the same table is 668 runs. The generator walks its own runs over every code point in Unicode and checks each against _sre.unicode_tolower, so a release that moves an answer fails there rather than drifting.

The table is read by one function and held on the engine rather than copied per row, and only a program that actually holds a reference under the wide flag asks for it at all. (?ai) is a third rule rather than the wide one narrowed: it is the twenty six ASCII letters and nothing else, so the Kelvin sign is not a k there. The Python differential moves from 28729 patterns compared to 28739, which is the ten that were held out for this, and stays at zero disagreements. Document 97.

Added: SQL reads a lambda

lambda x: x + 1 used to be refused by the transformer, and 349 statements in DuckDB's corpus stopped there, which was the largest entry left in the refusal histogram. 333 of them round trip now and the other 16 hold something else the transformer still turns down. The refusal moved to lowering and kept its sentence, because the sentence was already the right one: firepanda runs the functions it already has, and a function written inside a query would have to be compiled along with it.

The node holds the body and a run of interned parameter names. There is no node for a parameter, because a parameter is a name being bound and there is nothing under it, and the body refers to it the way it refers to a column. Nothing before the binder can tell the two apart, which is the same reason the refusal is where it is.

x -> x + 1 is not this and never was. The grammar reads the arrow as an operator at a precedence level of its own, and -> is also how DuckDB reaches into a JSON value, so the two spellings are the same text and telling them apart is a question about what stands on either side of it.

The printer writes the keyword spelling whatever was written, since the arrow is the ambiguous one and the keyword never is. A parameter is quoted by the ordinary column name rule, so lambda year: year keeps its bare year and lambda 'q': 1 comes back as lambda q: 1, the string literal standing in for a name being the same name in the other spelling.

Changed: a group by looks at whether its key is in order instead of waiting to be told

A group by on one key has had two routes for a while. A key whose equal values are adjacent can be grouped by a walk that closes a group each time the value changes, which is one comparison a row, and anything else builds a hash table. Which route a frame took was decided by a flag on the column, and the flag is set by a sort and by a file reader and by almost nothing else, so a key that arrived in order for any other reason paid for a hash table it did not need. TPC-H q21 groups l_orderkey twice, both times on a column that is in order and neither time on one that says so.

The flag is now proved rather than read when it is unknown. is_sorted stops at the first pair of rows out of order, so a key in no order costs a handful of rows, and a key in order costs one pass which is about a sixth of the hash table it replaces. That makes it a one sided bet: the case that wins saves roughly five times what the case that loses spends, and the case that loses is only a long run in order broken near the end. Frames under 65536 rows are left alone, because a group by that size is already under a millisecond and the scan would be the only thing either route added.

Measured on a 13900K, TPC-H sf1 in memory, three rounds in ABBA order with seven runs a round. q21 goes from 0.141, 0.135, 0.142, 0.139, 0.137 and 0.140 seconds to 0.083, 0.083, 0.085, 0.083, 0.085 and 0.083, which is 1.66 times with no run of one side touching the other. q18 goes from 0.028, 0.028, 0.029, 0.028, 0.029 and 0.027 to 0.023, 0.020, 0.021, 0.022, 0.021 and 0.020, which is 1.33 times and also disjoint. Across all 22 queries nothing else moves outside run to run noise, which is what should happen: q1, q3 and q10 group on more than one key and never reach the new code at all.

The answer does not change and the two routes are still checked against each other. What the scan will not do is remember what it found, because a group by borrows the frame and has nowhere to write it, so a frame grouped twice on the same key is scanned twice. DataFrame.sortedness is still the way to pay for the scan once and keep the answer. Issue #79.