GSoC 26: Adding streaming window functions to MariaDB

This summer, I was selected as a Google Summer of Code contributor to MariaDB, working directly with the optimizer to wire in a streaming path for window functions, mentored by Oleg Smirnov and Dave Gosselin.

The work is still not merged upstream, but you can view all the code here PR#5267

How the journey started

I’m Omar, a computer engineering student at Cairo University. I’ve wanted to contribute to open source for a while but was always intimidated by it.

I heard about GSoC and that’s where it started. A little while before the GSoC period had started, I started searching for an organization to begin contributing to, and my criteria were simple:

1. Be interesting and low-level enough that I’m forced to read and learn about a new field in CS.
2. Be challenging, so that I’m not competing with huge numbers.
3. Have an active community that’s willing to help new open source contributors.

While many organizations fit these criteria, I didn’t take long to land on MariaDB as my starting point into the open source world. It’s a database (cool), it’s well documented how to compile from source and run the tests, and they’re active. I made some small contributions to get familiar with the code base and the nature of the cycle there, and then proceeded to pick MDEV-38970 for my GSoC project, even though at the time I did not know what window functions were :)

What the project is about

Window functions are SQL functions that let you run a calculation across a set of rows related to the current row, with defined partitions and ordering, and without collapsing the rows into a single value the way GROUP BY does. If they’re new to you, this is a good intro.

MariaDB used to materialize any query that had a window function. Whether it was needed or not, a window function meant full materialization.

Materialization is an execution strategy where the database engine writes intermediate rows or partial query results into a temprary table, either in memory or spilled to disk to perform non-streamable operations, like sorting by keys from multi table joins or aggregating.

Consider a simple query:

SELECT rank() OVER (ORDER BY id) FROM t1 LIMIT 10;

Logically, this should just read the first 10 rows in id index order and apply RANK() over them, which is just a counter. Instead, the whole table gets copied into a temporary table first, then the rank function runs over every row, and only then are 10 rows sent back. That’s a big time and memory overhead (numbers at the bottom), and probably an order of magnitude more overhead if the table is large enough that the temporary table spills to disk.

To put into perspective, Linux perf shows that for ordinary window-function queries, about 42–48% of the time is spent on saving the computed values back into the temporary table. Here’s why that’s so costly: to store the result, the server rewrites the whole row back into the temp table for every row, not just the computed window value, but every column the query is carrying (the SELECT fields, the ORDER BY and PARTITION fields, and one field per window function), re-packed into the storage engine’s format. So for each row it moves a full, wide row roughly twice, once to snapshot the old version, once to write the new one back, purely to persist a value it had already computed in memory. This happens for all rows of the table regardless of if LIMIT exists.

But for a lot of window functions, the ones where you only ever need the current row and/or the rows before it like a rank or a running total, you never actually need the whole table sitting in memory at once. You can keep a little running state, look at each row as it arrives, update the state, emit the answer, and move on. That’s streaming. It’s a completely standard idea in databases; window functions in MariaDB just weren’t taking advantage of it yet. My project was to change that.

My contribution

The result is a new, tested execution path for window functions, the first in MariaDB that computes them without copying the table into a temporary table.

What I enjoy most is designing a solution that fits naturally into the existing architecture. Both while planning and all through the implementation, most of my time went into reading existing code, to wire the new path exactly where it belongs and reuse as much of the existing machinery as possible. Making the streaming path purely additive was a deliberate goal: the old materializing path is left exactly as it is, streaming only takes over when it’s provably safe, and every query that doesn’t qualify behaves exactly like before.

Pulling that off took understanding the existing execution well enough to know exactly where it was safe to divert.

Here’s the idea in plain terms:

• Hook into the join loop and compute as rows fly by: During normal query execution (assuming nothing else needs materialization), the join loop emits rows one by one and sends them to the client. Naturally, we hook the window function computation here, so that the value is computed, read live and then immediately sent.
• Let the optimizer decide how rows arrive: Window functions require that rows come in a specific order (more on this later), but they internally process the current row through a buffer, so they don’t care about the interface the row comes from, whether it’s a filesort, an index scan or a loose scan for a GROUP BY, we let the optimizer decide that.
• Reuse the window function machinery: Luckily, the existing machinery for processing window functions does not assume materialization. For the cases we care about (current row or previous), the frame cursors of the function just look at the current row value through the buffer, and they have the previous value cached (for handling partitions), so the way the functions are computed and how they look at the frame of rows is reused, with some added handling for aggregate functions that I’ll come to.

So the design deliberately mirrors how the server already does things, just without the detour through a temp table. Now let’s get more involved.

Proving when streaming is safe

The original ticket asked for a deliberately small starting case: RANK(), ordered by an index, no partitions or grouping. That one’s easy to see is safe, the index hands you the rows already sorted, so you just count them as they go by.

Much of the work was deciding when it’s safe to stream and finding cases where it’s not along the way, because getting a condition wrong means silently returning wrong answers. The set of conditions can be summarized as:

1. Functions are from a supported list (ROW_NUMBER, RANK, DENSE_RANK, SUM, AVG, COUNT, MIN and MAX), without DISTINCT.
2. Nothing else in the query independently requires materialization.
3. A single sorting pass satisfies the whole query. That is, there exists a window function whose order list is a maximal prefix of all other window orders. If the query has an external ORDER BY, then this should be covered too.
4. The frame looks at the current row, or UNBOUNDED PRECEDING.
5. The rows arrive at the join output in the exact shape they will be sent, no further aggregation is required. (example: for queries with GROUP BY, the optimizer picks a loose index scan).

Most of these conditions are about when to stream, not how to compute. The computation itself needed little change. The exceptions are where it got interesting.
An example that comes to mind though: for aggregate functions, a small nuance prevents us from getting the maximum use of streaming.
Per the SQL standard, the default frame unit is RANGE, this means if one runs a query like:

SELECT SUM(x) OVER(ORDER BY col) FROM T1;

This should do a running sum over the col order. For “peers” (equivalent col values), the SQL standard says they should get the same result. That means the execution should first look ahead for all x values in a col peer group, aggregate them, and then output the rows.

This does not align with our criteria for streaming. You can’t look ahead when you process row by row. A big use case for this type of query though is aggregating and sorting by a unique non-NULL column that has no peers, like a primary key.
So in order to get the optimization for this use case, users will have to write the query as:

SELECT SUM(x) OVER(ORDER BY col ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) FROM T1;

so as to remove that RANGE limitation. Who would write that though?

The solution here is that if we can prove that the ordering is unique and has no NULLs (those can repeat on unique columns), we can instead create a ROWS cursor instead of RANGE and get the performance without a rewrite. They’re the same logically. Simple change, big win.

Testing

I’ll talk about manual testing first, then the automated mtr tests.

A big portion of the time, testing is done manually by picking some query shape and observing the plan, then extending on it. Some bugs can only be found this way rather than by intuition, since the optimizer is very complex. Those vary from loud crashes to silent correctness bugs.

For example, while setting up the streaming for aggregates, I had a bug where the MAX and MIN functions would crash the server. The reason is a bit involved, window functions are designed so that they can work with a moving window of rows. For example, removing a row for the SUM function is trivial, it’s just a subtraction. For MAX and MIN though, the default cursor is a scan one, which means it walks the whole moving frame whenever a row is removed. This cursor is created by default, the fix was just to create a normal cursor since for our criteria, we only ever append to the frame, never remove.

A silent bug that comes to mind was a query with GROUP BY and HAVING. As said before, we stream GROUP BY under a certain condition (loose index scan), for this path, the HAVING condition is applied after the point where window functions are hooked, so the values come out wrong, they’re computed for rows that never reach the client. Note that this only happens when the HAVING condition is not rewritten into a WHERE clause.

Some other bugs were found by Oleg through the reviews, and he explains them well that the fix is usually obvious after.

The fixes are usually simple, finding and reasoning about them is the hard part. I’ve known this since my early contributions to MariaDB, before GSoC even started.

MariaDB, like any software, tests existing functionality through regressions. Test files have queries with either their plans or results, and running the tests just makes sure those don’t change.

For our testing purposes, we care about the plans (to show the optimization indeed happens), and correctness (to show that the results do not derail from the existing, battle tested materialization path).

For this, Oleg suggested running each and every test two times. Once as a normal query, and once with SQL_BUFFER_RESULT, a modifier that forces materialization. This way, the test persists the results of the two paths and they can easily be compared as multi sets where any difference would be a loud test fail.

Benchmarks and Numbers

To have some nuance of how much faster this is, we construct a simple table having just a million rows.

CREATE OR REPLACE TABLE bench_1m (id INT NOT NULL PRIMARY KEY, x DOUBLE NOT NULL);

We test both paths, once with an ordering that requires a filesort, and once with an ordering satisfied by an index.

Materialization takes about 5 seconds, entirely in memory without spilling to disk.

Streaming takes half of that, just the time needed for the filesort.

Materialization does not know about the index and does a filesort.

Basically free, reads only 10 rows from the index and performs the cheap aggregation.

What’s next

The PR is still under review, so the immediate next step is working through the optimization and correctness feedback and getting it merged.

Beyond that, streaming window functions were never the end in themselves, they’re the foundation for something bigger (MDEV-35970). The vision is to bring hybrid search into the MariaDB engine: instead of pulling all the data into the application and combining rankings there, the server itself blends results using reciprocal rank fusion (RRF).
Picture two streams that each hand back rows in ranked order, one from vector/semantic search, one from exact search. The user just wants the top results. To do RRF efficiently, the engine should pull a buffer of rows from both, rank them with a window function, and keep going only until it has enough to satisfy the LIMIT. Without streaming, that ranking would first have to materialize all the rows from both sources, exactly the overhead this project removes.

So this GSoC project is the groundwork RRF stands on. Building the RRF node on top is the direction I’m most excited to take once this work lands, and I plan to keep at it with the community.

What I learned this summer

Reading and modifying code that has significant parts written before you were born has a very good feeling to it, and of course it makes you learn a lot.

What I wanted from open source and GSoC is to have the skill to navigate a large codebase without being intimidated, and I got that and more. It feels good looking at all the optimizations done across the years and continuing on the work of such amazing engineers.

I learnt to use a debugger too. I was familiar with C++ but never worked on a big enough project to need a debugger, so I learned to use gdb and rr to step through the code and understand the flow of execution, where a variable changes exactly. Tracing a bug through the debugger is a very fun experience. I also learned a lot about how databases work, especially the optimizer and execution engine.

I want to thank both my mentors, Oleg and Dave, for being available, and to thank Oleg specifically for his time on code reviews. They’re always reproducible, real and he even goes the extra mile to tell me where he thinks the fix should land in my code. It has been a long time since I got such meaningful reviews.

Even at the start of the project, I took some time to open the PR because I wanted to have something working, he told me that it’s okay to open a PR early and keep working on it, so this was very reassuring in the beginning.

The code, and some other work

If any of this was interesting, the best next step is to read the actual patches:

• MDEV-38970: Streaming window functions — the main GSoC PR this whole post is about (under review).

And some other MariaDB work of mine outside of GSoC, if you’re curious:

• MDEV-38877: Unnecessary filesort on derived table materialization (merged)
• MDEV-7270: Replicas not honoring slave_skip_errors (merged)
• MDEV-38819: Wrong result of “Range checked for each record” after HAVING pushdown (under review)

So that’s basically my summer, hope you had a good one too :)