search

simlaudato / asterixdb

Automatically exported from code.google.com/p/asterixdb
0 stars 0 forks source link

Secondary btree index should not have a bloomfilter on it since the filter is not used for range search which is always the case for secondary index search #924

Open GoogleCodeExporter opened 8 years ago

GoogleCodeExporter commented 8 years ago 
Currently, all secondary index searches are considered as range search due to 
the fact that secondary index keys are not unique. Since bloomfilter is only 
used for point lookup, secondary btree index should not have a bloomfilter on 
it.

Original issue reported on code.google.com by kiss...@gmail.com on 10 Aug 2015 at 8:00

GoogleCodeExporter commented 8 years ago 
Then I would challenge the approach of "always doing a range search on a 
secondary index."  What if we have a condition "price = 20" where there is a 
secondary B-tree on "price"?  Clearly a bloom filter can help this predicate.  
Do we miss an opportunity of optimization here?

Original comment by che...@gmail.com on 10 Aug 2015 at 3:55

GoogleCodeExporter commented 8 years ago 
Yes. We haven't been exploiting that opportunity.

Original comment by kiss...@gmail.com on 10 Aug 2015 at 4:11

GoogleCodeExporter commented 8 years ago 
@Young-Seok: do you want to summarize our discussion today to close this 
discussion?

Original comment by che...@gmail.com on 11 Aug 2015 at 6:07

GoogleCodeExporter commented 8 years ago 
Discussion conclusion: secondary btree index will not have a bloomfilter on it.

The reasons are as follows:
1. Secondary btree index search can't use Bloomfilter for range searches since 
, in general, Bloomfilter can only be used for point lookup, i.e., single value 
equality predicate on the indexed key such as user_id (primary key field) = 10.
2. Secondary btree index search can't use Bloomfilter for point lookup either 
such as price = 20 since Bloomfilter in secondary btree index captures not only 
secondary key but also primary key, but search predicate only includes 
secondary key.    
3. Delete operation in secondary index may use the Bloomfilter to check the 
existence of the entry to be deleted, but the entry to be deleted will exist 
always when the delete operation is executed since the delete operation always 
preceded by the search operation. So, checking Bloomfilter in the situation is 
useless overhead. 
Based on 1,2, and 3, Bloomfilter on secondary btree index is useless. 
Therefore, this will be removed.

Original comment by kiss...@gmail.com on 11 Aug 2015 at 4:03