3 ms·
This is ABC of SQL: every SQL developer has to learn this lesson soon or later: Every additional JOIN you make creates a cartesian product of all previously joi
by slt2021 6y ago
This is ABC of SQL: every SQL developer has to learn this lesson soon or later: Every additional JOIN you make creates a cartesian product of all previously joined records and the number of rows grows exponentially => you join tables A to B to C to D -> SQL engine has to create AxBxCxD number rows, each letter representing number of rows in that table)
Of course specifying useful predicates that filter down dataset and having indexes on these columns helps avoid row explosion, but you can't have an index on each and every column, especially on OLTP database.
in example #2 the author joined 7 tables (multiply row count of 7 tables and this gives you an indea of how many rows SQL engine has to churn through) - big O complexity of query is (AxBxCxDxExFxG) of course it will be SLOW.
in example #4 he joins 4 tables and unions with 5 table join, so the big O complexity of query is AxBxCxD(1+E).
same as in programming, there is Big O complexity in your SQL queries, so it helps to know O() compelxity of queries that you write
TLDR: learn the SQL Big-O and stop compaining about the query planner, pls
- tehlike 6y agoSomething that helps with exploding cartesian problem is using json_agg for the joined tables. IT's available in postgres, it works great.
- meritt 6y agoYour understanding is flawed, these aren’t cross joins.
- jaredsohn 6y agoI've found denormalization to be helpful for such performance issues in that it reduces the number of joins. It can also be useful for debugging if you want to keep track of values from other tables at the time that data was processed within the primary table.
- slt2021 6y agodenormalization aka memoization aka "dynamic programming of SQL" :-) - all three provide speed-up because they compute value once and reuse it later
- mtone 6y agoExcept that your source of truth aka your raw data is now memoized, hardly a win. This is not a goal of memoization or dynamic programming at all. Perfect for a reporting database though.
- monoideism 6y agoA certain amount of denormalization can be helpful, but often there's a trade-off in terms of maintainability.
- rovr138 6y agoNot who you replied to. But yes, As an example, we keep our data normalized and add extra tables to do the operations we need. It’s expensive since we have to precompute, etc. But then on lookups it’s quicker. Like everything, it depends on what you want to optimize for.
- jaredsohn 6y agoYep, in my case we wanted to make user-facing queries fast (i.e. a reports page). The extra complexity (not much; we just have to remember when to update certain values in other tables when they change) is definitely worth it since load time dropped from 30 seconds sometimes to almost instant. Denormalizing everything is definitely a pain; keeping data in sync in mongodb (which lacks traditional joins) on a previous project was not fun; now using postgresql.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- epr 6y agodenormalization should only be seen as a last resort
- ericHosick 6y ago> Every additional JOIN you make creates a cartesian product of all previously joined records and the number of rows grows exponentially => you join tables A to B to C to D -> SQL engine has to create AxBxCxD number rows, each letter representing number of rows in that table) I think a cartesian product would be: SELECT * FROM A, B; Given sizes a, b the resulting number of rows would be a X b or O(N^2). With a join SELECT * FROM A INNER JOIN B ON A.id = B.id then the result rows would be MAX(a,b) or O(N). A JOIN is a predicate that filters down the dataset.
- slt2021 6y agoall queries with JOINs can be rewritten as cartesians: select * from a join B on col1=col2 will be rewritten by query optimizer into: select * from A, B /* this is cartesian that slows down your query */ WHERE a.col1=B.col2 in fact both queries produce the same execution plan if you check yourself
- deleted 6y ago[deleted]
- gfody 6y agoI think the point is rather that a join with a condition (which is the norm) is almost never actually executed as a cartesian product. take for example from tfa select * from customer_order_items the grain is one row per customer order item, and the next two joins don't change that select * from customer_order_items join customer_orders on order_id the grain is still one row per customer order item select * from customer_order_items join customer_orders on order_id join customers on customer_id the grain is still one row per customer order item ..etc.. of course later on they screw it up and take the cartesian product of customer_order_items by employ_markouts, but it's just 2 big factors not 7 - their query did finish after a few seconds. usually mistakes involving cartesian products with 7 factors just run for hours and eventually throw out of memory.
- whimsicalism 6y ago? not how it works behind the scenes at all
- gfody 6y ago> you join tables A to B to C to D -> SQL engine has to create AxBxCxD number rows this isn't really true. not every join is a cross join, and not every join even changes the grain of the result set. it is important to pay attention when your joins do change the grain of the result set, especially when they grow it by some factor - then it's more like a product as you say.
- slt2021 6y agoall queries with JOINs can be rewritten as cartesians: select * from a join B on col1=col2 will be rewritten by query optimizer into: select * from A, B /* this is cartesian that slows down your query */ WHERE a.col1=B.col2 in fact both queries produce the same execution plan if you check yourself
- gfody 6y agothe query is not the only input into the plan generator, the other inputs are the schema (with constraints and indexes) and their statistics - so you can't really say "check the plan for yourself" without all the inputs. and the only time the plan for "select * from A, B" is going to be the same as "select * from A, B where A.col1=B.col2" is when col1 and col2 are both neither primary keys nor foreign keys and that would be a weird condition under which to run such a query.
- slt2021 6y agopls reread my post, I wrote that query select * from A join B on col1=col2 is the the same plan as for select * from a, b where col1=col2 this is true regardless of schema and statistics, it is simply how query planner works under the hood and you can check it yourself on any database
- iaabtpbtpnn 6y agoThose are both inner joins, just a different syntax for writing them.
- ineedasername 6y agoI don't understand what you mean by saying each join creates a cartesian product. Join criteria avoid this. If I left outer join 7 rows on table A and 5 on table B and join on a unique key then I still only get 7 rows, not the cartesian product of 7x5 rows. I query across a dozen or more tables on a regular basis with aggregates, window functions, with statements, having clauses and so on. Performance is rarely a problem.