Simultaneous Resolution of Buffer Allocation and Query Scheduling Problems
Authors:
- 1 July 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 122-129
Abstract
Database management systems (DBMS) use external magnetic devices (disks) for the storage of mass data. In the context of very large databases, the query response time may be strongly influenced by two main factors: (i) the amount data needed to be accessed from the disk to the main memory cache and (ii) the order of queries, especially if queries share some common intermediate results. These two factors are related to two well known problems in databases: Buffer Management Problem (BMP) and Query Scheduling Problem (QSP). Usually, BMP and QSP are treated in the isolated way and their strong interaction is ignored by the existing solutions. This situation motivates us to consider the integrated problem including BMP and QSP. In this paper, we first propose a formalization of the integrated problem and show complexity. Secondly, three heuristics are proposed: naive, hill climbing and genetic algorithms dealing with our integrated problem. Finally, two intensive experiments are conducted: (1) theoretically using a cost model and (2) a real validation on Oracle11G.Keywords
This publication has 14 references indexed in Scilit:
- Caching intermediate result of SPARQL queries2011
- CFDC: A Flash-Aware Buffer Management Algorithm for Database Systems2010
- QoS-Oriented Multi-query Scheduling over Data Streams2009
- Dynamic Materialization of Query Views for Data Warehouse Workloads2008
- Real-Time Query Scheduling for Wireless Sensor Networks2007
- Index selection for databases: a hardness study and a principled heuristic solutionIEEE Transactions on Knowledge and Data Engineering, 2004
- Minimal schedulability interval for real-time systems of periodic tasks with offsetsTheoretical Computer Science, 2004
- Off-line scheduling of a real-time system1998
- Multiple-query optimizationACM Transactions on Database Systems, 1988
- An evaluation of buffer management strategies for relational database systemsAlgorithmica, 1986