Database Operations on Multi-Core Processors
The focus of this thesis is on investigating efficient database algorithms
and methods for modern multi-core processors in main memory environments.
We describe central features of modern processors in a historic perspective
before presenting a number of general design goals that should be
considered when optimizing relational operators for multi-core
architectures. Then, we introduce the skyline operator and related
algorithms, including two recent algorithms optimized for multi-core
processors. Furthermore, we develop a novel skyline algorithm using an
angle-based partitioning scheme originally developed for parallel and
distributed database management systems. Finally, we perform a number of
experiments in order to evaluate and compare current shared-memory skyline
Our experiments reveals some interesting results. Despite of having an
expensive pre-processing step, the angle-based algorithm is able to
outperform current best-performers for multi-core skyline computation.
In fact, we are able to outperform competing algorithms by a factor of
5 or more for anti-correlated datasets with moderate to large
cardinalities. Included algorithms exhibit similar performance
characteristics for independent datasets, while the more basic
algorithms excel at processing correlated datasets. We observe similar
performance for two small real-life datasets. Whereas, the angle-based
algorithm is more efficient for a work-intensive real-life dataset
containing more than 2M 5-dimensional tuples.
Based on our results we propose that database research targeted at
shared-memory systems is focused not only on basic algorithms but also
more sophisticated techniques proven effective for parallel and
distributed database management systems. Additionally, we emphasize
that modern processors have very fast inter-thread communication
mechanisms that can be exploited to achieve parallel speedup also for
Place, publisher, year, edition, pages
Institutt for datateknikk og informasjonsvitenskap , 2013. , 77 p.
IdentifiersURN: urn:nbn:no:ntnu:diva-22990Local ID: ntnudaim:8438OAI: oai:DiVA.org:ntnu-22990DiVA: diva2:655624
Nørvåg, Kjetil, Professor