Re: Hash Tables

hash size is purportedly 32 + keysize + rowsize (of the selected data). Interesting formula you've got there, I'll have to take a closer look. cheers j. ----- Original Message ----- From: "Curtis Crowson" <curtis@crowson1.com> To: <informix-list@iiug.org> Sent: Thursday, January 29, 2004 3:34 PM Subject: 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 ) sending to informix-list

> hash size is purportedly 32 + keysize + rowsize (of the selected data). > > Interesting formula you've got there, I'll have to take a closer look. > > cheers > j. My index time formula is slightly off but the shape is correct. Basically the depth of the btree* ( or plus it only matters slightly which informix standard indexes are ) is some function of the number of nodes in the tree. For a binary-tree each node one key and has two children branches. x represents the nodes at each level Level 0 1 2 3 4 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x So the number of nodes in this tree are: 1 + 2 + 4 + 8 + 16 = 31 or mo' betta 2^0 + 2^1 + 2^2 + 2^3 + 2^4 which is equal to (2^5) - 1 So if your index is 5 deep like our tree it will contain 31 nodes if n1 = n2 then lg_base_2( n1 ) = lg_base_2( n2 ) lg_base_2( 31 + 1 ) = 5 The depth of the tree divided by 2 is on average the number of nodes that you visit to find any key value ( that is where my formula is off ) lg_base_2( N )/ 2 = average number of nodes to visit. I am also assuming that the nodes are completely filled which isn't true. Knuth would be really mad at me. ;-) So you multiple by the time it takes to visit a node and add any fixed time and you have the formula for index accesses. The scan formula is left as an exercise. ;-)