Re: Hash Tables

> Could anyone explain to me exactly what happens when you perform a hash join > between multiple tables. The Informix doc I have read only references a > two table join. It says that a hash table is built of the driving table and > matched against hash values of the second table. What happens if there is > a third and fourth table? > This is how I under stand it. It may be wrong because I haven't seen any documentation to support it. ( I guess it would be better to know the answer when answering a question, but it doesn't seem to bother me at all. ;-) ) Normal index access happens in C * log of A( N ) time on average. Where A is the number of keys in each leaf ( index page )and N is the number of records in the table. C is of course the constant for how long it takes to look at each page. So for a nested loop join of 2 1000 row tables returning 100 rows in the driver table you have a cost of 100 * C log of A*(N ) for the join. Now what is going on for hash joins and why it is a good thing for large joins. the cost of calculating a hash on a table on a given table is c*N. The cost of calculating a hash on two tables assuming two threads is still c*N. What happens for a hash join is that informix creates a temp memory area where the join key is hashed into a slot with the address of the record on the device. Then it calculates the hash for the other table and adds this to the hash table. Joined keys will of course hash into the same slot so all informix has to do at this point is read the hash table because joined columns will all be in the same slot. I would think that this would take 3*c*N which is smaller than 2* NJ * C * log of A( N ) for some N and NJ. Where NJ is the number of join records. Please correct me if you know for sure. so I suspect the size of the hash table would be keysize and device address size * ( rows in table one and rows in table two )