Hammer Slide: Work- and CPU-efficient Streaming Window Aggregation
File(s)
Accepted version
Author(s)
Theodorakis, Georgios
Koliousis, Alexandros
Pietzuch, Peter R
Pirk, Holger
Type
Conference Paper
Abstract
The computation of sliding window aggregates is one of the core
functionalities of stream processing systems. Presently, there are
two classes of approaches to evaluating them. The first is non-
incremental, i.e., every window is evaluated in isolation even if
overlapping windows provide opportunities for work-sharing. While
not algorithmically efficient, this class of algorithm is usually very
CPU efficient. The other approach is incremental: to the amount
possible, the result of one window evaluation is used to help with
the evaluation of the next window. While algorithmically efficient,
the inherent control-dependencies in the CPU instruction stream
make this highly CPU inefficient.
In this paper, we analyse the state of the art in efficient incre-
mental window processing and extend the fastest known algorithm,
the Two-Stacks approach with known as well as novel optimisa-
tions. These include SIMD-parallel processing, internal data struc-
ture decomposition and data minimalism. We find that, thus opti-
mised, our incremental window aggregation algorithm outperforms
the state-of-the-art incremental algorithm by up to
11
×
. In ad-
dition, it is at least competitive and often significantly (up to
80%
)
faster than a non-incremental algorithm. Consequently, stream pro-
cessing systems can use our proposed algorithm to cover incremen-
tal as well as non-incremental aggregation resulting in systems that
are simpler as well as faster.
functionalities of stream processing systems. Presently, there are
two classes of approaches to evaluating them. The first is non-
incremental, i.e., every window is evaluated in isolation even if
overlapping windows provide opportunities for work-sharing. While
not algorithmically efficient, this class of algorithm is usually very
CPU efficient. The other approach is incremental: to the amount
possible, the result of one window evaluation is used to help with
the evaluation of the next window. While algorithmically efficient,
the inherent control-dependencies in the CPU instruction stream
make this highly CPU inefficient.
In this paper, we analyse the state of the art in efficient incre-
mental window processing and extend the fastest known algorithm,
the Two-Stacks approach with known as well as novel optimisa-
tions. These include SIMD-parallel processing, internal data struc-
ture decomposition and data minimalism. We find that, thus opti-
mised, our incremental window aggregation algorithm outperforms
the state-of-the-art incremental algorithm by up to
11
×
. In ad-
dition, it is at least competitive and often significantly (up to
80%
)
faster than a non-incremental algorithm. Consequently, stream pro-
cessing systems can use our proposed algorithm to cover incremen-
tal as well as non-incremental aggregation resulting in systems that
are simpler as well as faster.
Editor(s)
Bordawekar, Rajesh
Lahiri, Tirthankar
Date Issued
2018
Date Acceptance
2018-06-29
Citation
International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures, ADMS@VLDB 2018, Rio de Janeiro, Brazil, August 27, 2018, 2018, pp.34-41
Start Page
34
End Page
41
Journal / Book Title
International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures, ADMS@VLDB 2018, Rio de Janeiro, Brazil, August 27, 2018
Copyright Statement
© 2018 The Author(s)
Identifier
https://grtheod.github.io/
Source
International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures, ADMS@VLDB 2018, Rio de Janeiro, Brazil, August 27, 2018
Publication Status
Published
Start Date
2018-08-27
Coverage Spatial
Rio de Janeiro, Brazil