Scalable Data Management for Future Hardware

Foreword
Preface
Acknowledgements
Contents
Contributors
1 ADAMANT: Hardware-Accelerated Query Processing Made Easy
	1.1 Introduction
	1.2 Challenges for ADAMANT\'s Plug\'n\'Play Architecture
		1.2.1 C1: Device-Specific Processing Capabilities
		1.2.2 C2: Exploitation of Full Processing Power
		1.2.3 C3: Effective Parallel Execution of Multiple Queries
	1.3 Approximate Query Processing
		1.3.1 Approximation Approaches
		1.3.2 Bag of Little Bootstraps
		1.3.3 Streaming BLB
		1.3.4 FPGA-Based Bag of Little Bootstraps
			1.3.4.1 Gaussian Random Number Generation (GRNG) on FPGAs
			1.3.4.2 BLB Block Design
		1.3.5 Test Setup
		1.3.6 Evaluation
		1.3.7 Conclusion
	1.4 Device-Specific Primitive Graphs
		1.4.1 Primitives
			1.4.1.1 Motivation
			1.4.1.2 Survey of primitives
		1.4.2 Grouped Aggregation as Device-Specific Primitive
			1.4.2.1 Motivation
			1.4.2.2 Method
			1.4.2.3 Minimizing Atomics Using Private Space
			1.4.2.4 Evaluation
			1.4.2.5 Conclusion
		1.4.3 Primitive Libraries
			1.4.3.1 Motivation and Method
			1.4.3.2 Evaluation
			1.4.3.3 Conclusion
		1.4.4 Primitive Fusion
			1.4.4.1 Motivation
			1.4.4.2 Method
			1.4.4.3 Results
	1.5 FPGA Overlay Template
		1.5.1 Motivation
		1.5.2 Investigation of OpenCL-Based HLS
		1.5.3 FPGA Overlay Template
		1.5.4 Results
	1.6 Cross-Device Query Execution Methods
		1.6.1 4-Phase Chunked Execution for Cross-Device Execution
			1.6.1.1 Motivation
			1.6.1.2 Method
			1.6.1.3 Evaluation
		1.6.2 Combining Compiled and Interpreted Execution
			1.6.2.1 Motivation
			1.6.2.2 Method
			1.6.2.3 Evaluation
	1.7 Multi-query Processing
		1.7.1 Motivation
		1.7.2 Method
		1.7.3 Evaluation
		1.7.4 Conclusion
	1.8 Conclusion
	References
2 Query Processing on Heterogeneous Hardware
	2.1 Introduction
	2.2 Background
		2.2.1 Query Compilation
		2.2.2 Compilers
		2.2.3 Databases on Heterogeneous Hardware
	2.3 Query Processing on Heterogeneous CPU/GPU Systems
		2.3.1 Processor Architectures
		2.3.2 Conventional CPUs
		2.3.3 Dedicated GPUs
		2.3.4 GPU Integration
		2.3.5 GPU Programming Model
			2.3.5.1 Abstract Parallel Programming Model
			2.3.5.2 Scalable Parallelism
			2.3.5.3 Differences to CPU Programming
	2.4 Processing Large Data on GPUs with Fast Interconnects
		2.4.1 Analysis of Fast Interconnect
	2.5 Efficient Stream Processing Through Adaptive QueryCompilation
		2.5.1 Query Compilation
		2.5.2 Grizzly
			2.5.2.1 Challenges for Compilation-Based SPEs
			2.5.2.2 Core Principles of Grizzly
			2.5.2.3 Compilation-Based Query Execution
	2.6 Conclusion
	References
3 Efficient Event Processing on Modern Hardware
	3.1 Introduction
	3.2 Preliminaries
		3.2.1 Data Model
		3.2.2 Operations
	3.3 Related Work
	3.4 System and Hardware Overview
		3.4.1 ChronicleDB
			3.4.1.1 Index and Storage Design
			3.4.1.2 Optimizations
		3.4.2 Java Event Processing Connectivity (JEPC)
	3.5 Event Pattern Matching
		3.5.1 Index Acceleration
		3.5.2 Situation Pattern Matching
		3.5.3 Group Pattern Matching
	3.6 Energy Efficiency and iGPUs
		3.6.1 HSA Facilities
		3.6.2 Operators
		3.6.3 Energy Efficiency
			3.6.3.1 iGPUs
			3.6.3.2 Mobile Devices
			3.6.3.3 Evaluation
	3.7 Compression
	3.8 Applications
	3.9 Conclusion and Outlook
	References
4 Hybrid Transactional/Analytical Graph Processing in Modern Memory Hierarchies
	4.1 Introduction
	4.2 Background
		4.2.1 Persistent Memory Characteristics
		4.2.2 Property Graph Model
		4.2.3 Temporal Graphs
	4.3 Data Structures for Transactional Graph Data in PMem
		4.3.1 Design Goals
		4.3.2 Data Structures for Graphs
	4.4 Graph Query Processing
		4.4.1 Push-Based Approach
		4.4.2 Just-in-Time Query Compilation
		4.4.3 Adaptive Query Compilation
		4.4.4 Query Recovery
	4.5 Graph Analytics on Transactional Data
		4.5.1 Data Structures for Graph Analytics
	4.6 Exploiting the Storage Hierarchy for Time-Travel Queries
		4.6.1 Data Model
		4.6.2 Temporal Query Processing
		4.6.3 TMV Model
	4.7 Related Work
		4.7.1 PM-Aware Storage Design
		4.7.2 Graph Database Management
		4.7.3 Temporal Graph Data Management
	4.8 Evaluation
	4.9 Conclusion
	References
5 MxKernel: A Bare-Metal Runtime System for Database Operations on Heterogeneous Many-Core Hardware
	5.1 Introduction
	5.2 Task-Based Parallelism
		5.2.1 Background
		5.2.2 MxTask Abstraction
		5.2.3 Annotation-Driven Prefetching
			5.2.3.1 Managing Prefetch Requests
			5.2.3.2 Prefetch Distance
		5.2.4 Annotation-Driven Synchronization
			5.2.4.1 Integrated Synchronization Primitives
			5.2.4.2 Applying Synchronization
		5.2.5 Annotation-Driven Heterogeneity
	5.3 Leveraging Tasks at the DBMS Layer
		5.3.1 Building a Task-Based Blink-Tree
			5.3.1.1 Operations
			5.3.1.2 Annotation-Based Prefetching
			5.3.1.3 Annotation-Based Synchronization
		5.3.2 Experimental Evaluation
			5.3.2.1 Annotation-Based Prefetching
			5.3.2.2 Comparison with State-of-the-Art Data Structures
	5.4 Dynamic Resource Management with Tasks and Cells
		5.4.1 Background
		5.4.2 State of the Art
		5.4.3 Enabling Swift Adaptation with the MxKernel
		5.4.4 Experimental Evaluation
			5.4.4.1 Dynamic Adaptation System Cost
			5.4.4.2 Impact on Tail Latencies
	5.5 Conclusion and Future Work
	References
6 Scaling Beyond DRAM Without Compromising Performance
	6.1 Introduction
		6.1.1 The Tough Reality
		6.1.2 Our Contributions
	6.2 Mosaic
		6.2.1 Placement Mechanism
		6.2.2 Evaluation
	6.3 Plush
		6.3.1 The Problem with Persistent Memory
		6.3.2 Architecture
		6.3.3 Evaluation
	6.4 Programming Fully Disaggregated Systems
		6.4.1 Trends in Large-Scale Data Processing
		6.4.2 Design Principles
	6.5 ARM: Code Generation for High-End and Edge Devices
		6.5.1 Query Compilation
			6.5.1.1 Architectural Challenges
			6.5.1.2 Code Generation Evaluation
		6.5.2 Embedded ARM Processors
	6.6 Conclusions
	References
7 ReProVide: Query Optimization and Near-Data Processing on Reconfigurable SoCs for Big Data Analysis
	7.1 Introduction
	7.2 Related Work
	7.3 Heterogeneous Partially Reconfigurable Architecture for Near-Data Processing
		7.3.1 Reconfigurable Data-Provider Unit (RPU) Architecture
		7.3.2 Determining a Query-Specific Configuration for RPUs
		7.3.3 RPU-Supported Operators and Operations
		7.3.4 Optimistic Filtering to Support Complex and Blocking Operators
	7.4 Near-Data Processing of Streaming Data
		7.4.1 Raw Filtering for Optimistic Data-Stream Processing
		7.4.2 Parse-Filter-Project: Selective Data-Stream Parsing
			7.4.2.1 Avro Parsing
			7.4.2.2 JSON Parsing
	7.5 Query Optimization for Heterogeneous ReProVide Clusters
		7.5.1 Holistic Query Optimization
		7.5.2 Optimizing Relational and Stream-Based Queries for Heterogeneous Systems
			7.5.2.1 Plan Enumeration and Selection
			7.5.2.2 A Cost Model for Heterogeneous Query Processing
			7.5.2.3 Example Query and Execution Plans
			7.5.2.4 Managing Limited Hardware Resources and Accelerators
		7.5.3 Learning from the Past: Offline Optimization to Improve Query Optimization
			7.5.3.1 Detecting Query Sequences
			7.5.3.2 Probe Queries
			7.5.3.3 Query Repository
	7.6 Experimental Evaluation
	7.7 Summary
	References
8 Scalable Data Management on Next-Generation Data Center Networks
	8.1 Introduction
	8.2 Background
		8.2.1 Remote Direct Memory Access (RDMA)
		8.2.2 Programmable Switches
	8.3 Scalable Data Management with RDMA
	8.4 P4DB: The Case for In-Network OLTP
		8.4.1 Overview of P4DB
			8.4.1.1 Declustered Storage Model
			8.4.1.2 Transactional Properties
			8.4.1.3 Warm Transactions
		8.4.2 Experimental Evaluation
		8.4.3 Growing Hot-Sets Beyond Switch\'s Capacity
		8.4.4 Summary
	8.5 Zero-Sided RDMA
		8.5.1 Overview of Zero-Sided RDMA
			8.5.1.1 Core Challenges of Realizing Zero-Sided RDMA
			8.5.1.2 Communication Abstractions
			8.5.1.3 Flow of Data Transfers
			8.5.1.4 Hardware Requirements
		8.5.2 Switch vs. SmartNICs
		8.5.3 Advanced Communication Flows in Zero-Sided RDMA
		8.5.4 Experimental Evaluation
			8.5.4.1 Efficiency of Network-Driven Transfers
			8.5.4.2 Fine-Grained Flow Prioritization
		8.5.5 Summary
	8.6 Conclusion and Future Directions
	References
9 Managing Very Large Datasets on Directly AttachedNVMe Arrays
	9.1 Introduction
	9.2 Slicing Through the I/O Stack Abstraction Layers
		9.2.1 Experimental Setup
		9.2.2 Slicing Through the I/O Stack
		9.2.3 Secret Flags in the Kernel Universe
		9.2.4 A Lower Bound for I/O Handling
		9.2.5 Thank God It\'s Fsynced: Durability
	9.3 Benchmarking and Hardware Pitfalls
		9.3.1 Don\'t Trust a Benchmark You Did Not Do Yourself
		9.3.2 The Strange Case of the IOMMU and Its Root-Complex
		9.3.3 Too Hot to Handle
		9.3.4 The Shark
	9.4 I/O in High-Performance Storage Engines
		9.4.1 Visible Without Looking Glass
		9.4.2 NVMe-Enabled Performance in Storage Engines
		9.4.3 Exploiting New Kernel Features
	9.5 Conclusion
	References