Scrambling Query Plans to Cope with Unexpected Delays

<p>Accessing numerous widely-distributed data sources poses significant new challenges for query optimization and execution. Congestion or failure in the network introduce highly-variable response times for wide-area data access. This paper is an initial exploration of solutions to this variability. We investigate a class of dynamic, run-time query plan modification techniques that we call <em>query plan scrambling</em>. We present an algorithm which modifies execution plans <em>on-the-fly</em> in response to unexpected delays in data access. The algorithm both <em>reschedules</em> operators and <em>introduces</em> new operators into the plan. We present simulation results that show how our technique effectively hides delays in receiving the initial requested tuples from remote data sources.</p>