[HIVE-9277] Hybrid Hybrid Grace Hash Join

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.2.0
• Component/s: Physical Optimizer
• Labels: TODOC1.2 join
• Assignee: Wei Zheng
• Reporter: Wei Zheng
• Created: 07/Jan/15 01:30
• Updated: 18/Jul/15 06:48
• Resolved: 23/Mar/15 20:08

Description

We are proposing an enhanced hash join algorithm called “hybrid hybrid grace hash join”.

We can benefit from this feature as illustrated below:

• The query will not fail even if the estimated memory requirement is slightly wrong
• Expensive garbage collection overhead can be avoided when hash table grows
• Join execution using a Map join operator even though the small table doesn't fit in memory as spilling some data from the build and probe sides will still be cheaper than having to shuffle the large fact table

The design was based on Hadoop’s parallel processing capability and significant amount of memory available.

Issue Links

• is related to: HIVE-10287 Implement Hybrid Hybrid Grace Hash Join for Spark Branch [Spark Branch]
• is related to: HIVE-10123 Hybrid grace Hash join : Use estimate key count from stats to initialize BytesBytesMultiHashMap
• is related to: HIVE-10284 enable container reuse for grace hash join
• is related to: HIVE-9789 Hybrid Hybrid Grace Hash Join: improve hashtable serialization
• is related to: HIVE-9790 Hybrid Hybrid Grace Hash Join: improve side file serialization
• is related to: HIVE-10072 Add vectorization support for Hybrid Grace Hash Join
• is related to: HIVE-10403 Add n-way join support for Hybrid Grace Hash Join
• is required by: HIVE-11306 Add a bloom-1 filter for Hybrid MapJoin spills
• links to: Review Board