Equivalent of Presto Lookup Join in Velox

[aditi-pandit]

Description

In Velox today, HashJoin is used only when there is an equality predicate in the join condition . When there isn't any equality condition, NestedLoop Join is used.

In Presto, there is an operator for LookupJoin as well. This is the probe side lookup. There is a HashBuilder operator on the build side. This HashBuilder has fields for sortChannel and searchFunctionFactories ref that can be used to search specific values and follow sortLinks to find a range of values to match a condition. This allows for optimizations like prestodb/presto#8614 for non-equality joins. Link in LocalExecutionPlanner https://github.com/prestodb/presto/blob/master/presto-main/src/main/java/com/facebook/presto/sql/planner/LocalExecutionPlanner.java#L2374

In my mind, another similar option is to implement a B-tree in Velox.

Would be great if such functionality were available. It could be used in other operators/connectors as well.

It would give great performance, have reasonable spilling behavior and restrict NestedLoopJoin to cross joins only.

@mbasmanova @xiaoxmeng @Yuhta @oerling @pedroerp

[pedroerp]

Is it common to find joins which aren't equi-joins in the workloads you are running?

I'm not sure we ran until this before, which I guess it's because most of the joins in our workloads are equi? Cc: @mbasmanova @Yuhta

[aditi-pandit]

@pedroerp : Join planning for correlated queries often use non-equi joins. It is important for us to plan this efficiently.

I've heard in passing that most Meta queries use equi-joins. Though I remember Amit pushing for some NestedLoopJoin fixes in the past. So Meta workloads do have non-equi joins as well I think.

But the original NestedLoopJoin operators are non-Meta contribution AFAIK.

[Yuhta]

I checked the LookupJoin in Presto a little bit and find it can do first hash join on some keys, then do range query on other keys of the matched rows to further filter down rows (like the join filter we have in velox hash join). Do we want to support this use case? Or we just want to have range query join as the main way of join?

[mbasmanova]

CC: @usurai

[aditi-pandit]

@Yuhta : My use case if for range query join (without any equality condition). It becomes NestedLoopJoin today.

For hash join followed by range query we are fine with the HashJoin(Build/Probe) we have in Velox already.

[oerling]

Presto has a join where it builds a tree and then does lookups in that. Usually, databases make durable indices and then maintain these. The Presto range lookup is not like that, it builds on demand and just like a hash join. Thre is I recall some class called IndexBuilder or such. Should there be that i Velox? How would thuis spill? Would this be like an index in a traditional database with a buffer pool and all? How would this be prtitioned? Or broadcast? If it were partitioned, it would have to have a broadcast on the probe side or a range partition. The latter would have to be adaptive, since we are talking about a query time artifact, not an index tat somebody creates and is then maintained by the system.

Imagine a minimal implementation: Build it like a hash join but make a B tree over it instead of a hash table. If there is a leading equality, the build can be partitioned on that. Otherwise there is a broadcast from build if the build is small and a broadcast on probe if it is large. Then there is a representation of a range condition.

We have found no use for this at Meta. But somebody could build thuis of course. I an specify how this is done if somebody wants to write this.

[aditi-pandit]

@oerling : Agree with the idea of exploring a query time artifact instead of index in traditional database with a buffer pool.

Your suggestion to build it like a hash join but make it a B-tree with links to follow for a range search is a good starting point.

There isn't a pressing need from our side for this rightaway. But I'm intrigued to hear more about your ideas for this.

We might find interested folks to write this.