Change search
ReferencesLink to record
Permanent link

Direct link
Database Operations on Multi-Core Processors
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Computer and Information Science.
2013 (English)MasteroppgaveStudent thesis
Abstract [en]

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 algorithms. 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 synchronization-heavy algorithms.

Place, publisher, year, edition, pages
Institutt for datateknikk og informasjonsvitenskap , 2013. , 77 p.
URN: urn:nbn:no:ntnu:diva-22990Local ID: ntnudaim:8438OAI: diva2:655624
Available from: 2013-10-12 Created: 2013-10-12 Last updated: 2013-10-12Bibliographically approved

Open Access in DiVA

fulltext(2404 kB)296 downloads
File information
File name FULLTEXT01.pdfFile size 2404 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(184 kB)3 downloads
File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 296 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 46 hits
ReferencesLink to record
Permanent link

Direct link