Vertical partitioning of relational OLTP databases using integer programming

Rasmus Resen Amossen

    Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

    Abstract

    A way to optimize performance of relational row store databases is to reduce the row widths by vertically partition- ing tables into table fractions in order to minimize the number of irrelevant columns/attributes read by each transaction. This pa- per considers vertical partitioning algorithms for relational row- store OLTP databases with an H-store-like architecture, meaning that we would like to maximize the number of single-sited transactions. We present a model for the vertical partitioning problem that, given a schema together with a vertical partitioning and a workload, estimates the costs (bytes read/written by storage layer access methods and bytes transferred between sites) of evaluating the workload on the given partitioning. The cost model allows for arbitrarily prioritizing load balancing of sites vs. total cost minimization. We show that finding a minimum-cost vertical partitioning in this model is NP-hard and therefore the problem should obviously not be solved manually by a human DBA. We present two algorithms returning solutions in which single- sitedness of read queries is preserved while allowing column replication (which may allow a drastically reduced cost compared to disjoint partitioning). The first algorithm is a quadratic integer program that finds optimal minimum-cost solutions with respect to the model, and the second algorithm is a more scalable heuristic based on simulated annealing. Experiments show that the algorithms can reduce the cost of the model objective by 37% when applied to the TPC-C benchmark and the heuristic is shown to obtain solutions with costs close to the ones found using the quadratic program.
    Original languageEnglish
    Title of host publicationIEEE 26th International Conference on Data Engineering Workshops (ICDEW), 2010
    Number of pages6
    PublisherIEEE Press
    Publication date1 Mar 2010
    ISBN (Electronic)978-1-4244-6521-7
    Publication statusPublished - 1 Mar 2010
    Event5th International Workshop on Self Managing Database Systems (SMDB2010) - Long Beach, California, United States
    Duration: 1 Mar 20101 Mar 2010
    Conference number: 5th
    http://www.cs.duke.edu/smdb10/

    Workshop

    Workshop5th International Workshop on Self Managing Database Systems (SMDB2010)
    Number5th
    Country/TerritoryUnited States
    CityLong Beach, California
    Period01/03/201001/03/2010
    Internet address

    Keywords

    • vertical partitioning
    • relational row-store databases
    • OLTP
    • H-store architecture
    • simulated annealing heuristic

    Fingerprint

    Dive into the research topics of 'Vertical partitioning of relational OLTP databases using integer programming'. Together they form a unique fingerprint.

    Cite this