[BUG] Left Semi Join much slower than Inner join

[cheinger]

Describe the bug
I’ve noticed that Left Semi Join can be an order of magnitude slower than Inner Join. Below you can see the 10x slow down when we switch out Inner Join for Left Semi Join (same data & table sizes).

Inner Join

Left Semi Join

I did some further investigation and found that the cause for this slow down is the thrust::copy_if in left_semi_anti_join that copies the selected row indices that are found in the hash table. I switched this out for cub::DeviceSelect::Flagged and observed an 18x performance improvement as seen below:

Before

After

Expected behavior
I would expect Left Semi Join and Inner Join to be somewhat comparable in performance, and if anything, Inner Join to be slower because we have to handle duplicate keys.

Environment details
env_details.log

[cheinger]

I have created a PR with a fix: #10511

[jrhemstad]

I'm more interested to know why thrust::copy_if is so much slower than cub::DeviceSelect::flagged. If they don't share the same implementation, then they should be made to.

[cheinger]

@jrhemstad I did some further investigation and determined that the the reason thrust::copy_if was slower than cub::DeviceSelect::Flagged was actually because of the predicate lambda function we used in copy_if. The lambda performed the hash table lookup which significantly increased the register usage of the thrust::copy_if kernel and therefore reduced the occupancy of the kernel and furthermore the performance. So instead of using cub::DeviceSelect::Flagged I continue to use thrust::copy_if, but instead, the lambda just returns the corresponding index from the flagged array and now the performance was comparable to cub::DeviceSelect::Flagged. And below you can see the occupancy increased from 37% to 72%.

thrust::copy_if with original lambda

thrust::copy_if with flagged lambda

I have updated my PR to reflect these changes: #10511

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.