Earlier this year we announced the Beta release of Doltgres, the world's first and only version-controlled postgres-compatible SQL database. We're still hard at work delivering incremental improvements.

To be a drop-in Postgres replacement, Doltgres needs to support all the built-in tables and functions that Postgres does. There are a lot of them, to put it mildly. Most of them are pretty straightforward to implement and fit in well with the SQL execution engine we built for Dolt. But every now and then we encounter one that causes us to really scratch our heads to even understand the basic concept, let alone how we would support it.

Let's talk about Postgres's set-returning functions.

What's a set-returning function?

Functions in SQL are expressions, so they're valid anywhere a normal expression is, like as part of a SELECT statement. Here's a simple example.

postgres=# select random(), concat('a', 'b');
 0.042804816001707824 | ab

This is normal and uninteresting. Each of these expressions gets evaluated by calling the function, and its result gets returned as part of the output row. This is also true for a SELECT statement involving a table. For every row in the table, the expressions get evaluated and returned, 1 to 1.

postgres=# create table demo (a int);
CREATE TABLE
postgres=# insert into demo values (1), (2);
INSERT 0 2
postgres=# select random(), a from demo;
 0.4499824526554792 | 1
   0.77313393946452 | 2

Subqueries are also expressions that can be used in most places any normal expression can be. Here I'm selecting a row from another table as part of a SELECT.

select 1, (select a from t1 limit 1);
        1 | {1}

But subquery expressions used in this manner have a built-in constraint: they must return at most a single value. What happens if I leave off the the LIMIT clause in my subquery so it returns more than one value? An error.

select 1, (select a from t1);
ERROR:  more than one row returned by a subquery used as an expression

Again this is normal and expected, and the behavior is defined as part of the SQL standard. And indeed, the assumption that a function expression evaluates to a single value (which can be a tuple), that is evaluated a single time per input row, is pretty fundamental to SQL as a language. It holds almost everywhere.

But not in Postgres. Postgres includes a number of functions that return a set of elements. Using one of them causes the output of a query to potentially include more than one output row for every input row. One of the most widely used is generate_series, which generates a range of numbers, like this example from the Postgres docs.

SELECT * FROM generate_series(2,4);
 generate_series
-----------------
               2
               3
               4

This isn't so weird, right? generate_series is basically a table function, like JSON_TABLE, which MySQL had a decade ago and Postgres just got in 2024. Table functions are functions that output rows, and you use them in your queries in the same places you would use tables. Here's how JSON_TABLE works.

SELECT jt.* FROM
 my_films,
 JSON_TABLE (js, '$.favorites[*]' COLUMNS (
   id FOR ORDINALITY,
   kind text PATH '$.kind',
   title text PATH '$.films[*].title' WITH WRAPPER,
   director text PATH '$.films[*].director' WITH WRAPPER)) AS jt;

There's a little magic with JSON_TABLE in particular because it adds an implicit lateral join to the tables preceding it in the query, but that's all. It's a normal table factor, just one whose rows happen to come from a function, rather than a subquery or a literal table name.

But set-returning functions aren't table functions. The previous example of SELECT * FROM generate_series(2,4); just reveals a Postgres syntax quirk: you can SELECT * FROM any function to treat its output as a table function, e.g.:

postgres=# select * from random();
 0.05572541855966873

But again: set-returning functions are not themselves table functions, which can only be used in queries where tables are allowed. Set-returning functions can be used anywhere expressions are allowed. So this works fine.

SELECT a, generate_series(2,4) from t1;
 {1}     |               2
 {1}     |               3
 {1}     |               4
 {1,2,3} |               2
 {1,2,3} |               3
 {1,2,3} |               4

But wait... what is that even doing? It looks almost like a cross join with t1, but it isn't. Not really. Let's dig deeper and see how these functions behave.

It gets weirder

Things get even wackier when you realize you can combine these expressions with other expressions, like addition. Here we'll add 100 to the result of generate_series.

postgres=# select generate_series(1,3) + 100;
      101
      102
      103

You can also combine them with other expressions that also return sets, and the semantics get even weirder. Here we'll examine another set-generating function Doltgres needs to support, generate_subscripts. It takes as input an array value, and returns all the subscripts of that array.

select * from t1;
 {1}
 {1,2,3}
select * from t2;
 {9,10}
select generate_subscripts(a, 1), a, generate_subscripts(b, 1), b from t1, t2;
                   1 | {1}     |                   1 | {9,10}
                     | {1}     |                   2 | {9,10}
                   1 | {1,2,3} |                   1 | {9,10}
                   2 | {1,2,3} |                   2 | {9,10}
                   3 | {1,2,3} |                     | {9,10}

Look carefully at what happens here. It's nothing at all like a join between two table factors. This query is a cross join between the tables t1 and t2, which produces 2 distinct combinations of rows (two from t1, one from t2). Then for each of those combinations from the two tables in the FROM clause, it's generating an additional number of rows according to the array column contents. Let's look at just the first combination of rows from the join, [{1}, {9,10}] and examine what happens.

• generate_subscripts({1}) returns a single row, [1]. (Postgres array indexes are one-based).
• generate_subscripts({9,10}) returns two rows, [1], [2].
• This means that the input row [{1}, {9,10}] gets expanded into two output rows, since the maximum number of rows for any set-returning function's output for this input row is two.
• The expression generate_subscripts(a, 1) returns NULL when it runs out of elements for that input row.
• The columns from t1 and t2 are also returned verbatim, as are any other expressions.

Similarly, the input row [{1,2,3}, {9,10}] gets expanded into three output rows, since that's the maximum number of rows returned by the set-returning functions for that input row. This time, it's the expression generate_subscripts(b,1) that runs out of values to return and produces a NULL.

If you've spent any amount of time with SQL, you understand at a visceral level how weird this behavior is. SQL functions are not supposed to be able to change the cardinality of their input. If you include a function as part of a SELECT statement on a table with 5 rows, you expect to get 5 rows back, for any function. This is also why subquery expressions are restricted to returning a single row in the SQL standard. This invariant is true everywhere but these special functions.

What's happening here is almost like a strange inversion of aggregate functions paired with a GROUP BY clause, like this.

select sum(a) from t1 group by b;

Here the function sum() collapses N input rows from t1 into a single output row, using the optional GROUP BY to decide how to partition the input rows. Set-returning functions are almost the inverse of this behavior, but they aren't defined by any standard. They're just something Postgres invented.

And this behavior used to be even weirder. From the release notes to Postgres 10:

Set-returning functions are now evaluated before evaluation of scalar expressions in the SELECT list, much as though they had been placed in a LATERAL FROM-clause item. This allows saner semantics for cases where multiple set-returning functions are present. If they return different numbers of rows, the shorter results are extended to match the longest result by adding nulls. Previously the results were cycled until they all terminated at the same time, producing a number of rows equal to the least common multiple of the functions' periods.

What are you supposed to use these things for?

Set-returning functions are primarily used in a normal, boring manner that makes them very similar to normal table functions in operation. Here's an example from the docs that expands every value in a table with an array column.

SELECT a AS array, s AS subscript, a[s] AS value
FROM (SELECT generate_subscripts(a, 1) AS s, a FROM arrays) foo;
     array     | subscript | value
---------------+-----------+-------
 {-1,-2}       |         1 |    -1
 {-1,-2}       |         2 |    -2
 {100,200,300} |         1 |   100
 {100,200,300} |         2 |   200
 {100,200,300} |         3 |   300
(5 rows)

And if you use them in this boring manner, confined to subqueries where they belong, you might never notice how weird they are. And that's good advice you should typically follow.

Doltgres's implementation

Once we realized how weirdly these functions behave when evaluated, we had to do some deep thinking on how to integrate them into our SQL execution engine, which assumes (very reasonably) that functions cannot change the cardinality of a SELECT statement. In the end, our design looks like this:

• Set-returning functions return an iterator instead of a normal scalar value
• Special new logic in Project nodes iterate over any such values when present, matching the Postgres semantics and expanding the row count as necessary at execution time.

This is reasonably close to how Postgres handles things, with the caveat that Postgres returns iterators from operations in the normal course of business, so these set-returning functions didn't need much special handling in the Postgres engine. Our engine is not built that way at all. Here's how we adapt it in the crucial segment.

type nestedIterState struct {
	projections      []sql.Expression
	sourceRow        sql.Row
	iterEvaluators   []*RowIterEvaluator
}

func (i *ProjectIter) ProjectRowWithNestedIters(
	ctx *sql.Context,
) (sql.Row, error) {

	// For the set of iterators, we return one row each element in the longest of the iterators provided.
	// Other iterator values will be NULL after they are depleted. All non-iterator fields for the row are returned
	// identically for each row in the result set.
	if i.nestedState != nil {
		row, err := ProjectRow(ctx, i.nestedState.projections, i.nestedState.sourceRow)
		if err != nil {
			return nil, err
		}

		nestedIterationFinished := true 
		for _, evaluator := range i.nestedState.iterEvaluators {
			if !evaluator.finished && evaluator.iter != nil {
				nestedIterationFinished = false
				break
			}
		}

		if nestedIterationFinished {
			i.nestedState = nil
			return i.ProjectRowWithNestedIters(ctx)
		}
		
		return row, nil
	}

	row, err := i.childIter.Next(ctx)
	if err != nil {
		return nil, err
	}
	
	i.nestedState = &nestedIterState{
		sourceRow: row,
	}
	
	// We need a new set of projections, with any iterator-returning expressions replaced by new expressions that will 
	// return the result of the iteration on each call to Eval. We also need to keep a list of all such iterators, so
	// that we can tell when they have all finished their iterations.
	var rowIterEvaluators []*RowIterEvaluator
	newProjs := make([]sql.Expression, len(i.projs))
	for i, proj := range i.projs {
		p, _, err := transform.Expr(proj, func(e sql.Expression) (sql.Expression, transform.TreeIdentity, error) {
			if rie, ok := e.(sql.RowIterExpression); ok {
				ri, err := rie.EvalRowIter(ctx, row)
				if err != nil {
					return nil, false, err
				}

				evaluator := &RowIterEvaluator{
					iter: ri,
					typ:  rie.Type(),
				}
				rowIterEvaluators = append(rowIterEvaluators, evaluator)
				return evaluator, transform.NewTree, nil
			}
			
			return e, transform.SameTree, nil
		})
		
		if err != nil {
			return nil, err
		}

		newProjs[i] = p
	}
	
	i.nestedState.projections = newProjs
	i.nestedState.iterEvaluators = rowIterEvaluators
	
	return i.ProjectRowWithNestedIters(ctx)
}

type RowIterEvaluator struct {
	iter     sql.RowIter
	typ      sql.Type
	finished bool
}

func (r *RowIterEvaluator) Eval(ctx *sql.Context, row sql.Row) (interface{}, error) {
	if r.finished || r.iter == nil {
		return nil, nil
	}

	nextRow, err := r.iter.Next(ctx)
	if err != nil {
		if errors.Is(err, io.EOF) {
			r.finished = true
			return nil, nil
		}
		return nil, err
	}

	// All of the set-returning functions return a single value per column
	return nextRow[0], nil
}

There are still some bugs and edge cases to work out, but this gets all the queries in this blog post behaving the same as Postgres. This new functionality will be included in the next release of Doltgres when it's all working correctly.

Conclusion

Work continues on Doltgres. We implemented set-returning functions as part of our ongoing project to get the SQLAlchemy tool up and running. If you have a feature you want us to hit first, please file an issue to let us know! We love hearing from our customers.

Questions about Postgres, or about using the beta release of Doltgres? Find a bug you want fixed? Come by our Discord to talk to our engineering team and meet other Doltgres users.