Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Interleaving with coroutines: a systematic and practical approach to hide memory latency in index joins
 
research article

Interleaving with coroutines: a systematic and practical approach to hide memory latency in index joins

Psaropoulos, Georgios  
•
Legler, Thomas
•
May, Norman
Show more
2019
The VLDB Journal

Index joins present a case of pointer-chasing code that causes data cache misses. In principle, we can hide these cache misses by overlapping them with computation: The lookups involved in an index join are parallel tasks whose execution can be interleaved, so that, when a cache miss occurs in one task, the processor executes independent instructions from another one. Yet, the literature provides no concrete performance model for such interleaved execution and, more importantly, production systems still waste processor cycles on cache misses because (a) hardware and compiler limitations prohibit automatic task interleaving and (b) existing techniques that involve the programmer produce unmaintainable code and are thus avoided in practice. In this paper, we address these shortcomings: we model interleaved execution explaining how to estimate the speedup of any interleaving technique, and we propose interleaving with coroutines, i.e., functions that suspend their execution for later resumption. We deploy coroutines on index joins running in SAP HANA and show that interleaving with coroutines performs like other state-of-the-art techniques, retains close resemblance to the original code, and supports both interleaved and non-interleaved execution in the same implementation. Thus, we establish the first systematic and practical approach for interleaving index joins of any type.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00778-018-0533-6
Author(s)
Psaropoulos, Georgios  
•
Legler, Thomas
•
May, Norman
•
Ailamaki, Anastasia
Date Issued

2019

Published in
The VLDB Journal
Volume

28

Start page

451

End page

471

Subjects

Interleaving

•

Coroutines

•

Pointer-chasing

•

Main memory accesses

•

Data cache misses

•

Memory latency

•

Main memory databases

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DIAS  
Available on Infoscience
December 14, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/152969
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés