Designing Rayfall: One Expression Language for a Columnar Database

Columnar engines naturally organize computation around vectors to make effective use of single instruction, multiple data (SIMD) instructions. This makes vectors first-class citizens in such engines. The difficult design question appears when an engine's internal application programming interface (API) must be exposed to users: where should programming happen?

A native C API is sufficient for embedding, and many engines stop there. Building a complete analytical database, however, requires a full-featured language for programming on top of the engine.

There are well-known options:

• SQL - solves the relational part of this problem, but a database runtime may also expose direct vector calculations, object creation, user-defined lambdas, OS integration, orchestration, control flow, graph algorithms as well as generic-purpose programming, not only analytic queries. Implementing all of these in SQL would produce a standalone dialect besides the relational language.
• Embed an established scripting language - it immediately solves lambdas and control flow, but it also introduces a second runtime.  

Thus the language design problem is larger than just query syntax: "How can a columnar engine expose its native data types and operations without restricting users to C, duplicating those values in another runtime or hiding expressions from the engine optimizer"?

Rayfall provides a concrete case study. It is an expression language in which native values, vector operations, user-defined lambdas, and relational queries are the natural language components.

Its syntax is well-known S-expressions, which bring powerful mechanisms as well as a dramatically simple parser, which is mandatory in the case of real-time requests that require fast responses thus wasting time in parser would be irrational. 

Requirements 

Architecture

Rayfall uses S-expressions: 

(+ 2 3)
(* (+ 2 3) 4)
(sum [10 20 30])

The parser does not produce any AST; rather, it produces an evaluation tree immediately where each object is the same struct with a type tag, reference counter, and payload. 

• (...) - is a List
• [...] - homogeneous vector
• {...} - dictionary
• "..." - string literal
• [0-9]* - number
• [a-zA-Z]* - symbol
• (fn [args] (body)) - lambda

A dictionary is just a two array of the same length: keys and values. Thus, a table is just a flipped dict where keys are table column symbols, values are lists of column vectors. This is how, for example, Q language acts. 

Another advantage of an S-expressions-based language is equivalence of code and data:

(+ 1 2)                 ; an executable list
(quote (+ 1 2))         ; the same structure treated as data
[AAPL MSFT NVDA]        ; a typed symbol vector
{from: trades
 where: (> price 100)}  ; a dictionary containing expressions

Unification

Let's consider multiplication. 

(* 12.5 4)                         ; scalar call
(* [12.5 20.0 8.0] 4)              ; vector - scalar 
(select {from: trades                 
         notional: (* price qty)}) ; table columns 

While the expression surface stays the same, the execution strategy changes depending on argument types. This is the core idea behind Rayfall. Vector operations are not a library lying on top of a low-level API, and query expressions are not strings passed to a separate SQL frontend. They are the same language expressions interpreted in the same context.

Queries

Consider the following simple table:

‣ (set trades
…   (table [sym time side price qty]
…     (list
…       [AAPL AAPL MSFT MSFT NVDA AAPL]
…       [09:30:00.000 09:30:30.000 09:31:00.000
…        09:31:30.000 09:32:00.000 09:32:30.000]
…       [BUY SELL BUY SELL BUY BUY]
…       [100.0 101.0 400.0 399.0 170.0 102.0]
…       [150 50 20 30 100 200])))
┌──────┬──────────────┬──────┬───────┬─────┐
│ sym  │     time     │ side │ price │ qty │
│ SYM  │     TIME     │ SYM  │  F64  │ I64 │
├──────┼──────────────┼──────┼───────┼─────┤
│ AAPL │ 09:30:00.000 │ BUY  │ 100.0 │ 150 │
│ AAPL │ 09:30:30.000 │ SELL │ 101.0 │ 50  │
│ MSFT │ 09:31:00.000 │ BUY  │ 400.0 │ 20  │
│ MSFT │ 09:31:30.000 │ SELL │ 399.0 │ 30  │
│ NVDA │ 09:32:00.000 │ BUY  │ 170.0 │ 100 │
│ AAPL │ 09:32:30.000 │ BUY  │ 102.0 │ 200 │
├──────┴──────────────┴──────┴───────┴─────┤
│ 6 rows (6 shown) 5 columns (5 shown)     │
└──────────────────────────────────────────┘

Columns are just regular vectors that can be extracted and passed to ordinary functions:

‣ (set prices (at trades 'price))
[100.0 101.0 400.0 399.0 170.0 102.0]
‣ (set quantities (at trades 'qty))
[150 50 20 30 100 200]
‣ (* prices quantities)
[15000.0 5050.0 8000.0 11970.0 17000.0 20400.0]

And the result is another typed vector:

[15000.0 5050.0 8000.0 11970.0 17000.0 20400.0]

There is no query yet. Multiplication simply lifts its scalar behavior over two equally sized vectors.

Broadcasting is straightforward:

(* prices 1.05)

Now place the multiplication inside select:

‣ (select {from: trades
         sym: sym
         price: price
         qty: qty
         notional: (* price qty)})
┌──────┬───────┬─────┬────────────────┐
│ sym  │ price │ qty │    notional    │
│ SYM  │  F64  │ I64 │      F64       │
├──────┼───────┼─────┼────────────────┤
│ AAPL │ 100.0 │ 150 │ 15000.0        │
│ AAPL │ 101.0 │ 50  │ 5050.0         │
│ MSFT │ 400.0 │ 20  │ 8000.0         │
│ MSFT │ 399.0 │ 30  │ 11970.0        │
│ NVDA │ 170.0 │ 100 │ 17000.0        │
│ AAPL │ 102.0 │ 200 │ 20400.0        │
├──────┴───────┴─────┴────────────────┤
│ 6 rows (6 shown) 4 columns (4 shown)│
└─────────────────────────────────────┘

Here the expression itself has not changed. What changed is name resolution. Inside query, price, and qty are column names. Before any query evaluation, the engine mounts columns to their names as a regular environment frame, naturally making all existing expressions work the same way as they do in a non-query context! 

Once a query is passed to a select function, it becomes an operation graph and, when its shape is supported, a fused DAG pipeline. Otherwise, it falls back to a regular operators defined as a language primitives. 

This opens a door to composing vector operations inside a predicate:

‣ (select {from: trades
…          where: (and
…                   (> (* price qty) 10000.0)
…                   (in sym [AAPL MSFT]))
…          sym: sym-name
…          notional: (* price qty)})
┌──────┬──────────────────────────────┐
│ sym  │           notional           │
│ SYM  │             F64              │
├──────┼──────────────────────────────┤
│ AAPL │ 15000.0                      │
│ MSFT │ 11970.0                      │
│ AAPL │ 20400.0                      │
├──────┴──────────────────────────────┤
│ 3 rows (3 shown) 2 columns (2 shown)│
└─────────────────────────────────────┘

Here is a short breakdown:

1. `(* price qty)` produces a floating-point vector.
2. `>` converts it into a Boolean vector. 
3. `(in sym [AAPL MSFT])` produces another Boolean vector.
4. `and` combines the predicates.
5.  The entire expression is reused as a projection.

At the language level, this follows the same composition rules as:

(and
  (> (* prices quantities) 10000.0)
  (in (at trades 'sym) [AAPL MSFT]))

But inside the pipeline, the DAG optimizer can fuse or rewrite expressions without changing semantics. From the user's point of view nothing changed. Such homoiconical behavior allows the use of any vector operations existing in the language inside queries. Consider the following example:

; xbar rounds values down to a fixed bucket. Applied directly to a time vector
‣ (xbar
…   [09:30:12.000 09:30:48.000 09:31:05.000]
…   60000)
[09:30:00.000 09:30:00.000 09:31:00.000]

; The same operation can define a group key
‣ (select {from: trades
…          by: {minute: (xbar time 60000)}
…          trades: (count qty)
…          volume: (sum qty)
…          vwap: (/ (sum (* price qty))
…                   (sum qty))})
┌──────────────┬────────┬────────┬────────┐
│    minute    │ trades │ volume │  vwap  │
│     TIME     │  I64   │  I64   │  F64   │
├──────────────┼────────┼────────┼────────┤
│ 09:30:00.000 │ 2      │ 200    │ 100.25 │
│ 09:31:00.000 │ 2      │ 50     │ 399.4  │
│ 09:32:00.000 │ 2      │ 300    │ 124.67 │
├──────────────┴────────┴────────┴────────┤
│ 3 rows (3 shown) 4 columns (4 shown)    │
└─────────────────────────────────────────┘

This example reveals several execution levels without changing languages:

1. `xbar` transforms a vector into a grouping key.
2. `*` derives a vector consumed by `sum`.
3. `sum` reduces values per group.
4. `-` folds aggregate results into a scalar per group.

In a system with separate array and query languages, these often require different syntax, a user-defined function boundary, or intermediate materialized columns. Here they remain one expression tree.

Lambdas

The integration becomes even more interesting when the expression is named:

; define user function:
‣ (set trade-value
…   (fn [price quantity]
…     (* price quantity)))
lambda

; It can be called with ordinary vectors:
‣ (trade-value
…   (at trades 'price)
…   (at trades 'qty))
[15000.0 5050.0 8000.0 11970.0 17000.0 20400.0]

; And the same function can be called with query columns:
‣ (select {from: trades
…          where: (> (trade-value price qty) 10000.0)
…          sym: sym-name
…          value: (trade-value price qty)})
┌──────┬──────────────────────────────┐
│ sym  │            value             │
│ SYM  │             F64              │
├──────┼──────────────────────────────┤
│ AAPL │ 15000.0                      │
│ MSFT │ 11970.0                      │
│ NVDA │ 17000.0                      │
│ AAPL │ 20400.0                      │
├──────┴──────────────────────────────┤
│ 4 rows (4 shown) 2 columns (2 shown)│
└─────────────────────────────────────┘

For a lowerable single expression lambda, the query compiler reduces the call into the operation graph. Actual arguments are compiled once and referenced by offsets, so using a formal parameter more than once shares the corresponding subexpression rather than rebuilding it. And this is interesting, because Rayfall is not only giving familiar names to built-in query operations. User-defined lambdas can participate in queries as well as any other language expressions.

Layout

Internally, a Rayfall builtin is a runtime object. Even more, any datatype, including scalar, vector, dict, table, function, or builtin, is the same ray_t struct with type tag, reference counter, and payload union. This allows implementing a simple and efficient buddy allocator that operates on ray_t blocks; even more on-disk data is exactly the same as in-memory, so the runtime doesn't care about actual object allocation and allows lazy mmaping of huge datasets seamlessly. For standalone vectors, the atomic dispatcher can itself build a small operation graph and execute it via the vector engine. For unsupported shapes, it retains a typed per-operation path. And this happens seamlessly, not exposed to a user

Compiler

Rayfall has two relevant compilation paths.

Ordinary user-defined functions compile lazily into bytecode for a stack VM. The bytecode handles local slots, calls, control flow, recursion, traps, and returns. If compilation can not handle a form, execution can fall back into the recursive evaluator and vice versa.

Query expressions take another route. The query layer attempts to lower an expression into a typed operation DAG:

• Literals become constant nodes.
• Column names become scan nodes.
• Arithmetic and comparisons become typed operations.
• Supported lambdas are beta-reduced.
• Aggregations become reduction nodes.
• Structural clauses add filters, groups, projections, sorts, and limits.

The DAG then passes through type inference, constant folding, predicate and projection pushdown, filter reordering, partition pruning, and dead-code elimination.

The Bottom Line

Rayfall can be understood as an attempt to close the space between a low-level C API and a high-level query interface. The resulting language is a LISP-like one, with some extensions like first-class homogeneous vectors, dictionaries and tables. The parser, evaluator, and query compiler discussed here are available in the GitHub repo.