Multiple Key Lookup and .Q.fu

Question

Trading systems often need to enrich large market data tables with reference data.

Given a table containing an asset identifier and a dictionary mapping asset IDs to asset names, add a new column called assetName containing the asset name as an upper-case symbol.

Demonstrate how .Q.fu can be used to improve performance when many rows share the same asset ID.

Solution

t:([] asset:10000000?10000; price:10000000?10.0)

assetMap:(`u#-10000?10000)!-10000?`4

Time both versions with \ts (milliseconds, bytes):

q)\ts a:update assetName:`$upper string assetMap asset from t
2183 588756560
q)\ts b:update assetName:.Q.fu[{`$upper string assetMap x};asset] from t
50 268698816
q)a~b
1b

Example output:

asset price    assetName
------------------------
3422  3.927524 IJNH
925   5.170911 FFAC
5677  5.159796 FEFI
2384  4.066642 GBLL

Explanation

The expression:

`$upper string assetMap asset

performs four operations:

1. Looks up each asset ID in the reference data dictionary.
2. Converts the resulting symbols to strings.
3. Converts them to upper case.
4. Casts the result back to symbols.

Because assetMap has a unique attribute applied to its keys:

assetMap:(`u#-10000?10000)!-10000?`4

dictionary lookups use an internal hash table and are already very efficient.

A further optimisation is available because many rows share the same asset ID.

The function:

{`$upper string assetMap x}

always returns the same result for the same asset ID. Instead of evaluating the function once per row, .Q.fu evaluates it once per distinct value of asset and then expands the results back to the original table shape.

update assetName:.Q.fu[{`$upper string assetMap x};asset] from t

This reduces the amount of work dramatically when the number of distinct asset IDs is much smaller than the number of rows.

In the example above:

q)count t`asset
10000000
q)count distinct t`asset
10000

Without .Q.fu, the transformation is performed 10 million times.

With .Q.fu, it is performed only 10,000 times.

Multi-Key Dictionary Lookups

Another important optimisation is to perform lookups on the entire column at once:

assetMap asset

rather than row-by-row:

assetMap each asset

For example:

q)\ts c:update assetName:`$upper string assetMap each asset from t
2637 588756624
q)\ts a:update assetName:`$upper string assetMap asset from t
2183 588756560

Both produce the same result, but the vectorised lookup is faster because q performs the lookup in bulk rather than applying the dictionary once per row. (Most of the time in both is spent in upper string, which is why .Q.fu gives the much bigger win here.)

When working with large tables, the preferred approach is therefore:

1. Apply the unique attribute to dictionary keys where appropriate.
2. Perform lookups using whole columns rather than each.
3. Use .Q.fu when the transformation depends only on a small set of distinct values.