I. Introduction
Query plan caching has been widely adopted by RDBMSs to eliminate the overhead of repeated optimization [1], [2]. For frequently executed queries in which query optimization consumes a significant portion of total query execution time, it is beneficial to cache and reuse the optimal query plan [1]. A query plan is a tree of relational algebra operators, each encapsulating some information about choice of algorithm and resource allocation [3]. The optimal plan is computed via cost-based evaluation of candidate plans, taking into account recent statistics on the data and the current system state. Unfortunately, optimization time can become a performance bottleneck, particularly for queries that are cheap to exe-cute [4]. Plan caching addresses this problem; that is, query optimization can be bypassed if plans of frequently executed queries are cached and reused. A high level overview of plan caching is depicted in Figure 1: part (A). A parametric plan caching workflow.