How Does `s#` Enable Step-Function Lookup on a Keyed Table?

Question

Show how applying s# to a keyed table enables temporal lookups. How does this differ from a standard keyed table lookup, and how does it relate to aj?

Solution

/ Step function with a sorted dictionary (simplest form — scalar keys)
d: 0 1 5 10 15 ! `A`B`C`D`E
d 4              / ` — no key 4, returns null (no attribute yet)

d: `s# 0 1 5 10 15 ! `A`B`C`D`E
d 4              / `B — largest key ≤ 4 is 1, returns `B
d 10             / `D — exact match
d 16             / `E — largest key ≤ 16 is 15
d -1             / ` — no key ≤ -1, returns null

/ The same step-function behaviour applies to keyed tables
/ A keyed table is a dictionary mapping key rows to value rows
/ Simpler example with integer key for easy verification:
kt: ([k: 0 1 5 10 15] v: `A`B`C`D`E)
kt[enlist 5]     / (key lookup returns the value row for k=5)

kts: `s# kt
kts[enlist 4]    / step function: returns the row for k=1 (largest k ≤ 4)
kts[enlist 10]   / returns the row for k=10 (exact match)

Explanation

A standard dictionary lookup on a key that does not exist returns a null. A standard keyed table lookup on a key that does not exist returns a row of nulls.

When s# is applied to the key list of a dictionary or keyed table, lookup behaviour changes to a step function: a missing key returns the value associated with the largest key that is less than or equal to the query. This is "as-of" semantics.

Why this works: s# enables binary search. When kdb+ binary-searches for a key that does not exist, the search terminates at the position where the key would be inserted to maintain sorted order — the element immediately before that position is the largest key ≤ the query, and that element's associated value is returned.

Relationship to aj:

aj (as-of join) implements the same step-function semantics, but for joining two full tables rather than for single-point lookups:

/ aj: for each row in trades, find the most recent matching row in quotes
aj[`sym`time; trades; quotes]

aj also relies on the time values being in order: KX recommends that the quote table be sorted by time within each sym (with g# on sym in memory, or p# on disk), so that it can search for the most recent quote at or before each trade time.

The step-function keyed table is the lightweight version: useful when you need a single temporal lookup rather than a full join. Common use cases include looking up the prevailing exchange rate, instrument status, or reference price at a given point in time without joining two large tables.

Key column must be sorted: applying s# to a keyed table whose key column is not in ascending order throws 's-fail, just as it would for a plain list.