Parallel xasc

Sorting a table can be divided into two parts: determining the new order for the rows, and applying that ordering to the columns. While the former can’t be parallelized in q, the latter can. I don’t have any hard numbers handy at the moment, but with large tables and under the right conditions, I’ve seen noticeable speedups.

Note, BTW, that you can’t (and shouldn’t) write to disk from inside a peach, so this is only applicable to an ordinary in-memory table sort, not the on-disk variety (`c xasc`:t).

q)pxasc :{(count keys y)!flip{y x}[ iasc(raze x)#0!y]peach flip 0!y}
q)pxdesc:{(count keys y)!flip{y x}[idesc(raze x)#0!y]peach flip 0!y}

My kdb+ User Meeting Presentation

Here are the slides from the presentation I gave today at the kdb+ user meeting at BAML, in keynote, pdf, and powerpoint formats:

• (dis)functional select and de-queueing bugs.key
• (dis)functional select and de-queueing bugs.pdf
• (dis)functional select and de-queueing bugs.ppt

UPDATE: and here's the code as a loadable .q file:

• pres.q

Functional Query Functions

So, five months ago I said I’d cover functional query utility functions “next time”. Well, next time is finally here. Sorry for the wait; hope it was worth it.

Before I begin, though, two quick notes:

1. Functional queries have no performance advantage. They are identical to qsql queries in speed and memory usage.
2. Funcitonal queries are hard to maintain. Even using the techniques described here, functional queries are still harder to read and understand than qsql queries.

Therefore, functional queries should only be used when qsql is incapable of accomplishing the task at hand. (Typically, this involves dynamically choosing columns.)

As mentioned previously, getting the parse trees of the c, b, and a arguments to functional queries right is quite tricky. One technique I frequently use to make this easier is to use utility functions to abstract away as much of that complexity as possible. In their most basic form, they simply generate (composable) elements of the relevant structures:

q)c:{parse["select from t",$[count x;" where ",x;""]]. 2 0}
q)b:{parse["select",$[count x;" by ",x;""]," from t"]3}
q)a:{parse["select ",x," from t"]4}

For example:

q)t:([]x:1 2 3 4;y:1 1 2 3;z:7 8 9 10)
q)select sum x by y from t where x<>1
y| x
-| -
1| 2
2| 3
3| 4
q)?[t;c"x<>1";b"y";a"sum x"]
y| x
-| -
1| 2
2| 3
3| 4
q)

In practice, of course, these functions should be used to express in qsql whatever parts of a query are so expressible, while reserving the actual parse trees for the parts of the query that need them:

q)show each t{?[x;c"x<>1";b"y";(enlist y)!enlist(sum y)]}/:`x`z;
y| x
-| -
1| 2
2| 3
3| 4
y| z
-| --
1| 8
2| 9
3| 10
q)

More specialized utilities can also be written, once their need becomes apparent. One particularly difficult thing to express in functional form is a multi-column fby:

q)t2::update k:`a`a`b`c from t
q)select from t2 where i=(last;i)fby([]y;k)
x y z  k
--------
2 1 8  a
3 2 9  b
4 3 10 c
q)parse"select from t2 where i=(last;i)fby([]y;k)"
?
`t2
,,(=;`i;(k){@[(#y)#x[0]0#x 1;g;:;x[0]'x[1]g:.=y]};(enlist;last;`i);(+:;(!;,`y`k;(enlist;`y;`k)))))
0b
()
q)

The primary problem is that the parse of this query contains the instructions for assembling a table literal out of its individual pieces. Here’s the functional equivalent, written all the way out:

q)?[t2;enlist(=;`i;(fby;(enlist;last;`i);(flip;(!;enlist`y`k;(enlist;`y;`k)))));0b;()]
x y z  k
--------
2 1 8  a
3 2 9  b
4 3 10 c
q)

Using a utility function, it can instead be written much more simply:

q)fbyx:{.[parse["select from t where ",x,"fby c"]. 2 0 0;2 2;:;(flip;(!;enlist(),y;(enlist,y)))]}
q)?[t2;enlist fbyx["i=(last;i)";`y`k];0b;()]
x y z  k
--------
2 1 8  a
3 2 9  b
4 3 10 c
q)

Judicious application of these techniques (not to mention judicious application of functional querying in the first place) can make code much more readable.

Dictionaries and Vectors as Functions

IMAO this is one of the more interesting bits of theory embedded in q:

Considering a dictionary as a (partial) function from its key (domain) to its value (range), then two dictionaries f and g such that f's value and g's key are of the same type can be composed:

q)f:`a`b`c!1 2 3
q)g:1 2 3!("foo";"bar";"quux")
q)g f
a| "foo"
b| "bar"
c| "quux"
q)(g f)`b
"bar"
q)

Considering a vector v as a dictionary with a key of the vector of integers from 0 to count[v]-1, then v can be composed with a dictionary h of integer value:

q)v:42 137 23
q)h:`a`b`c!0 1 2
q)v h
a| 42
b| 137
c| 23
q)(v h)`b
137
q)

Principles of Parse Trees

One of the more frequent topics that comes up when people start moving beyond beginner's q is functional queries, which are required to parameterize a query by column name, and are often useful for various other reasons as well.

One of trickiest parts of functional queries is the parse trees that appear in their second, third, and fourth arguments (henceforth c, b, and a). Here are a few rules that should summarize most of what's important to know about them:

• c is a general list, each element of which is a parse tree. Its degenerate form (no conditions) is (), the empty general list.
• c appears in the results of parse with an extra level of enlist applied to it; this is only necessary when sending the parse tree back to eval (as opposed to using it to write a direct invocation of ?).
• b and a are both dictionaries with symbol keys and parse tree values. The degenerate form of b (no grouping) is 0b; the degenerate form of a (select all columns as-is) is ().
• Symbol literals are enlisted.
• Names (parameters, local or global variables, table columns, functions, etc.) become symbols.
• Functions become sexps, like in LISP.
• Adverbs are (technically) monadic functions which take dyadic verbs as arguments and yield dyadic verbs as their return values.
• Global constants can be referenced by name or by value.
• Anything which can be computed outside the query framework, may be.

Some elucidation on the last few points:

Adverbs will show up in the output of parse as ((adverb;`verb);`x;`y):

q)unshow parse"select f'[a;b]from t"
(?;`t;();0b;(,`b)!,((';`f);`a;`b))

While this will work fine, simply including the modified verb directly in the tree by value is also legal:

q)?[t;();0b;(enlist`b)!enlist(f';`a;`b)]

Built-in functions from the .q namespace will be included by value in parse output:

q)unshow parse"select dev a from t"
(?;`t;();0b;(,`a)!,(k){sqrt var x};`a))

These should always be replaced by their names in code:

q)?[t;();0b;(enlist`a)!enlist(var;`a)]

Finally, fully parsed code may be mixed freely with expressions which generate results which are otherwise acceptable:

q)unshow parse"select from t1 uj t2 where a in(exec a from t3)"
(?;(k){$[()~x;y;98h=@x;x,(!+x:.Q.ff[x;y])#.Q.ff[y;x];lj[(?(!x),!y)#x]y]};`t1;`t2);,,(in;`a;(?;`t3;();();,`a));0b;())

can be written as

q)?[t1 uj t2;enlist(in;`a;exec a from t3);0b;()]

Next time, I'll discuss how to write utility functions to make advanced constructs like multi-column fby easy to write.