Network-Aware Join Processing in Global-Scale Database Federations

TitleNetwork-Aware Join Processing in Global-Scale Database Federations
Publication TypeConference Papers
Year of Publication2008
AuthorsWang X, Burns R, Terzis A, Deshpande A
Conference NameIEEE 24th International Conference on Data Engineering, 2008. ICDE 2008
Date Published2008/04/07/12
ISBN Number978-1-4244-1836-7
KeywordsAstronomy, Computer networks, Concurrent computing, global-scale database federations, join scheduling algorithms, network utilization, network-aware join processing, parallel schedules, polynomial-time algorithm, Polynomials, Processor scheduling, Query processing, reduce resource usage, Scheduling algorithm, Spatial databases, spatial-join queries, Telecommunication traffic, Throughput

We introduce join scheduling algorithms that employ a balanced network utilization metric to optimize the use of all network paths in a global-scale database federation. This metric allows algorithms to exploit excess capacity in the network, while avoiding narrow, long-haul paths. We give a two- approximate, polynomial-time algorithm for serial (left-deep) join schedules. We also present extensions to this algorithm that explore parallel schedules, reduce resource usage, and define tradeoffs between computation and network utilization. We evaluate these techniques within the SkyQuery federation of Astronomy databases using spatial-join queries submitted by SkyQuery's users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead.