Toward timely, predictable and cost-effective data analytics

Modern industrial, government, and academic organizations are collecting massive amounts of data at an unprecedented scale and pace. The ability to perform timely, predictable and cost-effective analytical processing of such large data sets in order to extract deep insights is now a key ingredient for success. Traditional database systems (DBMS) are, however, not the first choice for servicing these modern applications, despite 40 years of database research. This is due to the fact that modern applications exhibit different behavior from the one assumed by DBMS: a) timely data exploration as a new trend is characterized by ad-hoc queries and a short user interaction period, leaving little time for DBMS to do good performance tuning, b) accurate statistics representing relevant summary information about distributions of ever increasing data are frequently missing, resulting in suboptimal plan decisions and consequently poor and unpredictable query execution performance, and c) cloud service providers - a major winner in the data analytics game due to the low cost of (shared) storage - have shifted the control over data storage from DBMS to the cloud providers, making it harder for DBMS to optimize data access. This thesis demonstrates that database systems can still provide timely, predictable and cost-effective analytical processing, if they use an agile and adaptive approach. In particular, DBMS need to adapt at three levels (to workload, data and hardware characteristics) in order to stabilize and optimize performance and cost when faced with requirements posed by modern data analytics applications. Workload-driven data ingestion is introduced with NoDB as a means to enable efficient data exploration and reduce the data-to-insight time (i.e., the time to load the data and tune the system) by doing these steps lazily and incrementally as a side-effect of posed queries as opposed to mandatory first steps. Data-driven runtime access path decision making introduced with Smooth Scan alleviates suboptimal query execution, postponing the decision on access paths from query optimization, where statistics are heavily exploited, to query execution, where the system can obtain more details about data distributions. Smooth Scan uses access path morphing from one physical alternative to another to fit the observed data distributions, which removes the need for a priori access path decisions and substantially improves the predictability of DBMS. Hardware-driven query execution introduced with Skipper enables the usage of cold storage devices (CSD) as a cost-effective solution for storing the ever increasing customer data. Skipper uses an out-of-order CSD-driven query execution model based on multi-way joins coupled with efficient cache and I/O scheduling policies to hide the non-uniform access latencies of CSD. This thesis advocates runtime adaptivity as a key to dealing with raising uncertainty about workload characteristics that modern data analytics applications exhibit. Overall, the techniques introduced in this thesis through the three levels of adaptivity (workload, data and hardware-driven adaptivity) increase the usability of database systems and the user satisfaction in the case of big data exploration, making low-cost data analytics reality.

Time- and Space-Efficient Spatial Data Analytics

Mirjana Pavlovic

Advances in data acquisition technologies and supercomputing for large-scale simulations have led to an exponential growth in the volume of spatial data. This growth is accompanied by an increase in data complexity, such as spatial density, but also by more varied data distributions. As data evolves, so do the needs of applications. Recently, we notice a shift from predefined to ad-hoc workloads, as a result of the recent data exploration trend among data-driven applications. At the same time, given the massive volume of data, it has become imperative to use computational and storage resources efficiently, where efficiency requirements typically vary across applications. In this thesis, we show that traditional spatial data management techniques underperform as data size and complexity increase: they waste both computational and storage resources. They are also inefficient in supporting ad-hoc workloads. To achieve time- and space-efficiency, we design spatial data management algorithms and storage layouts that leverage and adapt to data characteristics and workload access patterns. In particular, we revisit the design of spatial join algorithms, indexing techniques and point cloud data management solutions. First, we propose data-aware spatial joins that leverage and adapt to dataset characteristics to avoid wasting computational resources and achieve time-efficiency on non-uniform data distributions. GIPSY is designed to efficiently join two datasets with contrasting densities. GIPSY uses the sparser dataset to guide the join process and therefore, by leveraging dataset characteristics, selectively retrieves and joins only the data needed. TRANSFORMERS achieves robust performance and time-efficiency on non-uniform data distributions, by adapting to dataset characteristics. It detects local variations in distributions and adapts the join strategy and data layout to local dataset characteristics at run-time. We next introduce incremental indexing approaches that take into account workload access patterns. This way, they minimize the data-to-insight time and avoid unnecessary preprocessing costs, substantially accelerating the exploratory analysis of spatial data. Incremental indexes are built as a side-effect of query execution and only for the parts of the data queried. Space Odyssey is designed for exploratory analyses of multiple spatial datasets that reside on disk. It takes advantage of workload access patterns to incrementally index the datasets and optimize accesses to parts frequently queried together. QUASII supports spatial data exploration in main memory. QUASII reduces the data-to-insight time and curbs the cost of incremental indexing, by gradually and partially sorting the data, while simultaneously producing a data-oriented hierarchical structure. Finally, we propose a time- and space-efficient solution to storing and managing point cloud data in main memory column-store database management systems. Our approach leverages point cloud data properties to employ dictionary-based compression in the spatial data management domain and enhances it with indexing capabilities by using space-filling curves. The proposed scheme also represents a partitioning strategy. It is a middle ground between data- and space-oriented partitioning, accounting for the data distribution, while preserving the simplicity of grid-like structures.

EPFL2019

Timely and cost-efficient data exploration through adaptive tuning

Matthaios Alexandros Olma

Modern applications accumulate data at an exponentially increasing rate and traditional database systems struggle to keep up. Decision support systems used in industry, rely heavily on data analysis, and require real-time responses irrespective of data size. To offer real-time support, traditional databases require long preprocessing steps, such as data loading and offline tuning. Loading transforms raw data into a format that reduces data access cost. Through tuning, database systems build access paths (e.g., indexes) to improve query performance by avoiding or reducing unnecessary data access. The decision on what access paths to build depends on the expected workload, thus, the database system assumes knowledge of future queries. However, decision support systems and data exploration applications have shifting requirements. As a consequence, an offline tuner with no a priori knowledge of the full workload is unable to decide on the optimal set of access paths. Furthermore, access path size increases along with input data, thus, building precise access paths over the entire dataset limits the scalability of databases systems. Apart from long database pre-processing, offering efficient data access despite increasing data volume becomes harder due to hardware architectural constraints such as memory size. To achieve low query latency, modern database systems store data in main memory. However, there is a physical limit on main memory size in a server. Thereby, applications must trade memory space for query efficiency. To provide high performance efficiency, irrespective of dataset growth and query workload, a database system needs to (i) shift the decision of tuning from off-line to query-time, (ii) enable the query engine to exploit application properties in choosing fast access paths, and (iii) reduce the size of access paths to limit storage cost. In this thesis, we present techniques for query processing that are adaptive to workload, application requirements, and available storage resources. Specifically, to address dynamic workloads, we turn access path creation into a continuous process which fully adapts to incoming queries. We assign all decisions on data access and access path materialization to the database optimizer at query time, and enable access path materialization to take place as a by-product of query execution, thereby, removing requirements for long offline tuning processing steps. Furthermore, we take advantage of application characteristics (precision requirements, resource availability) and we design a system which can adaptively trade precision and resources for performance. By combining precise and approximate access paths, the database system reduces query response time and minimizes resource utilization. Approximate access paths (e.g., sketches) require less space in comparison to their precise counterparts, and offer constant access time. By improving data processing performance while reducing storage requirements through (i) adaptive access path materialization and (ii) using approximate and space-efficient access paths when appropriate, our work minimizes data access cost and provides real-time responses for data exploration applications irrespective of data growth.

EPFL2019

Efficient Query Processing for Spatial and Temporal Data Exploration

Eleni Tzirita Zacharatou

Core to many scientific and analytics applications are spatial data capturing the position or shape of objects in space, and time series recording the values of a process over time. Effective analysis of such data requires a shift from confirmatory pipelines to exploratory ones. However, there is a mismatch between the requirements of spatial and temporal data exploration and the capabilities of the data management solutions available today. First, traditional spatial query operators evaluate spatial relations with time-consuming geometric tests that oppose the interactivity expected from exploratory applications, creating an undue overhead. Second, spatial access methods are built on top of rough geometric object approximations that do not capture the complex structure and distribution of today's spatial data and are thus inefficient. Third, traditional indexes are typically built upfront before queries can be processed and over single data attributes, thus precluding interactive accesses to interesting data subsets that may be specified with constraints on multiple attributes. Finally, existing access methods scale poorly with increasingly granular spatial and temporal data originating from ever more precise data acquisition technologies and ever faster computing infrastructure. This thesis introduces a novel family of spatial and temporal access methods and query operators that aim to bridge the gap between existing data management techniques and data exploration applications. We show that spatial query operators can be decomposed into primitive graphics operations that are efficiently executed by graphics hardware (GPU) and allow to trade accuracy for interactivity. Furthermore, we design access methods that adapt to data characteristics, data growth trends, and workload access patterns, thereby providing scalable performance for ad-hoc queries over increasing data amounts. Specifically, we introduce a spatial approximation that adapts to the structural properties and distribution of the data, and propose spatial and time series access methods that leverage similarities between data items and support filtering over multiple attributes. Finally, we present an approach that indexes data incrementally, using queries as hints for optimizing data access.

EPFL2019

Time- and Space-Efficient Spatial Data Analytics

Mirjana Pavlovic

EPFL2019

Efficient Query Processing for Spatial and Temporal Data Exploration

Eleni Tzirita Zacharatou

EPFL2019

Timely and cost-efficient data exploration through adaptive tuning

Matthaios Alexandros Olma

EPFL2019