[sethev]

There have been hints in the research that this might be the case-but so far they haven't really beaten the heuristic approach in practice (outside of special cases).

For example there's a class of join algorithms called 'worst-case optimal' - which is not a great name, but basically means that these algorithms run in time proportional to the worst-case output size. These algorithms ditch the two at a time approach that databases typically use and joins multiple relations at the same time.

One example is the leapfrog trie join which was part of the LogicBlox database.