my-vegetable-has-exploded commented on PR #12754: URL: https://github.com/apache/datafusion/pull/12754#issuecomment-2564720663
> I'm planning on taking a look at this over the next week or so, but it will take a little time for me to get up to speed on the details of what you're trying to do here. Can you add any descriptive text to the PR so I don't need to wade through the entire conversation on the issue? I'm really glad that you're willing to review this PR. Overall, this PR might appear to be quite lengthy. Additionally, I've been quite busy recently preparing for my graduation thesis, so my responses might not always be timely. And this pr wants to support for inner IEJoin, optimizing join operations without equality join conditions but with two or more inequality conditions, and improving the performance of specific queries. The main idea of the IEJoin algorithm is to convert the join operation with inequality conditions into an ordered pair/inversion pair of permutation problem. For example, ``` SELECT t1.t id, t2.t id FROM west t1, west t2 WHERE t1.time < t2.time AND t1.cost < t2.cost ``` Conceptually it's executing in 3 steps: 1、Sort (r union s) on time in ascend order, add one column for time_rank(1..n) 2、Sort (r union s with time_rank) again on cost in ascend order, the time_rank in step 1 gets permutated into Permutation Array(represented as p) 3、Compute the ordered pair of permutation array p. For a pair (i, j) in l2, if i < j then e_i.cost < e_j.cost because l2 is sorted by cost in ascending order. And if p[i] < p[j], then e_i.time < e_j.time because l1 is sorted by time in ascending order. If we use btreemap to maintain all the p[i] where i<j, we can get all pairs in $NlogN+OutputSize$. And you can find more detailed examples in the comments. To parallel the above algorithm, we can sort t1 and t2 by time (condition 1) firstly, and repartition the data into N partitions, then join t1[i] and t2[j] respectively. And if the minimum time of t1[i] is greater than the maximum time of t2[j], we can skip the join of t1[i] and t2[j] because there is no join result between them according to condition 1. So I add the optimizer to ensure the input data has been sorted by condition1. >  > > It seems the main cost is sorting. By the way, this perf result shows that the sort process in permutation computing is the main cost currently. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: github-unsubscr...@datafusion.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: github-unsubscr...@datafusion.apache.org For additional commands, e-mail: github-h...@datafusion.apache.org
