Document Open Access Logo

Work-Efficient Query Evaluation with PRAMs

Authors Jens Keppeler, Thomas Schwentick , Christopher Spinrath

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.16.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Jens Keppeler
  • TU Dortmund University, Germany
Thomas Schwentick
  • TU Dortmund University, Germany
Christopher Spinrath
  • TU Dortmund University, Germany

Acknowledgements

We are grateful to Uri Zwick for clarifications regarding results in [Tal Goldberg and Uri Zwick, 1995] and to Jonas Schmidt and Jennifer Todtenhoefer for careful proofreading. We thank Martin Dietzfelbinger for helpful discussions. Furthermore, we thank the reviewers of ICDT for many insightful suggestions.

Cite AsGet BibTex

Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Work-Efficient Query Evaluation with PRAMs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICDT.2023.16

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
  • Theory of computation → Database query processing and optimization (theory)
Keywords
  • PRAM
  • query evaluation
  • work-efficient
  • parallel
  • acyclic queries
  • free-connex queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • The full version of this paper contains some proofs and additional details omitted in this version due to space constraints.
  • Full Version https://arxiv.org/abs/2301.08178

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  2. Miklós Ajtai. Σ₁¹ formulae on finite structures. Ann. of Pure and Applied Logic, 24:1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
  3. Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris. Database Theory. Open source at https://github.com/pdm-book/community, 2021. Preliminary Version, August 19, 2022.
  4. Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM J. Comput., 42(4):1737-1767, 2013. URL: https://doi.org/10.1137/110859440.
  5. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208-222. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74915-8_18.
  6. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. J. Comput. Syst. Sci., 41(3):274-306, 1990. URL: https://doi.org/10.1016/0022-0000(90)90022-D.
  7. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. J. ACM, 64(6):40:1-40:58, 2017. URL: https://doi.org/10.1145/3125644.
  8. Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News, 7(1):4-33, 2020. URL: https://doi.org/10.1145/3385634.3385636.
  9. Johann Brault-Baron. De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre. Theses, Université de Caen, April 2013. URL: https://hal.archives-ouvertes.fr/tel-01081392.
  10. Zhiyuan Chen, Johannes Gehrke, and Flip Korn. Query optimization in compressed database systems. In Sharad Mehrotra and Timos K. Sellis, editors, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001, pages 271-282. ACM, 2001. URL: https://doi.org/10.1145/375663.375692.
  11. E. F. Codd. Relational completeness of data base sublanguages. In R. Rustin, editor, Database Systems, pages 33-64. Prentice-Hall, 1972. Google Scholar
  12. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
  13. Tal Goldberg and Uri Zwick. Optimal deterministic approximate parallel prefix sums and their applications. In Third Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings, pages 220-228. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/ISTCS.1995.377028.
  14. Torben Hagerup. On a compaction theorem of Ragde. Inf. Process. Lett., 43(6):335-340, 1992. URL: https://doi.org/10.1016/0020-0190(92)90121-B.
  15. Xiao Hu and Ke Yi. Massively parallel join algorithms. SIGMOD Rec., 49(3):6-17, 2020. URL: https://doi.org/10.1145/3444831.3444833.
  16. Neil Immerman. Expressibility and parallel complexity. SIAM J. Comput., 18(3):625-638, 1989. URL: https://doi.org/10.1137/0218043.
  17. Neil Immerman. Descriptive Complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
  18. Joseph F. JáJá. An Introduction to Parallel Algorithms. Addison-Wesley, 1992. Google Scholar
  19. Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Work-efficient query evaluation with PRAMs, 2023. URL: https://doi.org/10.48550/ARXIV.2301.08178.
  20. Paraschos Koutris, Semih Salihoglu, and Dan Suciu. Algorithmic aspects of parallel data processing. Found. Trends Databases, 8(4):239-370, 2018. URL: https://doi.org/10.1561/1900000055.
  21. Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz, and Jan Van den Bussche. The semijoin algebra and the guarded fragment. Journal of Logic, Language and Information, 14(3):331-343, 2005. URL: https://doi.org/10.1007/s10849-005-5789-8.
  22. Philip D. MacKenzie. Load balancing requires omega(log^*n) expected time. In Greg N. Frederickson, editor, Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA, pages 94-99. ACM/SIAM, 1992. URL: http://dl.acm.org/citation.cfm?id=139404.139425.
  23. Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms. J. ACM, 65(3):16:1-16:40, 2018. URL: https://doi.org/10.1145/3180143.
  24. Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 721-730, 2008. URL: https://doi.org/10.1145/1374376.1374480.
  25. Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, and Thomas Zeume. Work-sensitive dynamic complexity of formal languages. In Stefan Kiefer and Christine Tasson, editors, Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021, volume 12650 of Lecture Notes in Computer Science, pages 490-509. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-71995-1_25.
  26. Peter van Emde Boas. Machine models and simulation. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pages 1-66. Elsevier and MIT Press, 1990. Google Scholar
  27. Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96-106. OpenProceedings.org, 2014 . URL: https://doi.org/10.5441/002/icdt.2014.13.
  28. Yilei Wang and Ke Yi. Query evaluation by circuits. In Leonid Libkin and Pablo Barceló, editors, PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 67-78. ACM, 2022. URL: https://doi.org/10.1145/3517804.3524142.
  29. Mihalis Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings, pages 82-94. IEEE Computer Society, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact