A new window Clause for SQL++

Each window is defined by its two boundaries: start (which comes first) and end (which comes later in the sequence order). The data sequence order is thus crucial. A window boundary occurs when one of the following events happen: (1) a new tuple arrives, or (2) some system time has elapsed (e.g. after 20 min or at the start of the hour). Case (1) refers to the event time, while case (2) refers to the processing time, i.e., the system time when a tuple is processed. In a streaming environment, window boundaries can also be created based on a system clock (and not only based on a new tuple’s attribute values).

Creating windows over stored data requires that the data is first ordered based on some attribute value; that is, data needs to be sorted first if it is not already ordered. This is typically the tuple’s event time. Thus in a stored data environment, window boundaries are defined based on event time. Another difference between streaming and stored data windows is that in a streaming environment, tuples may arrive late (and thus out of sequence order) and will be eliminated from the window results.

Depending on the relative positions of the window boundaries different window types have been discussed in the literature; the most common ones are sliding, tumbling, landmark and sessions [2, 27, 32]. In sliding windows a tuple can belong to many individual windows (thus windows can overlap). In contrast, in tumbling windows each tuple can participate in at most one window (i.e., windows do not overlap). Landmark windows are considered as a special case of sliding where every window’s start is fixed at a specific “landmark” (time or tuple), typically the start of the ordered sequence [27, 32]. Multiple landmarks are also possible [9]. The notion of sessions has been used in streaming systems to capture periods of specific activity in the data sequence; e.g. tuples that arrive close to each other, say within 5 min. Sessions are special cases of tumbling windows and are typically defined using a timeout (and possibly a window maximum duration) [2, 17, 36].

This paper concentrates mainly on sliding and tumbling windows as they are the most commonly used in practice. In addition, we discuss how to support typical session windows in Sect. 4.3.

Early streaming systems such as Aurora [1], TelegraphCQ [14] and STREAM [39] were the first to define windows as a way to process the incoming data into smaller analyzable subsets. More recent streaming systems focus on using partitioning to improve latency and throughput, e.g. Spark [41], Storm [22] and Flink [11]. Other works consider hardware optimization [13, 25, 28, 36]; examples are Saber focusing on GPUs and Streambox focusing on multi-core processors. There is also work on window aggregation [34, 35, 37], how to process out of order data in a window [2, 35, 42], and watermarks which determine how late data can arrive and still be processed by a window [5].

Most streaming systems have their own way of expressing windows and this differs between systems. There are two main approaches: using dataflow languages or SQL-like languages. The dataflow languages mainly follow an approach similar to the Google Dataflow Model [2]: they create operators for the windows, add properties to these operators and follow a Directed Acyclic Graph approach to process these windows over the streaming data. Examples include Aurora [1], Flink’s Data Stream API [11], Streambox [28], Microsoft Trill [13] and IBM’s SPL (Stream Processing Language) [20].

One early example of an SQL-like window language is STREAM’s Continuous Query Language (CQL) [4] which supported the creation of sliding windows in the FROM Clause by allowing the user to specify either time-based windows using the RANGE keyword or row-based windows using the ROWS keyword.

Another example appears in [27] where they model windows using RANGE, SLIDE, and WATTR. RANGE defines the window length in tuples or duration, SLIDE determines how far from the start of the previous window to start a new window in tuples or duration, and WATTR is the ordering attribute to order the data. Note that while this approach is intuitive and simple for the user to define windows, it is limited to creating fixed size windows.

As more stream processing systems were created, there has been work to develop a streaming SQL standard [23]. A streaming SQL example can be found in Apache Calcite’s SQL [6], used by projects such as Flink [11] and Samza [31]. In Calcite, the SQL OVER Clause is still used to create tuple-based sliding windows. However, Calcite also supports other window types such as tumbling and hopping (a sliding window using the system clock). These can be implemented through the use of the TUMBLE or HOP keywords in the GROUP BY Clause along with their parameters: the ordering attribute, the window length, and a window slide (for hopping windows). These windows are grouped together based on their ending tuple, as it is impossible to know when a window is complete before the last tuple closes it, and can be accessed in the SELECT Clause through the keywords TUMBLE_END or HOP_END respectively using the same parameters to find the grouping value.

Note that representing hopping windows in GROUP BY violates the relational semantics of SQL since in GROUP BY each input tuple belongs to exactly one group, which is not the case in hopping windows that are special cases of sliding windows. A proposed variation for streaming SQL [7] addresses this issue by moving the window creation (using TUMBLE or HOP) into the FROM Clause using table valued functions. Another feature of this approach is the use of EMIT that allows the user to control when results are output based on an event or system time.

Windows in stored data environments have been expressed using SQL for relational data and XQuery for semistructured data.

Since the OVER Clause was added to the SQL standard [43], window functions have attracted increasing interest and are implemented by the major database vendors. According to a 2016 survey, SQL window queries accounted for 4% of all queries in a workload collected from a multi-year deployment of a database-as-a-service platform [24]. A characteristic of SQL OVER is that it creates a window for each tuple in the sequence. There is also work on optimizing SQL OVER in a parallel environment [8, 10, 26] and on speeding up window queries using global sampling [33], holistic aggregates [38] and reducing data transfer [15]. A disadvantage of SQL OVER is that it is not as intuitive (from a usability perspective) for writing window queries. Various SQL concepts (like ORDER BY, GROUP BY) are reused within the OVER Clause, making window query writing quite challenging.

Another approach to writing window queries in SQL is by using the MATCH_RECOGNIZE Clause [29], which is used to identify events in a time sequence. MATCH_RECOGNIZE accepts a set of rows as input, and returns all matches for a given data pattern. It can thus identify windows that match a specific data pattern. MATCH_RECOGNIZE is used within FROM and effectively creates an elaborate sub-query on its own, which makes it even more complex and less intuitive than OVER for writing window queries. Note that MATCH_RECOGNIZE can express all of the OVER and WindowBy example queries used in this paper. However, it results in queries that are very difficult to optimize (see the discussion in [16] about the optimizer). There has been some work to optimize parts of MATCH_RECOGNIZE for queries with specific conditions and no duplicates [44].

Finally, XQuery has been extended to support window queries over stored semi-structured data [9]; here the order is the binding sequence provided by the document. XQuery windowing is different from SQL in that it uses a predicate based approach to define the start and end of a window. This is very powerful as it allows the user to create a window using a predicate on a tuple’s attribute values (i.e. a window does not need to be based on the only sequence order as in SQL OVER). It also allows the user to choose what type of window to use: tumbling, sliding or landmark. Note that the latest XQuery 3.1 standard Window Clause [40] does not support landmark windows. There has also been work to extend XQuery to allow patterns between the window start and end [18]. To the best of our knowledge there is no work extending XQuery windowing in a scalable way for parallel systems.

The SQL OVER Clause defines windows using a required window function (or aggregate function) and three optional parts: partitioning, ordering and framing [26, 43]. Partitioning comes first and groups the data so as to create different sequences; one per grouping key. Ordering these creates the ordered sequences. While optional, ordering is crucial for windowing; without ordering, SQL window queries could provide different results every time they run. Finally, framing is used to build windows on top of each ordered sequence. Examples of the required window function include built-in such as AVG or user-defined aggregates, as well as built-in functions for windows such as ROW_NUMBER). The OVER Clause can be used in the SELECT or ORDER BY Clauses. If the OVER Clause appears in SELECT, the result of the window function is appended (as an attribute) to the output tuple. If OVER is used within ORDER BY, the window function is first computed and then used to determine the order of the result.

An advantage of SQL OVER is that the use of ordering and partitioning allow the user to create ordered sequences as needed. The result of a window is appended to a single tuple in the ordered sequence. The advantage of framing is that it allows the user to pick window boundaries; these boundaries can be before, after or include the tuple that will append this window’s result. Consider as an example the window in Fig. 1a, which depicts a sliding window of size 3 tuples using the OVER Clause. To do so, in the SELECT, we used AVG as our window function followed by the OVER keyword. The parameters for OVER are followed by ORDER BY to sort by date and then the ROWS keyword to specify a framing. In this specific case, the framing is between CURRENT ROW and 2 FOLLOWING (3 tuples).

Note that OVER requires that every single tuple in the sequence creates a window; as a result, OVER is effectively limited to expressing sliding windows. In [27], tumbling windows are modeled as a special case of sliding windows where the RANGE of a window is equal to the SLIDE of that window (explained in Sect. 2). However, in the case of OVER, the SLIDE is always 1 tuple; thus, a tumbling window can occur only for a window size of length 1 tuple using the ROWS keyword, assuming there are no duplicates in the ordering attribute.

XQuery windowing, as part of the XQuery 3.0 Standard, consists of three required parts: a window type (tumbling or sliding), variables (start and end), and predicates (start and end). Note that XQuery uses the order of the binding sequence for its windowing hence no explicit ordering is needed. Variable access offers a major advantage to XQuery windowing as it allows the user to create windows on more than just the ordering attribute of the sequence. The variables enable access to the first and last tuple of the window and their positional variable (their numerical position in the ordered sequence). For each of the two tuples, XQuery also provides access to the tuple preceding or following that tuple. These tuple variables and positional variables can be referred to in the predicate (Boolean expression) used to start or end a window.

Moreover, XQuery allows the user to specify the window type (tumbling or sliding). Another advantage of XQuery is that it provides access to the whole window and its tuples through a user defined variable. Since data can be nested, this allows the user to return more than just an aggregation result over this window if needed. Nevertheless, in XQuery a window result always appends the tuple that started this window; this is a limitation since it does not allow a window to consider only tuples before (or after) its boundaries. Consider as an example the window in Fig. 1b, which depicts a sliding window of size 3 tuples using XQuery. To do so, we first use the keyword SLIDING WINDOW followed by the window result variable w. The start predicates contain the starting tuple of the window s and its position sp. The start predicate condition is to always start a window after the WHEN keyword. The end predicates include its position ep and the end predicate condition is when ep − sp = 2; which creates a window of size 3. This approach assumes that the dataset Ghcn is already ordered by time, and the user is also allowed to use the window variable w and the predicate variables s, sp and ep in forming the result.

A sketch of the grammar of our proposed WindowBy Clause appears in Fig. 2 (its semantics will be detailed in Sect. 3.3). Variables such as w, p and o are user defined and the user can change them. Its major (required) parts are window_properties (addressing desiderata (1) and (2)) and window_framing (covers (3) and (4)). Inspired by XQuery, the window properties allow the user to choose the window type (sliding or tumbling), and users can create ordered sequences as needed (inspired by OVER). The framing includes predicates (as in XQuery) and the ability to append the window result to any tuple in the sequence (as in OVER). Finally, the variable w enables accessing the tuples of a window, thus supporting desiderata (5) (as will further become clear through query examples). Combining the above advantages in the proposed WindowBY Clause will enable users to write a variety of useful and complex windows in an intuitive way (see Sect. 4).

Having identified the desiderata, we proceed to consider what language tools are needed for supporting them. An important difference between how SQL and XQuery handle windows is that XQuery uses a Clause to create windows while the SQL OVER approach, despite being named a Clause, is actually an expression. An expression is a language fragment that can be evaluated to return a single value [12]. Examples are boolean expressions, aggregate functions, numeric expressions etc. In SQL++, a query is made of several Clauses,such as SELECT, FROM, or GROUP BY, and each Clause does a specific task by consuming input tuples and producing output tuples. Clauses like FROM, WHERE, GROUP BY and HAVING are characterized as generators since they result in a stream of tuples. Clauses like ORDER BY, LIMIT and OFFSET are instead output modifiers since they do not create any new tuples; but can only order, limit or omit some of the tuples in the result stream. SELECT is special in that it constructs an output object for each tuple in its input.

Since OVER is an expression, it returns a single value (window result) per tuple; further, in SQL it can occur either in the SELECT or in the ORDER BY Clause. Being in either of these Clauses implies that the number of results tuples in the output stream is not changed by OVER; which simply attaches a window result to each tuple and in the case of ORDER BY, it orders the tuples using their window result. While this is fine for SQL windowing, since every tuple creates a window (i.e. each tuple is expanded with the window result), it will not suffice for WindowBy. As in XQuery, the WindowBy Clause should allow the user pick which tuples will create a window based on a predicate. An expression-based approach like OVER will not work; instead, a true Clause is needed for WindowBy.

Moreover, for each window, WindowBy should allow the user to access, using variables, the first and last tuple of the window as well as their positional variables, preceding tuple, and following tuple. Such variables are bounded as each window is considered. In SQL, the variables in scope (available attributes) are defined by the FROM Clause and stay in scope throughout the query block. Other Clauses in SQL cannot add new variables in scope; they can only place restrictions on which variables can be used in SELECT (e.g. as does the GROUP BY Clause). Hence, it would not be easy to add a new Clause to SQL Standard with our required desiderata.

We proceed by describing how the somewhat richer structure and semantics of SQL++ [12, 30] can help us avoid these shortcomings and can thus support all the desiderata of our WindowBy Clause. One significant difference from SQL is that SQL++ offers the ability to create or remove variables within each Clause as needed; i.e., variable creation is not limited to the FROM Clause.

Consider for example, GROUP BY. When used in SQL it restricts SELECT to use only the GROUP BY keys or aggregates. When used in SQL++, GROUP BY can also add new variables into the scope through the use of GROUP AS. As in SQL the GROUP BY Clause “hides” the original tuples in each group by exposing only the grouping keys and aggregation functions on the non-grouping fields; however its GROUP AS extension (used only within GROUP BY) makes the original tuples in the group visible to subsequent Clauses by creating a new variable. This allows a SQL++ query to generate output data both for the group as a whole and for the individual objects inside the group [12]. This is possible because SQL++ supports a nested data model.

As a result, SQL++ offers important advantages to support our WindowBy Clause as it naturally supports the variables needed to access various parts of the window and its contents. Finally note that the existing GROUP BY Clause even within SQL++ is not sufficient to support all of our windowing desiderata.

For example, desiderata (1) is not possible since ORDER BY happens after GROUP BY. Similarly, desiderata (2) fails since GROUP BY does not allow data to overlap between groups (and thus no sliding windows). Next is a detailed discussion of the WindowBy Clause semantics.

Figure 3 shows the top level SQL++ grammar extended to include our proposed WindowBy Clause. As WindowBy is an optional standalone Clause, the proposed extension does not affect/modify the results of any existing queries in SQL++. As can be seen from the figure, the WindowBy Clause is placed after GROUP BY. We designed WindowBy as a Clause to separate it from the SELECT Clause, which in our view reduces the complexity of writing window queries. Another important characteristic is that we allow the user to create, for each window w, predicate variables that refer to specific tuples/values in that window (e.g., starting tuple, its positional value etc.). Note that the result for each created window w is a complex tuple that contains all of the predicate variables for w as well as its data tuples as an ordered array, as can be seen in Fig. 10, box 3. The predicate variables and the window array for each w can then be used inside the SELECT clause so that the user can easily form the desired query result. Note that this requires a nested structure which cannot be expressed in traditional SQL; SQL++ has the advantage that it allows for nesting and makes it easy to create the desired window tuples. This allows the user to create windows over groups (if any). Note that this is similar to SQL where OVER is placed inside the SELECT or ORDER BY and thus applies to the results coming after GROUP BY.

As shown, the WindowBy Clause starts with the WINDOW BY reserved keyword followed by an identifier, the window properties and framing (Fig. 4a). The identifier is a user defined variable that can be referenced in later Clauses to access the window results; it is referred to as result variable below.

According to the SQL++ grammar (Fig. 3), ORDER BY occurs after the QueryBlock and hence after the WindowBy Clause. Thus, WindowBy needs to create its own ordered sequences and this is done through the properties section (Fig. 4b). In addition to ORDER BY, properties specify the TYPE of the window to be created (currently only sliding and tumbling are supported). There is also an optional partition section where the user can partition the data before ordering, based on a user specified expression.

The framing section is based on XQuery’s window Clause and it uses a predicate-based approach to create the window boundaries. There are three separate parts in framing (see Fig. 5a): the optional LABEL (to be discussed later), START and END. The START refers to the first tuple in the window, while END refers to the last one. They are each defined by the WindowByBoundary (Fig. 5b). Such a boundary can either by the keyword “UNBOUNDED” or a window predicate (Fig. 5c). “UNBOUNDED” allows the user to create windows that extend to the start or the end of the sequence of the partition. Like XQuery, the window boundary contains two parts: variables and an optional predicate (condition). The window variables (Fig. 6) for a START boundary correspond to the first tuple in the window (referred to by AS), its position in the sequence (AT; also termed as the positional variable), the tuple preceding the first tuple (PREV AS) and the tuple following the first tuple (NEXT AS). Similarly, for an END boundary these variables are relative to the last tuple of the window.

The optional window predicate (Fig. 5d), specified with the keyword WHEN, can use the above variables to form boolean conditions that start or end a window at a specific tuple. This removes the SQL OVER limitation that each tuple must start its own window. Given a finite ordered sequence, when the last tuple of the sequence is reached, there may be many windows whose END condition has not been met. By default, the WindowBy Clause will produce results for all windows whether they are ‘closed’ (these are windows for which a tuple was processed that matched the condition to END the window) or are still ‘open’ after the sequence is processed (no tuple in the sequence matched the END condition for this window). As in XQuery, when the ONLY keyword is used, the WindowBy Clause returns results only for the closed windows. After WindowBy, all variables preceding the WindowBy Clause go out of scope. Only variables introduced by WindowBy are available after it.

The concepts of partitioning, ordering and framing of the WindowBy Clause are visualized in Fig. 7 (following a similar approach from [26]). PARTITION BY separates the tuples into distinct groups, according to some attribute p in the Figure. Each partition is ordered by ORDER BY (using some attribute o) to create ordered sequences. The figure shows two ordered partitions with a window w created on one of these ordered partitions (w refers to the entire window framing). A user can create variables based on the start or the end tuple of a window, their positional values and their previous and next tuples. Window w starts from tuple t3 (denoted with variable startCurrentItem in the Figure) and ends at t7 (endCurrentItem). The positional variable for t3 (startCurrentPos) is 3 and for t7 (endCurrentPos) is 7. Variable startPreviousItem and startNextItem denote the previous and the next tuple of the start tuple. Similarly for endPreviousItem and endNextItem for the end tuple. A window consists of all tuples between the startCurrentItem and the endCurrentItem (within the same partition); in this example the window will consider all tuples between t3 and t7.

One limitation that the XQuery predicate-based approach has in framing is that a window’s result will always be appended to the tuple that started the window (first tuple in the window). To remove this limitation, the optional LABEL part was added in WindowBy (Fig. 5a). The label is used to denote the tuple that will include the appended the result; doing so allows the window boundaries to be before, after, or to include this tuple. If LABEL is not used, the WindowBy Clause will default to the label being the first tuple in the window (like XQuery). The variables in the LABEL window predicate reference the tuple that will have the result. These variables can be referenced later in the query.

Note that LABEL allows the WindowBy Clause to support queries that are possible in OVER but not in XQuery. Consider a generic SQL OVER query with framing. This framing can be separated into BETWEEN X and Y. X and Y can be either UNBOUNDED PRECEDING/FOLLOWING, CURRENT ROW, or n PRECEDING/FOLLOWING where n is a positive integer. If X is the current ROW, then in WindowBy the label refers to the start tuple. If instead the current row is in Y, then in WindowBy the label refers to the end tuple. As discussed earlier, in the WindowBy boundaries, the UNBOUNDED choice is allowed for both start and end. With access to the label variables and the start variables, representing in WindowBy a start condition in X for n PRECEDING or n FOLLOWING is simple to do by comparing the label variables with the start variables. Consider for example a ROW framing query where X is PRECEDING 5 in SQL OVER. Let’s assume that labelCurrentPos (startCurrentPos) corresponds to the label (start) positional variable (respectively) in WindowBy. The above OVER window boundary can be represented by having a WindowBy start condition of labelCurrentPos - startCurrentPos = 5, which implies that the start of the window is 5 tuples before the label. Likewise, the same can be represented for the case of Y of FOLLOWING 5 by having the end condition be endCurrentPos - labelCurrentPos = 5.

We now describe the nature of WindowBy variable bindings through an SQL++ query example. All window queries in this paper will be using a dataset from the Global Historical Climatology Network (GHCN) [19]. It contains measurements of climate data collected at stations across the world. In particular we will use the AsterixDB DDL that appears in Fig. 8; which contains a subset of all the attributes in the original GHCN table. Each GHCN tuple has four attributes: station, date, val, and dataType. Station corresponds to the id of the station that took the measurement, val refers to the reported measurement value, and dataType describes the type of the collected value. In our examples the measurement value “TMIN” corresponds to the minimum temperature collected by a station on the specific date. Other types of measurements that a station provides are maximum temperature, precipitation, snow depth, etc.

Consider the query: “When the value of TMIN in a specific station is less than 25 degrees, find the average value of TMIN over this measurement and the two following TMIN measurements of that station”. This is a sliding window (i.e., overlap between windows is allowed) with a window length of three tuples (including the starting tuple). The query using our WindowBy Clause appears in Fig. 9. There are three predicate variables declared: startCurrentItem which corresponds to the first tuple of the window, startCurrentPos which is the positional variable of this current tuple and endCurrentPos for the positional variable of the window’s last tuple. There is also the result variable w. ARRAY_AVG is a SQL++ aggregate function that computes the average for an array of tuples while ignoring missing or null values.

Figure 10 shows the Clauses’ output bindings for this WindowBy query. The FROM Clause outputs a bag of GHCN tuples (indicated as number 1 in the Figure) that becomes input to the WHERE Clause. For simplicity, we use integers to represent dates instead of the actual datetime values. Afterwards, the data is filtered to keep tuples that satisfy the expression in the WHERE Clause (dataType = “TMIN”). The output of WHERE becomes the input of the WindowBy Clause (number 2).

WindowBy will first partition the data by station. It will then order each partition by date (to create the ordered sequence) and then will create a (sliding) window for any input tuple that satisfies the starting condition (number 3). By construction, each window created is represented by a tuple that contains the following attributes: one attribute for each variable declared and one attribute to capture the result variable (providing the tuples of the window created). These variable’s values are bound as we sequentially process the data. When a tuple satisfies the start condition (the TMIN val is less than 25), its associated start variables startCurrentItem and startCurrentPos are bound to this tuple and its sequence position, respectively. When a tuple satisfies the ending condition, its associated end variable endCurrentPos is bound to this tuple’s sequence position. If the end of the sequence is reached, then any endCurrentPos variables are set to MISSING; MISSING is also appended to the result variable w of any unclosed window as shown in the figure.

In the example query in Fig. 10, WindowBy creates three windows, one starting at the tuple with the date 1 and val 20 for station 1, one starting at the tuple with the date 4 and val 23 for station 1, and one starting at date 1 and val 22 for station 2. In this example each window is represented by a tuple with the following four attributes: s (the first GHCN tuple of the window), sp (its position in the sequence), ep (the position of the last GHCN tuple in the window), and w (the result for this window that contains all the window’s GHCN tuples).

The first window in this example contains 3 GHCN tuples in w, those with dates (1, 2 and 4). Note that the tuple with station 1 and date 3 was removed by the WHERE Clause which causes the tuple with station 1 and tuple 4 to be the third tuple in this sequence. The case where a window is created but its end condition is never satisfied, is denoted in the output by using the keyword ‘MISSING’. This happens in the second window created for station 1 at date 4; note that the value of ep is MISSING. This window contains two GHCN tuples (with date 4 and 5) and since it never ended, the value MISSING is also added). The same occurs for the third window, created for station 2.

The window tuples resulting from the WindowBy Clause will then become input to the SELECT Clause which will then construct new tuples according to the user’s desired output (number 4). In particular, SELECT in the example outputs the station id of each window, the start time of the first tuple in the window and the average val of TMIN for over the tuples in the window. Note that attributes associated with variables introduced in the WindowBy (s and w) were used in the SELECT.

It is important to note that the above description provides a logical representation of how WindowBy computes the windows. Most windows (like the example shown) typically compute aggregates on the window tuples. As a result, the individual tuples within a window do not need to be materialized and carried forward (as in step 3; since step 4 only needs an average). A simple optimization will push the aggregation into the WindowBy processing thus avoiding actually materializing all the window tuples.

Different from sliding, tumbling windows do not allow overlap; while a window is open, no other windows can be created (i.e., a tuple can belong to at most one window). Note that OVER produces a window for each tuple in the input sequence. As a result, OVER will create sliding windows unless each window contains exactly 1 tuple (the starting tuple of the window), which is a degenerate case of tumbling windows. Below we examine two tumbling window examples that are the ‘tumbling’ version of sliding windows discussed in the previous section. In particular, an unbounded window and a window with fixed duration.

Sessions are special cases of tumbling windows modeling situations where there are periods of inactivity between subsequent windows and these periods are not included in the window results. Session windows involve the time order and group events that arrive at similar times; they have three parameters: timeout, maximum duration, and (an optional) partitioning key [17]. Partitioning is already part of our WindowBy Clause and a maximum duration is similar to the windows discussed in Sect. 4.2.2. Below we discuss how to represent windows with timeouts.

A timeout window query will continue accepting tuples until the time difference between arrivals of subsequent tuples is greater than the given timeout interval. For example, consider a window that remains open as long as subsequent tuples (from the same station) come within 5 min of each other. OVER cannot express this window because there is no mechanism to compare the difference in time between any arriving tuples; OVER only considers the time difference from the tuple that appends the result. This window is possible to express using WindowBy because the positional variables provide access to both a tuple and the tuple following it. The end condition ensures that the time difference between the last tuple of the window endCurrentItem and its subsequent tuple endNextItem is greater than 5 min (see Fig. 20).

This session query can also be expressed using a (much more complex) nested loop approach, very similar to the one taken for the unbounded tumbling window shown in Fig. 14b.

This section discusses two additional features in the WindowBy Clause, namely ONLY and LABEL.

Consider a WindowBy query creating sliding windows over an input sequence of n tuples; its output will contain between 0 and n windows (since not every tuple creates a window). As noted earlier, each window created is represented by a tuple that contains: one attribute for each variable declared (e.g. the starting and ending tuples and their positions) and one attribute to capture the result (all the tuples of the window created). For example in Fig. 10, the first window tuple (see box 3) has 4 attributes (startCurrentItem,startCurrentPos, endCurrentPos and w).

Consider first the case where the ordered sequence can be stored in a single node. Our basic WindowBy evaluation algorithm will sequentially process the tuples of this ordered sequence. For each tuple it will check whether the starting condition is satisfied, in which case it creates a new window. It then adds this tuple to any currently open windows (by ‘add’ we mean that this tuple is used in the calculation of the result of a window, typically an aggregate). Afterwards it checks if this tuple ends any open window(s), in which case it closes that window. For each window the variables for its start and end are assigned when the window is created/closed. Any windows that remain open after the entire tuple sequence is processed are reported in the output with the MISSING keyword added. If the ONLY option is used, then only closed windows are reported.

If the ordered sequence is too large to fit in a single node, it will be sliced into ordered subsequences, each handled by a different node. This creates an ordered node sequence, i.e., node NC1 followed by node NC2, followed by NC3, as shown in Fig. 21a (which also shows the tuples of the subsequence assigned to each node). Note that there are three ways that the windows can occur when the ordered sequence is distributed: (1) windows that start and end in the same node, (2) windows that start in a node but end in a later node, and (3) windows that start in a node but never end. In our approach, windows will be reported at the node where they started.

In this environment the WindowBy algorithm can create sliding windows in at most two passes. The first pass will use the previous single-node algorithm to find the locally completed windows within each node (i.e., those windows that start and end within the same node). Figure 21b, shows the finished windows after the first pass assuming the data is distributed in three nodes (NC1,NC2,NC3) as in Fig. 21a, assuming that the query is a sliding window of size 2 tuples. The windows shown in the figure follow the notation Wi-j:[list] where i corresponds to the NC where this window started, j is the id of this window within that NC and list provides the result tuples currently in this window. The finished windows in the first pass are W1-1, W2-1, W3-1 and W3-2 and correspond to windows that start and end within the same node. W1-1 is the first window created by NC1 and contains tuples 1 and 2. Node NC3 created 2 windows; the second one W3-2 has the list [6,MISSING] since it started at tuple 6 in the sequence and was open when the full sequence was processed (NC3 is the last node). Note that only the last node in the node sequence will add MISSING to its unfinished windows that did not close after processing its subsequence since this marks the end of the whole sequence. If every window can be completed locally, the algorithm ends in just one pass.

If there are windows that cannot be completed within a node (that is, windows that start in a given node but are still open when this node finished processing its subsequence), each node sends information about all its unfinished windows created after the first pass, to the nodes that are later in the node sequence; this is because such windows can end in any of the subsequent nodes (or remain open after the whole sequence is processed). In the example of Fig. 21b these are windows W1-2 and W2-2. For each unfinished window the information sent includes the window’s Wi-j identification and its start variables (but no window tuples are transferred).

In the second pass, each node works on any unfinished windows that it may have received from the first pass. A major difference with the first pass is that now, when processing a tuple, the algorithm does not check if this tuple starts a window; this was done in the first pass and all window starts are known. Each node will process every tuple in its subsequence. A given tuple will be considered by all the unfinished windows the NC received from the first pass as long as these windows are still open. Moreover, the algorithm will check if a given tuple ends any of those unfinished windows. If it does, the particular window is closed and it cannot consider any further tuples. The results of these windows are stored using the notation Wi-j.k:[list] where k corresponds to the id of the NC that computed the result for unfinished window Wi-j. In Fig. 21c there are three unfinished window results: in W1-2.2:[3], W1-2.3:[5], and W2-1.3:[5].

Using this information the node that started each window can now compute the final result for that window (Fig. 21d). For window W1-2, NC1 received results from NC2 (W1\(-\)2.2:[3]) and NC3 (W1\(-\)2.3:[5]) but the result from NC2 ends the window. Thus W1\(-\)2.3:[5] is discarded when calculating window W1-2.

The above distributed window algorithm can be easily updated in the case where LABEL is used; the difference is that now a node will send the information about its unfinished windows to nodes before or after it depending on the range of the window. A window will be reported by the node that contains the window’s label tuple.

A generic algorithm for calculating tumbling windows is to first calculate the set of sliding windows as above and then identify the tumbling windows using this set. To do so, all the boundaries of the sliding window are ordered and then sent to one node. The node can then sequentially identify the sequence of tumbling windows (another window cannot be open until the previous closes). Various optimizations are possible depending on the window query but this is out of this paper’s focus.

The following experiments consider the performance of windows with labels as well as session windows.

Consider the window with label example given in Fig. 17. This query represents a sliding window of length three tuples between the tuple preceding and the tuple after the current tuple, when the current tuple’s TMIN value is less than 25. The experimental results appear in Fig. 27. The performance of the label sliding window in WindowBy is slightly slower by 15% than a plain (no-label) sliding window case (say Fig. 23) because additional communication is now required with nodes before the current node (in addition to nodes after it). In our initial implementation a node sends unfinished windows to all nodes that require them and in this case, it sends them to all nodes before and after itself; as before, optimizations can be applied to reduce that communication but this is left for future work.

We next experimented with a session window with timeout using the query shown in Fig. 20. This query cannot be written using OVER because there is no mechanism to compare the difference in time between arriving tuples. It can be written using a rather complex SQL++ nested approach. (see Fig. 33 in the “Appendix”). The query performance between the WindowBy and nested approaches appears in Fig. 28. As with the tumbling unbounded window performance (of which sessions is a special case) the WindowBy approach is faster than the nested one.

Finally we examined how well our implementation of the WindowBy Clause scales. For the scale-up experiments we used three window examples: the sliding window with fixed duration of 1 week (from Fig. 11), the tumbling version of the same window (from Fig. 16) and a label window (from Fig. 17). In particular we started with one node handling a dataset of size 400 GB and continued doubling the number of nodes and the size of the overall dataset, while keeping the dataset size per node at 400 GB (that is, two nodes handled 800 GB, 4 nodes 1.6TB etc.) The query performance results appear in Fig. 29. As it can be seen our WindowBy implementation achieves good scale-up performance; the query execution time remains roughly the same, which means that the additional data is processed in roughly the same amount of time.