What if SELECT, FROM, WHERE were functions?

Check out this code:

movie WHERE ((company.country == "[us]") AND
             (keyword == "character-name-in-title"))
     SELECT (title AND cast.person.alias.text)

From a mile a way this just looks like a regular SQL query. If you stare at it though, a few things are off: where's the FROM clause? Why does the SELECT clause come last (like a sane language)? And what's going on with cast.person.alias.text? Is that JSON? Let me explain. First, I'll strip away some syntax magic. The same code in Rust looks like this:

movie.with(company.s(country).eq("[us]")
           .and(keyword.eq("character-name-in-title"))
   .select(title.and(cast.s(person).s(alias).s(text)))

Both snippets are queries in a new embedded query language/library we're building called Prela. The original snippet was actually in Scala, and each of WHERE, AND, and SELECT is an infix function, corresponding to Rust's .with, .and, and .select. The == operator is overloaded and corresponds to .eq. Finally, the . operator is also overloaded; it corresponds to Rust's .s which is just an alias for .select. In other words, each of the keywords/operators is a function. But what do the functions take in and produce?

The source code of Prela can be found here.

SQL is based on Codd's Relational Algebra (RA) which is an algebra of relations, a.k.a. tables. Each relational algebra operator takes in tables and produces a table. In contrast, Prela is based on Tarski's Algebra of Relations¹ (TAR), which is much less known and much older than Codd's Relational Algebra — although TAR is named after Tarski, its main ideas date all the way back to De Morgan in the 1860s. We've said RA is an algebra of tables — we can think of TAR as an algebra of columns. In both code snippets, each of the variables including movie, company, country conceptually corresponds to a table column. More concretely, they are represented as binary relations under the hood. To understand what's going on, let's consider the following table:

This table decomposes into 4 binary relations: the first maps each ID to its row, and the other 3 map each row to its title, year, and keyword, respectively. The special treatment of the ID column will make sense later.

We'll call the tables movie, title, year, and keyword from left to right. Now let's consider the simplest query we can write: movie.select(title) in Rust, or movie SELECT title in Scala. The .select operator implements relation composition, which first joins its arguments using the second column of the LHS and the first column of the RHS, then throws away the join column. Formally, r.select(s) is equivalent to the RA expression \pi_{r.1, s.2}(r \Join_{r.2 = s.1} s) where r.i is the i-th column of r. Another way to understand relation composition is to view it as a generalization of function composition, in the same way (binary) relations generalize functions. A binary relation is just a function that can map the same "input" to multiple different "outputs". Let's write r[x] to denote the values x maps to under r as if "applying" r to x, i.e., r[x] = \{y \mid (x, y) \in r\}. Further generalize the notation to allow a set as an argument, i.e., r[\mathbf{x}] = \bigcup_{x\in \mathbf{x}} r[x]. Then, the composition r.select(s) is exactly \lambda \mathbf{x} . r[s[\mathbf{x}]] (with further abuse of notation identifying a relation with its "function"). That's all very abstract, so let's go back to our example. The composition movie.select(title) joins the movie relation (the ID relation) with the title relation on row number. The result is a binary relation mapping every movie ID to its title. This also explains why we needed the row number on the second column of the ID table, because we need to join on it. Similarly, movie.select(year) maps IDs to years, and movie.select(keyword) maps IDs to keywords.

Composition also plays the roles of joins. Say we add a company column to the movie table, mapping each movie's row number to the ID of its production company, and decompose a separate company table with columns id, name, and country.

The query movie.s(company).s(id2row).s(country) then finds the country of a movie's production company, where id2row maps company IDs to row numbers. Because joining on a foreign key almost always means "resolving" the key to a row number first, Prela automatically inserts that .s(id2row) step for us, the same way Rust automatically dereferences pointers on field access. This lets us simply write movie.s(company).s(country), which reads as "movie's company's country". This is also what happened on the last line of the first two query snippets.

To "select" multiple attributes, we can use the .and operator: movie.select(title.and(year)) (or movie SELECT (title AND year) in Scala) maps each movie ID to a tuple of title and year. More rigorously, r.and(s) joins the arguments on their first column, but combines their second columns into a tuple; in RA: \pi_{r.1, (r.2, s.2)}(r \Join_{r.1 = s.1} s). Using our example, title.and(year) is the binary relation mapping 0 to (The Godfather, 1972), 1 to (Seven Samurai, 1954), and 2 to (Casablanca, 1942). The insistence on binary relations is crucial for compositionality: all our operators take in and produce binary relations, so they can be composed freely as long as the types line up.

Next, the predicate r.eq(v) filters a binary relation r, keeping only the rows whose second column equals v — in RA, \sigma_{r.2=v}(r). In our example, keyword.eq("character-name-in-title") keeps only the rows of keyword (which maps a movie to its keywords) whose keyword is that string, while company.s(country).eq("[us]") first composes company (movie to company) with country (company to country) to get a mapping from each movie to its country, then keeps only the ones in the US.

Finally, the restriction operator .with (in Rust) or WHERE (in Scala) implements exactly the left-semijoin r \ltimes_{r.2=t.1} t: it keeps only the rows of r whose second column matches some row of t. A happy accident is that .and doubles as logical conjunction when nested inside a .with clause. Putting it all together, the first 2 lines of our full example keep only the movie IDs that pass both the country filter and the keyword filter — American movies with a character's name in the title.

That's all the features we need for the original query snippets! Prela also supports grouping and aggregation in a rather clever way, as well as other common operators. You can check our paper for details.

But stepping back, what's the point of all this, besides a way to implement a "query language" without having to write a parser (which I admit was my original motivation, I hate writing parsers...)? You may also ask: "is this just an ORM?" Yes and no. Prela offers the ergonomics of an ORM without the added indirection. ORMs work by generating SQL, adding yet another layer of abstraction over an already opaque system. A common complaint for ORMs is that they make it harder to optimize queries when the performance is unsatisfactory. Ironically, the same complaint also applies to SQL itself, where plan hints only alleviates some of the pain. In contrast, Prela can be implemented extremely close to the metal. The Rust implementation inlines operators and compiles them into tight fused loops over raw arrays, running several times faster than DuckDB even without a query optimizer. Being an embedded language, the user can also pass arbitrary Rust code to the query and be assured the entire query will be compiled as a whole for good performance. All of this is thanks to the power of TAR, as binary relations offer a faithful model both at the semantic level (entity-relationship) and at the physical level (column stores). We also believe the power of TAR need not be limited to Prela. Column stores must assemble the columns back into relations in some way, and we suspect how that's implemented in mainstream systems already follows operations in TAR, and revisiting the implementation with the new-found clarity can greatly simplify the system.

If you enjoy our work, please consider supporting our research lab!