Article Preview
TopIntroduction
Database systems are facing an important growth of data that brings the need of high performance to a center stage. This growth is associated to an increasing number of complex analytical queries. Queries in such workloads may have common sub-expressions that are shared across multiple queries, which may have a significant impact on performance when they are reused. Data warehouses are a typical environment for large scale data and query interaction. This is generally due to the nature of their schema, usually a star, where no direct link exists between dimension tables. This feature makes all joins be based on the fact table, increasing the probability of finding common sub-expressions among different query plans. Query optimizers generally consider queries in an isolated way (one at a time) during the optimization process, which misses identifying common operations, resulting in redundant computations (Thomas, Diwan & Sudarshan, 2006). Multiple Query Optimization (MQO) tackled in (Sellis, 1988) brings a new dimension for database optimization by highlighting the interaction between queries. MQO has been exploited in several well-known problems such as:
- •
Materialized Views Selection Problem (MVSP) (Yang, Karlapalem & Li, 1997), that aims at identifying common sub-expressions to be materialized on disk so that they are not computed repeatedly.
- •
Buffer Management Problem (BMP) (Cornell & Yu, 1989), that defines the allocation and the replacement policy to manage retrieved data in a limited buffer space so that it can be reused as much as possible by other queries before it is evicted from the buffer pool.
- •
Query Scheduling Problem (QSP) (Gupta, Sudarshan & Viswanathan, 2001), that defines an order to evaluate a set of queries to take benefit from current content of a storage device before relevant data is evicted. The device may be a main memory buffer, or a secondary memory device such as hard disk, cloud, flash etc. For instance, when the storage device is a buffer, the QSP interacts with the BMP. In contrast, when the device is a disk, the QSP interacts with the MVSP (see Figure 1).
Figure 1. Interaction between physical design problems
In Scheuermann, Shim and Vingralek (1996), the authors argue that in a data warehouse, caching entire sets of retrieved queries is more efficient than individual pages. One of the requirements to exploit query interaction is to identify overlapping parts between query plans. Once commonalities are identified, new challenges are faced to manage them using either one (isolated selection) or many (multiple selection) optimization techniques. In the former, we can find MVSP (Yang, Karlapalem & Li, 1997), BMP (Cornell & Yu, 1989), and QSP (Gupta, Sudarshan & Viswanathan, 2001). The latter combines several techniques such as MVSP with QSP (Phan. & Li, 2008). and BMP with QSP (namely BMSQP) (Thomas, Diwan, & Sudarshan, 2006). The large search space makes each problem hard to solve either in an isolated way or combined with another. But on the other hand, the interdependency between some techniques allows to bring performance beyond. For instance, the BMP is identified as highly interdependent with the QSP. Indeed, the buffer content determines the next query to run, and the schedule determines the buffer content. BMP and QSP have been studied in several contexts of databases: traditional (Effelsberg & Härder, 1984), data warehouses (Scheuermann, Shim & Vingralek, 1996), semantic databases (Yang & Wu, 2011), and flash databases (Ou, Härder & Jin, 2010) etc. Recently, the two problems have been combined (Thomas, Diwan, & Sudarshan, 2006). These techniques have been considered at three levels: