DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2025.27

Parallel Query Processing with Heterogeneous Machines

Authors: Simon Frisk and Paraschos Koutris

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

We study the problem of computing a full Conjunctive Query in parallel using p heterogeneous machines. Our computational model is similar to the MPC model, but each machine has its own cost function mapping from the number of bits it receives to a cost. An optimal algorithm should minimize the maximum cost across all machines. We consider algorithms over a single communication round and give a lower bound and matching upper bound for databases where each relation has the same cardinality. We do this for both linear cost functions like in previous work, but also for more general cost functions. For databases with relations of different cardinalities, we also find a lower bound, and give matching upper bounds for specific queries like the cartesian product, the join, the star query, and the triangle query. Our approach is inspired by the HyperCube algorithm, but there are additional challenges involved when machines have heterogeneous cost functions.

Cite as

Simon Frisk and Paraschos Koutris. Parallel Query Processing with Heterogeneous Machines. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{frisk_et_al:LIPIcs.ICDT.2025.27,
  author =	{Frisk, Simon and Koutris, Paraschos},
  title =	{{Parallel Query Processing with Heterogeneous Machines}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.27},
  URN =		{urn:nbn:de:0030-drops-229683},
  doi =		{10.4230/LIPIcs.ICDT.2025.27},
  annote =	{Keywords: Joins, Massively Parallel Computation, Heterogeneous}
}

Search Results

Documents authored by Frisk, Simon

Parallel Query Processing with Heterogeneous Machines

Abstract

Cite as

Thanks for your feedback!

Could not send message