Hive processes joins very late in the processing system, which results in it being very greedy and aggressive with reading all columns of the table when joining data.

This implies that something like

select * from a join b on (a.key = b.key);

will have to read every single column in a and b, irrespective of whether one of the is a small table fitting in memory.

Mapjoins are a special class of hive's fast join operations which deal with one of the tables being very small.

If table b is a very small table, it can be read into memory entirely in the mapper. Which means the join operation has been reduced to a check whether the key from table a is present in the hashtable in memory.

This means that before the very first row of the big table is read, the entire key space of the small table is available in memory, which can be converted into a bloom filter and pushed down into the data reader, allowing for more selective processing of the data earlier in the pipeline.

For more information on filter pushdowns in Hive - https://cwiki.apache.org/Hive/filterpushdowndev.html#FilterPushdownDev-UseCases

And for bloomfilters, please read the wikipedia article on this probabilistic data structure. Also play around with http://www.jasondavies.com/bloomfilter/

This has already been done before, with little success - https://issues.apache.org/jira/browse/HIVE-1721

ORC has fledgling support for predicate pushdowns - needs https://reviews.facebook.net/D9831 + https://issues.apache.org/jira/browse/HIVE-4246

Project Members