[ 
https://issues.apache.org/jira/browse/HIVE-1721?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12927544#action_12927544
 ] 

Joydeep Sen Sarma commented on HIVE-1721:
-----------------------------------------

a bloom filter takes 10 bits per entry (with reasonable probability. i remember 
reading this value from wikipedia).

Our java hash tables take 2000 bytes per key-value pair (based on tests done by 
Liyin for reasonable sized keys/values).

So the idea is that if the small table is too big to be loaded into memory - 
but small enough that it's bloom filter can be stored in memory - then we can 
first do a filter of the large table and then do the sort.

> use bloom filters to improve the performance of joins
> -----------------------------------------------------
>
>                 Key: HIVE-1721
>                 URL: https://issues.apache.org/jira/browse/HIVE-1721
>             Project: Hive
>          Issue Type: New Feature
>          Components: Query Processor
>            Reporter: Namit Jain
>            Assignee: Siying Dong
>
> In case of map-joins, it is likely that the big table will not find many 
> matching rows from the small table.
> Currently, we perform a hash-map lookup for every row in the big table, which 
> can be pretty expensive.
> It might be useful to try out a bloom-filter containing all the elements in 
> the small table.
> Each element from the big table is first searched in the bloom filter, and 
> only in case of a positive match,
> the small table hash table is explored.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

Reply via email to