Multidimensional benchmarking in data warehouses

Akiko Campbell, Xiangbo Mao, Jian Pei, Abdullah Al-BarakatiIntell. Data Anal 2017 · DOI

TL;DR

This paper tackles the challenge of efficiently performing multidimensional benchmarking in data warehouses, a crucial task for business performance improvement that has been technically underexplored. The authors introduce novel algorithms, SIIC and DAM, that leverage data cube computation techniques to significantly reduce the computational and indexing overhead, demonstrating their effectiveness and scalability on benchmark and real-world datasets.

What Problem Does This Paper Address?

Organizations widely use benchmarking to identify areas for improvement. However, applying this practice effectively within data warehouses, especially from a technical efficiency standpoint, has been a significant challenge. Existing data cube and data warehouse techniques struggle to answer "benchmark queries" efficiently. These queries aim to compare a specific group (the "query unit") against others within a multidimensional context, identifying where the query unit excels or falls short. The sheer size of data cubes, which grows exponentially with dimensionality, makes brute-force approaches computationally infeasible. This paper addresses this gap by proposing methods to answer these complex benchmark queries efficiently.

Methods

The paper introduces two main algorithmic approaches:

  • Sorted Inverted Index Cube (SIIC): This method employs two key ideas. First, it sorts aggregate cells within a data cube by their aggregate values in descending order. This heuristic aims to find more significant advantages earlier. Second, it uses inverted indices for each unit-id attribute to quickly access and organize aggregate cells. This allows for efficient retrieval of relevant cells for ancestors, descendants, and siblings of the query unit. A pruning technique is also introduced to further optimize the search by eliminating aspects that cannot lead to top-k answers.
  • Dominant Answer Materialization (DAM): This approach builds upon SIIC but focuses on materializing only "dominant answers." A dominant answer is an aggregate unit and its aspect where no other unit or aspect offers a better performance ratio. DAM leverages the "quotient cube" method, which groups aggregate cells with identical descendant tuples and materializes only the upper bounds of these groups. This significantly reduces the number of cells that need to be computed and stored, leading to greater efficiency.

Datasets

The authors evaluated their algorithms using two datasets:

  • TPC-H benchmark: A standard synthetic dataset widely used for benchmarking database systems. The paper used a joined result of the PART and LINEITEM tables.
  • Weather data set: A real-world dataset containing over a million tuples with attributes related to weather observations.

Key Insights and Ideas

  • Benchmarking is technically challenging in data warehouses: Unlike traditional OLAP queries, benchmark queries require comparing specific units across multiple dimensions, which is computationally intensive with large datasets.
  • The "Dominant Answer" concept is key to efficiency: By focusing only on dominant answers, DAM drastically reduces the search space and materialization effort compared to methods that consider all aggregate cells.
  • Data cube structure can be exploited for efficiency: Both SIIC and DAM leverage data cube properties and advanced computation techniques (like quotient cubes) to optimize the process.
  • Pruning is crucial for SIIC: The pruning strategy in SIIC helps to cut down the search space during query answering, making it more efficient than a naive scan.

Key Results

The empirical study demonstrated significant improvements:

  • Reduced computation and indexing: The DAM method, in particular, computed and indexed substantially fewer cells compared to SIIC/SIICP. For instance, on TPC-H, DAM computed and indexed about 10% of the cells compared to SIICP/SIIC, with savings increasing as the dimensionality of UID increased.
  • Faster query answering and indexing: DAM consistently outperformed SIIC and SIICP in both index construction (materialization) and query answering times across both TPC-H and Weather datasets. DAM's runtime increased more slowly with increasing dimensionality.
  • Lower memory usage: DAM consumed significantly less memory than SIIC and SIICP, both during index construction and query answering. This memory advantage also scaled better with increasing dimensionality.
  • Scalability: The DAM algorithm showed strong scalability with increasing dataset sizes, maintaining its efficiency advantage over SIIC and SIICP.

Limitations and Future Work

  • Search Scope Limitations: While the paper addresses ancestor and descendant search scopes, the sibling search scope for SIIC is noted as potentially incurring significant cost in the worst case.
  • Future Work: The authors plan to develop tools based on their techniques to enable multidimensional benchmarking in business. They also aim to explore new types of analytic queries and tasks that can be built upon benchmark queries.

Summary updated

BibTeX
@article{campbell2017multidimensional,
  author = {Akiko Campbell and Xiangbo Mao and Jian Pei and Abdullah Al-Barakati},
  title = {{Multidimensional benchmarking in data warehouses}},
  journal = {Intell. Data Anal.},
  year = {2017},
  doi = {10.3233/ida-160035},
}

Loading related content...

Figure