Because of the semistructured nature of XML data, partitioning strategy for data parallelism is not an obvious process. At KDE laboratory, this issue has already been studied previously. The following thesis focuses on the metadata parallelization of XML documents in order to execute the Holistic Twig Joins algorithm in a cluster environment (shared-nothing memory). At the end, the thesis also evaluates multi-core CPU (shared memory) for parallel query processing.
Two new models are introduced: the Grid Metadata model for XML (GMX, 4th chapter in the dissertation) and the Stream-based Partitioning for XML (SPX, 5th chapter in the dissertation). GMX model is refered as static partitioning while SPX model is refered as dynamic partitioning. This categorization may lead to misunderstanding if you do not keep in mind that static and dynamic refer to the cluster environment and not the query processing execution. None of the GMX and SPX models adapt partitioning on-the-fly while executing TwigStack algorithm.
One paper is named "On-the-fly Partitioning of XML Node Streams for Parallel Holistic Twig Joins". This paper introduces the SPX model as an on-the-fly process. Again, it should not be misunderstood: partitioning and query processing are not carried out in the same time for the same query. This process is on-the-fly from cluster node point of view since a node can partition and process a new incoming query without stopping the process of the whole set of queries (as opposed to GMX).
GMX model exploits the relationships between XML documents and query patterns to perform workload-aware partitioning of XML data. SPX model explores the structural relationships of query elements and a range-containment property of XML streams to generate partitions. Those both schemes were designed specifically for parallel holistic twig joins processing, thus streams of XML nodes are partitioned instead of XML documents.
Both proposed XML data partitioning schemes do not take into account the issue of XML data updates. In case of document change, whole partitioning has to be done again.
This section presents an overview of each model. The two models are complementary.
GMX model is divided into three main stages: generation of metadata, partitioning part and distribution part.
GMX model uses document and query metadata. Document metadata are generated from XML documents while query metadata are generated from query logs (i.e., previously executed queries). Document metadata consists of streams of XML nodes and query metadata consists of statistics: query occurence, estimated root-to-leaf output size and estimated final output size. The result of the GMX model is a 2-dimensional representation of the cost relationships between XML documents and queries.
When metadata have been computed, partitioning stage performs clustering or refining of documents and queries according to the cost function and gathered metadata. The aim of making use of the cost function is to take into account the coherency between twig pattern queries and XML documents. The cost model is detailed in the thesis and will not be introduced in this document. Partitioning methods are inspired by OLAP-operations of relational data. They provide five different granularities.
The last stage is the distribution part. Partitions are allocated across the cluster nodes. Each node's workload should be balanced compared to others. The selected approach gives only sub-optimal workload balance. Actually, finding the optimal workload assignment is too costly. Heuristic functions are used to minimize workload variance. A threshold mechanism is implemented to find overloaded cluster nodes.
According to its author, the [GMX] model has feature of reducing the workload variance significantly in cluster system, duplicating XML data necessarily to avoid data dependency among cluster nodes, and exploiting inter-query parallelism and intra-query parallelism.
The thesis deals with inter- and intra- query parallelisms. In the example figure of the GMX model, we can see 4 queries on 3 documents. The 2-dimension division partitions the workload on a per XML document and a per query path basis. If the workload consists of a unique document and a unique query path, workload cannot be further partitioned through GMX model, then SPX model has to be used since this model allows better intra-query parallelism.
A workload imbalance can occur during query processing, despite GMX partitioning. SPX model has been introduced to cope with this issue. The aim here is to produce partitions each containing a subset of the query twig tree. The structure of the XML data drives the portioning process thus the method is also relevant for one XML document and one query only. Unlike GMX model, this model have no granularity limit. Like GMX model, this model produces partitions having no dependency among each other thereby duplicating some document metadata. Although the lack of granularity limit, there is still a trade-off to find because higher parallelism also creates bigger amount of redundant data which decreases the efficiency of each parallel process.
The SPX model is divided into two main stages: partitions generation and allocation of those partitions. Like for GMX model, the thesis provides an allocation plan based on a cost model. This part is not further detailed since it is dedicated to cluster environment that is outside the scope of this document.
The containment properties defined in the work of Zhang et al. is extended with the notion of left and right containment. If D is a descendant of A, D is left contained in A is equal to this condition: (doc_noA = doc_noD AND left_posA < left_posD) OR doc_noA < doc_noD. A similar definition applies to right containment: (doc_noA = doc_noD AND right_posA < right_posD) OR doc_noA < doc_noD. Using those two properties, most left and most right containment can easily be defined. This is a key feature of the SPX partitioning model since it is used to respect range containment property among streams in the resulting partitions.
All the following figures are based on the same example. They show SPX partitioning using different representations.
<?xml version="1.0" encoding="UTF-8" ?>
<!-- partition 1 -->
<library>
<category name="France">
<book>
<title language="English">The Little Prince</title>
<title language="日本語">星の王子さま</title>
<author>Antoine de Saint-Exupéry</author>
</book>
</category>
<category name="England">
<book>
<title language="日本語">ふしぎの国のアリス</title>
<!-- partition 2 -->
<title language="English">Alice in wonderland</title>
<title language="Français">Alice au pays des merveilles</title>
<author>Lewis Carroll</author>
</book>
</category>
</library>
To start the partitioning, SPX model suggests beginning with the biggest stream. In the example, the two biggest streams are those bound to title and @language query nodes (they contain 5 elements). title's stream was randomly chosen to undertake the initial split. Since we targeted two partitions, one contains three elements while the other contains two elements.
The resulting partitions are then propagated to all other streams of the query tree using the range containment property.
For example, if the root node of the XML document is involved into the query, this node would be duplicated in all partitions (since there is always only one root element in an XML document, this is a restriction of the standard).
1 function upward(basePartition, stream)
2 for streamPart in basePartition
3 # look for the biggest range containment
4 searchLeftContainment(first(streamPart), stream)
5 mostLeft = nextMostL(stream)
6 searchRightContainment(last(streamPart), stream)
7 mostRight = nextMostR(stream)
8 ancStreamPart = copyStream(stream, mostLeft, mostRight)
9 ancStreamPartitions = ancStreamPartitions + ancStreamPart
10 return ancStreamPartitions
11 end
1 function downward(basePartition, stream)
2 if isDuplicate(basePartition)
3 descStreamPartitions = equalPartitioning(stream, windowSize)
4 return descStreamPartitions
5 end if
6 foreach streamPart in basePartition
7 # look for the biggest range containment
8 searchLeftContainment(first(streamPart), stream)
9 mostLeft = nextMostL(stream)
10 searchRightContainment(last(streamPart), stream)
11 mostRight = nextMostR(stream)
12 ancStreamPart = copyStream(stream, mostLeft, mostRight)
13 ancStreamPartitions = ancStreamPartitions + ancStreamPart
14 end foreach
15 return ancStreamPartitions
16 end