Query Execution Algorithms Design & Optimization

Query execution is an important part of database technology. The speed of query can directly affect the performance and efficiency of the systems. There are four principal methods for execution of the operations of relational algebra, which include scanning, sorting, indexing and hashing. Our national database management system DM3 uses these four methods to execute its queries. There are two problems to be solved in DM3. One is that the space utilization of B+ tree is low. The other is that hash functions have many collisions. In order to solve these problems, a new bottom-up method of constructing B+ tree and a new two-dimension-address hash algorithm are designed detailedly. The first new method uses a bottom-up method to construct a B+ tree. It can improve the space utilization of B+ tree and the efficiency of constructing B+ tree. It makes sure that the leaves of B+ tree are in a sequence on the disk, so it is efficient to read data of B+ tree's leaves from the disk. The second new method describes a new hash algorithm, which uses a two-dimension-address to determine a key's position in the hash table. One dimension is stored in the hash table. In order to store the other dimension, an auxiliary table is used. It has fewer collisions than conventional hash algorithms. The most important and surprising property of the new hash algorithm is that the average key-compare time is no more than 1/n when we use two-dimension-address hash algorithm to search a key word in the hash table, where n is the size of the auxiliary table.In practice, these algorithms have good performance.