AdaptivelyProcessingRemoteData详解.pptVIP

Adaptively Processing Remote Data Zachary G. Ives University of Pennsylvania CIS 650 – Database Information Systems February 28, 2005 Administrivia Next reading assignment: Doan et al. – LSD Recall that the midterm will be due 3/16 You can go ahead and choose a topic – let me know which one Today’s Trivia Question Sources of Query Answering Cost Regular computation (this has a minimum cost) But we can get held up by: Inflexible query plans Delays – we “stall” in waiting for I/O Query scrambling Pipelined hash joins Bad query plans Bad estimation of intermediate result sizes The focus of the Kabra and DeWitt paper Insufficient source information Eddies and ADP Exploration vs. exploitation; extrapolating performance Kabra and DeWitt Recap Provides significant potential for improvement without adding much overhead Biased towards exploitation, with very limited information-gathering A great way to retrofit an existing system In SIGMOD04, IBM had a paper that did this in DB2 But not appropriate for remote data Relies on us knowing the (rough) cardinalities of the sources Query plans aren’t pipelined A Second Issue: Delays May have a very computationally inexpensive plan, but slow sources The query plan might get held up waiting for data Solution 1: query scrambling Rescheduling – while delayed, find a non-executing part of the query plan and start it Operator synthesis – when nothing can be rescheduled, might tinker with the original plan Want to do this in a cost-based way Cost-Based Query Scrambling Divide plan into runnable subtrees based on schedule; schedule those with 75% efficiency Each may be run out of order if it materializes Cost = mat. write + processing + mat. read Efficiency = (M – MR) / (P + MW): savings / cost When no more runnable subtrees, need to do something Operator synthesis: try to find a computation that will mask the delay – only how much should we do? PAIR: only do a single join over a pair of relations IN: include delay, chooses to de