A Window Join Optimization Algorithm Based on Minimum Spanning Tree

Different from traditional database systems, a data stream management system (DSMS) mainly processes concurrently continuous queries. Because queries would be added or deleted at any moment, the focus of query optimization for a DSMS is to find an algorithm that adapts to add and delete queries frequently. Furthermore, as window join is one of the highest cost operations of continuous queries, window join optimization will notably improve a DSMS performance. Therefore, a window join optimization algorithm is proposed. For each new query, all the probing sequences of each data stream are built like minimum spanning tree algorithm. To complete concurrent window joins, the probing sequences which start from a same stream should be built into one tree whose root node is the stream. If prefixes of probing sequences are the same, they can be grouped into one branch of the tree to reduce the duplicate calculation. Because the algorithm does not execute cost comparison of grouping common join predicate, adding or deleting a query does not influence other query plans, and complicated dynamic plan migration is not needed. Theoretics and experimental results show that the algorithm is simple and optimization performance is acceptable.