Optimization And Approximate Calculation Of Window Functions

Window functions have been a part of the SQL standard since 2003 and have been well studied during the past decade.And the window function has more and more exten-sive application prospects with the growth of the analytical applications demands.Despite its simple syntax,window functions can express many complex queries,such as ranking,moving average,cumulative sum and so on.Although almost all the current mainstream commercial database support window function,the existing implementation strategy is in-efficient,and can not meet the processing needs of large-volume data,especially in online scenarios.Recently,some optimization algorithms of window functions,based on shared com-puting,have been proposed to deal with the large and complex data analysis problems.However,the personalized optimization work for specific window functions is insuffi-cient.This paper focuses on the optimization of MIN/MAX window functions,improves the existing TW algorithm[1],and proposes a more efficient IM~2algorithm.In addition,in many current application scenarios,users do not need completely accurate analysis re-sults and pay more attention to time efficiency,and each user has different requirements for accuracy and time.The existing optimization works not only have a bottleneck in the further improvement of the optimization capability,but more importantly,they can not perform customized analysis services for the needs of different users,and the systems have poor interaction.Therefore,in order to meet the requirements of this kind of on-line analysis,this paper also proposes a window function execution framework based on sampling technology to further improve the analysis and interaction performance.Main contributions of our work can be summarized as follows:·MIN/MAX window function optimization algorithmIn this paper,an IM~2optimization algorithm based on SKYLINE tuple values?is proposed for the MIN/-MAX window function.The characteristic of the SKYLINE tuple is that it satisfies not less than(for the MAX function)or not more than(for the MIN function)any tuple behind it in the current window.The IM~2algorithm stores TOP-K SKYLINE tuples and returns the results to reduced the calculation.·Window local sampling optimization algorithmIn online computing systems,people pay more attention to the response speed of the query and can tolerate a range of result errors.Based on this purpose,this paper proposes a local sampling method that only selects a part of the tuples in each window to participate in the calculation.In order to further increase the performance of the algorithm,a more efficient incremental algorithm is proposed.·Window global sampling optimization algorithmLocal sampling completely preserves the calculation results of each window.However,the similarity of neigh-boring windows results in the redundancy of the data.When the user does not have strict requirements on the integrity of results,global sampling can be used to fur-ther reduce the computational cost.The core idea of the algorithm is to sample the original data to generate small data before computing.Then the relevant operations are performed on the small data set.The algorithm is designed based on the two different calculation modes of the window functions ROW and RANGE.·Algorithm implementation and verification This paper not only proves the ef-ficiency of the proposed algorithm from the perspective of theory analysis,but also implements the proposed algorithm in the current mainstream open-source database PostgreSQL.Compared with other commercial databases,it has a significant opti-mization effect.In addition,for the two types of sampling optimization algorithms,the derivation process for calculating the confidence interval is given.