2012 · 12 citations · 28 references
ComputingComputer ScienceAlgorithmsDatabasesOptimizationPerformance OptimizationQuery OptimizationQuery ProcessingStructured Query LanguageAdaptive OptimizationAdaptive Query OptimizationFeedback OptimizationHierarchical Data ManagementQuery Performance OptimizationRecursionRecursive Queries
Recursive queries were introduced as part of ANSI SQL 99 to support processing of hierarchical data typical of air flight schedules, bill-of-materials, data cube dimension hierarchies, and ancestor-descendant information (e.g. XML data stored in relations). Recently, recursive queries have also found extensive use in web data analysis such as social network and click stream data. Teradata implemented recursive queries in V2R6 using static plans whereby a query is executed in multiple iterations, each iteration corresponding to one level of the recursion. Such a static planning strategy may not be optimal since the demographics of intermediate results from recursive iterations often vary to a great extent. Gathering feedback at each iteration could address this problem by providing size estimates to the optimizer which, in turn, can produce an execution plan for the next iteration. However, such a full feedback scheme suffers from lack of pipelining and the inability to exploit global optimizations across the different recursion iterations. In this paper, we propose adaptive optimization techniques that avoid the issues with static as well as full feedback optimization approaches. Our approach employs a mix of multi-iteration pre-planning and dynamic feedback techniques which are generally applicable to any recursive query implementation in an RDBMS. We also validated the effectiveness of our proposed techniques by conducting experiments on a prototype implementation using a real-life social network data from the FriendFeed online blogging service.
28
Wikipedia: The Free Encyclopedia
Reference Reviews · 2002 · 2.4K citations
Timos Sellis · ACM Transactions on Database Systems · 1988 · 809 citations · Full text
An Infrastructure for Adaptive Dynamic Optimization
2003 · 445 citations
Efficient and extensible algorithms for multi query optimization
Prasan Roy, S. Seshadri, S. Sudarshan et al. · ACM SIGMOD Record · 2000 · 409 citations