jonnifyelixir
F4 / F4.12 / range

F4.12 · part 3 of 3 · range by time

Query by time range

The last capability the store needs is “what was created between these two times.” Because a Snowflake puts the timestamp in its high bits, ids sort by creation time, and a time window becomes an id range: compute the id that any entry at the start would have, and the one at the end, and every entry in the window is an id between them. The query needs no separate timestamp column — the bound is computed straight from the clock.

Five lessons in the partition, at known times. Pick a window and watch the bounds pick out the entries created inside it.

A window becomes a range Advanced: bounds, sorting, and the catch

A window becomes a range

The window’s start and end map to id bounds [min, max). An entry is in the window when its id falls in that range — equivalently, when its decoded time does. The lesson at 13:35 sits before every window here, so it is never matched. Pick a window.

Time window · select one · 2026-05-31 UTC

min ≤ id < max 2 of 5 in window 

      

      
window: 14:00–14:10

      
matched: 2 entries

    

    
No timestamp was stored, yet the store answered a time-range query. The id is the sort key and the
      clock, so a window of time and a range of ids are the same question.

  


  

    
Advanced: bounds, sorting, and the catch

    

      
The bound is arithmetic: a Snowflake is (milliseconds_since_epoch << 22) plus
        node and sequence bits, so the smallest id at time t is (t - epoch) << 22.
        Compute that for the window’s start and end and you have [min, max); the same
        trick drove the database range query in F4.08, where id >= min AND id < max rode
        the primary-key index with no created_at column.

      
The catch in memory is that a CHAMP is ordered by hash, not by key, so it cannot be sliced by an id range
        directly. Two honest options: keep a sorted index of ids alongside the partition — a sorted set or tree
        — and binary-search the bounds for a true range scan; or, when a partition is small, filter it by decoded
        time, which is what the demo does. Either way the namespace partition keeps the work to one entity kind, and
        the id-as-clock means the window never has to be stored to be queried.

    

    
# range/2 — a time window becomes id bounds over one partition
def handle_call({:range, ns, from, to}, _from, store) do
  min = Snowflake.at(from)                    # (from - epoch) <<< 22
  max = Snowflake.at(to)
  hits =
    store
    |> Map.get(ns, Champ.new())              # only this namespace's partition
    |> Champ.keys()
    |> Enum.filter(fn id -> id >= min and id < max end)  # in the window
  {:reply, {:ok, hits}, store}
end

    

      

        
a time window

        
“Everything created between 14:00 and 14:10.”

      

      
      

        
an id range

        
[min, max) from the clock; the partition’s entries in between.

      

    

    
That completes the lab — a partitioned, branded-CHAMP store that grows by namespace,
      resolves any id with a free timestamp, and answers time-range queries — and with it the
      Algorithms & Data Structures chapter. Return to the
      chapter overview.

  


  

    
References

    
Primary sources for this lab, and the lessons it assembles.

    

      
Sources

      
      
Related in this course