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.
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
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.
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)
if you study engine internals, especially MergeJoin, HashJoin, NestedLoopJoin - they all do comoute cartesian while simultaneously applying predicates. Some operations are faster because of sorting and hashing, but they still do cartesian.
Last, you have offered no significant support for your claims, and as the initiator of the discussion making the claim of cartesian joins, the burden of proof is on you to provide evidence for your claims.
In any case, your persistence in digging your hole deeper and deeper on this issue is embarrassing, and I won't be cruel enough to enable that further. Feel free to reply, but I am done, with a final recommendation that you continue your learning and not stop at the point of your current understanding. You at least seem earnest in your interests in this topic, so you should pursue it further.
it's called merge join because it employs the merge algorithm (linear time constant space)[1] - this can only be used when the inputs are sorted. likewise the hash join entails building a hash table and using it (linear time linear space)[2] but the inputs don't have to be sorted. the point of these is to avoid the O(N*M) nested loop
(Note when I say linear performance, I mean the join predicate is executed a linear amount of times, but the initial sort/hash operation was probably more like O(n log n))
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.
in fact both queries produce the same execution plan if you check yourself
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
> This latter equivalence does not hold exactly when more than two tables appear, because JOIN binds more tightly than comma. For example FROM T1 CROSS JOIN T2 INNER JOIN T3 ON condition is not the same as FROM T1, T2 INNER JOIN T3 ON condition because the condition can reference T1 in the first case but not the second.
[1] https://www.postgresql.org/docs/current/queries-table-expres...
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.
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.
Perfect for a reporting database though.
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