{'fraction_non_alphanumeric': 0.03378606796985304, 'fraction_numerical': 0.006950106389325273, 'mean_word_length': 4.688309484757649, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems

The emergence of programmable data-plane targets has motivated a new hybrid design for network streaming analytics systems that combine these targets' fast packet processing speeds with the rich compute resources available at modern stream processors. However, these systems require careful query planning; that is, specifying the minute details of executing a given set of queries in a way that makes the best use of the limited resources and programmability offered by data-plane targets. We use such an existing system, Sonata, and real-world packet traces to understand how executing a fixed query workload is affected by the unknown dynamics of the traffic that defines the target's input workload. We observe that static query planning, as employed by Sonata, cannot handle even small changes in the input workload, wasting data-plane resources to the point where query execution is confined mainly to userspace. This paper presents the design and implementation of DynamiQ, a new network streaming analytics platform that employs dynamic query planning to deal with the dynamics of real-world input workloads. Specifically, we develop a suite of practical algorithms for (i) computing effective initial query plans (to start query execution) and (ii) enabling efficient updating of portions of such an initial query plan at runtime (to adapt to changes in the input workload). Using real-world packet traces as input workload, we show that compared to Sonata, DynamiQ reduces the stream processor's workload by two orders of magnitude.


Introduction
Networks supporting Internet-connected applications and devices have witnessed exponential growth in both scale and complexity. To effectively manage these networks, operators must keep track of both coarse and fine-grained aspects of network traffic from a variety of perspectives, e.g., devicespecific, service-specific, and aggregate. They use this information to detect and, ultimately, react to an increasingly diverse set of performance and security-related network events or requirements in near-real-time. Unfortunately, the number of required tasks and the speed at which they need to be executed exceed the capabilities of human operators and have motivated many network service providers to consider taking humans "out-of-the-loop" altogether through automation. To achieve this objective, today's networks rely increasingly on modern network streaming analytics systems capable of running a large number and wide range of different queries at line rate for up to billions of packets per second.
A common feature of many of these systems leverages programmable data plane targets (e.g., Intel Tofino [36]), which are capable of executing some or all parts of different queries at line rate. These devices can also send intermediate results to state-of-the-art stream processors (e.g., Apache Flink [29]) for further back-end processing. Most of these hybrid systems (e.g., Marple [26], Newton [46], Sonata [10], UnivMon [23], etc.) specify how to break down the input queries into individual dataflow operators, how to compile these operators in the data plane, and how to combine the output of respective operators executed in the data plane with modern stream processors to answer various queries accurately. However, since modern programmable data planes are inelastic by design and highly constrained in terms of available hardware resources (e.g., memory, ALUs), these systems also need to decide how to partition the dataflow operators for each query between the data-plane target and the stream processor and how to allocate resources for the different dataflow operators in the data plane. This decisionmaking is often called query optimization or query planning, and its efficacy dictates a systems' ability to scale to higher data rates and a larger number of input queries.
Unfortunately, most of the existing hybrid systems only focus on the mechanisms of using data-plane targets for query execution, and do not consider query planning. For example, in the case of Marple [26], it is unclear how to configure the data-plane targets to support multiple queries for arbitrary traffic workloads. In contrast, Sonata [10] supports query planning by deciding how to iteratively refine the input queries such that data-plane targets selectively spend limited resources on the traffic of interest (iterative refinement); how to map the queries' dataflow operators to stateful/stateless data structures in the data plane (operator mappings); and how to allocate resources to these data structures (resource allocation). However, Sonata's query planning is "static" or "early-binding" in nature; query planning decisions are made at compile time and not at runtime.
Though these "early bindings" minimize runtime complexity, they prevent the system from reacting to changes in traffic patterns over time and, therefore, cause the system to miss out on possible opportunities to reap scalability gains. This observation begs the question: can designing hybrid network streaming analytics systems based on more dynamic query planning improve these systems' scalability, and if so, how much?
In this paper, we answer that question in the affirmative by developing new query planning algorithms that combine query-specific iterative refinement with dynamic query planning and exploit the opportunities afforded by this unique combination. We can divide these algorithms into two categories: (1) bootstrapping algorithms for computing an initial query plan that is amenable to dynamic updates at compiletime, and (2) runtime algorithms for dynamically updating this initial query plan at runtime. To demonstrate their feasibility in practice, we integrate these algorithms into a Tofinobased prototype implementation DynamiQ. Figure 1 gives an overview of DynamiQ's architecture. This work makes the following concrete contributions: Traffic Dynamics Analysis (Section 2). We leverage packet-level traffic traces from real-world production networks to better understand static query-planning's limitations. In particular, we consider Sonata [10] and use a set of telemetry queries ( Table 2) to show that relying on static query plans can increase the amount of traffic sent to the stream processor by 3-4 orders of magnitude-the same amount of work produced by offloading query execution to the data plane in the first place. We also provide evidence that dynamically redistributing the memory allocated to different operators at runtime suffices to adapt to input workload dynamic-motivating DynamiQ's query-planning algorithms. Bootstrapping algorithms (Section 3). Recognizing that it is not possible to change query refinement decisions and some data-plane resource allocations at runtime (e.g., size of registers for stateful operations), computing effective refinement plans and data-plane resource allocations at compiletime is critical. Additionally, we must compute the same to be amenable to some runtime adjustment. To this end, we present the design and implementation of two algorithms that compute initial query refinement plans and data-plane resource allocations, respectively. We demonstrate that these algorithms have desirable properties, including the ability to find effective query plans for different input workloads and data-plane targets.
Runtime algorithms (Section 4). We present the design and implementation of two runtime algorithms for adapting to traffic dynamics. The first algorithm considers an operator's past memory requirements and estimates that operator's required memory for the future window. The second algorithm uses these predicted values to compute new operator mappings in the data plane dynamically. We demonstrate that this operator-mapping problem is NP-Hard and that, when implemented, these algorithms introduce modest overhead.
In Section 5, we describe how DynamiQ enables dynamic operator mapping using Intel's Tofino-based switch [36]. In Section 6, we use a set of realistic monitoring queries on publicly-available, real-world packet traces [7] to show that DynamiQ's query planning achieves near-optimal performance, reducing the stream processor's workload by more than two orders of magnitude, compared to the static query planning used by Sonata. We also demonstrate that the results are robust to input traffic and query workload, switch constraints, etc. We will make our prototype, code base and datasets publicly available to support additional research (Section 8).
This work does not raise any ethical issues.

Background and Motivation
In this section, we first describe how hybrid telemetry systems use query planning to compute static query plans. We then concretely explore the limitations of static query planning and argue for the need to develop dynamic query plans. We make use of the publicly-available code base of Sonata [40] to make these points.

Network Streaming Analytics Systems
The emergence of high-speed, programmable data-plane switches has motivated new, hybrid designs for network monitoring systems that combine these devices' fast packet processing speeds with the flexible and horizontally scalable data processing capabilities of modern stream processors (e.g., Apache Spark [35]). Such designs are especially desirable given the current trend towards automating network management and increasingly more complex management tasks requiring more fine-grained levels of monitoring and control. At the same time, these systems must cope with the limitations inherent in coupling programmable data plane targets with general-purpose CPUs. On the one hand, the former have much faster packet processing speed (in the Tbps range) than the latter, but their programmability is limited compared to general-purpose CPUs. On the other hand, data plane targets have limited compute resources (e.g., memory, processing stages, storage) that host-based CPU systems do not face. Further advances in data plane technology notwithstanding, the compute resources available to programmable 1 packetStream ( W ) 2 . map ( p => ( p . sIP, p . dIP ) ) 3 . distinct ( ) 4 . map ( ( sIP, dIP ) => ( sIP, 1 ) ) 5 . reduce ( keys = ( sIP, ) , f= sum ) 6 . filter ( ( sIP, count ) => count > Th ) Query 1. Detect superspreader hosts. Executing this query at at a coarser level (e.g. 8) entails adding a map operator that sets the last 24 bits of sIP to zero before line 2. data plane targets are considered precious and must be used judiciously for the foreseeable future.
Given the scarce resources available in the data plane, hybrid, network streaming analytics systems must carefully perform query planning; that is, given a set of network monitoring queries, the system must determine which portions of each query to execute where without compromising the queries' accuracy. Unlike the database research literature (e.g., see [14] and references therein), query planning has received little attention to date in the networking research literature and is largely absent from most existing network streaming analytics system (e.g., Marple [26], UnivMon [23] and others). However, we expect effective query planning to play a decisive role in determining the practicality of deploying these hardware-based network streaming analytics systems in production networks.

Case Study: Static Query Planning
An illustrative query as running example. Query 1 shows how network operators can use Sonata [10] to express the superspreader detection task as a dataflow query over a packet stream. Under the hood, Sonata's query planner divides a representative input workload in the form of packet traces into consecutive windows (e.g., 3 seconds). The planner first seeks to perform query refinement; this is a process of iteratively "zooming-in" over successive windows on portions of the traffic that satisfy the input query at a coarser level of granularity. Planning for query refinement boils down to exploring all refinement levels that the network operator allows and choosing the set of refinement levels that best reduce the workload for the stream processor without compromising accuracy. Refinement levels are based on the hierarchical structure inherent to specific keys in a query. For example in Query 1, source and destination IP addresses (sIP and dIP, respectively) inherently possess hierarchy. The finest refinement level would be an IP address with a /32-bit mask applied and all those ( < 32)-bit masks would be coarser levels. Of many, one candidate refinement plan could be: * → 8 → 32. In the first window, the /8-bit masked version of Query 1 executes by modifying the original query and inserting map(sIP => sIP/8) before line 2. In the immediately following window, the original input query, i.e., the /32-bit masked version of Query 1, is then executed for those source IP addresses that satisfied the query at the /8 refinement level. Note that query refinement reduces the amount of data plane resources required per-window at the cost of returning an answer to the original query with a slight delay; this delay is a function of the selected monitoring window and the length of the refinement plan. After selecting a refinement plan and augmenting Query 1 for the selected refinement levels, Sonata's query planner next focuses on query partitioning; it decides for each of the refined queries how to execute which subset of dataflow operators (e.g.,distinct, reduce, etc.) in the data plane. To make this decision, Sonata's query planner must map specific dataflow operators to data plane resources and how much of the finite switch memory to allocate for each operator. From packet traces to cost matrices. To compute this optimal query plan, Sonata's query planner generates for each window a cost matrix by synthesizing and executing versions of each refined query. Specifically, the cost matrix provides estimates of the amount of memory required and the number of packet tuples processed by each of the stateful operators used in each combination of all considered refinement and partitioning plans. If , , and denote the sets of queries, refinement levels, and stateful operators for query ∈ , respectively, then the total number of queries Sonata has to run to generate the cost matrix for one window is on the order of ∈ | | 2 * | |. In the case of Query 1, | |=2 (distinct and reduce) and we will assume a network operator-specified maximum refinement levels of | |=8. With these parameters, 56 different cost matrix values must be computed and evaluated just for Query 1. Clearly, computing cost matrices is expensive and, even with state-of-the-art data analytics systems (e.g., BigQuery [37]), computing them for one hour of packet traces takes around four hours. From cost matrices to query plans. Sonata's query planner then provides the cost matrices as input to an integer linear program (ILP). This ILP also takes various data-plane and ordering constraints into consideration when computing the query plan that minimizes the number of packets that are sent to the stream processor. More precisely, Sonata considers a Protocol Independent Switch Architecture(PISA)-based data-plane target[38], whose packet-processing pipeline is divided into multiple physical stages with finite resources. For stateful operations, this target uses stateful ALUs and SRAM memory, called registers, local to a single stage to update and maintain state, respectively. Packets use metadata fields to carry additional information, such as, intermediate query results, across different stages. Sonata's ILP formulation incorporates the following data plane constraints: amount of metadata that can be stored ( ), the number of stateful ALUs per stage ( ), the amount of stateful memory in bits per stage ( ), and the number of stages ( ). Solving this ILP yields a static query plan consisting of: (1) refinement plan, (2) operator mapping-between dataflow operators and data-plane components, and (3) register allocation-deciding how much of the scarce SRAM memory to allocate to each register for stateful operations in the data plane.

Limitations of Static Query Plans
For a given set of queries, Sonata assumes that neither the input workload (i.e., total number of packets arriving at the switch) nor the resulting workload for the computed query plan (i.e., cost matrices) change much or at all over time. As a result, Sonata's static query plan that was "trained" using historical packet traces from the network is assumed to also perform well in the future. Wasteful use of hardware resources. However, an empirical evaluation of Sonata's performance shows that this assumption does not hold in practice. In our evaluation, we use the set of input queries described in [10] and CAIDA's anonymized and unsampled packet traces [7] as input workload (see Section 6 for details). Figure 2a depicts the number of packets observed at the switch and the resulting tuples received at the stream processor over 60 successive threesecond windows. For this experiment, Sonata's query planner was trained on the input workload data from the first window only to highlight the perils of using a stale query plan. Though the query plan effectively reduced the number of tuples processed at the stream processor (blue line) from the number of packets processed at the switch by several orders of magnitude, using this stale query plan in successive windows resulted in an almost instantaneous workload increase at the stream processor. After the first window, the number of tuples processed at the stream processor is nearly in parity with the total input workload arriving at the switch (red line). Using a stale query plan trained on different windows as input shows similar behavior. Relying on Sonata'a static query planning can eliminate the benefit of partially executing query operators in the data plane and effectively relegates query execution to user space -similar to not having partitioned query execution to a programmable data plane in the first place.
Why are static query plans ineffective? To explain the root cause for why static query plans fail to reduce the number of tuples sent to the stream processor, we first examine how data plane resources are consumed with a stale query plan. If a static query plan works well for a given window ( ), there are three possible outcomes for each of the stateful operators in the subsequent window ( ′ ): the amount of memory required to execute the stateful operator in the data plane in window ′ is (1) less than, (2) more than, or (3) exactly the same as that required in window . Only in this last case does static query planning have a clear advantage.
The first case results in under-utilizing limited switch memory and introduces an opportunity cost-the wasted memory could have been allocated for other operators that need more memory in ′ . In the second case, all operators that Sonata cannot fit into the switch's finite memory cannot be fully executed in the data plane. This case is even more consequential for queries with more than one stateful operator; should there not be enough memory for the first operator to execute in the data plane, then all the packets from the first operator onward will be sent to the stream processor (see Appendix B). Nevertheless, case (2) also affords an opportunity cost-any stateful memory that had been allocated to any of the subsequent operators will go unused and could have been allocated to other operators that would benefit from more memory in ′ . Figure 2b visualizes how Sonata's static query plan fares over two consecutive windows (top) and ′ (bottom). Each window is shown as a horizontally-laid-out, stacked bar plot, where each block in a stacked bar plot represents a stateful operator; the block sizes are proportional to the amount of allocated memory as specified by the static query plan. The color signifies that operator's contribution to the number of tuples sent to the stream processor. Here, a cyan-colored block represents the first stateful operator whose output is processed in the data plane itself resulting in no contribution to the workload at the stream processor. On the other hand, a black-colored block represents the second (or some later) stateful operator that cannot be executed in the data plane because the first (or some previous) operator could not be allocated sufficient memory. We observe that 46% of all operators in this static query plan are over-provisioned (case 1) and 44% are under-provisioned (case 2). This analysis highlights static query plans' inability to adapt to variation in operator memory requirements from one window to the next. This inability leads to wasted data plane resources and causes a much higher workload at the stream processor for future windows compared to the window for which the static query plan was trained. Alternative static query planning techniques. We also considered alternative static query plans that enhance Sonata's query planner to more effectively handle workload dynamics. A detailed discussion of our explorations of these alternative static query planning techniques is presented in Appendix A. The main takeaway from these investigations is that while some of these techniques perform better than Sonata's solution, the gains are only marginal and highly sensitive to the input workload.

Dynamic Query Planning to the Rescue
Static query plans fail to adapt to the variability in the operators' memory requirements over time and are therefore a major roadblock towards effectively leveraging programmable data plane targets in support of network streaming analytics. To overcome the weaknesses of static query planning, we argue here for considering dynamic query planning and provide a short preview of how we incorporate dynamic query planning into the design of our new hybrid network streaming analytics system, DynamiQ. Redistributing memory at runtime. Figure 2b shows two successive windows to visualize the prevalence of underand over-provisioning of operator memory that results from static query planning; Figure 3a further illustrates this point. For each of the stateful operators in Sonata's static query plan, we quantify the variability of required memory across sixty consecutive windows using the coefficient of variance (CoV) and show the distribution of obtained CoV-values (red line). We observe that the CoV-values for the different operators exhibit significant variability, especially when compared with the low variability of the total memory required (blue line). Moreover, Figure 3b shows that high variability is not restricted to the smaller operators but that operators with a high memory footprint can also exhibit high variability. The low variability of the total memory combined with the high variability of the memory required for individual operators suggests that, for any window, the memory requirements for some operators increase while they decrease for the others. This observation also suggests that dynamically redistributing operators at runtime should more efficiently use available switch memory such that the operators that require more/less memory are assigned more/less resources.
Optimal, yet impractical, dynamic query planning. To dynamically redistribute operator memory at runtime, one approach is to use Sonata's query planner and compute a new query plan for each window separately. Although such an approach will output optimal query plans that minimize the load at the stream processor, the obtained plans are impractical. First, implementing these plans requires resizing register memory in the data plane. However, for most existing data-plane targets, resizing data-plane registers implies recompilation, meaning taking the switch offline for a few seconds [46]. Second, realizing these plans requires changing the queries' refinement plans at runtime which in turn adversely affects the queries' accuracy (see Appendix B for details). Lastly, computing these plans requires knowing each window's input data and resulting cost matrix prior to the beginning of a window-an impossible task. Our approach in a nutshell: DynamiQ. Given the opportunities that careful query planning affords and the practical constraints that modern data plane targets impose, we consider in this paper an approach to dynamic query planning where instead of changing the entire query plan, we only update operator mappings at runtime. In particular, our approach consists of fixing the refinement plan and register size configuration at compile time prior to running the queries and then dynamically changing the mapping between operators and data-plane registers at runtime. We show that such an approach efficiently uses the scarce data plane resources and can be implemented at runtime. First, we must compute both an initial refinement plan and an initial allocation of register sizes in a way that facilitates dynamically mapping operators to registers at runtime. We use the term bootstrapping to describe the process of determining these initial refinement plans and register size allocations. We then show that bootstrapping can be done in ways that are less sensitive to input workload dynamics and more dependent on the structure of the query workload, which we assume in this paper to be invariant over time (Section 3). To update the operator mappings at runtime, we need a learning model to predict the cost matrix for future windows. We then use these predicted values to compute new operator mappings in ways that incur minimal overheads (Section 4).

Bootstrapping Query Plans
Given that runtime changes of register sizes in the data plane and refinement plans are not feasible, we consider a purposefully-designed compile time "bootstrapping" effort. This effort consists of computing an initial refinement plan (Section 3.1) and initial register size allocation (Section 3.2) at compile time in ways that ultimately facilitate efficient operator mappings (i.e., memory redistribution) at runtime (Section 5).

Computing Refinement Plan
Total operator memory. We quantify a refinement plan's memory footprint using the metric of total operator memory (TOM), which is defined as the sum of memory required for all the stateful operators of a given refinement plan. Given the limits on the total available memory and the overall number of ALUs in the data plane, when selecting an effective initial refinement plan from among all considered plans, our goal should be to select one that has the smallest TOM-value and the fewest total number of stateful operators. To illustrate, in the case of our example Query 1, for the earlier considered   Table 1 shows that the memory requirements for the two stateful operators at the * → 8 and 8 → 32 levels are (523.7 K, 948.8 K) and (6.5 K, 14 M), respectively. Therefore, this plan's TOM value is 0.52 + 0.95 + 0.0065 + 14 ≈ 15.5 M. Also note that while the alternative refinement plan * → 16 → 32 has the same number of stateful operators, its TOM-value is about 50% lower (i.e., 7.2 M). Therefore, we would prefer to use the refinement plan * → 16 → 32 as it has a lower memory overhead. Relationship between TOM and total number of operators. To characterize the relationship between TOM and the number of operators, we use the cost matrices for the queries considered in Section 2 and performed the following experiment. For a given number of operators ( ), we consider for each window the refinement plans that are pertinent to these operators and select the refinement plan for which the mean of all TOM-values across all windows is minimum (min-mean-TOM). We repeat this experiment for each , starting with the minimum value that is determined by the number of operators required to execute all queries at the finest refinement level (i.e., /32) and ending with the maximum value that is configuration-specific and is capped by the number of available ALUs (registers) in the data plane target used (i.e., 72). Figure 4a shows that the min-mean-TOM values decrease as the number of operators ( ) increases. It shows that refinement plans with smaller TOM require more operators (and vice versa) and argues for selecting a refinement plan that strikes the right balance between the total operator memory and the number of operators. TOM-based heuristic. We next leverage our empiricallyconfirmed intuitive argument to develop a simple heuristic algorithm for selecting an initial refinement plan. To this end, for each (i.e., number of operators), our algorithm first computes the refinement plans for which the mean TOM-values across all input windows is minimum. It then searches for the -value that maximizes the objective function ( , ) = where denotes the difference between the total available memory in the data plane and the computed value of minmean-TOM and is the difference between the available number of registers and number of operators. In effect, this algorithm is determining a refinement plan for which the difference between the available and required memory and between the available and required registers is as high as possible. Figure 4b shows the convex shape of this objective function as a the number of operators varies across the range of possible values.

Computing Register Sizes
Our goal here is to compute (optimal) register sizes that given the refinement plan enable efficient operator mappings at runtime. This problem can be formulated as an ILP, however the performance of the solvers on the generated ILPs is unsatisfactory, possibly due to the NP-hardness of solving general ILPs. Additionally, there is the risk that ILP solutions would be over-fitted on the input data. As a result, we look for alternative solutions in the form of simple heuristics that are "good enough". However, developing heuristic solutions for this problem is further complicated by hardware-specific constraints on available data-plane resources. Specifically, there is an upper bound on the memory allocated to an individual register. There is also a cap on the total memory allocated to all the registers in each physical stage. Right-sizing a single stage. Since finding a memory allocation that works for all physical stages simultaneously, satisfies the various constraints, and helps us achieve the stated objective for our bootstrapping effort is challenging, we consider the following simplified version of the problem. The simplification consists of decomposing the problem by first finding a register-size configuration that works well for a single stage and then replicating that same configuration across all stages. Here, our intuition is that given the hardware-specific constraints, intra-stage memory allocation matters more than inter-stage memory allocation. We argue that for a given stage, a configuration that uses more of the existing ALUs and more of the available memory should perform better than those with fewer ALUs and less memory. While there is no apparent downside to using all available memory, how memory is distributed across different registers matters. In fact, in the absence of practical reasons for favoring either small or large registers (i.e., high variability in sizes) or assigning all registers the same size (i.e., zero variability), we opt for a distribution of register-sizes that exhibits a moderate amount of variability. To this end and for simplicity, we consider here variability scenarios that result from allocating memory proportional to a register's order; that is, if {1, 2, ..., } denotes the ordered set of registers in a stage, then the register sizes will be { , 2 , ..., }, where is a scaling factor. Slice-n-Repeat (SnR) heuristic. Our goal is to develop a "slice-n-repeat" algorithm that first finds a good register size configuration for a single stage (slice) and then "repeats" that same configuration across all other stages. Based on the above observations, we focus here on synthesizing a slice configuration that meets the given sizing constraints, uses all the ALUs and all the memory available in a single stage, and satisfies the stipulated proportional relationship between allocated memory and registers' order. As a result, our algorithm simply needs to solve a linear program for a single variable which is the scaling factor for register sizes. Our goal is to simply find the largest value of , subject to the constraints that the maximum size allocated the the largestsized register does not exceed the max memory limit for a single register and that the sum of the memory allocated to all the registers does not exceed the total memory limit for a stage.
To illustrate, consider a setting where there are a total of eight ALUs (or registers) in a stage, where the maximum memory that we can allocate to a single register is 1 Mb, and the total available memory across the entire stage is capped at 2 Mb. In this case, the optimization problem has two constraints: 8  18 } Mb. Note that the SnR heuristic does not depend on any cost matrix as input and is, thus, insensitive to the input workload dynamics. It only depends on the set of input queries, which we assume in this paper to be given and fixed.

Dynamic Operator Mappings
In this section, we describe how DynamiQ maps operators to data-plane registers at runtime (Section 4.1) and how it deals with the fact that in practice, the input data and resulting cost matrix for a given window is not available at the start of the window when the operator mapping decisions have to be made (Section 4.2).

Operator Mapping Problem
Definition. Assuming that the current window ( ) executes the initial query plan, then the input for our operatorto-register mapping problem consists of (1) the register-size configuration ( ) used for , and (2) the cost matrix for the next window ( ′ ): i.e., the memory required ( ) and number of input and output tuples ( and ) for dataflow operators ∈ . Here, is the set of all stateful operators.
Our objective is to find a solution to this problem in the form of a configuration that specifies for window ′ the mapping of stateful operators ∈ to the set of registers ∈ that minimizes the load at the stream processor for ′ . Hardware and ordering constraints. Solving this optimization problem is made more complicated by domainspecific requirements that further restrict the set of feasible solutions. For example, we can have a one-to-many relationship between dataflow operators ( ) and data-plane registers ( ); that is, we can map an operator to multiple registers, but a register can only support one stateful operator at a time. Additionally, our problem's solution has to satisfy the ordering constraints that can arise from query partitioning. More concretely, if → are two stateful operators for a query, and ( ) represents the set of stages to which is mapped, then ( ( )) < ( ( )). For example, in the case of Query 1, we can only map the reduce operator for stages greater than the ones assigned to the distinct operator. NP-hardness. We prove that finding an optimal assignment of operators to registers is NP-hard. Our proof is by reduction from the 3-PARTITION problem and due to limited space, we present the formal proof in Appendix C.1. We also note that NP-hardness holds even for data-planes with a single stage and when there are no dependencies between stateful operators. Greedy heuristic. We now present a greedy heuristic for solving the operator mapping problem that both results in minimal workload at the stream processor and is computable in a few tens of milliseconds -i.e., an efficient and practical solution. Intuitively, an approach that sorts all the operators based on a utility score and greedily maps them based on that score should suffice. However, such an approach does not work well due to the ordering constraints. Instead of making decisions for individual operators, the proposed heuristic makes decisions for pairs of operators → . 1 The algorithm sorts these operator pairs based on their assignment score. We define this score as the ratio of workload reduction at the stream processor to the memory footprint when the operator pair is mapped to the data plane. It iterates over the data-plane stages in order, and greedily selects the operator pairs with the highest assignment score for each stage. This approach prioritizes selecting operator pairs that help reduce the stream processor's workload with smaller memory overhead in the data plane. We provide the pseudocode for this algorithm in Appendices C.4 and C.5.

Predicting Future Workload
Our formulation of the operator mapping problem assumes oracular knowledge of future cost matrices to compute new operator mappings at runtime. However, this assumption does not hold in practice. This section describes how Dy-namiQ uses the cost values from the past to predict future memory requirements and how it uses these predicted values to compute new operator mappings.
Off-the-shelf learning model. Our goal is to use the past windows' cost values to predict the future cost values, one window at a time. Given the high cost associated with generating cost matrices, we consider learning models that do not require a large training dataset. Among various off-the-shelve time-series prediction tools, we chose the Winter-Holt's double exponential smoothing prediction (DESP) method [41], mainly for its simplicity and ability to adequately capture the short-term trends in memory requirements for the different operators over time (we observe that for most operators, the median prediction error is less than 10 %). 2 Scaling predicted values. Figure 5 shows the relationship between prediction error and memory requirements. Here, each colored dot represents an operator, where the value on the x-axis indicates the (median) required memory, the y-axis indicates the prediction error, and the color encodes the operator's contribution to the load at the stream processor. The figure shows that even small prediction errors for operators with a high memory footprint can have a significant impact on the stream processor's load. We observed similar trends (not shown here) for the number of input tuples ( ) and the variability of the memory required. Even with more sophisticated learning models, we expect non-zero prediction errors. Thus, to reduce the impact of prediction errors, we opted for an approach that scales the predicted values based on their effect on the stream processor's load. More specifically, we used the training dataset to cluster data-flow operators based on three features: number of input tuples ( ), memory required ( ), and variability in required memory. Here, to deal with and values across multiple windows, we considered their 95 ℎ percentile values. This clustering effort produced 10 well-defined groups of operators, and we computed a different scaling factor for each group using Bayesian Optimization (BO) [3].

Implementation
DynamiQ augments Sonata's query planner, runtime, and data-plane driver modules. The most challenging part of implementing DynamiQ is to develop a new data-plane driver for Tofino-based targets, allowing them to map stateful operators to registers at runtime dynamically. This section describes how we enable dynamic operator mapping for a Tofino-model switch, which offers register-accurate chip simulation for Tofino in software [16], and report DynamiQ's runtime overheads.
Enabling dynamic operator mapping at runtime. This task entails updating (1) programs for stateful ALUs (e.g., reduce to distinct), (2) a set of keys for stateful operations (e.g., sIP to (sIP, dIP)), and (3) operator-to-register mappings. To enable these operations, DynamiQ encodes the decisions in the packets' metadata and uses match-action tables to dynamically update these fields at the end of each window. More specifically, it creates two categories of metadata fields, namely persistent fields, and ephemeral fields. Unlike persistent fields, DynamiQ reuses the ephemeral ones after every stateful operation. For example, the metadata fields carrying the information about which ALU programs (e.g.,distinct or reduce) to use are reusable across different stages and are thus ephemeral. We provide a more detailed description of our Tofino-based implementation and the metadata scheme in Appendix D. A key lesson from this proposed approach is that compared to Sonata, system incurs additional metadata overhead of around 120 bits per ALU. Though this overhead is high, it should be possible to bring it down with a more efficient data-plane implementation. Runtime overheads. DynamiQ performs the following operations at runtime: (1) read the register values from the data-plane targets, (2) predict the input data (i.e., cost matrix values), (3) run the greedy heuristic to compute operator mappings, and (4) update the match-action tables in the data plane. Together, the first three operations take between 100-200 ms to complete. DynamiQ minimizes the impact of these delays by only using the cost matrix values from previous windows to predict the cost matrix for the next window. We verified that using no (or only partial) information about the cost matrix values in the current window Optimal-MAX-DP ✗ Impractical 41.8 M Computes optimal query plans using MAX-DP's query planner for each window. Optimal-Sonata ✓ 29.6 K Computes optimal query plans using Sonata's query planner for each window. Table 3. Query-planning techniques emulated for evaluation.
for predicting the cost matrix has negligible impact on Dy-namiQ's performance. Our current implementation updates the match-action table entries sequentially, which incurs an overhead of 200-300 ms. Updating the match-action table entries in parallel can reduce the runtime overhead for this last operation to less than 10 ms in the future.

Evaluation
Our multi-faceted evaluation of DynamiQ described in this section results in the following key takeaways: • DynamiQ achieves near-optimal workload reduction. Compared to existing telemetry systems that use static query plans with (e.g., Sonata) or without (e.g., Marple) iterative refinement, DynamiQ reduces the stream processor's workload by more than two orders of magnitude (see Table 3 and Figure 6).
• DynamiQ's performance gains are robust to differences in switch constraints, input workloads, query workloads, and training intervals (see Figure 8).
• Each of the bootstrapping and runtime algorithms described in Sections 3 and 4 contribute to the achieved performance gains of DynamiQ and we quantify their individual contributions (due to limited space, see Appendix F for details).
• The ability of DynamiQ to dynamically map operators at runtime is demonstrated with a case study that leverages a Tofino-model switch [16] (due to limited space, this use case is detailed in Appendix D.2). We provide the instructions to reproduce this case study over GitHub [1].

Setup
Telemetry queries. For a fair comparison, we used the same query workload as in Sonata [10]; that is, we used eight different telemetry queries that process layer 3 and 4 header fields for evaluation. 3 Table 2 lists the queries and shows how they differ in terms of the number of stateful operators (| |) and their memory footprint ( ). For queries with join operators, we show the memory footprint for all stateful operators in individual sub-queries. Packet Traces. We used four one-hour-long packet traces, collected three months apart within a single year and from 3 Out of 11 queries considered in [10], three required payload information. the same source [7]. Similar to Sonata, we apply a speedup factor of 20× to simulate a 100 Gbps workload. Applying a window size of three seconds thus yields a total of four threeminute-long traces (each consisting of 60 windows) that we used for evaluation. We split the resulting 60 windows into a test set and training set and use the training data to bootstrap initial query plans. Unless specified otherwise, we present the results for one of the four packet traces and only use one window for bootstrapping. We present results for the other three traces and longer training intervals in Section 6.3. Impact of packet orderings. We now describe how we estimate additional load at the stream processor when the required operator memory exceed the allocated memory in the data plane. Our approach (denoted as "average case") assumes a random ordering of the incoming keys, irrespective of the number of tuples that map to these keys. We now quantify the impact of packet ordering on the estimation of load. More specifically, we consider two extreme cases with skewed orderings. The first case is where only the keys with just one tuple arrive last and thus don't find space in the data plane. The second case we consider is where all the singletuple keys arrive first and use all the allocated memory in the data plane. We refer to the first case as the "best case", and the second case as the "worst case". We describe in detail the calculations used for computing the load at the stream processor in Appendix E. We also present the comparison between the three cases in Figure 13 in the appendix. Impact of hash collisions. Hash collisions are intrinsic to stateful operations in the data plane. Sonata [10] evaluates the impact of hash collisions on load at stream processor and shows that to mitigate the impact of hash collisions, hybrid telemetry systems need to either over-provision the registers in the data plane or use more ALUs/stages to compile a stateful operators across multiple stages. In this paper, we don't evaluate the impact of hash collision as it affects both the static and dynamic query plans equally. Comparisons with existing systems. We compare the performance of DynamiQ with the performance of two other telemetry systems: MAX-DP and Sonata. We borrowed MAX-DP from [10] because it emulates the set of telemetry systems, such as Marple [26] and UnivMon [23], etc., that don't use iterative refinement. Its query plan consists of offloading as many stateful operators as possible to the switch. We use  Sonata because it is a system that does use iterative refinement. Table 3 provides descriptions for how we emulated these systems as well as for different variants of DynamiQ itself. Finally, we compare against Optimal-MAX-DP and Optimal-Sonata, which mimic the optimal (yet) impractical query planning techniques with and without iterative refinement, respectively. Also, note that except for DynamiQ-Pred, all other dynamic query-planning techniques in Table 3 assume oracular knowledge (i.e., future cost matrix values) and are therefore not realizable in practice.
Quantifying the performance of the different query plans listed in Table 3 requires estimating the additional load at the stream processor when the required operator memory exceeds the allocated data-plane memory. In Appendix E, we describe how we accurately estimate this metric without requiring packet-level simulations. Targets. Query planning is most challenging when the gap between required and available data-plane resources is small. To emulate such resource-constrained settings, unless specified otherwise, we present results for a simulated PISA switch with 12 physical stages, eight stateful ALUs per stage, and 1.5 Mb of register memory per stage. For each stage, a single register can use up to 0.75 Mb of memory. We quantify the effect of switch resources on DynamiQ's performance in Section 6.3.

Workload at Stream Processor
To quantify the load at the stream processor for the different query-planning techniques listed in Table 3, we perform the following experiment. For each technique, we consider a window and use the corresponding input cost matrix to compute the initial query plan according to the considered technique. We then apply this plan to all remaining 59 windows, and compute the max load observed at the stream processor. We repeat this process for each of the 60 windows and compute the distribution of these max load values. Table 3 (third column) reports these distributions' median values. DynamiQ vs. Sonata. Figure 6a compares the performance of DynamiQ-Oracle (green line) with Sonata (red line) and Optimal-Sonata (black line). We observe that for most input windows, the initial query plans computed by DynamiQ-Oracle reduce the load at the stream processor by more than two orders of magnitude compared to Sonata. This result reinforces our argument that is combining query-specific iterative refinement and dynamic query planning results in significant workload reductions at the stream processor. This result also shows a marginal difference in performance between DynamiQ-Oracle and Optimal-Sonata-demonstrating the efficacy of DynamiQ's bootstrapping and runtime algorithms. DynamiQ vs. MAX-DP. Figure 6b compares DynamiQ's performance with that of MAX-DP and MAX-DP-D. We observe that in the absence of query-specific iterative refinement, the impact of dynamic query planning is minimal. We also note that the performance of MAX-DP-D, which employs both DynamiQ's register sizing heuristic and Dy-namiQ's greedy heuristic for dynamic operator mappings, is close to Optimal-MAX-DP, demonstrating the generality of DynamiQ's bootstrapping and runtime algorithms. DynamiQ-Oracle vs. DynamiQ-Pred. DynamiQ-Oracle assumes oracular knowledge; that is, it knows the input data for future windows. Clearly, this assumption does not hold in practice, and Figure 6c assesses the cost of using predicted cost values as input to compute the operator mappings at runtime. It shows that although DynamiQ-Pred sends more tuples to the stream processor compared to DynamiQ-Oracle, it still reduces the median load at the stream processor by more than two orders of magnitude compared to Sonata. The (right) tail behavior of the distribution for DynamiQ-Pred results from the high prediction errors for operators with a high memory footprint. This result also shows that our design choice to scale the predicted cost values helps reduce the workload at the stream processor. Compared to DynamiQ-Pred (with scaling), not scaling the predicted values (i.e., DynamiQ-Pred (w/o scaling)) increases the load at stream processor by at least one order of magnitude. Note that unlike the experiments described above, to preserve temporal dependencies in the packet traces for the prediction model, we used the first ten windows for training DynamiQ-Pred's learning model and show the workload distribution for 1 3  the next 50 windows. Table 3 reports the median workload over these 50 windows.

DynamiQ-Pred
Visualizing memory allocation and load contribution. Figure 7 extends the visual presented in Section 2 ( Figure 2b) and compares the overall performance of MAX-DP, Sonata, DynamiQ-Oracle, and DynamiQ-Pred, respectively. For each of these query-planning techniques, the figure depicts five consecutive windows (rows) and shows for each window (row) the memory allocations (block size) and contributions to the load at the stream processor (block color) for the different operators. Here, the y-axis indicates the time (window). Sonata with its static query planning uses the first window's cost matrix as input to compute the query plan and applies that very plan for the future windows. We observe that MAX-DP uses a few large-sized blocks, and most of them contribute significantly to the load at the stream processor (i.e., red/orange colors). Compared to MAX-DP, Sonata uses more (relatively) smaller-sized blocks whose contributions to the stream processor's load start to increase right after the first window (i.e., yellow/red/black colors). In contrast, the predominantly green/yellow/cyan-colored plots for DynamiQ-Oracle and DynamiQ-Pred for all five windows is visual evidence that the contributions of the individual operators of these two dynamic query planning techniques to the stream processor's load are significantly lower compared to Sonata. Also note that compared to DynamiQ-Oracle, DynamiQ-Pred has a few operators in a couple of windows whose contributions to the stream processor's load are high (red/orange blocks). Their occurrence is due to large errors in predicting the memory requirements for these operators. We also observe that DynamiQ-Pred uses more data-plane memory than DynamiQ-Oracle and we attribute this observation to our design choice of scaling the predicted values (i.e., overestimating the memory requirements).

Sensitivity Analysis
We next demonstrate DynamiQ's robustness to various input workloads, switch constraints, query workloads, and training intervals. Input traffic workload. To assess the (in)sensitivity of Dy-namiQ's performance to different input workloads, Figure 8a shows the workloads at the stream processor for four different hours of packet trace data. We observe that the overall trend (i.e., DynamiQ performs better than Sonata and Optimal better than DynamiQ) is consistent across the different datasets. Compared to Sonata, we observe smaller gains for DynamiQ for the first hour which can be explained by the fact that the variability in total memory is high in the first hour, which in turn affords the runtime fewer opportunities for finding good dynamic operator mappings. Switch constraints. To assess DynamiQ's performance for different data-plane target configurations, we first quantify the impact of the number of stages and number of ALUs, keeping the total memory constant. As can be seen from Figure 8b and Figure 8c, decreasing (increasing) the number of stages or ALUs makes dynamic query planning less (more) effective in terms of the max number of tuples that are sent to the stream processor. Second, with respect to quantifying the impact of total memory for a fixed number of stages and 11 ALUs, Figure 8d shows that the difference in performance between DynamiQ and Sonata diminishes as the total available memory decreases. This observation reflects the fact that there are less opportunities for the runtime to redistribute memory when total memory is already tight (i.e., operating in resource-constrained settings). Query workload. Figure 8e compares DynamiQ's and Sonata's performance for different query workloads. We observe that DynamiQ consistently outperforms Sonata, and the performance gap is smaller for workloads with fewer input queries. Training intervals. With multiple windows of training data (cost matrices), Sonata uses the median value as an input to its ILP solver. Figure 8f compares DynamiQ's and Sonata's performance for different training intervals. We observe that the number of training intervals have minimal impact on the difference in performance between the two.

Related Work
Network streaming analytics systems. Modern data plane technologies have had a profound impact on network telemetry [19,34,43]. Existing network telemetry systems can be roughly grouped into purely host-based platforms [2,6,11,25,28,32,33,42,45]) and data plane-only systems [4,22,23,44,47]), and include as of late also hybrid designs [10,12,13,20,21,26,30,31,46]. Most existing hybrid telemetry systems focus on mechanisms for compiling a subset of dataflow operators in the switch (e.g., Marple [26], Newton [46], etc.). Among hybrid telemetry systems, only Sonata [10] is concerned with algorithms for computing static query plans that make effective use of limited switch resources for a given query workload, traffic workload and data-plane target. DynamiQ is a hybrid system for singleswitch settings and static query workloads that is capable of dynamically updating query plans to successfully respond to input workload dynamics. Database systems. A large body of literature in the database research community deals with the problem of query optimization in general (e.g., see [14] and references therein) and adaptive (or dynamic) query processing in particular (e.g., see [8] and references therein). In the context of traditional (single-machine) database systems, dynamic query planning concerns runtime feedback to modify intra-query processing in ways that provide more efficient resource utilization. DynamiQ has much in common with recent work such as Qoop [24] that focuses on big data analytics tasks in multi-node clusters and makes a case for "on-the-fly" query (re)planning; that is, switching query plans during query execution to adapt to changing resource availability. DynamiQ's dynamic query planning is an instance of such on-the-fly query (re-)planning that adapts the query plans to make the best use of limited data-plane resources.

Limitations & Future Directions
An ideal network streaming analytics system should be able to compute effective query plans for executing dynamic query workloads in distributed settings for dynamic input workloads. While Sonata has been designed and works well for static input and query workloads in single-switch settings, DynamiQ represents an important improvement over Sonata in the sense that it considers dynamic query planning as a means to effectively deal with dynamic input workloads in single-switch settings. Moreover, DynamiQ's ability to dynamically map operators to data-plane registers at runtime lays the foundation for system designs that can readily accommodate dynamic query workloads; that is, compute effective query plans for query workloads where the set of operators that requires mapping changes as the query workload changes.
While much work remains, we view DynamiQ as a promising step towards achieving the stated "ideal". For example, although a few of the existing network telemetry systems (e.g., Marple [26], Newton [46]) operate in distributed settings, it is unclear if they can compute effective query plans for dynamic input/query workloads and/or arbitrary topologies/routing. We plan to extend DynamiQ's query-planning setup for distributed settings as part of our future work. At the same time, realizing that DynamiQ provides excellent opportunities to leverage machine learning (e.g., for workload prediction) to reduce the load at the stream processor, we also plan to explore if or how leveraging machine learning can improve query planning for network telemetry systems more generally.

Conclusion
For network streaming analytics systems to leverage programmable data-plane targets effectively requires dynamic query planning. Our new prototype DynamiQ satisfies this requirement by first computing effective initial query plans and then dynamically changing them by updating the operator mappings at runtime. We show that DynamiQ achieves near-optimal workload reduction and can reduce the load at the stream processor by more than two orders of magnitude compared to existing systems, such as Sonata, Marple, etc., that use static query plans. These performance gains are also robust to differences in switch constraints, input traffic workloads, query workloads, etc. We also demonstrated how we integrate DynamiQ's runtime algorithms with Tofino-based data-plane targets. 5 . map ( ( sIP, dIP ) => ( dIP,1 ) ) 6 . reduce ( keys = ( dIP, ) , f= sum ) 7 . filter ( ( dIP, count ) => count > Th ) Query 2. Detect DDoS Attacks.

A Static Query Planning
In this part of the appendix, we report on the different techniques we investigated to characterize the limitations of static query planning. We divide this exploration into two broad categories: (1) overprovisioning, where we scale the input for query planning to handle future input workload dynamics, and (2) overfitting, where we extend Sonata's query planner to find the optimal query plan for all the input windows.
The efficacy of static query plans depends critically on how well they can account for the dynamic changes inherent in future windows over longer time horizons. The inability to effectively handle these future changes results in ineffective query plans, especially for scenarios where network resources are scarce. To handle future workload dynamics, one can simply scale the cost matrix and then compute query plans to address the scaled memory requirements. Such an approach can reduce the number of under-provisioning cases which in turn can decrease the load at the stream processor. However, such over-provisioning comes at a cost -a significant fraction of available switch memory may remain unused. We now discuss two different approaches for scaling the cost matrices. Uniform scaling. One simple approach to account for the unknown changes encountered in future windows is to uniformly over-provision the input cost matrix by, for instance, doubling the memory requirements for all the cost matrix elements and then using these over-provisioned cost matrices as input to Sonata's ILP solver. While the resulting static query plan will work well for operators whose memory requirements for future windows are higher than their median value, for the remaining operators, this approach results in wasteful allocation of switch memory that is already in short supply to start with and leads to increased loads at the stream processor, especially for windows that see plenty of wasted switch memory. Selective scaling. Different cost matrix elements have different variability. Also, the impact of over-provisioning for different operators (cost matrix elements) on the stream processor's load is different. Thus, instead of using a uniform scaling factor for the entire cost matrix, one can use different scaling factors for different cost matrix elements. We explored a close-loop technique to find the right overprovisioning levels for different operators. In particular, we used Bayesian Optimization [3] to compute the overprovisioning levels for different cost matrix elements. To reduce the search space, we only computed query-specific over-provisioning levels. Here, we optimized a black-box function which takes as input the query-level scaling factor and gives as output a score indicating the workload at the stream processor across all input windows. The score that we used in our experiments minimizes the sum of log of workload at the stream processor in each window: ∈windows log 2 (Load at SP) . In principle, while such an approach should help with finding good static query plans, it does not generalize well, especially with limited training data. Given the high cost of generating cost matrices, both for collecting the raw data and then processing it, we expect limited availability of training data in practice.

A.2 Over-fitting.
To compute its query plan, Sonata uses the median value of all the cost matrices as an input to its ILP solver. One possible improvement over Sonata's current approach is to extend its query-planning ILP to optimize for all the input windows simultaneously. However, since the number of constraints for this extended ILP increases linearly with the number of input windows and since the computational complexity of computing an approximate solution of the ILP for a single window is already high, we expect this approach to take orders of magnitude more time to converge to a (near-)optimal solution. Moreover, the resulting query plan will be overfitted for the input cost matrices and will therefore suffer from the same problems as Sonata's original query planner when it comes to handling the traffic workload dynamics encountered during future windows.

B Accurate Query Evaluation
In this part of the appendix, we describe how we ensure accurate query evaluation. More specifically, we show that for queries with multiple stateful operators, if the first stateful operator requires more memory than provisioned in the data plane, we need to send the output of the first operator to the stream processor and bypass the remaining stateful operators in the data plane. We also show that changing refinement plans for a query at runtime affects its accuracy. Thus, DynamiQ computes the refinement plans using the bootstrapping algorithm at compile time itself. Handling under-provisioned data-plane registers. Under-provisioned data-plane targets can result in increase in hash collisions. If a packet's key generates a collision, we send it to the stream processor. We then perform the aggregation operation for all the packets belonging to this key at the stream processor and join it with the result of the ones aggregated in the data plane to report the final output. This partial execution approach works well if we observe hash 14 collisions for the query's last operator that gets executed at the switch. However, if the collision occurs for an intermediate aggregation operation, sending the packet to the stream processor affects accuracy. For example, consider Query 2 to detect victims of DNS reflection attacks. If the query plan is such that we execute up to line 6 in the data plane, then handling hash collisions for the distinct operator is non-trivial. More concretely, if we apply the remaining operators for the keys that observe collision for the distinct operator and join it with the output of the reduce operator for the other keys, the output will be different. To illustrate, consider the set of input tuples as {( , ), ( , ), ( , ), ( , )}, and threshold (line 7) of 2. Due to collision, we send the tuple ( , ) to the stream processor. Here, with partial query execution, the output is a null set, different from the actual output ( , 2).
To ensure accurate query evaluation, we have two options. The first option is to send the output of the distinct operator in the case of a collision to the stream processor, bypassing the remaining operators in the data plane. The other option is to send the output of the distinct operator back to the data plane. Given the complexity of realizing this second option, we chose to use the first option. Changing refinement plans. In Section 2, we mentioned that changing the refinement plan at runtime affects a query's accuracy. Below, we provide an explanation and then describe a technique that can address this issue but is not practical in the sense that it cannot be executed at runtime. However, the technique can be used in practice when the frequency of changing refinement plans is of the order of hours or days. In this case, the changes are intended to handle significant shifts in the overall traffic patterns.
A straw man approach is to abruptly change the refinement plan from one plan to the other. To recall, iterative refinement works by filtering the input workload of an operator based on the previous window's output of another operator . The operator executes at the previous refinement level relative to that of the operator . Thus, if DynamiQ changes the refinement plan in a window, the filtering mechanism is severely impaired. Consider a concrete examplerefinement plan for window 1 is 0 → 8 → 24 → 32 (call it 1 ) and the refinement plan for the successive window 2 is 0 → 16 → 28 → 32 (call it 2 ). Note that the output from the operator executing at \8 in window 1 would be used for filtering the input workload for the operator executing at \24 in window 2 . However, when abruptly changing from 1 to 2 , there is no operator executing at \24 in 2 . Moreover, the new operators introduced in 2 (e.g., \28) lack the information to apply the filter operation for their input workload. In essence, changing refinement plans at runtime requires making these abrupt changes to refinement plans, but making such changes affects the query's accuracy.
To preserve query accuracy, we can iteratively change the refinement plan over multiple consecutive windows. In the example described above, instead of adding all the operators for refinement plan 2 in 2 , we only add operator \16 in 2 , \28 in 3 , and so on. This approach never introduces any operators that lack the information to create an input workload filter in any window. Since this approach takes windows to modify the plan (here is the number of refinement levels), it is not suited for making changes at runtime. Another related problem concerns predicting the memory requirements for new operators. In particular, the proposed approach requires estimating the memory requirements for new operators at different granularities for which we have no historical data. Estimating the memory requirements of such operators will require a more sophisticated learning model that leverages the spatial relationship between operators at different levels of granularities. We leave this exploration for future work.

C Operator Mapping Deep Dive
This part of the appendix provides a formal proof that the problem of finding an optimal assignment of dataflow operators to data-plane registers is NP-hard. The NP-hardness holds even when there is just a single stage in the data plane, and there are no dependencies between the operators. For this reason we do not include these aspects in the formal definition of the problem that we show is NP-hard. Nevertheless, the hardness of the Optimal Assignment problem defined below directly translates to hardness of finding an optimal operator mapping.

C.1 Problem Formulation
Let and be sets of registers and operators, respectively. Each register ∈ is equipped with a non-negative integer capacity . Each operator ∈ is equipped with a positive integer size , as well as two non-negative integer costs; is the unsatisfied cost, while is the satisfied cost of operator . We require that ≤ for every operator . An assignment is a function : → , and the satisfaction ratio of an operator with respect to an assignment is denoted by ( , ) and defined as An operator is said to be unsatisfied by the assignment if ( , ) = 0, satisfied if ( , ) = 1, and partially satisfied otherwise.
The cost of operator with respect to the assignment is denoted by ( , ) and defined as ( , ) = · ( , )+ ·(1− ( , )). Thus the cost of a satisfied operator is the satisfied cost , the cost of an unsatisfied operator is the unsatisfied cost , while the cost of a partially satisfied operator is somewhere between and based on the satisfaction ratio ( , ). The cost of an assignment is denoted by ( ) and defined to be the sum ( ) = ∈ ( , ) of the costs of all operators in with respect to .
In the Optimal Assignment problem, we are given as input a set of registers, a set of operators, a capacity 15 for every register, and a size , a satisfied cost and an unsatisfied cost for every operator . The task is to compute an assignment of minimum cost.

C.2 NP Hardness Proof
We will prove that Optimal Assignment is NP-hard by reduction from the 3-Partition problem. Recall that for this problem, the input is a set = { 1 , . . . } of positive integers, together with a positive integer . The task is to determine whether there exists a partition of into disjoint subsets 1 , . . . , /3 so that for every ≤ /3 it holds that (1) | | = 3 and (2) ∈ = . We refer to such a partition as a solution partition. It is known (see for example [15]) that 3-Partition remains NP-hard even when every ∈ satisfies /4 < < /2. This guarantees that any partition of into 1 , . . . , ℓ that satisfies requirement (2) also automatically satisfies requirement (1) and therefore is a solution partition. Theorem 1. Optimal Assignment is NP-hard.
Proof. We give a reduction from the variant of 3-Partition where every ∈ satisfies /4 < < /2. Given an input ( = { 1 , . . . , }, ) to 3-Partition, we create an input to Optimal Assignment as follows. The set has registers { 1 , . . . , } and for every ≤ , the register has capacity . The set has /3 operators { 1 , 2 , . . . , /3 }. Every operator has size = , satisfied cost = 0, an unsatisfied cost = 1. This concludes the construction. We now prove that the instance , of 3-Partition has a solution partition if and only if the constructed instance , has an assignment of cost at most ∈ = 0. For the forward direction, suppose that there exists a solution partition 1 , . . . , /3 of . Define the assignment : → as follows: For every ∈ we find the unique so that ∈ and set ( ) = . To argue that ( ) = ∈ , it is sufficient to show that for every operator ∈ we have ( , ) = 1. In particular we have that  (1), that | | = 3, of solution partitions. We conclude that 1 , . . . , /3 is a solution partition, completing the proof. □

C.3 Remarks
The proof of Theorem 1 shows that it is in fact NP-hard to determine whether a given instance admits an assignment of cost 0. Thus, assuming P ≠ NP, the Optimal Assignment problem can not admit an approximation algorithm with any factor. Moreover, the choice of satisfied cost of 0 and un-satisfied cost of 1 for every operator in the proof of Theorem 1 might lead the reader to believe that the NP-hardness result only kicks in for instances with unrealistic choices of costs. However it is easily verified that the proof of Theorem 1 never relies on the precise choice of costs and goes through for any selection of operator costs, as long as < for every operator ∈ .
Finally, Theorem 1 shows that Optimal Assignment is strongly NP-hard (i.e., that it remains NP-hard even when all input integers are coded in unary).

C.4 Generalized Optimal Assignment
We now turn to the greedy heuristic that we use to compute the operator-to-register mappings at runtime. However, first we need to formally define the problem for which we design an algorithm, we call the problem General Optimal Assignment, GOA for short. The GOA problem is a generalization of the Optimal Assignment problem defined in Section C.1.
Thus, input for GOA still contains a set of registers, a set of operators, a capacity for every register, and a size , a satisfied cost and an unsatisfied cost for every operator . The task is to compute an assignment of minimum cost. However GOA differs from Optimal Assignment in three ways. First, we allow the assignment to be a partial assignment. That is, instead of being a function : → , is a function : ′ → for a subset ′ . We will say that ′ is the domain of , that registers in ′ are assigned by and the registers in \ ′ are unassigned by . The definition of cost of an operator with respect to an assignment readily extends without modification to partial assignments. 16 The second way in which GOA differs from Optimal Assignment is that there is additional input that restricts the set of partial assignments that we can select from. Every register ∈ also comes with a positive integer stage . Finally, input contains a partition of operators into disjoint nonempty sets 1 , . . . , ℓ and a bijection : → {1, . . . , | |} for every ≤ ℓ. If 1 , and 2 are operators in the same set and ( 2 ) = ( 1 ) + 1 then 1 is said to be the parent of 2 , and 2 is the child of 1 . The sets are called dependency chains.
Finally, the cost of an assignment in GOA is different from the sum of costs of all operators with respect to an assignment. The first unsatisfied operator in the dependency chain with respect to the assignment is defined as = arg min ∈ : ( , )≠1 ( ). The cost of a dependency chain with respect to the assignment is denoted by ( , ) and defined as The cost of an assignment in GOA is denoted by ( ) and defined to be the sum ( ) = =1 ( , ) of the costs of all dependency chains with respect to .
A partial assignment : ′ → is said to be feasible if the following conditions are satisfied for every pair 1 , 2 of operators such that 1 is the parent of 2 , and so on. (i) If any register is mapped by to 2 , then 1 is satisfied by . (ii) For every pair 1 , 2 of registers so that ( 1 ) = 1 and ( 2 ) = 2 then 1 < 2 . The intuitive interpretation of these conditions is that if we want to satisfy a child 2 then we first have to satisfy the parent 1 , and wait until the next stage before starting to satisfy the child 2 .
We summarize the statement of GOA: Input consists of a set of registers, a set of operators, a capacity and stage for every register, and a size , a satisfied cost and an unsatisfied cost for every operator . Furthermore, input consists a partition 1 , . . . ℓ of into dependency chains and an ordering : → {1, . . . , | |} for every dependency chain . Note that a dependency chain here represents the sequence of stateful operators for the input queries. For Query 1, the set of stateful operators distinct → reduce is an example of a dependency chain. The task is to compute a feasible (partial) assignment of minimum cost.

C.5 Greedy Heuristic: The Algorithm
Our algorithm follows a natural greedy strategy: start with the partial assignment 0 which leaves all registers unassigned. This is a feasible solution. The algorithm then gradually extends the assignment in a series of iterations, maintaining a feasible assignment at every intermediate step. When it is no longer possible to assign even more registers and maintain feasibility the algorithm halts.
We will say that an assignment 2 : ′′ → is an extension of an assignment 1 : ′ → if ′ ⊂ ′′ and 1 ( ) = 2 ( ) for every ∈ ′ . In other words 2 assigns all the registers that 1 does in precisely the same way, and assigns some additional registers. A feasible extension of is an extension ′ of that is itself a feasible assignment. We are now ready to describe the general overview of the algorithm. Each possible way to compute the candidate set and selecting from leads to a new heuristic. There are infinite possibilities for complex rules here; we have tried to design our rules to be as simple as possible (both conceptually and to implement) while still avoiding some of the pitfalls that lead the algorithm to output assignments with too high a cost. We now discuss precisely what set of feasible extensions our algorithm computes, and how it selects the extension ∈ to use. We start with the rule for selecting from . Our rule for selecting ∈ is perhaps the most natural one -select the from that gives the most "bang per buck", where "bang" refers to the cost of the assignment and "buck" refers to the total capacity of the assignment. More formally, we define the total capacity of an assignment with domain ′ as cap( ) = ∈ ′ . Our algorithm selects from that maximizes ( )− ( ) cap( )−cap( ) . This kind of selection rule has found tremendous success for other optimization problems, perhaps most famously for Set Cover [5], or maximization of monotone submodular functions [27].
Having set the selection criteria we now turn to discussing how we compute the set of candidate extensions. It turns out that to get the algorithm to produce high-quality solutions we need to consider extensions that assign multiple registers to multiple operators in addition to . At the same time we want to avoid having a too large set , since this makes the algorithm slow. The way we handle this trade-off is to go over all possibilities of which operator to satisfy, but to greedily choose the registers which are assigned to the operator. The next sub-routine, extend encapsulates this idea.
We will say that a dependency chain is satisfied by if all operators in are satisfied by . If is not satisfied by then contains a unique operator such that is not satisfied by and every ′ ∈ with ( ′ ) < ( ) is satisfied by . We will call this operator the active operator in the dependency chain . Our algorithm will always best ← r; 8 if best is empty then 9 best ← Largest unassigned register r in stage t; 10 ← ∪ {best → o} consider a single dependency chain at a time, and will always seek extensions that assign registers to the active operator in . When the active operator becomes satisfied, the next operator in the dependency chain becomes the active operator.
The active stage of the dependency chain is the lowest value for so that (i) there exists at least one register with stage = that is unassigned by and (ii) if the active operator of has a parent then every register with ( ) = satisfies < . The active stage of the assignment is the minimum active stage of all dependency chains. The extend sub-routine takes as input the assignment we wish to extend and a dependency chain which is not satisfied by . It then returns a feasible extension ′ of which, in addition to the domain of , assigns a single register to the active operator of . The sub-routine may also return that no such extension exists. We now describe the extend subroutine in detail.
The extend subroutine takes as input and . It then computes the active operator of and the active stage of . Among all the un-assigned registers with = such that + ′ ∈ : ( ′ )= ′ ≥ , select the one with smallest . Return the extension of that additionally assigns to . If no un-assigned with = such that + ′ ∈ : ( ′ )= ′ ≥ exists return the extension of that additionally assigns ′ to , where ′ is the register with largest ′ among all un-assigned registers with ′ = .
We are now ready to describe how the set is computed. The algorithm first computes the active stage of the assignment . It then iterates over all dependency chains which are not satisfied by , and whose active stage is precisely equal to . For each such dependency chain the algorithm proceeds as follows. Initially it sets 0 := and = 0. Then, as long as is not satisfied by it adds to , sets +1 to be the output of extend on and , and increments . The resulting set is union of the output of this algorithm for all the choices of dependency chain .

C.6 Remarks on Heuristic for GOA
We remark that our actual implementation of the heuristic of Section C.5 contains several optimizations. For example the actual implementation does not first compute the set and then select the extension from . Instead it enumerates all of the elements ∈ in the manner described in Section C.5, computes their "bang-per-buck" score on the fly, and keeps the ∈ with highest score.
By enumerating the elements in in a carefully chosen order and using appropriate data structures we can re-use a lot of computations when calculating the score of each element . We omit the details of these optimizations, since they do not change which assignment the algorithm produces. We also consider an enhanced version of the heuristic of Section C.5. Here, whenever the active stage of the current assignment increments, we remove from the domain of all registers whose stage is at least . This allows the greedy algorithm to "undo" choices for stage which were made when the active stage was strictly less than and the algorithm had less information about which operators still need registers assigned to them. DynamiQ uses this enhanced version of the greedy heuristic to compute operator mappings.

D Tofino-based Implementation
In this part of the appendix, we detail how we implemented different functionalities in a Tofino-based switch to enable dynamic operator mappings. We also present a case study that demonstrates how this implementation handles input workload dynamics, a capability that is missing from Sonata. Finally, we quantify the runtime overheads for this implementations.

D.1 Dynamic Operator Mappings
As described in Section 5, enabling dynamic operator mappings in the data plane entails dynamically changing: (1) the 18 Figure 10. Match-action tables to select the key for stateful operation.
modify_field (   program for each stateful arithmetic logic unit (SALU) for each register in the data plane, (2) the set of keys used for stateful operations, and (3) the packet-processing pipeline in the data plane. Updating SALU programs. Figure 9 shows how DynamiQ uses a table, execute_op, to dynamically change a SALU's program. For this table, it defines actions executing the reduce and the distinct program, respectively. This table reads a packet's select_prog metadata field to decide which action (i.e., SALU program) to select for stateful operations. Updating the set of keys for stateful operations. To understand how DynamiQ dynamically updates the keys for stateful operations, consider the case where the two keys, say, dIP and sIP, and DynamiQ needs to dynamically decide which of the two to use for computing the index value for the stateful operation. Figure 10 shows how DynamiQ uses the init_hash_field_data table to apply two different actions. Each of these actions read the packet field value from the packet, apply the mask (for iterative refinement), and write the masked value to the packet's metadata field. Figure 11 shows how DynamiQ uses this metadata field to compute the hash index for stateful operation. Extending this code block to enable hashing on multiple packet fields is straightforward. Here, instead of creating a single metadata field, DynamiQ creates multiple metadata fields and then changes their values using tables specific to each of these fields. Updating the packet-processing pipeline Dynamically mapping stateful operators to different registers in the data plane requires updating the packet processing pipeline to ensure sequential composition of these operators. Sonata used a combination of the query-specific metadata field qid_drop and IF statements to compose dataflow operators in the data plane. Such an approach is only suited for static operatorto-register mappings. DynamiQ's control program applies all the match-action tables in sequence, and uses a packet's metadata-fields to decide whether or not to apply particular actions in the match-action table to it. Such an approach enables DynamiQ to dynamically reconfigure the packetprocessing pipeline at runtime.
To enable such flexible packet processing, DynamiQ narrows the scope of the drop metadata field to match-action tables for stateful operators. The decision of whether the remaining downstream operators should be applied to this packet is encoded in this drop field. Such a change ensures that DynamiQ can compose these operators without requiring IF statements.
DynamiQ also enables support for multiple compile time dependencies. For example, if there are two operators and in the first stage and and in the second stage, it enumerates all possible dependencies between them, i.e., → , → , → and → . To realize these dependencies, it makes the operators in second stage (i.e., and ) match on both and 's 'drop' metadata. At runtime, DynamiQ adds match-action table entries such that only one of the two possible dependencies actually occur for these operators.
Note that although making an exact match on drop fields (where denotes the number of operators in the last stage) requires 2 match-action table entries at runtime, an operator in the second stage only follows on a single operator in the first stage, which in turn enables DynamiQ to use a single ternary match-action rule. 19 Figure 11. Match-action tables to compute the hash value for the selected the key for stateful operation.
Metadata fields. So far, we described how DynamiQ used different metadata fields to dynamically update the packet processing pipeline at runtime. We now summarize the type of metadata fields DynamiQ uses and provide an estimation of their memory overhead.
• Ephemeral fields. For each data-plane register, Dy-namiQ needs the following metadata fields: (1) a one bit select_program field to change the SALU program at runtime; (2) a one bit drop field to mark if the packet needs further processing; (3) a index field of size 2 (register size) bits to store the index for executing a stateful operation; (4) a keys field for storing the packet fields it uses as keys for the stateful operation. All these fields are narrowly scoped, can be reused across stages, and are therefore termed ephemeral. A single register requires around 114 bits (1 for SALU program + 1 for drop + 96 for keys + 16 for index). Thus, for the target considered in this paper (8 stages), DynamiQ requires around 1.8 Kb for a packet's metadata for ephemeral fields.
• Persistent fields. For each query, DynamiQ needs the following metadata fields: (1) a 16-bit qid field for each query that gets executed in the data plane; (2) keys to store the packet fields that are used as keys for computing the index value for query's last stateful operator in the data plane; and (3) index field to store the hash value for the key fields. The index field enables DynamiQ's runtime to read the aggregated value from the data plane, which in turn enables DynamiQ to emit the output (key, value) pair to the stream processor for further processing. For each query, DynamiQ requires 128 bits in a packet's metadata for these persistent fields, which is similar to Sonata's metadata footprint. This number will increase as the number of input queries increases.
DynamiQ introduces an additional optimization to avoid wasting register memory for distinct operation. More concretely, for reduce operation, DynamiQ configures a twodimensional register memory specifying the number of rows, where each row is of size 32 bits. For the match-action table applying the reduce operator, it updates the value in the row identified by the index field. Naively, using the same approach for distinct operator will waste 31 bits for each row as it only requires one bit to store the state. To ensure that the SALU programs for distinct operator can make use of all available bits in the register, DynamiQ uses five additional bits for computing the hash. These five bits enable the match-action table to select a bit among the 32 bits in each row. This optimization further requires additional 80 bits in packet's metadata for the target considered in the paper.

D.2 Case Study
We now demonstrate how the different building blocks described above enable DynamiQ to dynamically update the packet processing pipeline in the data plane, enabling it to update operator-to-register mappings at runtime. Setup. For this case study, we use the two queries Query 3 and Query 2 from Table 2. To simplify the experiment, we do not consider iterative refinement (i.e., both queries use all 32 bits of the dIP and sIP fields for stateful operations). Also, we only execute one stateful operator for each query in the data plane, i.e., we execute the reduce for Query 2 in userspace.
We use the Tofino-model [16] on a n1-highcpu-8 machine over Google Cloud Platform (GCP) [9]. We use Scapy [39] to send the traffic to this switch. The input workload is bi-modal, i.e., at first, the reduce operator for Query 3 receives more keys than the distinct operator for Query 2, and then the opposite scenario occurs. More specifically, for the first three windows, Query 3 receives traffic with around 10 distinct dIPs, and Query 2 receives traffic with around 100 distinct (sIP,dIP) pairs per window. After three second, these numbers change to around 100 and 10, respectively. We run this experiment with both DynamiQ and Sonata, each using two registers (sized 64×32 and 2048×32 bits) in the data-plane to execute these queries. When the change in traffic patterns occurs, DynamiQ swaps the mapping between stateful operators and data plane registers while Sonata continues to apply the same operator to register mappings. Observations. Figure 12 shows the number of tuples received by the stream processor. We observe that the workload at the stream processor is the same for both systems for first three one-second windows. However, when the traffic 20 1 packetStream ( W ) 2 . filter ( p => p . tcp . flags == 2 ) 3 . map ( p => ( p . dIP, 1 ) ) 4 . reduce ( keys = ( dIP, ) , f= sum ) 5 . filter ( ( dIP, count ) => count > Th ) Query 3. Newly opened TCP connections. Case study with Tofino-model. Here, incoming traffic workload changes after three seconds. As a result, the workload at stream processor increases for Sonata, and remains almost the same for DynamiQ. pattern changes at = 3, we observe that while the workload for Sonata increases, it remains essentially unchanged for DynamiQ. Note that the slight reduction in the workload at the stream processor for DynamiQ is because the reduce operator for Query 3 that receives more keys after the traffic pattern flips only reports the ones that exceed the threshold. Here, to handle the workload dynamics, Dy-namiQ is changing the operator-to-register mappings, which entails: (1) changing the SALU program from distinct to reduce, and vice versa; (2) changing the index key from sIP to dIP, and vice versa; and (3) updating the packet processing pipeline to ensure that the stream processor can correctly apply the remaining dataflow operations in the userspace. This experiment demonstrates DynamiQ's ability to dynamically update operator-to-register mappings at runtime to handle workload dynamics.
We provide the instructions to reproduce this case study with a Tofino-model switch over GitHub [1].

D.3 Runtime Overheads
DynamiQ requires updating the match-action tables in the data plane at runtime. The number of match-action table entries that DynamiQ updates are proportional to the number of ALUs or registers in the data plane. In the worst case, for each data-plane register, DynamiQ needs to update eight match-action table entries. Here, two are required to configure the tables that enable selecting the right SALU program, five to choose the set of fields for computing the index, and one for updating the drop field. Thus, for the data-plane target considered in the paper, DynamiQ will require updating 576 match-action table entries. Our current implementation with Tofino's PD-API [16], which updates the match-action table entries one at a time, will take around 200-300 ms to update these many match-action table entries, which is relatively inefficient. However, as discussed in Section 5, this is not a fundamental limitation for DynamiQ. A more efficient API that can update the match-action table rules in parallel can significantly reduce this overhead.

E Load at Stream Processor
This part of the appendix describes how, as part of our evaluation, we extended Sonata's simulator to emulate each of the query-planning techniques listed in Table 3. Some of these techniques (e.g., DynamiQ-Pred, Sonata, etc.) require us to estimate the additional load at the stream processor when the required operator memory exceeds the allocated memory in the data plane. While we can compute this load accurately using a packet-level simulation, such an approach is prohibitively slow.
Instead of packet-level simulation, Sonata uses the stream processor to aggregate cost values for each window and uses these values to estimate the stream processor's load. However, such aggregation loses all information about the order in which packets are processed in the data plane. How we estimate load at the stream processor? To address this issue, we approximate the additional load using the average value. Specifically, we report the product of the average number of tuples-per-key and the number of keys that cannot fit in the data-plane register. For example, if the average number of tuples-per-key for an operator is 10 and given the register size, five keys cannot fit in, then our estimate of the additional load at the stream processor will be 50.
Recall that for every operator, the cost matrix provides three metrics: ( , , ). Here, denotes the number of input tuples for the operator, the number of output tuples after applying the stateful operation, and is the required operator memory. The memory allocated for this operator in the data plane is denoted by . If is greater than , the data-plane register is overprovisioned. In this case, the number of tuples sent to the stream processor ( ) is given by = .
For the cases where the data-plane register is under-provisioned (i.e., < ), we estimate the load due to keys that find an entry in the data plane to be and the additional load due to hash collision to be − . Therefore, the total load due to under-provisioning is estimated as avg = + − . We now describe the calculations used for estimating the best and the worst case load estimates. Recall that in the best case, the keys with only a single tuple arrive at last.   We can express this load as best = + − . Here, denotes the memory footprint of a single key. For the worst case, all the single-tuple keys arrive first and use all the allocated memory in the data plane. We can express this load as worst = − . Figure 13 in the appendix shows the load at the stream processor for each of these three cases. The experiment is similar to the one we conducted for Figure 2a. In particular, we used the first window's cost matrix to compute a static query plan using Sonata's query planner. We then apply this plan on all the 60 windows. We used the three different expressions described above to compute the load at the stream processor for average, best, and worst case, respectively.

F Query Planning Variants
In this part of the appendix, we evaluate the different variants of static and dynamic query planning techniques that are listed in Table 4 and that we implemented as part of our evaluation. Both the static and dynamic variants differ in terms of their choice of algorithms for computing initial query plans (i.e., refinement plans and initial register sizes). Variants of dynamic query planning. To quantify the contributions of initial query plans, we repeat the experiment described in Section 6.2, and Figure 14a shows for each variant the distribution of the load at the stream processor. Here, the gap between DynamiQ-Rand and Sonata quantifies the contributions of dynamic operator mapping because both techniques use the same initial query plan (i.e., the one that consists of the refinement plan and register size configuration computed by Sonata's query planner). Next, the gap between DynamiQ-Rand and DynamiQ-TOM, and DynamiQ-Rand and DynamiQ-SnR, quantifies the contributions of our proposed TOM-based and SnR algorithms, respectively. In both cases, the gains are marginal and demonstrate that both SnR and TOM-based algorithms are not very useful by themselves. Significant workload reductions at the stream processor are only possible when used in combination (i.e., DynamiQ-Oracle). Variants of static query planning. Figure 14b shows the performance of different variants of static query planning. Compared to Sonata, Sonata-Boot reduces the load at the stream processor by half (zero percent over-provisioning case). As we increase the level of over-provisioning, the load initially decreases because over-provisioning has the effect of reducing under-provisioning for many operators. However, as the over-provisioning level keeps increasing, the amount of wasted memory also increases, and so does the resulting load at the stream processor. Compared to DynamiQ, the workload reductions attainable with over-provisioned static query plans are only marginal.

G Bootstrapping Deep Dive
This part of the appendix considers the two proposed bootstrapping algorithms in more detail. More specifically, we provide an intuition for why the two proposed heuristics are effective in providing opportunities for workload reduction with dynamic operator mappings at runtime. 22

Refinement Plan
Register Sizes    TOM-based vs. Sonata's refinement plans. Figure 15a shows the relationship between mean-TOM (y-axis), the number of operators (x-axis), and the max load at the stream processor across all 60 windows (indicated by the data points' color) for refinement plans computed by TOM (star-shaped data points) and Sonata's query planner (circles), respectively. The plot clearly separates the refinement plans selected by our TOM-heuristic (i.e., points in lower left corner) from those computed by Sonata (i.e., points towards the upper right corner) and shows that the characteristic features of the TOM-based plans (i.e., low mean TOM and small number of operators) enable them to handle the workload dynamics more efficiently than Sonata's plans, resulting in a significant reduction in load for the stream processor (i.e., green-vs redcolored nodes). SnR-based vs. Sonata's register sizes. To better understand why the proposed SnR heuristic works well, we conducted the following experiment to be able to compare the performance of the register sizes computed by Sonata's query planner and their slice-n-repeat counterparts. For the experiment, we selected among the slice-n-repeat configurations the ones which result in minimum load at the stream processor. In Figure 15b, we observe that for these performant slices, (1) the load they impose on the stream processors is similar to that of DynamiQ, (2) the total memory and total number of ALUs used by these configurations are high, and (3) the register sizes are approximately proportional to their order or IDs. These empirical observations explain why our SnR heuristic is effective-it tries to emulate the register size distribution of these performant slices.