Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Reaching back to move forward: using old ideas to achieve a new level of query optimization
University of Oxford, United Kingdom.
University of Oxford, United Kingdom.
TU Wien, Austria.
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-7742-0439
Show others and affiliations
2023 (English)In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), CEUR-WS , 2023, article id 6Conference paper, Published paper (Refereed)
Abstract [en]

Join queries involving many relations pose a severe challenge to today's query optimisation techniques. To some extent, this is due to the fact that these techniques do not pay sufficient attention to structural properties of the query. In stark contrast, the Database Theory community has intensively studied structural properties of queries (such as acyclicity and various notions of width) and proposed efficient query evaluation techniques through variants of Yannakakis' algorithm for many years. However, although most queries in practice actually are acyclic or have low width, structure-guided query evaluation techniques based on Yannakakis' algorithm have not found their way into mainstream database technology yet.

The goal of this work is to address this gap between theory and practice. We want to analyse the potential of considering the query structure for speeding up modern DBMSs in cases that have been traditionally challenging. To this end, we propose a rewriting of SQL queries into a sequence of SQL statements that force the DBMS to follow a Yannakakis-style query execution. Through first empirical results we show that structure-guided query evaluation can indeed make the evaluation of many difficult join queries significantly faster.

Place, publisher, year, edition, pages
CEUR-WS , 2023. article id 6
Series
CEUR Workshop proceedings, ISSN 1613-0073 ; 3409
Keywords [en]
large join queries, query optimization, Yannakakis' algorithm
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-211822Scopus ID: 2-s2.0-85162848779OAI: oai:DiVA.org:umu-211822DiVA, id: diva2:1781848
Conference
15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Available from: 2023-07-11 Created: 2023-07-11 Last updated: 2024-07-02Bibliographically approved

Open Access in DiVA

fulltext(932 kB)63 downloads
File information
File name FULLTEXT01.pdfFile size 932 kBChecksum SHA-512
a61712d871698914c240032f4b08421a2e56bd4da8c7a03dd698d246d14006e981fd941d03c605e3b1957106177aed109739fc949ebdaaf040a4eaf7bb7d1fb1
Type fulltextMimetype application/pdf

Other links

ScopusProceedings

Authority records

Okulmus, Cem

Search in DiVA

By author/editor
Okulmus, Cem
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 63 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

urn-nbn

Altmetric score

urn-nbn
Total: 287 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf