Optimization Online


Query Batching Optimization in Database Systems

Mehrad Eslami (mehrad***at***mail.usf.edu)
Vahid Mahmoodian (mahmoodian***at***mail.usf.edu)
Iman Dayarian (idayarian***at***cba.ua.edu)
Hadi Charkhgard (hcharkhgard***at***usf.edu)
Yicheng Tu (tuy***at***mail.usf.edu)

Abstract: Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of rigorous modeling and theoretical study for query processing and optimization. Query batching in database systems has strong resemblance to order batching in the warehousing context. While the latter is a well-studied problem, the literature on optimization techniques for query batching problem is quite scarce/nonexistent. In this study, we develop a Mixed Binary Quadratic Program (MBQP) to optimize query-batching in a database system. This model uses the coeffcients of a linear regression on the query retrieval time, trained by a large set of randomly generated query sets. We also propose two heuristics, the so-called restricted-cardinality search methods I and II, for solving the proposed MBQP. To demonstrate the effectiveness of our proposed techniques, we conduct a comprehensive computational study over randomly generated instances of three well-known database benchmarks. The computational results show that when the proposed MBQP is solved using the designed heuristics, an improvement of up to 61.8% in retrieving time is achieved.

Keywords: batching problem; database systems; mixed binary quadratic programming; linear regression; restricted-cardinality search method

Category 1: Applications -- Science and Engineering (Multidisciplinary Design Optimization )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 10/24/2019
Entry Accepted: 10/24/2019
Entry Last Modified: 04/01/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society