Towards Cost-based Optimizations of Twig Content-based Queries.
Michal Krátký, Radim Bača · DATESO · 2008
In recent years, many approaches to indexing XML data have appeared. These approaches attempt to process XML queries efficiently and sufficient query plans are built for this purpose. Some effort has been expended in the optimization of XML query processing [20]. There are not many works that take cost-based query optimizations into account. In work [20], we find some cost-based considerations, however, they work only with one type of structural join and one type of underlying index. There are works depicted two types of query processing as well [10, 17]. The first type applies an element-based index, the second type applies a navigation in a persistent DOM-like structure. In our work, we propose usage of two path-based indices that provide significant potential for a query optimization based on a cost-based join selection. We can identify some classes of approaches for efficient processing of XML queries. The first class includes approaches based on shredding [18] (storing an XML document in many relations, where each element name has its own relation). These approaches work well only on specific documents with a defined XML schema. The second class of approaches [15, 21, 1] provides an elementbased decomposition of an XML document. These methods usually work with a labeling scheme and they differ mainly in various join algorithms. We identify two main types of join algorithms. The first join type works with sorted node sets merged by a type of holistic join [3, 4]. This kind of structural join is optimal when a small number of nodes is rejected during the structural join. In this case, nodes are retrieved in a very efficient way with a small number of I/O. In our article, this kind of join operation is called a merge join. Another type of join algorithm is based on context nodes [9], where each location step is processed using context nodes from the previous step. We say that this approach utilizes a previously processed location step and uses the nodes for an efficient search of nodes in the next step. If there is a large number of rejected nodes in the join operation, this kind of join is efficient. In our article, this kind of join operation is called a progressive join. There are approaches that decompose XML documents according to the node path, as opposed to the node name. Handling the paths during a query processing