Join reordering

[wangxiaoying]

I'm curious about the join reordering implementation inside datafusion. After a quick search of the code, I found that there are two rules that may reorder the join:

• EliminateCrossJoin: it completely reorders the joins from scratch in a way such that the join conditions can all be pushed down into the join node (preventing cross join).
• JoinSelection: it reorders the given join input according to statistics in terms of deciding the build and probe side.

Please let me know if I missed anything here, but it seems like there is no traditional join reordering in query optimization literature such as using DP or MEMO to decide the best join order in terms of performance. I found a related issue here in general for the optimizer framework but it also seems to be paused for a while. Are there any ongoing plans or discussions to implement such things?

[andygrove]

I am not aware of any active plans to pursue join reordering in DataFusion. It is a challenging problem because it requires statistics that are not readily available when running ad-doc queries against file-based data sources.

[wangxiaoying]

I see. Thanks for the answer : )

[alamb]

Ideally, what I would love t to see is better statistics support (e.g. #8229 and other things) and the existing basic join reordering support in DataFusion and an example of how to implement more sophisticated reordeirng strategies that people can add / extend for their usecase

[alamb]

See also a recent discussion

• Discussion: API for Join Access Path and Join Order Selection #17718