30 ms·

The curious case of the aggregation query

76 points by eatonphil 3y ago

crazygringo 3y ago
> Now the mysterious query: SELECT (SELECT sum(a) FROM xx LIMIT 1) FROM aa To be clear, that's just an absolutely pathological query, since column "a" doesn't exist in table "xx" -- it only exists in table "aa". You can use values from outer queries inside of inner queries, which are called "correlated subqueries". Which is not recommended unless you're already a real SQL expert, because they're so confusing (and their performance is also pretty absymal). But this isn't even that -- this is an aggregate function across an outer variable. I consider myself a strong SQL expert, but looking at this query, it just feels nonsensical. Not only could I not tell you what it would produce -- I couldn't even guess at what its author intended it to mean in the first place. > Later in the article we will see that SQL implementations don’t even agree about the correct result. I'm not surprised at all. I'm actually more surprised they produce results at all, rather than just errors about it being an invalid query.
- MarkusWinand 3y ago
  No question, such a query should not be written. That's probably the reason why this odd behavior, which is even different in various DBMSes, is not causing everyday problems.
  - marcosdumay 3y ago
    The reason the behavior doesn't cause problems is because everybody treats automatic aggregation as a voodoo where they know one recipe that works and anything different is domain of the Devil. And, IMO, that's a very sane and reasonable way to treat it. The entire idea of automatic aggregation is flawed, and those queries should just have a `group by ()` explicit at the right place.
    - foldU 3y ago
      I agree, I think the original sin here is the fact that whether a `SELECT` is an aggregation is determined by the contents of the scalar expressions at all. I think most of this weirdness comes directly out of wanting to be able to write both `SELECT sum(x) FROM xx` and `SELECT x FROM xx` and have them work. Not that I have a better solution offhand, in SQL grouping by a constant value is not actually the same as not writing `GROUP BY` at all since the behaviour on empty tables is different.
      - marcosdumay 3y ago
        Not writing `group by` is the same as writing `group by ()`. And yeah, the difference between that and a value is one of those really surprising things on SQL that actually make sense and should be this way. Unfortunately, there are many of those.
        foldU 3y ago
        Ah my apologies, I wasn't familiar with that syntax.
        marcosdumay 3y ago
        No need to apologize. My post didn't make that clear at all.
      - derefr 3y ago
        What's an aggregation per se? A SQL query is best thought of an arbitrary generator function. You can, using functions like UNNEST, end up emitting multiple row-tuples for each processed input row-tuple. An aggregation is just a generator function that happens to reduce over all the input rows and then emit one row-tuple when there's no more input. Query-planning engines do not special-case this. It's just a generator node like any other generator node. Consider: using window functions, you can do partial aggregations over subsets of the input — without even necessarily partitioning the input (i.e. you can compute "running totals" and other wacky state-machine-like outputs.)
- indigo945 3y ago
  I don't find it that confusing, to be honest. When the article presented the "mysterious" query, I guessed the result correctly. A correlated subquery will always execute the entire expression for each row of the outer query. Since the value of `sum(a)` is known in the context of the outer query, it doesn't really matter where you select it from in the inner query. Therefore, the following queries are all identical: SELECT sum(a) FROM aa; SELECT (SELECT sum(a) FROM xx LIMIT 1) FROM aa; SELECT (SELECT sum(a) FROM generate_series(1, 1)) FROM aa; To maybe explain why this behaviour makes sense, stop thinking about aggregate queries for a second, and just consider normal expressions. What would you expect the result of the following query to be? SELECT (SELECT a + x FROM xx LIMIT 1) FROM aa; This is obviously a bad query because it uses `LIMIT` without `ORDER BY`, but let's just put that aside. This query should make some sense to pretty much any SQL developer: you take each `a` value from `aa`, and then add the value from the "first" (whatever that means) `x` value from `xx` to it. (In my test on Postgres, this returns [11, 12, 13], but there's obviously no guarantee because we neglected to sort `xx`.) Now, since that was easy, consider this simplification of that query: SELECT (SELECT a FROM xx LIMIT 1) FROM aa; I think that if the previous query made sense, this one should also make sense, as the expression simple has one less term. The result is obviously [1, 2, 3]. So, what should the aggregate return: SELECT (SELECT sum(a) FROM xx LIMIT 1) FROM aa; The only real difference is that the outer query is now aggregated, and therefore it is implicitly in one big grouping, and therefore returns only one row. So the correlated subquery gets run once, for that one row - what's the value for `sum(a)` in that row, the one row that the outer query returns? Well, 6. Duh.
  - foldU 3y ago
    (I'm the author of the original post [1]) And while I think the rules, in the end, make sense, I think it's not quite as clear cut as you describe, consider: SELECT (SELECT sum(1) FROM xx LIMIT 1) FROM aa; which returns 3 3 3 Personally, I think having the inner aggregation always attach to the nearest `SELECT` would have been an equally valid way of defining how this works, but it just so happens it is not defined that way. [1]: https://buttondown.email/jaffray/archive/sql-scoping-is-surprisingly-subtle-and-semantic/ https://buttondown.email/jaffray/archive/sql-scoping-is-surp...
- nimish 3y ago
  Correlated subqueries are absolutely fine and are equivalent to (possibly lateral) joins. They aren't as easy to identify and optimize as such, so I wouldn't necessarily recommend them, but sometimes they make sense. Not an issue with a good query planner and if they clarify a query.
  - da_chicken 3y ago
    Yeah, correlated subqueries are fine. Unless you're on MySQL, which (historically, at least) was infamously terrible at executing them. The reason this query works is because correlated subqueries... need something to correlate with! Usually the column from the outside query is only referenced in the WHERE clause, but there isn't really a reason you can't reference it in the inside query's SELECT clause. After all, what if you needed it for a CASE expression there? There are certainly better ways to write what this query is accomplishing -- at the very least there are ways to write it that make it much more clear what your intentions are -- but just because it's weird doesn't mean it's invalid. The developers know they cannot anticipate all possible operations that might be desired, and there are already countless ways to write queries incorrectly.
  - HDThoreaun 3y ago
    As an employee at a database company working on the plan optimizer I would like to ask you not to use correlated subqueries for my own sanity. Close to 100% of the mind blowing bugs are correlated subqueries. Kidding of course but holy shit my life would be so much easier without them.
    - nimish 3y ago
      I am curious as to why. They should be represented like joins, right?
      - HDThoreaun 3y ago
        They’re slow as fuck and most of them can be rewritten to not be correlated, so we attempt to heavily rewrite them. There’s basically an entire subfield of cs research that focuses on strategies for rewriting CSQs and the papers have gotten progressively more and more complicated making them very difficult to reproduce without bugs. I’ve spent easily weeks just reading these papers let alone implementing them.
crdrost 3y ago
For a while now, whenever I have taught SQL to people (which was only I think 3 times over like 8 years) I ask them to imagine that the word SELECT can be replaced with AGGREGATE which unlocks these magical words GROUP BY and SUM and so forth, and they understand me perfectly well: and then I drop on them that I was lying and the magic word is still SELECT but you have to know which kind of SELECT it is from context clues and they are like “What???? Whyyyyyy.”
- derefr 3y ago
  To be honest, teaching SQL "syntax in" seems like a really backwards way of getting an understanding of what SQL is doing. I run the tech side of a company almost entirely built on complex SQL queries. If I were to take a fresh college student and "teach them SQL"... well, I wouldn't teach them SQL. I'd teach them relational algebra: projection, selection, join, etc. as mathematical operators over bags of tuples. I'd make sure that they could show me what the bag-of-tuples looks like at each step, as each operator is applied. I'd get them to write code in some programming language with first-class Set and Tuple datatypes, that does these operations as in-memory functional transforms over bag-of-tuples -typed variables. And then, once they have that solid understanding, I'd show them, in order: 1. that there exist these systems called RDBMSes that maintain durable, mutable bags-of-tuples they call tables (which is weird when you think about it; coming from a math world, a relation should be an immutable mathematical object, a value-object defined by its members. But RDBMS tables aren't relations, not exactly — and this is where you can go into detail about SQL `NULL`, "nullable columns", and how in an RDBMS, the absence of an asserted row-tuple in a table doesn't necessarily mean the implicit assertion of its logical negation as a logical predicate; it rather means "haven't been fed the truth-value of that relation yet." RDBMS query engines aren't relational-algebra computers; they're relational-algebra provers — and NULL is their "not proven"!); 2. that these systems accept a COBOL-like declarative syntax for either • referencing their tables (`TABLE foo`); • expressing relational algebra upon their tables (`SELECT ... FROM foo ...`); • defining arbitrary literal bags-of-tuples (e.g. `VALUES (1, 2)` — bet you didn't know that was toplevel-grammatical in SQL!); • expressing relational algebra upon arbitrary literal bags-of-tuples (e.g. `SELECT a FROM (VALUES (1, 2)) AS x (a, b)`); • or any combinations of the above — using UNION, INTERSECT, or introducing any of the above as a common table expression and then referencing it by name. 3. that these systems also accept COBOL-like imperative syntax — one which really has not-much-at-all to do with relational algebra — for modifying the durable, mutable bag-of-tuples asserted by a given table (INSERT, UPDATE, DELETE, TRUNCATE); 4. and that, completely unnecessarily, these systems also have a COBOL-like imperative syntax for modifying the definitions of the tables themselves (unnecessary because the data-definition schema could have just been, itself, a set of tables that you modify through DML statements. INFORMATION_SCHEMA exists, but it's read-only in every RDBMS I've ever seen. Wacky, isn't it?)
random3 3y ago
So approximately a SQL standard (aggregation "tree-climb") combined with a non-standard (LIMIT) which prevents an error yield an unexpected behavior.
gigatexal 3y ago
Please don’t use this as an interview question. It is absolutely diabolical.

76 points by eatonphil 3y ago

> Now the mysterious query: SELECT (SELECT sum(a) FROM xx LIMIT 1) FROM aa To be clear, that's just an absolutely pathological query, since column "a" doesn't exist in table "xx" -- it only exists in table "aa". You can use values from outer queries inside of inner queries, which are called "correlated subqueries". Which is not recommended unless you're already a real SQL expert, because they're so confusing (and their performance is also pretty absymal). But this isn't even that -- this is an aggregate function across an outer variable. I consider myself a strong SQL expert, but looking at this query, it just feels nonsensical. Not only could I not tell you what it would produce -- I couldn't even guess at what its author intended it to mean in the first place. > Later in the article we will see that SQL implementations don’t even agree about the correct result. I'm not surprised at all. I'm actually more surprised they produce results at all, rather than just errors about it being an invalid query.

MarkusWinand 3y ago
No question, such a query should not be written. That's probably the reason why this odd behavior, which is even different in various DBMSes, is not causing everyday problems.
- marcosdumay 3y ago
  The reason the behavior doesn't cause problems is because everybody treats automatic aggregation as a voodoo where they know one recipe that works and anything different is domain of the Devil. And, IMO, that's a very sane and reasonable way to treat it. The entire idea of automatic aggregation is flawed, and those queries should just have a `group by ()` explicit at the right place.
  - foldU 3y ago
    I agree, I think the original sin here is the fact that whether a `SELECT` is an aggregation is determined by the contents of the scalar expressions at all. I think most of this weirdness comes directly out of wanting to be able to write both `SELECT sum(x) FROM xx` and `SELECT x FROM xx` and have them work. Not that I have a better solution offhand, in SQL grouping by a constant value is not actually the same as not writing `GROUP BY` at all since the behaviour on empty tables is different.
    - marcosdumay 3y ago
      Not writing `group by` is the same as writing `group by ()`. And yeah, the difference between that and a value is one of those really surprising things on SQL that actually make sense and should be this way. Unfortunately, there are many of those.
      - foldU 3y ago
        Ah my apologies, I wasn't familiar with that syntax.
        marcosdumay 3y ago
        No need to apologize. My post didn't make that clear at all.
    - derefr 3y ago
      What's an aggregation per se? A SQL query is best thought of an arbitrary generator function. You can, using functions like UNNEST, end up emitting multiple row-tuples for each processed input row-tuple. An aggregation is just a generator function that happens to reduce over all the input rows and then emit one row-tuple when there's no more input. Query-planning engines do not special-case this. It's just a generator node like any other generator node. Consider: using window functions, you can do partial aggregations over subsets of the input — without even necessarily partitioning the input (i.e. you can compute "running totals" and other wacky state-machine-like outputs.)
indigo945 3y ago
I don't find it that confusing, to be honest. When the article presented the "mysterious" query, I guessed the result correctly. A correlated subquery will always execute the entire expression for each row of the outer query. Since the value of `sum(a)` is known in the context of the outer query, it doesn't really matter where you select it from in the inner query. Therefore, the following queries are all identical: SELECT sum(a) FROM aa; SELECT (SELECT sum(a) FROM xx LIMIT 1) FROM aa; SELECT (SELECT sum(a) FROM generate_series(1, 1)) FROM aa; To maybe explain why this behaviour makes sense, stop thinking about aggregate queries for a second, and just consider normal expressions. What would you expect the result of the following query to be? SELECT (SELECT a + x FROM xx LIMIT 1) FROM aa; This is obviously a bad query because it uses `LIMIT` without `ORDER BY`, but let's just put that aside. This query should make some sense to pretty much any SQL developer: you take each `a` value from `aa`, and then add the value from the "first" (whatever that means) `x` value from `xx` to it. (In my test on Postgres, this returns [11, 12, 13], but there's obviously no guarantee because we neglected to sort `xx`.) Now, since that was easy, consider this simplification of that query: SELECT (SELECT a FROM xx LIMIT 1) FROM aa; I think that if the previous query made sense, this one should also make sense, as the expression simple has one less term. The result is obviously [1, 2, 3]. So, what should the aggregate return: SELECT (SELECT sum(a) FROM xx LIMIT 1) FROM aa; The only real difference is that the outer query is now aggregated, and therefore it is implicitly in one big grouping, and therefore returns only one row. So the correlated subquery gets run once, for that one row - what's the value for `sum(a)` in that row, the one row that the outer query returns? Well, 6. Duh.
- foldU 3y ago
  (I'm the author of the original post [1]) And while I think the rules, in the end, make sense, I think it's not quite as clear cut as you describe, consider: SELECT (SELECT sum(1) FROM xx LIMIT 1) FROM aa; which returns 3 3 3 Personally, I think having the inner aggregation always attach to the nearest `SELECT` would have been an equally valid way of defining how this works, but it just so happens it is not defined that way. [1]: https://buttondown.email/jaffray/archive/sql-scoping-is-surprisingly-subtle-and-semantic/ https://buttondown.email/jaffray/archive/sql-scoping-is-surp...
nimish 3y ago
Correlated subqueries are absolutely fine and are equivalent to (possibly lateral) joins. They aren't as easy to identify and optimize as such, so I wouldn't necessarily recommend them, but sometimes they make sense. Not an issue with a good query planner and if they clarify a query.
- da_chicken 3y ago
  Yeah, correlated subqueries are fine. Unless you're on MySQL, which (historically, at least) was infamously terrible at executing them. The reason this query works is because correlated subqueries... need something to correlate with! Usually the column from the outside query is only referenced in the WHERE clause, but there isn't really a reason you can't reference it in the inside query's SELECT clause. After all, what if you needed it for a CASE expression there? There are certainly better ways to write what this query is accomplishing -- at the very least there are ways to write it that make it much more clear what your intentions are -- but just because it's weird doesn't mean it's invalid. The developers know they cannot anticipate all possible operations that might be desired, and there are already countless ways to write queries incorrectly.
- HDThoreaun 3y ago
  As an employee at a database company working on the plan optimizer I would like to ask you not to use correlated subqueries for my own sanity. Close to 100% of the mind blowing bugs are correlated subqueries. Kidding of course but holy shit my life would be so much easier without them.
  - nimish 3y ago
    I am curious as to why. They should be represented like joins, right?
    - HDThoreaun 3y ago
      They’re slow as fuck and most of them can be rewritten to not be correlated, so we attempt to heavily rewrite them. There’s basically an entire subfield of cs research that focuses on strategies for rewriting CSQs and the papers have gotten progressively more and more complicated making them very difficult to reproduce without bugs. I’ve spent easily weeks just reading these papers let alone implementing them.

crdrost 3y ago

For a while now, whenever I have taught SQL to people (which was only I think 3 times over like 8 years) I ask them to imagine that the word SELECT can be replaced with AGGREGATE which unlocks these magical words GROUP BY and SUM and so forth, and they understand me perfectly well: and then I drop on them that I was lying and the magic word is still SELECT but you have to know which kind of SELECT it is from context clues and they are like “What???? Whyyyyyy.”

derefr 3y ago
To be honest, teaching SQL "syntax in" seems like a really backwards way of getting an understanding of what SQL is doing. I run the tech side of a company almost entirely built on complex SQL queries. If I were to take a fresh college student and "teach them SQL"... well, I wouldn't teach them SQL. I'd teach them relational algebra: projection, selection, join, etc. as mathematical operators over bags of tuples. I'd make sure that they could show me what the bag-of-tuples looks like at each step, as each operator is applied. I'd get them to write code in some programming language with first-class Set and Tuple datatypes, that does these operations as in-memory functional transforms over bag-of-tuples -typed variables. And then, once they have that solid understanding, I'd show them, in order: 1. that there exist these systems called RDBMSes that maintain durable, mutable bags-of-tuples they call tables (which is weird when you think about it; coming from a math world, a relation should be an immutable mathematical object, a value-object defined by its members. But RDBMS tables aren't relations, not exactly — and this is where you can go into detail about SQL `NULL`, "nullable columns", and how in an RDBMS, the absence of an asserted row-tuple in a table doesn't necessarily mean the implicit assertion of its logical negation as a logical predicate; it rather means "haven't been fed the truth-value of that relation yet." RDBMS query engines aren't relational-algebra computers; they're relational-algebra provers — and NULL is their "not proven"!); 2. that these systems accept a COBOL-like declarative syntax for either • referencing their tables (`TABLE foo`); • expressing relational algebra upon their tables (`SELECT ... FROM foo ...`); • defining arbitrary literal bags-of-tuples (e.g. `VALUES (1, 2)` — bet you didn't know that was toplevel-grammatical in SQL!); • expressing relational algebra upon arbitrary literal bags-of-tuples (e.g. `SELECT a FROM (VALUES (1, 2)) AS x (a, b)`); • or any combinations of the above — using UNION, INTERSECT, or introducing any of the above as a common table expression and then referencing it by name. 3. that these systems also accept COBOL-like imperative syntax — one which really has not-much-at-all to do with relational algebra — for modifying the durable, mutable bag-of-tuples asserted by a given table (INSERT, UPDATE, DELETE, TRUNCATE); 4. and that, completely unnecessarily, these systems also have a COBOL-like imperative syntax for modifying the definitions of the tables themselves (unnecessary because the data-definition schema could have just been, itself, a set of tables that you modify through DML statements. INFORMATION_SCHEMA exists, but it's read-only in every RDBMS I've ever seen. Wacky, isn't it?)

random3 3y ago

So approximately a SQL standard (aggregation "tree-climb") combined with a non-standard (LIMIT) which prevents an error yield an unexpected behavior.

gigatexal 3y ago

Please don’t use this as an interview question. It is absolutely diabolical.