Effiziente Integration von Data- und Graph-Mining-Algorithmen in relationale Datenbanksysteme

Manuel Then, Linnea Passing, Nina C. Hubig, Stephan Günnemann, Alfons Kemper, Thomas NeumannLWA 2015 · OpenReview

Abstract

Traditionally, data mining requires moving data from relational databases to specialized analytical frameworks, incurring a significant "data tax." This paper explores the deep integration of complex data and graph mining algorithms directly into the HyPer main-memory database. By utilizing novel SQL extensions for iterative processing and specialized kernel operators, the authors demonstrate that in-database mining can eliminate ETL overhead and outperform popular frameworks like Apache Spark by up to two orders of magnitude.

Introduction

The standard workflow for big data analytics involves extracting data from a database (ETL) and loading it into tools like MATLAB or Spark. This approach is increasingly inefficient as datasets grow and change rapidly. While some commercial databases offer mining libraries, these are often surface-level integrations that treat algorithms as black boxes. This paper proposes a "deep integration" where mining logic and standard SQL queries are compiled and optimized together using LLVM-based code generation.

Methodology

The researchers introduced a multi-layered approach within the HyPer database system to support high-performance analytics:

  1. Iterative SQL Extensions: Standard SQL recursion is designed for monotonic growth, which is memory-intensive for machine learning. The authors proposed a new syntax: WITH RECURSIVE [Algo] AS ([Initialization] ITERATE [Step] UNTIL [Condition]). This allows the system to overwrite state between iterations, drastically reducing memory overhead.
  2. Kernel-Level Operators: Common algorithms like PageRank are implemented as first-class physical operators. This enables the use of optimized graph representations that surpass the performance of standard relational tables.
  3. Lambda Expressions: To maintain flexibility, users can pass Lambda functions into SQL queries (e.g., custom distance metrics for K-Means), allowing for custom logic without sacrificing parallel code generation benefits.
  4. Layered User Model: The system supports various user levels, from laypeople using pre-defined functions to programmers writing low-level User-Defined Functions (UDFs).

Experimental Setup

The system was evaluated using both synthetic vector data and real-world graph benchmarks. The vector datasets (Syn 1–3) varied in dimensionality and scale to test K-Means clustering, while the LDBC Social Network Benchmark (SF 1 and 10) provided complex graph structures for PageRank testing.

Characteristics of the synthetic vector and LDBC graph datasets used in the evaluation.

Key Results and Discussion

The performance of HyPer was compared against Apache Spark 1.4.0 and MATLAB R2015a. The results highlight the efficiency of deep integration:

  • PageRank (Graph Analysis): The specialized kernel operator (HyPer Op) was 1–2 orders of magnitude faster than Spark. Even the SQL-extension version (HyPer SQL) outperformed Spark and scaled more effectively.
  • K-Means (Vector Analysis): HyPer's kernel implementation was approximately 1–2x faster than Spark, demonstrating that even without specialized graph structures, the compilation approach is highly competitive.
  • Memory Management: While MATLAB suffered from "Out of Memory" (OOM) errors on larger datasets (Syn 3 and LDBC SF 10), HyPer managed its memory pool effectively, processing the data without failure.
Performance comparison of HyPer (Operator and SQL versions) against Spark and MATLAB.

Conclusion

By integrating mining algorithms directly into the database engine, the authors successfully eliminated the ETL bottleneck. The use of LLVM-based compilation allows the database to pipeline data seamlessly between standard SQL queries and complex mining logic. Future work will focus on maturing the query optimizer to automatically generate optimal plans for complex iterative algorithms and expanding the library to include techniques like Support Vector Machines and Deep Learning.

Summary updated

BibTeX
@inproceedings{then2015effiziente,
  author = {Manuel Then and Linnea Passing and Nina C. Hubig and Stephan Günnemann and Alfons Kemper and Thomas Neumann},
  title = {{Effiziente Integration von Data- und Graph-Mining-Algorithmen in relationale Datenbanksysteme}},
  booktitle = {LWA},
  year = {2015},
  url = {https://openreview.net/forum?id=X3LNfbZnurt},
}
Figure