License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.16
URN: urn:nbn:de:0030-drops-177589
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17758/
Keppeler, Jens ;
Schwentick, Thomas ;
Spinrath, Christopher
Work-Efficient Query Evaluation with PRAMs
Abstract
The paper studies query evaluation in parallel constant time in the PRAM model. While it is well-known that all relational algebra queries can be evaluated in constant time on an appropriate CRCW-PRAM, this paper is interested in the efficiency of evaluation algorithms, that is, in the number of processors or, asymptotically equivalent, in the work. Naive evaluation in the parallel setting results in huge (polynomial) bounds on the work of such algorithms and in presentations of the result sets that can be extremely scattered in memory. The paper first discusses some obstacles for constant time PRAM query evaluation. It presents algorithms for relational operators that are considerably more efficient than the naive approaches. Further it explores three settings, in which efficient sequential query evaluation algorithms exist: acyclic queries, semi-join algebra queries, and join queries - the latter in the worst-case optimal framework. Under natural assumptions on the representation of the database, the work of the given algorithms matches the best sequential algorithms in the case of semi-join queries, and it comes close in the other two settings. An important tool is the compaction technique from Hagerup (1992).
BibTeX - Entry
@InProceedings{keppeler_et_al:LIPIcs.ICDT.2023.16,
author = {Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher},
title = {{Work-Efficient Query Evaluation with PRAMs}},
booktitle = {26th International Conference on Database Theory (ICDT 2023)},
pages = {16:1--16:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-270-9},
ISSN = {1868-8969},
year = {2023},
volume = {255},
editor = {Geerts, Floris and Vandevoort, Brecht},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17758},
URN = {urn:nbn:de:0030-drops-177589},
doi = {10.4230/LIPIcs.ICDT.2023.16},
annote = {Keywords: PRAM, query evaluation, work-efficient, parallel, acyclic queries, free-connex queries}
}
|
Keywords: |
|
PRAM, query evaluation, work-efficient, parallel, acyclic queries, free-connex queries |
|
Collection: |
|
26th International Conference on Database Theory (ICDT 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
17.03.2023 |
