Optimization Method Of Twig Query Based On Partial Evaluation And Hot-trace Compilation

With Internet technology's rapid development, much information publication and access have been implemented by the Internet. Therefore, in order to fully and effectively express the rich data in the Internet, W3 C proposed XML as the format of information sharing. XML with its characteristics of cross-platform, semi-structured, and easy expansibility, has been widely used in description and exchange of all kinds of data on the Internet, and gradually becomes the de facto standard. To this end, efficient query processing becomes an inevitable requirement using XML data.In order to standardize the XML data query and processing operations, W3 C proposed XQuery as a standard language of XML data query. And its core operation is Twig query, also known as tree pattern query. Therefore, designing an efficient algorithm of Twig query has become a hot research topic. There have been some of the more common twig query algorithm, such as, MPMGJN based on structural join algorithm, TwigStack based on holistic join algorithm, Twig2 Stack developed by the TwigStack algorithm, TwigList avoiding complex structure like hierarchical stack in Twig2 Stack, TreeMatch further reducing the intermediate results, etc. Among them, TreeMatch algorithm is considered to be one of the best Twig query algorithm, since it reduce intermediate results to a great extent. However, in the core operation getNext of TreeMatch algorithm, there are much calculation relying on the Twig query pattern. When the number of getNext calls is a lot, the redundant calculation will affect the performance.To further improve TreeMatch algorithm, this paper proposes a novel optimization method based on partial evaluation and hot-trace compilation. Firstly, the method takes Twig pattern as the invariant to do partial evaluation, and translates the query into a sequence of Twig Query Machine instructions, which avoids some redundant computation in Twig pattern query process. Secondly, the method does hot-trace compilation optimization for the instruction sequence to achieve more efficiency in interpretive execution. Experimental results show that the efficiency of Twig query will increase by 20% to 60% using the optimization method.