lobsters score: 46 · tags: plt
I don’t think it’s because it is declarative. It certainly helps.
But it’s the semantics of relational algebra that are amenable to optimization. Specifically, the nested JOIN is not a nested loop. It’s not even a loop. It’s a query that can be analyzed as to its dependencies on other queries, plus database statistics,
score 1 · canonical
If I’m being picky, the subquery in the example is not a nested join (unless you think of the subquery as expressing an infinite relation as I do in imp, but that’s definitely not the standard semantics given to sql).
the semantics of relational algebra that are amenable to optimization a query that can be analyzed as to its dependencies on other queries
But if we ask specifically what in the semantics of relational algebra makes it amenable to optimization? Or what it makes it tractable to analyze the dependencies of a subquery, when analyzing the dependencies of a loop body in python is so intractable? It’s going to look something like that list of requirements.
score 1 · canonical
It’s not just that SQL is declarative, it’s that:
- this sort of query is very common workload
- SQL databases have statistics which inform the planner
- I can’t perform the optimisation myself since SQL does not allow for it
Would such an optimisation be useful for a general purpose language? Seems doubtful, it would basically be an edge case which can be resolved by hand. Not only that, but it could cause undesirable side-effects e.g. a hash joinrequires the allocation of a hash map, is that something I want?
TFA is also missing requirements e.g. performing a hash join requires that data be hashable in the first place, that is more or less intrinsic to most SQL databases / data, but very much not so to for general purpose programming languages.
score 3 · canonical
Would such an optimisation be useful for a general purpose language?
C# LINQ is designed to allow it, though the optimization is done by the LINQ provider not the compiler. And LINQ by and large boils down to a declarative sublanguage somewhere between list comprehensions and SQL.
I imagine that this kind of optimization would be more generally useful in an array language or languages that make heavy use of dataframes.
score 4 · canonical
It’s not just that SQL is declarative
It’s not even because SQL is declarative :p
this sort of query is very common workload I can’t perform the optimisation myself since SQL does not allow for it
You’re talking about what makes query planning desirable or economical. But none of this has any bearing on what makes the optimizations possible .
SQL databases have statistics which inform the planner
Materialize does not have access to statistics but can still perform the optimization in the example. Whereas the same optimization in python would be intractable even with access to statistics.
TFA is also missing requirements e.g. performing a hash join requires that data be hashable in the first place,
I think that’s covered by:
Some way to reason about the properties of functions (eg that a == b implies hash(a) == hash(b)…
Eg this is very difficult to reason about at compile-time in python, but in rust the compiler could just check for
impl Hash for T.
score 5 · canonical
But none of this has any bearing on what makes the optimizations possible .
But it does, it is the primary reason.
Or the secondary reason if the first is ROI: not only can you implement a hash join yourself in the average langage, such a join would only be useful in specific data shapes following the relational model, in most cases your data would be nested or the link would already be expressed through a hash map.
I think that’s covered by:
It’s not, what you quote is an operational implication, it does not account for hash(a) not being a thing at all.
Eg this is very difficult to reason about at compile-time in python, but in rust the compiler could just check for impl Hash for T.
Not according to TFA, since you can have a nonsensical Hash operation all the same.
score 1 · canonical
But none of this has any bearing on what makes the optimizations possible .
But it does, it is the primary reason.
What if we distinguish “what lets us know the transformation preserves the semantics of the query” (aka makes the transformation possible) from “what lets us know that the transformation is profitable” (aka makes us expect the tranformation is an optimization, not a pessimization). There are plenty of transformations for the first that don’t depend on statistics at all.
I take it this is what Jamie meant by
You’re talking about what makes query planning desirable or economical. But none of this has any bearing on what makes the optimizations possible .
but perhaps the extra elaboration is helpful.
score 2 · canonical
This goes wrong in the very first paragraph. That query does not, “read literally”, say to do two nested loops. SQL is a clunky way of writing an expression in relational algebra, not a clunky way of writing a series of operations. That’s what “declarative” is really trying to say. 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.
Using LINQ in C# as the example would have taken this post in a completely different direction.
score 7 · canonical
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, (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 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.
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
Am I the only one that often thinks that I don’t want SQL optimizing anything automatically? I’d rather describe in steps:
- select these rows using this index/key,
- narrow down to these columns
- do these transformations, etc.
in that exact order instead discovering sometimes that query planner does something stupid and having to patch it up? After all - I have a prefect understanding of the data model, while the query planner has to do bunch of heuristics that sometimes fail in unexpected ways.
I do realize that not everyone is like me, that auto-optimization is convenient. But just like static typing can be seen as extra effort for tighter control, so having tight control over a query can be beneficial. And I guess a query language/method like this could e.g. have a way to turn on auto-optimizer etc.
score 3 · canonical
I write a lot of SQL queries on a daily basis. I might like better abilities to control the optimizer sometimes, but I would not want the default to require that I specify data access patterns.
There are also plenty of queries where I think I’d have a hard time getting the patterns right, because I don’t know the data patterns–that’s why I’m writing a query. “How many jobs are in status X but were created more than 10 days ago and meet some other conditions that are not cheap to compute”. I’m writing this because I hope the number is low, but part of what I’m guarding against is the failure mode where status X has suddenly become very common.
score 6 · canonical
I strongly agree with this.
There should be a lower level functional language describing relations (tables & indices) and operations on them.
I mean, every database has this inside (the query plan - explain), I just want a syntax defined and an API to run queries with it. (For the write path, it might be a bit more complex, but the read operations are straightforward).
Of course SQL is fine as a higher level language. It’s even possible that during development you might record the optimised query plan along with the SQL, and have checks that they match so that you are notified (and can accept/reject) any change (due to existence of an extra index, for example).
score 1 · canonical
Query planner optimizations aren’t just convenient, but they also allow you to write very reusable code around your database. Either in the database or in your own code, it allows you to assemble subqueries that mean something and then you can consume them in a multitude of ways.
Say you have 4 ways to assemble expressions like this and then 4 ways to extract results from them. In your approach, you’d have to write 16 separate programs to operate over your tables and indexes explicitly, and in all likelihood there would be very little reuse between these programs, but with the query planner you can nicely decompose your domain with subqueries, you can see the contents of those subqueries by running them against your DB and then reuse them to let the query planner write non-trivial programs for you. It’s all correct by construction modulo performance.
With your 16 programs that are conceptually related but implementation-wise unrelated, you’d also have to write a lot of tests to make sure they’re doing something coherent among themselves.
score 6 · canonical
yeah, this was my experience working with large scale systems at dropbox – whenever we permitted direct access to MySQL, it was effectively forcing a very specific index traversal. and, despite our best efforts, the query planner would still decide to do a full table scan or spill to disk at the worst possible times.
this was a big input to our design for convex (disclosure: cofounder), where the query API is pretty much just accessing index ranges (https://docs.convex.dev/database/indexes/). performance is extremely predictable, and with the right ergonomics, it can feel pretty good!
score 1 · canonical
What happens when the properties of the data change? Does performance change or does this allow some part of the stack to optimize the query execution? Or does it not need that.
score 1 · canonical
we only expose
O(log n)primitives for database indexes (point lookups and index scans), so performance is pretty reasonable even if the dataset changes in scale or distribution.we’re currently working on profiling tools for developers who want to optimize further, but we’ve found that most developers don’t have to worry about it.
score 1 · canonical
“declarative” is sort of an unfortunate term to emerge in computer science. The point is to contrast the language in question with “imperative” languages but in reality all programming languages are declarative. Take for example code in the IO monad is Haskell. Is that declarative or imperative? In one sense it’s declarative since it’s a purely functional / data-oriented construct, in another sense it is imperative because it describes how data flows across a sequence of IO operations.
Going back to the OP, the fact that SQL is declarative is not what enables a wide range of optimizations. It’s that SQL specifies fewer semantics in terms of what its constructs mean computationally. Haskell is another language that is underspecified in terms of how computations happen and also is amenable to a wide array of optimizations. It isn’t necessarily that it’s declarative.
score 1 · canonical
It’s a good point that “we haven’t conventionally done this and it would be quite tricky to” is often casually treated as “this can’t be done.” I think if you take that all the way, the idea that you can’t do high-level transforms on Python is also a simplification. I’m also not opposed to (either) simplification–some kind of limited scope for an explanation can make practical sense. But it’s also fun to consider here some of the ways implementers approach ‘walls’ that get in the way of useful optimizations.
One comparison is with JavaScript: for a long time there was an assumption that a lot of optimizations were just inapplicable given the lack of a type system and everything, until eventually we found a way to do them. Often it meant using data collected during execution to guess at what the efficient-to-execute program inside the dynamic JavaScript was, and coming up with checks so you could ‘deoptimize’ in case the assumptions turn out false.
Some interesting stabs towards clever execution of Python include numeric libraries that let you write a subset of Python and get it JITed via something looking at the AST, and the many numeric libraries that layer on typing and special collection types to do certain tasks faster. Most directly like the high-level transforms in the post are query builder interfaces where you apply operations like set intersect, subtract, filter, and so on in a way that feels native (sometimes using operators like
&and|) while you’re really building up a query representation that is optimized and executed lazily.Those ideas in Python, and some related ideas like typed arrays and asm.js in JavaScript, end up kind putting a mini-language that’s more transformable inside the larger, more familiar, more expressive, easier-to-write language that’s less transform-friendly. It’s not the transforms of arbitrary code that the post was about, but these things do seem to provide folks interesting wins!
Relatedly, I think it’s sort of interesting that making efficient algorithms idiomatic seems to reshape the code people write, e.g.
setis a normal Python type that’s not doing any special magic, but has probably prevented a lot of quadratic nested loops. “Huge list” types that directly support a bunch of efficient algorithms on them (which might internally involve sorting or hashing or external-memory variants of them) aren’t unthinkable either.A totally different comparison point is compiling shaders: the code looks imperative and serial, and the way it’s executed looks much different from what you might imagine looking at the source. (And the compilers are, uh, really something, I hear.) Someone called queries “database shaders” once (someone replied “row shaders”) and that sticks with me.
Again, I’m not saying the original post is wrong. It’s true the language properties it mentions would make high-level transformation more feasible, and they were trying to talk about optimizing Python as it’s written now, not things that change how it’s written. At the same time I think the pragmatic tricks that folks use to try to chip away at the barriers to optimization now are interesting to look at next to the ideal of static, there-by-default compiler optimizations.
score 3 · canonical
One comparison is with JavaScript: for a long time there was an assumption that a lot of optimizations were just inapplicable given the lack of a type system and everything, until eventually we found a way to do them.
Yes but this only goes so far … I wrote a little rant here about how AOT compilation (Rust, C++, Go) is better for a big class of problems, basically anything in involving languages – interpreters, type checkers, formatters, linters
https://news.ycombinator.com/item?id=35045520
To be controversial, JITs have “failed”, otherwise we wouldn’t be rewriting a lot of code. Emery Berger frames Perl / Python / JS / PHP as the “irrational exuberance” languages
The canonical example being that the TypeScript compiler would be a lot faster if it wasn’t running on a JavaScript runtime. All that type info is thrown away, and doesn’t contribute to speed.
Many people are rewriting these tools in AOT languages (esbuild in Go, etc.) and that choice makes a lot of sense. Python has a lot of really slow tools like Black and or yapf, compared with clang-format.
For Oils we wrote a Python-to-C++ translator that uses MyPy static types. It was more work to make the source program 100% statically typed, vs. trying to get a JIT to do it, but it’s way faster, and uses way less memory [1]. We basically have garbage-collected C++ semantics and not Python semantics (but Python syntax). So it’s all AOT, and no JIT at all.
Brief Descriptions of a Python to C++ Translator
I still prefer an interpreter-like development experience, and I like dynamic languages for metaprogramming. But if the concern is speed, then AOT compilation with static types is just better IMO. (For numeric problems, the pattern where you use Python to generate an IR and then compile/parallelize/GPU it is still AOT, so it’s true that you have to look more carefully, and can’t just go by the language)
[1] e.g. https://www.oilshell.org/release/0.20.0/benchmarks.wwz/mycpp-examples/
score 3 · canonical
To be fair to JIT folks, in their niche JITs seem to help. But AOTs and AOT-friendly languages obviously are not going anywhere and mycpp looks fascinating.
Not saying The Way is to sneak optimizations into languages that aren’t friendly to them, really just that the absolute ‘can’t X without Y’ can be tricky when sometimes life, uh, finds a way.
score 2 · canonical
For some more color, I get a strong impression that the v8 codebase is monstrously complex, and kind of “topped out” several years ago.
That is, trying to make it faster now is like squeezing blood out of a stone. It seems impressive but I think under the hood it’s strained - https://v8.dev/blog
v8 is at least 2 million lines of code now, it’s probably almost the size of GCC or Clang.
I’ve been watching videos on WebAssembly for the past few years, and two of the co-creators Andreas Rossberg and Ben Titzer were also tech leads of v8. (WASM is basically JavaScript JITs in the browser given an alternative front end that’s not JS. My rough version of the history at the end of this comment - https://lobste.rs/s/djxada/missing_point_webassembly#c_dveoie )
It’s honestly a little surprising to me how much they throw shade at v8 :-P It sounds like they regret the state of the codebase, and it was not fun to work in.
On the other hand, mycpp is like a 5000 line Python program that prints C++. It’s dirt simple and naive (since I don’t really know how to write compilers), but it results in very fast code. As long as we can correctly print C++ types, then the C++ compiler does all the work.
So naively that’s 2M lines vs. 5000 lines, or a 400x code size difference. Honestly that sounds roughly right – v8 is more the product of 400 engineers, while mycpp is like 1.
But mycpp is much faster, just because it does straightforward AOT.
The tradeoff of course is that it took us quite awhile to make the Oils statically typed, so this technique is possible. Definitely longer than I thought, for a relatively small codebase. But there was really no other option, since it’s not like we will write a JIT … that is a crazy amount of engineering
score 2 · canonical