That query does not, “read literally”, say to do two nested loops. SQL is a clunky way of writing an expression in relational algebra
There’s actually no direct correspondence between sql and classic relational algebra. Converting sql to relational algebra is difficult and there are a lot of cases where databases just bail out.
All the query planners I’m familiar with actually translate the example query to an internal representation that includes some kind of nested loop operator. Postgres and sqlite don’t optimize that any further, leaving two nested loops in the final physical plan:
postgres> explain select users.id, (selectsum(posts.likes) from posts where posts.user_id = users.id) from users;
QUERY PLAN
---------------------------------------------------------------------
Seq Scan on users (cost=0.00..90649.75rows=2550 width=12)
SubPlan 1-> Aggregate (cost=35.52..35.53rows=1 width=8)
-> Seq Scan on posts (cost=0.00..35.50rows=10 width=4)
Filter: (user_id = users.id)
Materialize and cockroach are able to hoist operations out of the loops. But materialize produces a dag of operators and cockroach often use operators that rely on physical row ids. Neither is exactly what I’d think of as classic relational algebra.
The Python equivalent would construct an expression tree from primitives and then it would be fairly obvious that you could run an optimizing transform on it.
The sql compiler parses sql code into an expression tree and then optimizes it. The python compiler parses python code into an expression tree and then optimizes it.
If you make some dsl that builds a tree of relational operators but allow the leaves to produce side-effects or non-termination then you still can’t optimize it. If you make some dsl that allows loops but constrains side-effects within their bodies, then you can optimize it.
There’s nothing magic about trees of expressions that allows optimizations. Language semantics are what matter. For the kinds of optimizations in this example, the semantics that are important are ones that allow the compiler to reason about whether loop operations can be reordered. That’s true whether you expose the loops directly or hide them within relational algebra or list comprehensions.
I’m sorry I used the imprecise term “relational algebra” to refer to the semantic model of SQL. My point is that the expression tree of a SQL statement is not made of loops, it’s made of table expressions (with join operations), column references, aggregates, filters, CTEs, etc. To oversimplify again, it’s mostly about set operations, not loops.
Of course in the query planner it gets turned into something executable, which will sometimes involve loops, but that’s not the model of the language itself. Python expressions get turned into bytecode so they can be executed, but you don’t write Python as a way of expressing bytecode.
To be concrete, the semantic expression tree of
select users.id, (selectsum(posts.likes) from posts where posts.user_id = users.id) from users
isn’t
R=[]
for (u in users) {
x=[]; for (p in posts) { if (p.user_id = u.id) x+=p.likes }
R+=(u.id, sum(x))
}
return R
(Which in 2024 would be a much more natural way to write it in the first place, which is why I mentioned LINQ.)
In my experience writing and helping others to write SQL, if you write it thinking that you’re writing loops, it’s not as effective as if you write it thinking about set operations, especially as the queries get more complex. Not to mention that the error messages will actually make sense! To me this is like writing Rust thinking about structs, traits, borrows, etc. rather than thinking about assembly (99% of the time).
I’m not a SQL expert (though I have dug into the PG query planner on occasion) so maybe I’ve been doing this wrong, but it does seem to work.
There’s actually no direct correspondence between sql and classic relational algebra. Converting sql to relational algebra is difficult and there are a lot of cases where databases just bail out.
All the query planners I’m familiar with actually translate the example query to an internal representation that includes some kind of nested loop operator. Postgres and sqlite don’t optimize that any further, leaving two nested loops in the final physical plan:
postgres> explain select users.id, (select sum(posts.likes) from posts where posts.user_id = users.id) from users; QUERY PLAN --------------------------------------------------------------------- Seq Scan on users (cost=0.00..90649.75 rows=2550 width=12) SubPlan 1 -> Aggregate (cost=35.52..35.53 rows=1 width=8) -> Seq Scan on posts (cost=0.00..35.50 rows=10 width=4) Filter: (user_id = users.id)sqlite> explain select users.id, (select sum(posts.likes) from posts where posts.user_id = users.id) from users; addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 24 0 0 Start at 24 1 OpenRead 0 4 0 1 0 root=4 iDb=0; users 2 Rewind 0 23 0 0 3 Column 0 0 1 0 r[1]= cursor 0 column 0 4 BeginSubrtn 0 3 0 0 r[3]=NULL 5 Null 0 4 4 0 r[4..4]=NULL; Init subquery result 6 Integer 1 5 0 0 r[5]=1; LIMIT counter 7 Null 0 6 7 0 r[6..7]=NULL 8 OpenRead 1 2 0 3 0 root=2 iDb=0; posts 9 Rewind 1 16 0 0 10 Column 1 1 8 0 r[8]= cursor 1 column 1 11 Column 0 0 9 0 r[9]= cursor 0 column 0 12 Ne 9 15 8 BINARY-8 83 if r[8]!=r[9] goto 15 13 Column 1 2 9 0 r[9]= cursor 1 column 2 14 AggStep 0 9 7 sum(1) 1 accum=r[7] step(r[9]) 15 Next 1 10 0 1 16 AggFinal 7 1 0 sum(1) 0 accum=r[7] N=1 17 Copy 7 4 0 0 r[4]=r[7] 18 DecrJumpZero 5 19 0 0 if (--r[5])==0 goto 19 19 Return 3 5 1 0 20 Copy 4 2 0 0 r[2]=r[4] 21 ResultRow 1 2 0 0 output=r[1..2] 22 Next 0 3 0 1 23 Halt 0 0 0 0 24 Transaction 0 0 4 0 1 usesStmtJournal=0 25 Goto 0 1 0 0Materialize and cockroach are able to hoist operations out of the loops. But materialize produces a dag of operators and cockroach often use operators that rely on physical row ids. Neither is exactly what I’d think of as classic relational algebra.
The sql compiler parses sql code into an expression tree and then optimizes it. The python compiler parses python code into an expression tree and then optimizes it.
If you make some dsl that builds a tree of relational operators but allow the leaves to produce side-effects or non-termination then you still can’t optimize it. If you make some dsl that allows loops but constrains side-effects within their bodies, then you can optimize it.
There’s nothing magic about trees of expressions that allows optimizations. Language semantics are what matter. For the kinds of optimizations in this example, the semantics that are important are ones that allow the compiler to reason about whether loop operations can be reordered. That’s true whether you expose the loops directly or hide them within relational algebra or list comprehensions.
score 13 · canonical
I’m sorry I used the imprecise term “relational algebra” to refer to the semantic model of SQL. My point is that the expression tree of a SQL statement is not made of loops, it’s made of table expressions (with join operations), column references, aggregates, filters, CTEs, etc. To oversimplify again, it’s mostly about set operations, not loops.
Of course in the query planner it gets turned into something executable, which will sometimes involve loops, but that’s not the model of the language itself. Python expressions get turned into bytecode so they can be executed, but you don’t write Python as a way of expressing bytecode.
To be concrete, the semantic expression tree of
select users.id, (select sum(posts.likes) from posts where posts.user_id = users.id) from usersisn’t
R=[] for (u in users) { x=[]; for (p in posts) { if (p.user_id = u.id) x+=p.likes } R+=(u.id, sum(x)) } return Rit’s more like
users .join(posts .filter(user_id=users.id) .groupby() .project(sum(likes) as sum)) .project(users.id, posts.sum)(Which in 2024 would be a much more natural way to write it in the first place, which is why I mentioned LINQ.)
In my experience writing and helping others to write SQL, if you write it thinking that you’re writing loops, it’s not as effective as if you write it thinking about set operations, especially as the queries get more complex. Not to mention that the error messages will actually make sense! To me this is like writing Rust thinking about structs, traits, borrows, etc. rather than thinking about assembly (99% of the time).
I’m not a SQL expert (though I have dug into the PG query planner on occasion) so maybe I’ve been doing this wrong, but it does seem to work.
score 3 · canonical