TY - GEN

T1 - Implementing Window Functions in a Column-Store with Late Materialization

AU - Mukhaleva, Nadezhda

AU - Grigorev, Valentin

AU - Chernishev, George

PY - 2019/1/1

Y1 - 2019/1/1

N2 - A window function is a generalization of the aggregation operation. Unlike aggregation, the cardinality of its output is always the same as the cardinality of input. That is, the semantics of this operator imply computing values for extra attributes for each row, depending on its context, either expressed by a sliding window or a previously evaluated row. Window functions are a very powerful tool, which is also popular among data analysts and supported by the majority of industrial DBMSes. It allows to gracefully express quite complex use-cases, such as running sums and averages, local maximum and minimum, and different types of ranking. Since they can be expressed without self-joins and correlated subqueries, their evaluation can be performed much more efficiently. In this paper we discuss an implementation of window functions inside a disk-based column-store with late materialization. Late materialization is a technique that aims to keep tuple reconstruction back from individual columns as long as possible. Initially popular in the late 00’s, it is rarely considered nowadays. However, in case of window functions it allows to substantially lower memory footprint. Another contribution of this paper is the application of a segment tree to computing RANGE-based window functions.

AB - A window function is a generalization of the aggregation operation. Unlike aggregation, the cardinality of its output is always the same as the cardinality of input. That is, the semantics of this operator imply computing values for extra attributes for each row, depending on its context, either expressed by a sliding window or a previously evaluated row. Window functions are a very powerful tool, which is also popular among data analysts and supported by the majority of industrial DBMSes. It allows to gracefully express quite complex use-cases, such as running sums and averages, local maximum and minimum, and different types of ranking. Since they can be expressed without self-joins and correlated subqueries, their evaluation can be performed much more efficiently. In this paper we discuss an implementation of window functions inside a disk-based column-store with late materialization. Late materialization is a technique that aims to keep tuple reconstruction back from individual columns as long as possible. Initially popular in the late 00’s, it is rarely considered nowadays. However, in case of window functions it allows to substantially lower memory footprint. Another contribution of this paper is the application of a segment tree to computing RANGE-based window functions.

KW - Aggregation

KW - Analytical function

KW - Column-store

KW - Late materialization

KW - OLAP

KW - PosDB

KW - Query processing

KW - Window function

UR - http://www.scopus.com/inward/record.url?scp=85075860707&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/implementing-window-functions-columnstore-late-materialization

U2 - 10.1007/978-3-030-32065-2_21

DO - 10.1007/978-3-030-32065-2_21

M3 - Conference contribution

AN - SCOPUS:85075860707

SN - 9783030320645

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 303

EP - 313

BT - Model and Data Engineering- 9th International Conference, MEDI 2019, Proceedings

A2 - Schewe, Klaus-Dieter

A2 - Singh, Neeraj Kumar

PB - Springer Nature

T2 - 9th International Conference on Model and Data Engineering, MEDI 2019

Y2 - 28 October 2019 through 31 October 2019

ER -