A Query Beehive Algorithm for Data Warehouse Buffer Management and Query Scheduling

A Query Beehive Algorithm for Data Warehouse Buffer Management and Query Scheduling

Amira Kerkad (LIAS/ISAE-ENSMA, University of Poitiers, Poitier, France), Ladjel Bellatreche (LIAS/ISAE-ENSMA, University of Poitiers, Poitier, France), Pascal Richard (LIAS/ISAE-ENSMA, University of Poitiers, Poitier, France), Carlos Ordonez (University of Houston, Houston, TX, USA) and Dominique Geniet (LIAS/ISAE-ENSMA, University of Poitiers, Poitier, France)
Copyright: © 2014 |Pages: 25
DOI: 10.4018/ijdwm.2014070103


Analytical queries, like those used in data warehouses and OLAP, are generally interdependent. This is due to the fact that the database is usually modeled with a denormalized star schema or its variants, where most queries pass through a large central fact table. Such interaction has been largely exploited in query optimization techniques such as materialized views. Nevertheless, such approaches usually ignore buffer management and assume queries have a fixed order and are known in advance. We believe such assumptions are too strong and thus they need to be revisited and simplified. In this paper, we study the combination of two problems: buffer management and query scheduling, in both static and dynamic scenarios. We present an NP-hardness study of the joint problem, highlighting its complexity. We then introduce a new and highly efficient algorithm inspired by a beehive. We conduct an extensive experimental evaluation on a real DBMS showing the superiority of our algorithm compared to previous ones as well as its excellent scalability.
Article Preview


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:

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 15: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing