Teaching K to speak q: tables, the join family, and bare qSQL

K gives you a dictionary and a transpose. A q table is, formally, a transposed dictionary of columns — +`a`b!(1 2;3 4) — and once you notice that, it is tempting to declare the job done and go home. It is not done. "You can express a table" and "you can work with tables" are separated by table literals, keyed tables, meta, eight joins, a query language, and about four hundred small decisions about argument order that determine whether anyone who already knows q can sit down at your prompt and be productive in the first minute.

This post is the layer that closed that gap: releases 1.0 through 1.5, from the first select to being able to type one without quotes around it.

Starting point: a table is a flipped dict

d:`sym`px!(`AAPL`MSFT; 187.3 411.2)     / a dictionary of two vectors
t:+d                                     / flip it: now it's a table
t`px                                     / 187.3 411.2 — a column IS a vector

That last line is the whole reason this works. A column is not a wrapper, not a Series object, not a chunked thing — it is exactly the vector you would have written by hand, with the same header and the same payload. Every optimisation in the four posts after this one depends on that staying true.

But +`sym`px!(`AAPL`MSFT; 187.3 411.2) is not something you want to type forty times a day, and it is certainly not what a q programmer's fingers already know.

Table literals, in the parser (1.2)

q writes a table as ([]sym:`AAPL`MSFT; px:187.3 411.2) and a keyed table as ([sym:`AAPL`MSFT] lot:100 10). I wanted both, and I wanted them to be syntax, not a function that takes a string.

So they went into src/p.c, the C parser. The scanner recognises ([ and decides, on whether anything sits between the brackets, whether it is building a plain table or a keyed one; the columns are parsed as ordinary expressions, so anything legal on the right of a colon is legal in a column.

([]sym:`AAPL`MSFT`AAPL; px:187.3 411.2 187.4; sz:100 250 50)
/  sym  px    sz
/  ----------------
/  AAPL 187.3 100
/  MSFT 411.2 250
/  AAPL 187.4 50

([sym:`AAPL`MSFT] lot:100 10)      / keyed table

A bare table at the prompt renders as a grid. That sounds cosmetic and it is not: an engine where you have to call a function to look at your data is an engine you will not explore in, and exploring is ninety percent of what a research session is.

meta, and the third column

q's meta returns a keyed table of column, type and attribute. Mine does the same, and it is nine characters:

meta:{d:+unkey x;xkey[`c;+`c`t`a!(!d;{@*x}'value d;{`at x}'value d)]}

Read it right to left: flip the (un-keyed) table into a dictionary of columns; build a new dictionary with three fields — the names, the type of each column's first element, and each column's attribute; flip that into a table; key it by c.

The a column is `at, the attribute reader. It is there from the first release because I already knew the attribute story was going to matter, and because a column whose sort order is a promise the kernel relies on had better be a promise you can see. Post three is that story.

c     | t a
------|-----
sym   | s p
time  | j s
px    | f
sz    | i

The join family

q has eight joins and a tick shop uses most of them in a week. All eight are in amber.k, and all eight take brackets rather than infix, because Amber does not allow a user-defined function to be applied infix — x f y parses as two nouns. That is a property of the host grammar, and rather than fight it I documented it and moved on.

Seven of those are ordinary relational operations expressed in array primitives. ej, for instance, is one line — an equi join is an inner join against a table you keyed on the fly:

ej:{[c;x;y]ij[x;xkey[c;y]]}

The eighth is the one the whole engine ends up being about.

Why the as-of join is different

Every serious question about execution quality starts with the same join: for each trade, what was the quote standing at the moment it printed?

That is not an equality join. There is no matching key — you want the last right row whose timestamp does not exceed the left row's, per symbol. Expressed in SQL it becomes a correlated subquery or a window function over a union, and the planner has to rediscover from the shape of the query that what you meant was "walk both sequences in order". It usually does not.

In 1.0 aj was pure K: for every trade, a binary search into that symbol's quote slice. Correct, and slow, because it was a scalar operation performed in a loop — the exact thing an array language exists to avoid. In 1.5 I rewrote the matcher to issue one vectorised bin per group instead of one scalar search per row: roughly 700 ms down to 115 ms at 50,000 rows, ~6×, identical results.

That was the last version written in K. In 1.9 it became a C kernel with a branch-free lower_bound, which is post four. The pure-K version is still in the tree as ajmK, because a reference implementation you can diff against is worth more than the space it takes.

qSQL, as a template engine

The interesting problem in select vwap:wavg[sz;px] by sym from trades where px>0 is that sz, px and sym are not variables. They are column names, and they only mean anything relative to the table named after from.

So qsql.k does the obvious thing, carefully. It splits the clause on the keywords, tokenises each expression, and rewrites every bare identifier that is a column of the target table into an indexing expression. Then it compiles the result into a one-argument lambda and hands that to the existing engine.

qword:{((x>64)&x<91)|((x>96)&x<123)|((x>47)&x<58)|x=95}   / word-char mask
qidsub:{[cols;s] … in[`$t;cols] … "(x`",t,")" … }          / bare name -> (x`name)
qfn:{[cols;e]. "{[x]",qidsub[cols;e],"}"}                  / expr string -> 1-arg fn

wavg[sz;px] becomes {[x]wavg[(x`sz);(x`px)]}. Names that are not columns are left alone, so a global, a user function or a literal still means what it meant. And because the rewritten text is compiled by . — the real evaluator — the expression language inside a query is the whole language, with no separate grammar to maintain.

Underneath sit three functions that do the actual work, and they are usable directly:

qwhere[t; mask]                                     / filter
qselect[t; …]                                       / project
qby[t; `sym; (,`vwap)!,{wavg[x`sz;x`px]}]           / group + aggregate

qby takes a table, one or more grouping columns, and a dictionary from output name to function. Each function receives the sub-table for one group — which is why {wavg[x`sz;x`px]} reads two columns and returns one number. It is a small interface and it has never needed to change.

Bare qSQL: the line rewriter (1.5)

Up to 1.4 you wrote sel"select … from t". The quotes are a papercut and papercuts compound: they break syntax highlighting, they make you escape things, and they are a constant small reminder that you are talking to a K interpreter wearing a q costume.

1.5 added qrw, a rewriter that runs on the REPL's input line before evaluation. If the line looks like a query, it becomes the matching sel/exq/upd/del call. If it does not, it is passed through untouched.

select from trades where px>150
select vwap:wavg[sz;px], n:#px by sym from trades
select vwap:wavg[sz;px] by time:1m xbar time from trades
exec px from trades where sym=`AAPL
update px:px*1.01 from trades where sym=`AAPL
delete from trades where sz<100

It handles the cases you actually hit: assignment (r:select …), and a prefix applied to the whole query (5#select …, count select …). It deliberately does not run inside a .k script — there the string form or the functional form is what you use, because a source file being silently rewritten line by line is a debugging experience nobody wants.

1.5 also fixed select from t — a column-less select with a leading from, which the clause splitter had been mis-splitting — and, less visibly, made repl.k actually load all six library modules. Before that, std, qsql, temporal, sys, hdb and ipc were on disk and simply never loaded, so sel and the moving aggregates were silently unavailable at the prompt. Everything worked in the test suite, which loads them explicitly. That is a good lesson about what a test suite is not.

Narrowing before grouping

One refinement worth flagging here even though it landed much later, because it belongs to this layer conceptually. qby materialises one sub-table per group, and the function that does it indexes every column it is handed. On a wide table that means copying dozens of columns per group that no aggregate ever reads.

qrefs tokenises an aggregate expression with the same tokeniser qidsub uses to rewrite it, so the set of names it returns is exactly the set of columns the compiled function can reach. qproj then narrows the table to those columns before grouping. It can only ever narrow, so it cannot change a result — and the cost of a group-by starts scaling with columns used instead of columns present.

fin.k: giving the vocabulary a domain (1.4)

A general table engine is not the same thing as something a desk can use. 1.4 added fin.k, auto-loaded after amber.k, which is where the market-data vocabulary lives:

gentq n matters more than it looks. It generates a session — trades and quotes globals with plausible microstructure — which means every example, every benchmark and every bug report can start from one line and be reproducible on someone else's machine. It also stamps the attributes on the key columns (`s on time, `p on sym), so the default state of a freshly generated session is the fast one rather than a trap.

gentq 100000                       / sets global `trades` and `quotes`
m:aj[`sym`time; trades; quotes]    / TAQ: prevailing quote for every trade
tsign m                            / Lee-Ready trade sign (+1 buy / -1 sell)
effspread m                        / effective spread = 2|px-mid|
bars[1; trades]                    / 1-minute OHLCV

The rest of 1.1 – 1.5, briefly

• Temporal helpers (1.1) — hms hh mm sec milli minute second stime ptime, and minbar / bar / xbar for OHLC bucketing. Times as milliseconds since midnight, mirroring q's convention. These were library functions over integers; they became real types in 1.7.
• Grid rendering (1.1, fixed properly in 1.3) — tables, keyed tables and dictionaries print as q-style grids. 1.3 fixed list-valued dictionaries (what group returns), nested columns (what xgroup returns), and a crash where iskeyed ran an odometer over a plain vector.
• ./a rebuilds when the C sources are newer than the binary (1.3) — the reason table literals mysteriously did not render for some people was that they were running a stale build. Making the launcher check is two lines and removed an entire category of bug report.
• Help pages — \q scalars and sets, \j tables and joins, \z temporal and attributes, \m the finance module. Built in, because the first thing you want in an unfamiliar array language is a list of what exists.
• CI from 1.1 — the suite grew 97 → 104 → 148 → 153 assertions across these releases, run on every push.

Where this left things

By 1.5 you could sit down at the prompt, type gentq 1000000, type a select … by … from … where … without quoting it, join trades to quotes as-of, bucket into one-minute bars and see a grid — all in a language whose vocabulary a q programmer already knows.

What you could not do was any of it particularly fast on ten million rows. The query layer was K calling K; the joins were K; the temporal functions were integer arithmetic wearing a costume. That is what the next two posts are about — starting with the one piece of C-level machinery that was there from the very first release, because I knew from the start that everything else would depend on it.