Network-Aware Join Processing in Global-Scale Database Federations
| Title | Network-Aware Join Processing in Global-Scale Database Federations |
| Publication Type | Conference Papers |
| Year of Publication | 2008 |
| Authors | Wang X, Burns R, Terzis A, Deshpande A |
| Conference Name | IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008 |
| Date Published | 2008/04/07/12 |
| Publisher | IEEE |
| ISBN Number | 978-1-4244-1836-7 |
| Keywords | Astronomy, 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 |
| Abstract | 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. |
| DOI | 10.1109/ICDE.2008.4497467 |