DocumentCode :
3322569
Title :
Network-Aware Join Processing in Global-Scale Database Federations
Author :
Wang, Xiaodan ; Burns, Randal ; Terzis, Andreas ; Deshpande, Amol
Author_Institution :
Johns Hopkins Univ., Baltimore, MD
fYear :
2008
fDate :
7-12 April 2008
Firstpage :
586
Lastpage :
595
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.
Keywords :
query processing; global-scale database federations; join scheduling algorithms; network utilization; network-aware join processing; parallel schedules; polynomial-time algorithm; reduce resource usage; spatial-join queries; Astronomy; Computer networks; Concurrent computing; Polynomials; Processor scheduling; Query processing; Scheduling algorithm; Spatial databases; Telecommunication traffic; Throughput;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on
Conference_Location :
Cancun
Print_ISBN :
978-1-4244-1836-7
Electronic_ISBN :
978-1-4244-1837-4
Type :
conf
DOI :
10.1109/ICDE.2008.4497467
Filename :
4497467
Link To Document :
بازگشت