System and method using partial just-in-time compilation to resolve memory access pattern problems in hash table probing
A system and method for just in time compilation for hash table probing are disclosed. In one implementation, the method of using just-in-time compilation is used to combine the stages of hash value computation and initial lookup into a single compound operation. In another implementation, the method of using just-in-time compilation is used to combine the stages of a hash table record and input record checking to detect if these records are equal, and if not, fetching the next possible record in the linked list of the per-bucket records.
1. An apparatus for hash table lookups in a block oriented processing system, the apparatus comprising:
a database that performs block oriented processing;
the database having a database engine that just in time compiles multiple compound operations into a compound function, wherein the compound function is used to perform efficient hash table lookups in the block oriented processing system,
wherein the compound function includes at least a first stage that checks if a hash table record and an input record are equal and a second stage that fetches data based on a result of the first stage.
2. The apparatus of claim 1 , wherein the second stage fetches a next record in a hash table bucket-chain list for hash table records that failed in the first stage.
3. The apparatus of claim 1 , wherein the second stage fetches attribute values for hash table records that passed in the first stage.
4. The apparatus of claim 1 , wherein the block oriented processing system is a vectorized database system.
5. The apparatus of claim 1 , wherein at least one of the multiple queries corresponds to a hash join operation on one or more tables of the database.
6. The method of claim 1 , wherein the compound function is reused for multiple queries to perform the efficient hash table lookups in the block oriented processing system.
7. The apparatus of claim 6 , further comprising a store that stores the compound function and allows the compound function to be reused for the multiple queries.
8. A method for hash table lookups in a block oriented processing system using just in time compiling of compound operations, the method comprising:
performing block oriented processing of records on a database;
just-in-time compiling, by a database engine associated with the database, multiple compound operations into a compound function, wherein the compound function is used to perform efficient hash table lookups in a the block oriented processing system,
wherein the compound function includes at least a first stage that checks if a hash table record and an input record are equal and a second stage that fetches data based on a result of the first stage.
9. The method of claim 8 , wherein the second stage fetches a next record in a hash table bucket-chain list for hash table records that failed in the first stage.
10. The method of claim 8 , wherein the second stage fetches an attribute value in the database.
11. The method of claim 8 , wherein the block oriented processing system is a vectorized database system.
12. The method of claim 8 , wherein at least one of the multiple queries corresponds to a hash join operation on one or more tables of the database.
13. The method of claim 8 , wherein the compound function is reused for multiple queries to perform the efficient hash table lookups in the block oriented processing system.
14. The method of claim 13 , further comprising a store that stores the compound function and allows the compound function to be reused for the multiple queries.