Вычислить декартово произведение быстро, как СУБД

Question

Я исследовал, как эффективно вычислить декартово произведение двух произвольных множеств, но я обнаружил, что решения всегда довольно неэффективны, если размер наборов огромен. Мой вопрос в том, как такие языки базы данных, как MySQL, выполняют эту задачу эффективно, есть ли алгоритм или способ эмулировать декартово-произведение так, как это делают языки базы данных.

PD: Я использую java. не

Answer 1

В принципе, нет - если вы хотите, декартово произведение двух наборов размеров n,m - размер декартовой продукта n*m - и вам нужно O(nm) алгоритм его генерации.

Однако для языков баз данных, когда вы делаете такие вещи, как 'join', вам иногда не нужно генерировать все соединение, чтобы получить ответ - если все, что вы собираетесь делать позже, просто подсчитывает количество элементов или сумма.
Это может быть указано в Pig LatinОператор COGROUP, который создает только неявное соединение, чтобы позднее просто использовать размеры или суммы, а не реальный декартовый продукт. Это потенциально может быть намного более эффективным, если его правильно использовать в правильной ситуации.