A Genetic Algorithm for Selecting Horizontal Fragments

Introduction

Decision support applications require complex queries, e.g., multi way joins defining on huge warehouses usually modelled using star schemas, i.e., a fact table and a set of data dimensions (Papadomanolakis & Ailamaki, 2004). Star schemas have an important property in terms of join operations between dimensions tables and the fact table (i.e., the fact table contains foreign keys for each dimension). None join operations between dimension tables. Joins in data warehouses (called star join queries) are particularly expensive because the fact table (the largest table in the warehouse by far) participates in every join and multiple dimensions are likely to participate in each join.

To speed up star join queries, many optimization structures were proposed: redundant structures (materialized views and advanced index schemes) and non redundant structures (data partitioning and parallel processing). Recently, data partitioning is known as an important aspect of physical database design (Sanjay, Narasayya & Yang, 2004; Papadomanolakis & Ailamaki, 2004). Two types of data partitioning are available (Özsu & Valduriez, 1999): vertical and horizontal partitioning. Vertical partitioning allows tables to be decomposed into disjoint sets of columns. Horizontal partitioning allows tables, materialized views and indexes to be partitioned into disjoint sets of rows that are physically stored and usually accessed separately. Contrary to redundant structures, data partitioning does not replicate data, thereby reducing storage requirement and minimizing maintenance overhead. In this paper, we concentrate only on horizontal data partitioning (HP).

HP may affect positively (1) query performance, by performing partition elimination: if a query includes a partition key as a predicate in the WHERE clause, the query optimizer will automatically route the query to only relevant partitions and (2) database manageability: for instance, by allocating partitions in different machines or by splitting any access paths: tables, materialized views, indexes, etc. Most of database systems allow three methods to perform the HP using PARTITION statement: RANGE, HASH and LIST (Sanjay, Narasayya & Yang, 2004). In the range partitioning, an access path (table, view, and index) is split according to a range of values of a given set of columns. The hash mode decomposes the data according to a hash function (provided by the system) applied to the values of the partitioning columns. The list partitioning splits a table according to the listed values of a column. These methods can be combined to generate composite partitioning. Oracle currently supports range-hash and range-list composite partitioning using PARTITION - SUBPARTITION statement. The following SQL statement shows an example of fragmenting a table Student using range partitioning.

CREATE TABLE student (Student_ID Number(6), Student_FName VARCHAR(25), Student-LName VARCHAR(25), PRIMARY KEY (Student_ID) PARTITION BY RANGE (student_LN) (PARTITION student_ae VALUES LESS THAN (‘F%’) TABLESPACE part1, PARTITION student_fl VALUES LESS THAN (‘M%’) TABLESPACE part2, PARTITION student_mr VALUES LESS THAN (‘S%’)  TABLESPACE part3, PARTITION student_sz VALUES LESS THAN (MAXVALUE) TABLESPACE part4);

HP can also be combined with others optimization structures like indexes, materialized views, and parallel processing. Several work and commercial systems show its utility and impact in optimizing OLAP queries (Noaman & Barker, 1999, Sanjay, Narasayya & Yang, 2004; Stöhr, Märtens & Rahm, 2000). But none of these studies has formalized the problem of selecting a horizontal partitioning schema to speed up a set of queries as optimization problem with constraint and proposed selection algorithms.