6 ms·

> 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

> 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 ago
all 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 ago
  I 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
- ineedasername 6y ago
  All queries could technically be expressed as a cartesian product but that is not necessary and not what happens in practice. Both of the above might produce the same plan because they are both treated as joins. One is expressed as an explicit join, the other as an implicit join, but neither requires the query engine to produce a cartesian product on execution. If it did, queries I run in seconds would require more storage or RAM than probably exists in my entire workplace, and I'm not using anything that would usually be considered "big data".
  - slt2021 6y ago
    >>queries I run in seconds would require more storage or RAM than probably exists in my city my explanation to this: CPUs ave very fast. My CPU is 4Ghz so a single core can do a lot of computations in one second, and a SQL engine is smart enough to make cartesian computation (as part of a query plan) and discard the result if row does not meet predicate condition. in fact I agree that not entire cartesian is being computed, if you specify enough predicates. But the query still multiplies rows. In the author's article he is joining employees when customer_id columns in NULL so this is technically a cartesian, because NULL predicate is not very selective (=there are a lot of rows with value of NULL)
    - ineedasername 6y ago
      You are not using the term cartesian product correctly as applied to how database engines execute queries. Multiple people have detailed the problems with your ideas on how such things work. A fast processor cannot overcome the the need for multiple terabytes of RAM that would be required to process common queries if databases worked as you describe. Databases are significantly more likely to get bottlenecked by RAM than CPU, and your incorrect understanding of how databases work would require as much RAM as a large "big data" cluster to run queries on moderately sized data sets. Then even if it had that RAM, the bandwidth of the system's bus channels would be incapable of transporting it fast enough to return results in 500ms. Certainly not on my system with a few dozen other people working at the same time, and especially not when I have to query the live production system with a few thousand end users instead of the data warehouse. Databases do not work this way.

slt2021 6y ago

all 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 ago
I 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
ineedasername 6y ago
All queries could technically be expressed as a cartesian product but that is not necessary and not what happens in practice. Both of the above might produce the same plan because they are both treated as joins. One is expressed as an explicit join, the other as an implicit join, but neither requires the query engine to produce a cartesian product on execution. If it did, queries I run in seconds would require more storage or RAM than probably exists in my entire workplace, and I'm not using anything that would usually be considered "big data".
- slt2021 6y ago
  >>queries I run in seconds would require more storage or RAM than probably exists in my city my explanation to this: CPUs ave very fast. My CPU is 4Ghz so a single core can do a lot of computations in one second, and a SQL engine is smart enough to make cartesian computation (as part of a query plan) and discard the result if row does not meet predicate condition. in fact I agree that not entire cartesian is being computed, if you specify enough predicates. But the query still multiplies rows. In the author's article he is joining employees when customer_id columns in NULL so this is technically a cartesian, because NULL predicate is not very selective (=there are a lot of rows with value of NULL)
  - ineedasername 6y ago
    You are not using the term cartesian product correctly as applied to how database engines execute queries. Multiple people have detailed the problems with your ideas on how such things work. A fast processor cannot overcome the the need for multiple terabytes of RAM that would be required to process common queries if databases worked as you describe. Databases are significantly more likely to get bottlenecked by RAM than CPU, and your incorrect understanding of how databases work would require as much RAM as a large "big data" cluster to run queries on moderately sized data sets. Then even if it had that RAM, the bandwidth of the system's bus channels would be incapable of transporting it fast enough to return results in 500ms. Certainly not on my system with a few dozen other people working at the same time, and especially not when I have to query the live production system with a few thousand end users instead of the data warehouse. Databases do not work this way.