A Data Placement Strategy for Parallel XML Databases

Guoren WangJournal of Software 2006 · DOI

TL;DR

This paper introduces WIN, a novel data placement strategy for parallel XML databases that partitions XML documents based on "intermediary nodes" and query workload. WIN aims to improve query processing speed and scalability by intelligently replicating root data and distributing sub-trees across nodes, outperforming existing methods in experimental evaluations.

What Problem Does This Paper Address?

As XML data grows in volume and complexity, processing queries efficiently on single machines becomes a bottleneck due to I/O and memory limitations. Parallel database systems offer a solution, but their performance heavily relies on effective data partitioning. Traditional partitioning strategies from relational or object-oriented databases don't directly translate to XML's semi-structured, tree-like nature, which can lead to data redundancy or skewed workloads. This paper addresses the challenge of optimally partitioning XML documents across multiple nodes in a parallel database system to maximize query processing efficiency and scalability.

Methods

The core of the WIN strategy lies in the concept of intermediary nodes. An XML document, represented as a tree, is partitioned into a replicated "root-tree" and a set of "sub-trees." The root-tree, containing frequently accessed data, is duplicated on all nodes. The sub-trees, on the other hand, are distributed across nodes.

The key innovation is how these sub-trees are determined and distributed:

  • Intermediary Nodes (INs): A set of intermediary nodes is chosen within the XML tree. These nodes act as roots for the sub-trees that will be partitioned. The nodes above the INs (up to the root) form the replicated root-tree.
  • Workload-Aware Partitioning: The distribution of sub-trees is based on estimated user query workloads. The goal is to balance the workload across all nodes.
  • Heuristic Rules: Identifying the optimal set of intermediary nodes is an NP-hard problem. WIN employs heuristic rules to guide the search for a good partitioning, balancing query workload distribution and minimizing replication costs. These rules prioritize partitions that lead to more balanced workloads and avoid excessive replication.
  • WIN Algorithm: The WIN algorithm iteratively explores potential intermediary node sets, expanding them and evaluating their "benefit" (improvement in workload balance and reduced replication cost) using a defined metric. It selects the set that offers the best trade-off.
  • Partitioning Algorithm: Once the optimal intermediary nodes are identified, the Partition() algorithm groups sub-trees by parent nodes, aiming for similar structures within groups. These groups are then distributed to nodes to balance workloads, ensuring local data completeness and reducing communication overhead.

Datasets

The paper uses the XML Benchmark Project (XMark) dataset as a basis. They generated XML documents of varying sizes (20MB to 100MB) based on a fixed DTD. A complex query set of 20 standard XQuery queries was used for performance testing.

Key Insights and Ideas

  • The "Intermediary Node" Concept: This is the central novel idea, providing a flexible way to decompose XML trees for parallel processing. It bridges the gap between full replication and complete partitioning.
  • Workload-Awareness is Crucial: Simply partitioning based on structure (like PSPIB) isn't enough. Considering the actual query patterns and their estimated workload is vital for achieving true load balancing.
  • Heuristics for NP-Hard Problems: The paper demonstrates a practical approach to tackling an NP-hard optimization problem by using intelligent heuristic rules to prune the search space and find good-enough solutions efficiently.
  • Balancing Replication and Partitioning: The WIN algorithm explicitly considers the trade-off between replicating data for faster access and partitioning it to distribute load, aiming for an optimal balance.

Key Results

Experimental results show that the WIN algorithm significantly outperforms existing strategies, particularly the PSPIB (Path Instance) algorithm, in terms of both speedup and scaleup.

  • Speedup: For various queries (Q5, Q6, Q20), WIN consistently achieved better speedup values across different document sizes and numbers of sites. For instance, in Figure 5 (Q5 speedup on 20M document), WIN shows a higher speedup than PSPIB.
  • Scaleup: WIN demonstrated superior scaleup performance, meaning its efficiency degrades less as the number of processing nodes increases. Figure 10 (Q5 scaleup) shows WIN's scaleup performance is close to linear, while PSPIB's is irregular and wavy. This indicates WIN scales better to larger parallel systems.
  • Query Types: WIN showed strong performance across different query types, including string manipulation (Q5), regular path expressions (Q6), and complex aggregation queries (Q20), suggesting its general applicability.

Limitations and Future Work

  • Static Partitioning: The paper focuses on static partitioning of XML documents. The authors acknowledge that dynamic partitioning strategies for XML documents are a key area for future research.
  • Query Workload Estimation: While WIN uses workload estimation, the accuracy of these estimations directly impacts performance. Further research into more precise workload prediction models could enhance WIN.
  • Experimental Setup: The experiments were conducted on a homogeneous, shared-nothing parallel system. Performance might vary on heterogeneous or shared-disk architectures.

The authors suggest that future work should focus on dynamic partitioning strategies to adapt to changing query patterns and data updates.

Summary updated

Abstract

This paper targets on parallel XML document partitioning strategies to process XML queries in parallel. To describe the problem of XML data partitioning, a concept, intermediary node, is presented in this paper. By a set of intermediary nodes, an XML data tree can be partitioned into a root-tree and a set of sub-trees. While the root-tree is duplicated over all the nodes, the set of the sub-trees can be evenly partitioned over all the nodes based on the workload of user queries. For the same XML data tree, there are a number of intermediary nodes sets, and different intermediary nodes sets will generate different partitions. It can be evaluated if a partitioning is good based on the workload of user queries. It is obviously an NP hard problem to choose an optimal partitioning. To solve this problem, this paper proposes a set of heuristic rules. Based on the idea described above, this paper designs and implements an XML data partitioning algorithm, WIN, and the extensive experimental results show that its speedup and scaleup performances outperform the existing strategies.
BibTeX
@article{wang2006data,
  author = {Guoren Wang},
  title = {{A Data Placement Strategy for Parallel XML Databases}},
  journal = {Journal of Software},
  year = {2006},
  doi = {10.1360/jos170770},
}
Figure