learnkdb
Back to Performance Benchmarks

Attributes · Performance Benchmarks · Practice Question

At What Point Does the Unique Attribute Start Providing a Significant Benefit?

Sign in to track your progress

Question

For a column with high cardinality (many distinct values), at approximately what data size does the unique attribute start providing a meaningful performance benefit over a linear scan?

Solution

/ Benchmark: single-value lookup at different table sizes
/ (from KX columnar database white paper)
/ Table: keyed on sym, filtering for one value

/ 100K rows: ~0ms both with and without `u#
/ 1M rows:   ~0ms with `u#, ~2ms without
/ 10M rows:  ~0ms with `u#, ~23ms without
/ 100M rows: ~0ms with `u#, ~233ms without

/ At ~1 million rows, the linear scan becomes measurably slower
/ At ~100 million rows, the gap is 230ms vs 0ms

/ Practical verification — neg[n]?`8 generates n distinct random symbols:
t: ([] sym:neg[10000000]?`8; val:10000000?100.0)   / 10M rows, unique syms, no attribute
s: t[`sym] 5000000                                  / a symbol that is in the table
\ts select from t where sym=s                      / measurably slow
t: update `u#sym from t
\ts select from t where sym=s                      / almost instant with `u#

Explanation

The unique attribute provides hash-based lookup, whose cost does not grow with the table. Without it, where sym=x compares every row with the target. For small tables, O(n) is fast enough that the hash table overhead of u# provides no advantage. As the table grows, the linear scan time grows linearly while the hash lookup stays constant.

The crossover point is approximately 1 million rows.

Below 1M rows, a linear scan typically completes in under a millisecond — fast enough that u# provides no perceptible improvement. Above 1M rows, the gap opens. At 100M rows, KX's white paper measured 233ms vs 0ms — a penalty that compounds if the query runs repeatedly or concurrently.

This rule of thumb helps with practical decisions:

  • Small reference tables (instruments, currencies, exchanges) with fewer than 1M rows: u# is beneficial but not urgent
  • Growing tables (instrument universe expanding over time): apply u# before the table reaches 1M rows
  • High-frequency lookup columns in large tables: apply u# immediately

Note on workspace: the unique attribute also dramatically reduces workspace for lookups. In the white paper, a single-value select on a 100M-row table used 134MB of workspace without u#, and about 1KB with it.

Keyed tables and direct indexing:

For keyed tables (keyed on sym), direct indexing is even faster than a select statement, regardless of whether u# is applied:

kt: `sym xkey ([] sym:`AAPL`GOOG`MSFT; price:150 2800 310)
kt[`AAPL]        / direct key lookup — faster than select from kt where sym=`AAPL

For very large keyed tables, applying u# to the key column provides the same O(1) benefit as for regular columns.