Generating Efficient Execution Plans for Vertically Partitioned XML Databases

Patrick Kling, M. Tamer Özsu, Khuzaima DaudjeePVLDB 2010 · DOI · OpenReview

TL;DR

This paper tackles the challenge of efficiently querying vertically partitioned XML databases. They introduce a novel method for generating distributed execution plans that optimize for response time, outperforming both centralized and naive distributed approaches, especially for selective queries.

What Problem Does This Paper Address?

As XML data becomes ubiquitous, so does the need for scalable query processing. While centralized XML databases are well-understood, they struggle with large datasets and heavy workloads. Relational databases have addressed this through distribution and partitioning, but directly applying these techniques to XML is difficult due to XML's tree structure and query models. This paper focuses on generating efficient distributed execution plans for XML databases that are vertically partitioned, meaning different types of data are stored at different locations. The core problem is how to combine results from these distributed fragments to answer a query quickly, considering the inherent parallelism and potential overheads of distributed systems.

Methods

The authors propose a multi-pronged approach:

  • Distribution Model: They adopt a distribution model based on schema characteristics and query operators, similar to relational databases (horizontal, vertical, and hybrid fragmentation). Their focus is specifically on vertical fragmentation.
  • Distributed Execution Plan Generation: They introduce a technique for constructing distributed execution plans that are independent of local query evaluation strategies. This involves localizing queries, generating local plans at each site, and then optimizing how these local results are combined.
  • Optimization Techniques:
    • Pushing Cross-Fragment Joins: This technique pushes join operations from the distributed plan into the local query plans. This allows filtering of irrelevant document subtrees early on, reducing the amount of data processed locally and shipped. They ensure this optimization doesn't compromise parallelism by using pipelined execution.
  • Label Path Filtering: This method filters document subtrees based on their "label path" (the sequence of node types from the root). This is useful when cross-fragment join pushing isn't fully applicable (e.g., for non-left-deep plans) and offers a way to prune subtrees without impacting parallelism.
  • Response Time-Based Cost Model: A crucial component is a cost model that estimates the response time of a distributed execution plan. This model considers the costs of local plans, cardinalities, and importantly, the parallelism and dependencies introduced by the optimization techniques.

Datasets

The authors use the XMark benchmark [21] for their experiments. They specifically mention using collections of on-line auction data generated by XMark, scaling them to various sizes (35 MB, 350 MB, 3.5 GB, 120 MB, 1.2 GB, 12 GB). They also use a subset of queries from the XPathMark benchmark for their second experiment, including both original and "selective" versions (with added value predicates).

Key Insights and Ideas

  • Vertical Partitioning is Key for XML Scalability: Just like in relational systems, distributing XML data via partitioning is essential for handling large datasets and query workloads.
  • Optimizations are Crucial for Distributed XML: Naive distributed query execution can sometimes be worse than centralized approaches due to overhead. Techniques like pushing cross-fragment joins and label path filtering are vital for realizing the benefits of distribution.
  • Pushing Joins is Generally Preferred: The paper strongly suggests that pushing cross-fragment joins is the most effective optimization, especially for selective queries, as it significantly reduces local processing and data transfer.
  • Parallelism is Paramount: The proposed optimizations are designed to maintain or improve parallelism, preventing distributed execution from becoming a bottleneck. Pipelined execution is key to achieving this.
  • Response Time is the Right Metric: Focusing on response time as the cost metric, rather than just throughput, is critical for interactive query systems.

Key Results

  • Significant Speedups: Optimized distributed query execution (using cross-fragment join pushing) achieved speedups of up to 6x compared to centralized execution for challenging queries (Q3-Q5). For simpler queries (Q1-Q2), the speedup was even more pronounced.
  • Outperforming Centralized: For larger datasets, optimized distributed execution consistently outperformed centralized execution, demonstrating its scalability benefits.
  • Label Path Filtering Benefits: While less impactful than join pushing, label path filtering still provided noticeable improvements, especially when applicable to multiple fragments.
  • Cost Model Overhead is Minimal: The cost model's overhead was negligible (less than 0.01 seconds), making exhaustive plan enumeration feasible.

Limitations and Future Work

  • Focus on Vertical Partitioning: The paper explicitly states that their focus is on vertically partitioned XML databases, and plans for horizontal and hybrid distribution will be addressed in future work.
  • Plan Shapes: The cross-fragment join pushing optimization is most effectively applied to left-deep execution plans. While label path filtering is more general, the paper acknowledges that other plan shapes might not fully benefit from join pushing.
  • Future Work: The authors suggest that extending their work to horizontal and hybrid fragmentation is a natural next step. They also mention that pruning irrelevant subtrees is an ongoing area of research.

Summary updated

BibTeX
@article{kling2010generating,
  author = {Patrick Kling and M. Tamer Özsu and Khuzaima Daudjee},
  title = {{Generating Efficient Execution Plans for Vertically Partitioned XML Databases}},
  journal = {Proc. VLDB Endow.},
  year = {2010},
  doi = {10.14778/1880172.1880173},
}

Loading related content...

Figure