| dc.description.abstract | Rindex (a short for RAM Index) is designed as a platform to be used
top of a traditional database management system (DBMS). The main
focus for this project has been on how to maximize the usage of the
available main memory by keeping the indexes entirely in RAM. This
way we avoid disk I/O when using an index, and therefore increase the
efficiency drastically. In Rindex the relations still resides on
disk, only the indexes are kept entirely in memory. This
distinguishes Rindex from already existing MMDBMS (main memory DBMS).
We have designed and implemented a first version of this
platform. This version of Rindex is limited in that it only supports
a 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. On
startup, the platform generates an index on every attribute that are
comparable, e.g. integer, floats, and strings. Inverted indexes are
also generated.
The main focus of this thesis is to analyzes the efficiency of the
substitution operator, a special operator in Rindex. The operator
substitutes the attribute values in a intermediate index, with the
corresponding values from another attribute (i.e. values with the same
primary key).
We propose several different solutions to optimize this operator, and
this results in a significantly improved substitution operator. We
design new data structures for the inverted index, since the
substitution algorithm heavily depends and follows from this
structure.
We also analyzes the algorithm that inserts the substitution operator
into the query tree. Our attempt to improve the algorithm, i.e. to
minimize the number of substitution operators, led to the conclusion
that it requires knowledge of the cost estimates and heuristics used
by the optimization algorithm. The reason is that the optimization
algorithm and this algorithm often disagrees on the ordering of the
operators.
The thesis is written in Norwegian. | nor |