Click here to view and discuss this page in DocCommentXchange. In the future, you will be sent there automatically.

SQL Anywhere 10.0.1 » SQL Anywhere Server - SQL Usage » Query Optimization and Execution » Query execution algorithms » Miscellaneous algorithms

Filter and Pre-filter algorithms Next Page

Hash Filter algorithm

A Hash Filter or Hash Map, sometimes referred to as a bloom filter, is a data structure that represents the distribution of values in a column or set of columns. The hash filter can be viewed as a (long) bit string where a 1 bit indicates the existence of a particular row, and a 0 bit indicates the lack of any row at that bit position. By hashing the values from a set of rows into bit positions in the filter, the database server can quickly determine whether or not there is a matching row of that value (subject to the existence of hash collisions).

For example, consider the plan:

R<idx> *JH S<seq> JH* T<idx>

Here you are joining R to S and T. The database server reads all of the rows of R before reading any row from T, and can immediately reject rows of T that can not possibly join with R. This reduces the number of rows that must be stored in the second hash join.

A Hash Filter may be used in queries that satisfy both of the following conditions:

In this circumstance, the hash filter constructed as a result of the first join can substantially improve the performance of the second join. This is achieved by performing a lookaside into the hash filter's bit string to determine if any row has been previously processed successfully by the first join—if no such row exists, the hash table probe for the second join can be avoided entirely since the lack of a 1 bit in the Hash Filter signifies that the probe would fail to yield a match.