Determining join order
Hi, in the process of writing a MAL backend for a query compiler, I'm trying to optimize the join order of arbitrary theta joins on whole relations (i.e. predicates may be arbitrary). To implement this, I use a simple heuristic for 2-way theta joins on relations: First the cheap predicates are identified, then the necessary joins are performed on the columns. After that all results of the cheap predicates are merged via joins on the OIDs. Finally, expensive predicates (i.e. with a lot of qualifying tuples) are implemented by applying a binary scalar operation and using a *subselect* and a *projection*/*leftfetchjoin*, since all columns are aligned now. To conclude: 2-way joins may not be atomic MAL joins (i.e. not column-wise), but they very well could be. So, what I'm looking for is some facility in MonetDB, with which I am able to break down a n-way join into 2-way joins, with the smallest possible intermediate results, without assuming too much about how those 2-way joins are implemented. The first thing I found was the *scheduler* module, which is also on the official website ( https://www.monetdb.org/Documentation/Manuals/MonetDB/Optimizers/Memoization ). But that seems no more up to date, since most of the functions are missing and the semantics of join operators in MAL has changed quite a bit. Is there anything else I can use for this task (aside from implementing some dynamic programming algorithm within MAL)? Kind regards, Moritz
participants (1)
-
Moritz Bruder