Compute Cartesian Product Fast like DBMS

Question

I've researched about how to efficiently compute the cartesian product of two arbitrary sets, but I've found that the solutions are always quite inefficient if the size of the sets go huge. My question is, how Data base languages like MySQL do this task efficiently, is there an algorithm or a way to emulate the cartesian product in the way the Data Base languages do?.

PD: I'm using java.

Answer 1

Basically, no - if you want a cartesian product of two sets of sizes n,m - the size of the cartesian product is n*m - and you need O(nm) algorithm to generate it.

However, for data base languages, when you do things like 'join', you sometimes do not need to generate the entire join to get the answer - if all you are going to do later on is just count number of items, or sum.
This can be shown in Pig Latin's COGROUP operator, which only creates an implicit join, in order to later just use the sizes or sums - and not the real cartesian product. This potentially could be much more efficient if used properly in the right situation.