Database Operations on Multi-Core Processors

Abstract

The focus of this thesis is on investigating efficient database algorithmsand methods for modern multi-core processors in main memory environments.We describe central features of modern processors in a historic perspectivebefore presenting a number of general design goals that should beconsidered when optimizing relational operators for multi-corearchitectures. Then, we introduce the skyline operator and relatedalgorithms, including two recent algorithms optimized for multi-coreprocessors. Furthermore, we develop a novel skyline algorithm using anangle-based partitioning scheme originally developed for parallel anddistributed database management systems. Finally, we perform a number ofexperiments in order to evaluate and compare current shared-memory skylinealgorithms.Our experiments reveals some interesting results. Despite of having anexpensive pre-processing step, the angle-based algorithm is able tooutperform current best-performers for multi-core skyline computation.In fact, we are able to outperform competing algorithms by a factor of5 or more for anti-correlated datasets with moderate to largecardinalities. Included algorithms exhibit similar performancecharacteristics for independent datasets, while the more basicalgorithms excel at processing correlated datasets. We observe similarperformance for two small real-life datasets. Whereas, the angle-basedalgorithm is more efficient for a work-intensive real-life datasetcontaining more than 2M 5-dimensional tuples.Based on our results we propose that database research targeted atshared-memory systems is focused not only on basic algorithms but alsomore sophisticated techniques proven effective for parallel anddistributed database management systems. Additionally, we emphasizethat modern processors have very fast inter-thread communicationmechanisms that can be exploited to achieve parallel speedup also forsynchronization-heavy algorithms.