Rindex (a short for RAM Index) is designed as a platform to be usedtop of a traditional database management system (DBMS). The mainfocus for this project has been on how to maximize the usage of theavailable main memory by keeping the indexes entirely in RAM. Thisway we avoid disk I/O when using an index, and therefore increase theefficiency drastically. In Rindex the relations still resides ondisk, only the indexes are kept entirely in memory. Thisdistinguishes Rindex from already existing MMDBMS (main memory DBMS).
We have designed and implemented a first version of thisplatform. This version of Rindex is limited in that it only supportsa subset of the SQL language, and just utilizes static indexes(i.e. modifying relations or schemas is currently not supported).Rindex contains all the standard components: scanner, parser,optimizer, plan generator, plan selector, and plan executor. Onstartup, the platform generates an index on every attribute that arecomparable, e.g. integer, floats, and strings. Inverted indexes arealso generated.
The main focus of this thesis is to analyzes the efficiency of thesubstitution operator, a special operator in Rindex. The operatorsubstitutes the attribute values in a intermediate index, with thecorresponding values from another attribute (i.e. values with the sameprimary key).
We propose several different solutions to optimize this operator, andthis results in a significantly improved substitution operator. Wedesign new data structures for the inverted index, since thesubstitution algorithm heavily depends and follows from thisstructure.
We also analyzes the algorithm that inserts the substitution operatorinto the query tree. Our attempt to improve the algorithm, i.e. tominimize the number of substitution operators, led to the conclusionthat it requires knowledge of the cost estimates and heuristics usedby the optimization algorithm. The reason is that the optimizationalgorithm and this algorithm often disagrees on the ordering of theoperators.
The thesis is written in Norwegian.