What Is the Memory Overhead of Each Attribute?

Question

How much extra memory does each attribute need, and what does that cost scale with? How could you measure it?

Solution

KX does not publish exact per-attribute memory formulas, but the cost follows from what each attribute stores:

To measure it, compare .Q.w[]used` before and after creating an attributed copy:

x: asc 10000000?`$string til 5000     / 10M symbols, 5,000 distinct, sorted
before: .Q.w[]`used
y: `g#x                                / grouped copy
(.Q.w[]`used) - before                 / bytes for the copy plus the index

Repeat with `p#x and compare. (Applying s# to an already-sorted list doesn't make a copy, so it shows almost no change.)

Explanation

s# — no extra memory. It only marks the list as sorted, so kdb+ can binary-search it.

p# — small. Because equal values are contiguous, kdb+ only needs to record where each value's block starts — one entry per distinct value, however many rows there are. That is why it is so cheap for an HDB sym column: the cost depends on the number of instruments, not the number of trades.

g# — grows with the number of rows. The index holds the position of every row, grouped by value — the same structure group returns.

u# — grows with the number of rows. The hash table has an entry for every value, and since u# requires every value to be different, that is one per row.

As a rough guide, measured on KDB-X with the method above: for 10 million symbols with 5,000 distinct values, the p# copy needed hardly any more memory than an unattributed copy, while g# needed roughly 90MB more. For 10 million unique longs, u# needed roughly 400MB more than the list itself. These figures include the memory allocator's rounding up to powers of two, so treat them as orders of magnitude only.

This is why p# is preferred on HDB data, which is sorted at end of day anyway, while g# is the price paid in the RDB for fast lookups on data that arrives unsorted.