Bloom Filters

Oracle Database, as of 10g Release 2, uses bloom filters in various situations. Unfortunately, no information about their usage is available in Oracle documentation. For this reason, I decided to write a paper to explain not only what bloom filters are, but also, and foremost, to describe how Oracle Database makes use of them. Specifically, to explain how the database engine uses bloom filters to reduce data communication between slave processes in parallel joins and to implement join-filter pruning.

Originally, I wrote this paper for the IOUG Select Journal. Even if I wrote it last June, I wanted to receive the printed copies before putting it online. Today a packet with five copies of the Q4/2008 issue and a polo shirt arrived… Hence, it is now available online as well.

If you don’t have access to Select Journal, you can download it from this page.

10 Comments

  1. September 26, 2008    

    Very enjoyable paper.
    I knew about Bloom Filters in general, but it was nice to see a simple PL/SQL implementation and to know where they are used within Oracle.

  2. September 28, 2008    

    Pretty timely, too! ;-) Page 14, here …

    http://www.oracle.com/technology/products/bi/db/exadata/pdf/exadata-technical-whitepaper.pdf

    I’ve made a start on your book, btw. Looks good so far but it’ll probably end up half-read for a few months like all the books do. I have a course slides deadline approaching so it’s back on the shelf for now ….

  3. September 28, 2008    

    Hi Doug

    Timely ?!?

    I’m aware of bloom filters in Oracle since December 2005. So, I wanted to write something about them for a long time. IIRC we also discussed about them at the 2006 UKOUG conference… Therefore, I’m really happy that this short paper is, at last, published.

    Cheers,
    Chris

  4. September 28, 2008    

    I was laughing about the coincidence. I’ve been aware of bloom filters for quite a while too but it’s just funny that this should come out at a time when bloom filters happen to have been mentioned in the same week as they’re mentioned in an important Oracle white paper. It was just a small joke really.

  5. September 28, 2008    

    Well, not *just* a joke. It’s nice that your paper comes out just when a lot of people might be wondering what a Bloom Filter is. Therefore it is timely in that sense.

  6. October 1, 2008    

    Thanks Christian for this really nice whitepaper and helped me with understanding some of the concepts
    (and thanks Doug for the link, although Kevin didn’t appriciated it)

    ;-)

  7. October 2, 2008    

    Dennis Yurichev [1] posted on Oracle-L [2] about a list of Undocumented Oracle Functions. There are (at least) 2 which might be of some interrest. Maybe they could look the examples more real ;-)

    SYS_OP_BLOOM_FILTER
    SYS_OP_BLOOM_FILTER_LIST
    

    [1] http://www.yurichev.com/
    [2] http://www.freelists.org/archives/oracle-l/10-2008/msg00037.html

  8. Kenny Roytman's Gravatar Kenny Roytman
    October 23, 2008    

    Christian,

    Thanks for the interesting paper.

    Any idea how Dennis Yurichev generates that listing of undocumented functions?

  9. October 23, 2008    

    Hi Kenny

    On Linux/Unix I would execute the following command:

    strings $ORACLE_HOME/bin/oracle | grep -e "^SYS_OP_w*$" | sort -u

    Cheers,
    Chris

  10. November 23, 2008    

    Look at msqdef.o file in libserver11.a, it contain (if I’m correct) all functions, not just SYS_OP.

  1. AMIS Technology blog » Blog Archive » Bloom Filters, Hierarchical Profiling,… - feast for DBAs (considered harmful..) on May 18, 2009 at 18:40
  2. Parallel Execution – 4 | Oracle Scratchpad on February 26, 2014 at 13:58

Leave a Reply

Your email address will not be published. Required fields are marked *