Which Attribute Has the Most Memory Overhead, and Which Has None?

Question

Compare the memory overhead of the four kdb+ attributes. Which has none, and which tend to be the most expensive?

Solution

/ Measure the memory used by an attributed copy of a list
mem: {[a;x] .Q.gc[]; b:.Q.w[]`used; y:a#x; .Q.gc[]; (.Q.w[]`used)-b}

x: asc 10000000?`$string til 5000     / 10M sorted symbols, 5,000 distinct
mem[`s;x]     / almost nothing: s# on a sorted list just sets a flag, no copy
mem[`p;x]     / about the size of a plain copy of x: the block index is tiny
mem[`g;x]     / noticeably more: the copy plus an index of every position

u: til 10000000                       / 10M unique values
mem[`u;u]     / the most: the copy plus a hash table with an entry per value

Explanation

Each attribute stores a different structure alongside the list, and the size of that structure determines the overhead:

Sorted `s# — none. It is only a flag saying the list is in ascending order, so kdb+ can binary-search it. No index is built.

Parted `p# — small, proportional to the number of distinct values. It records where each value's contiguous block starts. For a column with 5,000 distinct symbols, that is 5,000 entries however many rows there are.

Grouped `g# — grows with the number of rows. It keeps an index of every row position, grouped by value.

Unique `u# — grows with the number of rows. It keeps a hash table with an entry for every value — one per row, since all values are distinct.

Measured on KDB-X with the code above, g# on the 10M symbols added roughly 90MB, and u# on 10M unique longs roughly 400MB (both including the memory allocator's rounding to powers of two). So the order is s# (none) < p# (tiny) < g# and u#, with u# typically the largest per row.

These costs are usually worth paying: KX's white paper shows g# cutting the workspace of a single-symbol query on a 100M-row table from 1.2GB to 8.9MB.

Practical implication: if memory is tight and the data can be sorted, prefer p# over g# — which is exactly what an HDB does. The trade-off is that p# requires contiguous data and is removed by any in-memory modification, while g# is kept through appends of data in any order.