Daniel Lupei

École Polytechnique Fédérale de Lausanne

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Christoph Koch

École Polytechnique Fédérale de Lausanne

Val Tannen

University of Pennsylvania

Miloš Nikolić

University of Edinburgh

Todd Mytkowicz

Microsoft Research (United Kingdom)

Madan Musuvathi

Microsoft (United States)

Andres Nötzli

Cubist Pharmaceuticals (United States)

Saeed Maleki

Microsoft Research (United Kingdom)

Yanif Ahmad

Johns Hopkins University

Christof Koch

Allen Institute

Oliver Kennedy

University at Buffalo, State University of New York

Cooperative Institutions

École Polytechnique Fédérale de Lausanne

Microsoft Research (United Kingdom)

Microsoft (United States)

University at Buffalo, State University of New York

Cornell University

University of Edinburgh

University of Oxford

Laboratoire d'Informatique Fondamentale de Lille

University of Split

University of Colorado Boulder

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Jumping the ORDER BY Barrier in Large-Scale Pattern Matching

Daniel Lupei Mike Barnett Saeed Maleki Madan Musuvathi Todd Mytkowicz

Event-series pattern matching is a major component of large-scale data analytics pipelines enabling a wide range of system diagnostics tasks. A precursor to pattern matching is an expensive ``shuffle the world'' stage wherein data are ordered by time and shuffled across the network. Because many existing systems treat the pattern matching engine as a black box, they are unable to optimizing the entire data analytics pipeline, and in particular, this costly shuffle. This paper demonstrates how to optimize such queries. We first translate an expressive class of regular-expression like patterns to relational queries such that they can benefit from decades of progress in relational optimizers, and then we introduce the technique of abstract pattern matching, a linear time preprocessing step which, adapting ideas from symbolic execution and abstract interpretation, discards events from the input guaranteed not to appear in successful matches. Abstract pattern matching first computes a conservative representation of the output-relevant domain of every transition in a pattern based on the (unary) predicates of that transition. It then further refines these domains based on the structure of the pattern (i.e., paths through the pattern) as well as any of the pattern's join predicates across transitions. The outcome is an abstract filter that when applied to the original stream excludes events that are guaranteed not to participate in a match. We implemented and applied abstract pattern matching in COSMOS/Scope to an industrial benchmark where we obtained up to 3 orders of magnitude reduction in shuffled data and 1.23x average speedup in total processing time.

Unary operation

Regular expression

Benchmark (surveying)

Source

Cite

Citations (0)

Incremental View Maintenance For Collection Programming

arXiv (Cornell University) (2014)

Christoph Koch Daniel Lupei Val Tannen

In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the materialized view more efficiently than via recomputation. In this work we propose the first solution for the efficient incrementalization of positive nested relational calculus (NRC+) on bags (with integer multiplicities). More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify IncNRC+; a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incremental maintenance for NRC+ is within the complexity class NC0 and we showcase how recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries [25], can also be applied to IncNRC+.

Fragment (logic)

Source

Cite

Citations (0)

Compilation Techniques for Incremental Collection Processing

Daniel Lupei

Many map-reduce frameworks as well as NoSQL systems rely on collection programming as their interface of choice due to its rich semantics along with an easily parallelizable set of primitives. Unfortunately, the potential of collection programming is not entirely fulfilled by current systems as they lack efficient incremental view maintenance (IVM) techniques for queries producing large nested results. This comes as a consequence of the fact that the nesting of collections does not enjoy the same algebraic properties underscoring the optimization potential of typical collection processing constructs. We propose the first solution for the efficient incrementalization of collection programming in terms of its core constructs as captured by the positive nested relational calculus (NRC+) on bags (with integer multiplicities). We take an approach based on delta query derivation, whose goal is to generate delta queries which, given a small change in the input, can update the materialized view more efficiently than via recomputation. More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify IncNRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incrementalmaintenance for NRC+ is within the complexity class NC0 and we showcase how Recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries, can also be applied to IncNRC+ . Existing systems are also limited wrt. the size of inner collections that they can effectively handle before running into severe performance bottlenecks. In particular, in the face of nested collections with skewed cardinalities developers typically have to undergo a painful process of manual query re-writes in order to ensure that the largest inner collections in their workloads are not impacted by these limitations. To address these issues we developed SLeNDer, a compilation framework that given a nested query generates a set of semantically equivalent (partially) shredded queries that can be efficiently evaluated and incrementalized using state of the art techniques for handling skew and applying delta changes, respectively. The derived queries expose nested collections to the same opportunities for distributing their processing and incrementally updating their contents as those enjoyed by top-level collections, leading on our benchmark to up to 16.8x and 21.9x speedups in terms of offline and online processing, respectively. In order to enable efficient IVM for the increasingly common case of collection programming with functional values as in Links, we also discuss the efficient incrementalization of simplytyped lambda calculi, under the constraint that their primitives are themselves efficiently incrementalizable.

Nesting (process)

10.5075/epfl-thesis-8019

Cite

Citations (0)

Incremental View Maintenance For Collection Programming

Christoph Koch Daniel Lupei Val Tannen

Materialized view

10.1145/2902251.2902286

Cite

Citations (23)

DBToaster: higher-order delta processing for dynamic, frequently fresh views

The VLDB Journal (2014)

Christoph Koch Yanif Ahmad Oliver Kennedy Miloš Nikolić Andres Nötzli

Materialized view

Stored procedure

Millisecond

SQL Injection

10.1007/s00778-013-0348-4

Cite

Citations (60)

Incremental View Maintenance For Collection Programming

arXiv (Cornell University) (2014)

Christof Koch Daniel Lupei Val Tannen

Fragment (logic)

10.48550/arxiv.1412.4320

Cite

Citations (0)

Incremental View Maintenance for Nested-Relational Databases.

arXiv (Cornell University) (2014)

Daniel Lupei Christoph Koch Val Tannen

Incremental view maintenance is an essential tool for speeding up the processing of large, locally changing workloads. Its fundamental challenge is to ensure that changes are propagated from input to output more efficiently than via recomputation. We formalize this requirement for positive nested relational algebra (NRA+) on bags and we propose a transformation deriving deltas for any expression in the language. The main difficulty in maintaining nested queries lies in the inability to express within NRA+ the efficient updating of inner bags, i.e., without completely replacing the tuples that contain them. To address this problem, we first show how to efficiently incrementalize IncNRA+, a large fragment of NRA+ whose deltas never generate inner bag updates. We then provide a semantics-preserving transformation that takes any nested query into a collection of IncNRA+ queries. This constitutes the first static solution for the efficient incremental processing of languages with nested collections. Furthermore, we show that the state-of-the-art technique of recursive IVM, originally developed for positive relational algebra with aggregation, also extends to nested queries. Finally, we generalize our static approach for the efficient incrementalization of NRA+ to a family of simply-typed lambda calculi, given that its primitives are themselves efficiently incrementalizable.

Nested loop join

Relational algebra

Fragment (logic)

Nested set model

Source

Cite

Citations (1)