Striving for Optimal Performance
  • Blog
    • Archive
    • Categories
    • Search
  • Troubleshooting Oracle Performance
    • Description
    • Structure
    • Table of Contents
    • Forewords
    • Reviews
    • Downloadable Files
    • Addenda and Errata
    • First Edition
  • Public Appearances
    • Past Public Appearances
  • Contact
  • About

Bloom Filters

26 September 2008 12 Comments Written by Christian Antognini

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.

10gR2, 11gR1, Parallel Processing, Partitioning, Query Optimizer
Book Presentation
Granularity 'APPROX_GLOBAL AND PARTITION'

12 Comments

2 Pings/Trackbacks

  1. Chen Shapira Chen Shapira
    26 September 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.

    Reply
  2. Doug Burns Doug Burns
    28 September 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 ….

    Reply
  3. Christian Antognini Christian Antognini
    28 September 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

    Reply
  4. Doug Burns Doug Burns
    28 September 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.

    Reply
  5. Doug Burns Doug Burns
    28 September 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.

    Reply
  6. Marco Gralike Marco Gralike
    1 October 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)

    ;-)

    Reply
  7. Martin Berger Martin Berger
    2 October 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

    Reply
  8. Kenny Roytman Kenny Roytman
    23 October 2008    

    Christian,

    Thanks for the interesting paper.

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

    Reply
  9. Christian Antognini Christian Antognini
    23 October 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

    Reply
  10. Dennis Yurichev Dennis Yurichev
    23 November 2008    

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

    Reply
  11. AMIS Technology blog » Blog Archive » Bloom Filters, Hierarchical Profiling,… - feast for DBAs (considered harmful..) AMIS Technology blog » Blog Archive » Bloom Filters, Hierarchical Profiling,… - feast for DBAs (considered harmful..)
    18 May 2009    

    […] Bloom Filters – by Christian Antognini. […]

  12. Parallel Execution – 4 | Oracle Scratchpad Parallel Execution – 4 | Oracle Scratchpad
    26 February 2014    

    […] A Bloom filter is simply a small dataset created by the first slave set that is a “summary” of the values that are likely to be useful in the join. As it builds the in-memory hash table, the first slave set can construct a Bloom filter for the join values; when the hash table is complete the first slave set can pass the Bloom filter to the second slave set (possibly by way of the query co-ordinator, I haven’t checked the mechanism yet) allowing the second slave set to discard the data that definitely won’t be needed and passing only data that will probably be needed through the table queue.  (Note: the Bloom filter is not a perfect filter, it may allow some data that isn’t needed. For more detailed information about Bloom filters, see this article by Christian Antognini.) […]

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

Leave a Reply Cancel reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.