25

–––––––––––––––––––––––

Data Partitioning for Designing and Simulating Efficient Huge Databases

Ladjel Bellatreche, Kamel Boukhalfa, Pascal Richard, and Soumia Benkrid

25.1   INTRODUCTION

Data warehousing is becoming more complex in terms of applications, data size, and queries, including joins and aggregations. Data warehouse projects always stress performance and scalability because of the data volumes and the query complexity. For instance, eBay's data warehouse includes 2 petabytes of user data and millions of queries per day.¹ Data distribution for ensuring high parallelism becomes a crucial issue for the research community.

Most of the major commercial database systems support data distribution and parallelism (Teradata, Oracle, IBM, Microsoft SQL Server 2008 R2 Parallel Data Warehouse, Sybase, etc.). Data warehouses store large volumes of data mainly in relational models such as star or snowflake schemas. A star schema contains a large fact table and various dimension tables. A star schema is usually queried in various combinations involving many tables. The most used operations are joins, aggregations, and selections [1]. Joins are well known to be expensive operations, especially when the involved relations are substantially larger than the size of the main memory [2], which is usually the case in business intelligence applications. The typical queries defined on the star schema are commonly referred to as star join queries and exhibit the following two characteristics: (1) There is a multitable join among the large fact table and multiple smaller dimension tables, and (2) each of the dimension tables involved in the join operation has multiple selection predicates on its descriptive attributes. To speed up star join queries, many optimization techniques were proposed. In Reference 3, we classified them into two main categories: redundant techniques such as materialized views, advanced index schemes, vertical partitioning, and parallel processing with replication, and nonredundant techniques like ad hoc joins, where joins are performed without additional data structures like indexes (hash join, nested loop, sort merge, etc.), horizontal partitioning (HP), and parallel processing without replication. In this chapter, we concentrate only on horizontal partitioning since it is more adapted to reduce the cost of star join queries.

HP has been mainly used in logical distributed and parallel database design in the last decades [4, 5]. Recently, has become a crucial part of physical database design [1, 6‒9], where most of today's commercial DBMS offer native data definition language (DDL) support for defining horizontal partitions (fragments) of a table [8]. In the context of relational warehouses, HP allows tables, indexes, and materialized views to be partitioned into disjoint sets of rows that are physically stored and accessed separately. Contrary to materialized views and indexes, horizontal data partitioning does not replicate data, thereby reducing space requirements and minimizing the update overhead. The main characteristic of data partitioning is its ability to be combined with some redundant optimization techniques such as indexes and materialized views [10]. It also affects positively query performance, database manageability, and availability. Query performance is guaranteed 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. Partitioning can also improve the performance of multitable joins by using a technique known as partition-wise joins. It can be applied when two tables are being joined together, and at least one of these tables is partitioned on the join key. Partition-wise joins break a large join into smaller joins. With partitioning, maintenance operations can be focused on particular portions of tables. For maintenance operations across an entire database object, it is possible to perform these operations on a per-partition basis, thus dividing the maintenance process into more manageable chunks. The administrator can also allocate partitions in different machines [6, 11]. Another advantage of using partitioning is that when it is time to remove data, an entire partition can be dropped, which is very efficient and fast, compared to deleting each row individually. Partitioned database objects provide partition independence. This characteristic of partition independence can be an important part of a high-availability strategy. For example, if one partition of a partitioned table is unavailable, all of the other partitions of the table remain online and available. The application can continue to execute queries and transactions against this partitioned table, and these database operations will run successfully if they do not need to access the unavailable partition.

Two versions of HP exist [12, 13]: primary and derived (known as referential partitioning in Oracle 11g [7]). Primary HP of a table is performed using attributes defined on that table. Derived HP, on the other hand, is the fragmentation of a table using attributes defined on another table. In other words, the derived HP of a table is based on the fragmentation schema of another table (the fragmentation schema is the result of the partitioning process of a given table). The derived partitioning of a table R according to a fragmentation schema of S is feasible if and only if there is a join link between R and S (R contains a foreigner key of S). It has been used to optimize data transfer when executing queries in the distributed database environment.

In traditional databases (relational and object oriented), tables/classes are horizontally partitioned in isolation. Consequently, the problem of selecting horizontal fragments of a given table T of a database may be formulated as follows:

Given a representative workload W defined on the table T, find a partitioning schema FS of T, such that the overall query processing cost (∑_Q∈Wf_Q × Cost(Q, FS), where f_Q represents the access frequency of the query Q) is minimized. According to this formalization, the database administrator (DBA) does not have any control on the generated fragments of table T. Since each table is fragmented in an isolated way, it is difficult to measure the impact of generated fragments on the rest of the tables of database schema.

In relational data warehouses, HP is more challenging compared to that in traditional databases. This challenge is due to the different choices to partition a star schema:

1. Partition only the dimension tables using simple predicates defined on these tables (a simple predicate p is defined by p: A_i θ Value, where A_i is an attribute of a dimension table, θ ∈ { = , <, >, ≤, ≥}, and Value ∈ Dom(A_i)). This scenario is not suitable for online analytical processing (OLAP) queries because the size of the dimension tables is generally smaller than the size of the fact table, and any star query accesses the fact table. Therefore, any HP that does not take into account the fact table is discarded.
2. Partition only the fact table using simple predicates defined on this table if they exist, since it is very large. Usually, restriction (selection) predicates are defined on dimension tables and not on fact tables. The raw data of the fact table usually never contain descriptive (textual) attributes because the fact relation is designed to perform arithmetic operations such as summarization, aggregation, and average on such data. Recall that star join queries access dimension tables first and, after that, the fact tables. This choice is also discarded.
3. Partition some/all dimension tables using their predicates, and then partition the fact table based on the fragmentation schemas of dimension tables using referential partitioning mode. This approach is more adapted to partition relational data warehouses since it takes into consideration the star join query requirements and the relationship between the fact table and dimension tables. In our study, we adopt this scenario. To illustrate it, we consider the following example.

■ EXAMPLE 25.1

Let us consider a star schema with three dimension tables (Customer, Time, and Product) and one fact table, Sales. Suppose that the dimension table Customer is partitioned into two fragments, CustFemale and CustMale, using the Gender attribute, and table Time into two fragments, TimeHalf₁ and TimeHalf₂, using the Month attribute, as follows:

• CustFemale = σ_{(Gender = “F”)}(Customer)
• CustMale = σ_{(Gender = “M”)}(Customer)
• TimeHalf₁ = σ_{(Month ≤6)}(Time)
• TimeHalf₂ = σ_{(Month >6)}(Time)

Following the third scenario, the fact table Sales is then fragmented based on the partitioning schema of Customer and Time into four fragments Sales₁, Sales₂, Sales₃, and Sales₄ such as

• Sales₁ = Sales ⋉ CustFemale ⋉ TimeHalf₁
• Sales₂ = Sales ⋉ CustFemale ⋉ TimeHalf₂
• Sales₃ = Sales ⋉ CustMale ⋉ TimeHalf₁
• Sales₄ = Sales ⋉ CustMale ⋉ TimeHalf₂.

The initial star schema (Sales, Customer, Product, Time) may be represented as thejuxtaposition of four substar schemas S₁, S₂, S₃, and S₄ such as S₁: (Sales₁, CustFemale, TimeHalf₁, Product) (sales activities for only female customers during the first half); S₂: (Sales₂, CustFemale, TimeHalf₂, Product) (sales activities for only female customers during the second half); S₃: (Sales₃, CustMale, TimeHalf₁, Product) (sales activities for only male customers during the first half); and S₄: (Sales₄, CustMale, TimeHalf₂, Product) (sales activities for only male customers during the second half).

The generated number of fragments (N) of the fact table is given by where m_i and g represent the number of fragments of the dimension table D_i and the number of dimension tables participating in the fragmentation process, respectively. This number may be very large. For example, suppose we have the Customer table partitioned into 50 fragments using the State attribute (case of 50 states in the United States), Time into 36 fragments using the Month attribute (if the sale analysis is done based on the last 3 years), and Product into 80 fragments using the Package_type attribute. Therefore, the fact table is decomposed into 144,000 fragments (50 × 36 × 80) using the referential partitioning mode. Consequently, instead of managing one star schema, the DBA will manage 144,000 substar schemas. It will be very hard for her or him to maintain all these substar schemas [14]. To avoid the explosion of the number of fact table fragments, we formalize the problem of selecting a HP schema as an optimization problem:

Given a representative workload W defined on a relational data warehouse schema with n dimension tables {D₁,…, D_n} and one fact table F and a constraint (called maintenance bound B) representing the number of fact fragments, identify dimension tables that could be used for derived partitioning of the fact table F, such that (∑_Q∈Wf_Q × Cost(Q, FS)) is minimized and maintenance constraint is satisfied (N ≤ B). The number B may be given by the DBA.

We present in this chapter a comprehensive study of the HP problem including primary and referential modes based on six aspects: (1) proposition of a methodology for HP in relational data warehouses guided by the total number of fragments, (2) study of complexity of referential data HP problem, (3) proposition of two selection algorithms ensuring simultaneously primary and referential partitioning, (4) proposition of combined selection approach of HP and bitmap join indexes (BJI), (5) experimental study to show the benefit and limitations of HP, and (6) proposition of simulator tool assisting data warehouse administrators (DWAs) to perform the physical design (partitioning and/or indexing).

The rest of the chapter is organized as follows: Section 25.2 presents the state of the art and related work. Section 25.3 is devoted to the presentation of our HP approach. In Section 25.4, we study the complexity of the HP selection problem and we show its hardness. Section 25.5 presents two selection algorithms, simulated annealing and hill climbing, to select near-optimal fragmentation schemes. Section 25.6 presents our combined selection approach of HP and BJI. In Section 25.7, we present the experiments that we conducted using the most popular benchmark APB1. Section 25.8 describes in detail our simulator tool, baptized SimulPh.D, to assist the administrator during his or her tasks. Section 25.9 concludes the chapter by summarizing the main results and discussing future works.

25.2   BACKGROUND AND RELATED WORK

HP has been largely studied in the literature, where several algorithms were proposed that we propose to classify into two main categories: unconstrained approaches and threshold-based approaches (Fig. 25.1). Early work on horizontal fragmentation can be found in the first category. They select a partitioning schema for a database without worrying about the number of generated fragments. We have shown that this number may be very important, which greatly complicates their manageability. We can find two classes in this category of approaches: minterm generation-based approaches and affinity-based approaches.

The minterm generation-based [4] approach starts with a table T and a set of predicates p₁,…, p_n of the most frequently asked queries defined on relation T and outputs a set of horizontal fragments of the table T. The main steps of the minterm generation-based approach are (1) generation of minterm predicates M = {m∣m = ⋀(1 ≤ k ≤ n)P_k^*}, where P_k^* is either p_k or ¬p_k, (2) simplification mintermsin M and elimination of useless ones, and (3) generation of fragments: Each mintermm generates a fragment defined as σ_m (R) (σ is a selection operation). This approach is simple, but it has a high complexity. For n simple predicates, this algorithm generates 2ⁿ minterms. It can be used for a reasonable number of simple predicates. In order to reduce this complexity, another approach was proposed, which adapts the vertical partitioning algorithm [15]. Predicates having a high affinity are grouped together. An affinity between two predicates, p_i and p_j, is computed as the sum of frequencies of queries accessing simultaneously these two predicates. Each group gives a horizontal fragment defined as a conjunction of its predicates. This algorithm has a low complexity [16], but it takes into account only access frequencies to generate horizontal fragments and ignores parameters like size of tables and selectivity factors of predicates.

FIGURE 25.1.Classification of HP approaches.

Given the need to have a reasonable and controlled number of fragments, new threshold-based approaches are proposed. This threshold represents the maximum number of fragments that the administrator wants to have. The main objective of threshold-based approaches is to partition a table into B fragments such that B is less than or equal to the threshold (constraint bound). Thus, in addition to the set of selection predicates, these approaches require that the administrator sets the threshold value. Two major classes of works exist in this category: data mining-based approaches and cost-based approaches.

The data mining-based approach was proposed in the context of XML data warehouses [17]. It uses the K-means clustering algorithm to group selection predicates that can fragment the data warehouse. The threshold B (number of fragments) is given as the input parameter for the K-means algorithm. K-means is used to group the predicates in B groups. The proposed approach consists in three main steps: (1) coding of selection predicates, (2) classification of predicates, and (3) generating fragments. The coding of a predicate is to assign each predicate to the query in which it is referenced to build the extraction context. The classification of predicates uses the clustering algorithm K-means [18] to create B classes of predicates. The construction of fragments is based on classes of predicates identified in the classification stage. Each class of predicates is used to generate a horizontal partition. The approach proposes to partition the dimension document by horizontal primary partitioning and the facts document by horizontal derived fragmentation. To ensure complete fragmentation, a fragment ELSE is added. It is the negation of all conjunctions of predicates. This approach controls the number of generated fragments but does not guarantee performance of the generated fragmentation schema.

The cost-based approach starts with a set of potential fragmentation schemes of relation R and using a cost model measuring the number of inputs and outputs required for executing a set of queries; it computes the goodness of each schema [19]. The schema with a low cost is considered as the final solution. The DBA may quantify the benefit obtained by this solution. Its main drawback is that the DBA does not have control of the number of generated fragments.

All the work we cited has proposed approaches for HP of isolated selection. Several works proposed to combine HP with other optimization techniques. Sanjay et al. [8] proposed an integration of horizontal and vertical fragmentation in the physical design of databases. Stöhr et al. [11] proposed the combination of HP with parallel processing in parallel data warehouses. The approach exploits hierarchies of dimensions to fragment data warehouses modeled by a star schema. The approach exploits parallelism within and between queries to reduce the cost of query execution. The approach also proposes the use of BJI defined on attributes not used to partition the data warehouse. In Reference 20, we proposed the HP & BJI approach, which combines HP and BJI in the physical design of relational data warehouses. HP & BJI starts with selecting a HP schema and then identifying the set of nonprofitable queries after partitioning and the set of attributes not used to partition the data warehouse. In the second step, HP & BJI select a configuration of join indexes based on the two sets of attributes and queries identified in the last stage. The main particularity of this approach is that it prunes the search space of an optimization technique (indexes) using another optimization technique (HP). Recently, Bellatreche et al. [6] proposed a combination design approach of parallel data warehouses using HP. Unlike existing works that consider the problems of fragmentation and allocation independently, the proposed approach considers a combined problem of fragmentation and allocation. Actually, horizontal fragmentation is an integral part of the physical design of most important DBMS editors: Oracle [13], DB2 [21], SQL Server [22], PostgreSQL [23], and MySQL [24]. To show this interest, we consideran example of one of the most popular DBMSs, which is Oracle.

Figure. 25.2 shows the main partitioning modes in Oracle. The first HP mode supported by Oracle was range partitioning (in Oracle 8). It is defined by a tuple (c, V), where c is a column type and V is an ordered sequence of values from the domain of c. In this partitioning, an access path (table, materialized view, and index) is split according to a range of values of a given set of columns. Oracle 9 and 9i added other modes like Hash and List and Composite (Range‒Hash, Range‒List). The Hash mode decomposes the data according to a hash function (provided by the system) applied to the values of the partitioning columns. List partitioning splits a table according to the list values of a column. Composite partitioning is supposed by using PARTITION‒SUBPARTITION statement. Note that these modes are also supported by other commercial databases like SQL Server, Sybase, and DB2. These partitioning modes are considered as basic modes of any partitioning tool supported by commercial DBMS. Oracle 11g proposes several fragmentation modes. The composite partitioning method has been enriched to include all possible combinations of basic methods (except those that begin with the hash mode): List‒List, Range‒Range, List‒Range, and List‒Hash. Recently, a new composite mode, Hash‒Hash, is supported by Oracle 11g Release 2 [13]. Another interesting mode called virtual column partitioning is proposed, which allows a table to be decomposed using a virtual attribute defined by an expression, using one or more existing columns of a table, and storing this expression as metadata only. Oracle supports another partitioning mode, interval partitioning. This mode extends the capabilities of the range mode to define equipartitioned ranges using an interval definition. Rather than specifying individual ranges explicitly, Oracle will create any partition automatically as needed whenever data for a partition is inserted for the very first time. Recently, in Oracle 11g Release 2, the interval composite mode is introduced. Three interval composites are supported: interval‒range, interval‒list and interval‒hash. Note that all these modes concern only the primary HP, where a table is partitioned using its attribute(s). The referential partitioning mode allows partitioning a table by leveraging an existing parent‒child relationship. This partitioning is similar to derived HP [12]. Unfortunately, a table may be partitioned based only on one table.

FIGURE 25.2. Horizontal partitioning modes.

Oracle and several commercial DBMSs provide DDL for managing partitions. Two main functions are provided: merge partitions and split partition. The first function consists in merging two partitions into one. The second function splits a partition into two partitions. The syntax of the use of these functions is given below:

ALTER TABLE <table_name>

MERGE PARTITIONS <first_partition>, <second_partition>

INTO PARTITION <partition_name>

TABLESPACE <tablespace_name>;

ALTER TABLE <table_name>

SPLIT PARTITION <partition_name>

AT <range_definition>

INTO (PARTITION <first_partition>, PARTITION <second_partition >)

Note that other functions are available, such as deleting a partition, adding a new partition, moving a partition, and renaming a partition.

Oracle also allows index fragmentation. An index created on a table is either coupled or uncoupled with the underlying partitioning mode of this table. Two kinds of partitioned indexes are supported in Oracle: local and global partitioned indexes. A local index is created on a partitioned table that is coupled with the partitioning strategy of this table (attributes, mode, and number of fragments). Consequently, each partition of a local index corresponds to one and only one partition of the underlying table. A local index enables optimized performance and partition maintenance. When a query references one partition, only its local index is loaded instead of the entire index. When a partition is dropped/updated, only its local index will be removed/updated. Local indexes are very suitable for OLAP applications. A global partitioned index is defined on a partitioned or nonpartitioned table. It is partitioned using a different partitioning strategy than the indexed table. For example, table Customer could be range partitioned by attribute Age, while a global index is range partitioned by attribute Salary. This kind of index is suitable for online transactional processing (OLTP) applications.

By exploring most academic and industrial works, we figure out that most of the approaches in selecting a HP schema suppose a decomposition of domain values of attributes participating in the fragmentation process. We can classify these approaches into two main categories (see Figure. 25.3): (1) user-driven approaches and (2) query- driven approaches. In the first category, the DBA decomposes the domain values of each partitioning attribute based on her or his knowledge of database applications and imposes a priori the number of generated horizontal fragments. For example, the following statement allows partitioning the table Customer using State attribute using the list mode into four fragments:

FIGURE 25.3. Domain decomposition approaches classifi cation.

CREATE TABLE Customer (CID NUMBER(5), Name VARCHAR2(30), State VARCHAR2 (20), City Varchar2 (20))

PARTITION BY LIST (State) (PARTITION Customer_west VALUES(‘California', ‘Hawaii'), PARTITION Customer_east VALUES (‘New York', ‘Virginia', ‘Florida'), PARTITION Customer_central VALUES(‘Texas', ‘Illinois'), PARTITION Customer_other VALUES(DEFAULT));

The main characteristic of this category is that the DBA controls the number of generated fragments. She or he sets this number based on her or his knowledge and experience on database applications. Its main drawbacks are (1) the absence of a metric measuring the quality of the generated partitioning schema, (2) the difficulty on choosing attributes that will participate on fragmenting a table, and (3) an efficient decomposition of domains of fragmentation attributes is not ensured.

In query-driven partitioning approaches, the domain values of fragmentation attributes are explicitly decomposed based on simple selection predicates of the most frequently asked queries defined on relation T. We can classify these approaches into two categories: those that use predicates to generate the final decomposition of domains and those that use algorithms to do so. We can distinguish two trends in the first category: approaches without predicates clustering and approaches with predicates clustering. The first trend uses directly selection predicates for generating minterms [4]. Minterms are used to generate the domain decomposition. The predicate clustering approach begins with a step of grouping predicates into multiple partitions. These partitions are used to generate domain decomposition. Clustering is based on either the affinities [16] or clustering algorithm like K-means [17]. All the approaches we have presented do not guarantee the quality of the final domain decomposition. To overcome this problem, greedy approaches have been proposed. Their idea is to start by initial decomposition (random or issued from a different approach we have cited), then to iteratively improve decomposition by merging or splitting subdomains. Improving the initial decomposition is guided by a cost model, which estimates the execution cost of frequently asked queries on a partitioned schema generated by domain decomposition. We present in the next section our fragmentation methodology and the two selection algorithms that we have proposed.

25.3   FRAGMENTATION METHODOLOGY

As for redundant technique (materialized views, indexes) selection problems, horizontal selection schema selection is done based on a set of the most frequently asked queries ({Q₁,…, Q_W}), where each query Q_j has an access frequency f_Qj. Note that each star join query Q_j is defined by a set of selection predicates and a set of join predicates. The selection predicates are essential for the partitioning process. Note that each selection predicate has a selectivity factor. To partition a relational data warehouse, we present the following methodology:

1. Extraction of all selection predicates used by the queries.
2. Assignment to each dimension table D_i (1 ≤ i ≤ n) its set of selection predi- cates, denoted by SSPD_i.
3. Ignorance of dimension tables having an empty SSPD (i.e., they will not participate in fragmenting the fact table). Let D^candidate be the set of all dimensiontables having a nonempty SSPD. Let g be the cardinality of D^candidate (g ≤ n).
4. Identification of the set fragmentation attributes SFAC candidate. A fragmentation attribute is an attribute of dimension tables participating in the partitioning process.
5. A decomposition of domain values of each fragmentation attribute into subdomains. This decomposition may be done either intuitively by the DBA using her or his knowledge of warehouse applications or guided by simple predicates defined on each fragmentation attribute. Each subdomain may be represented by a simple predicate and it has a selectivity factor defined on the fact table.
6. Selection of a final fragmentation schema using an algorithm that exploits the decomposition of all domains of fragmentation attributes. Such algorithm shall reduce query processing cost and satisfy the maintenance constraint. In order to illustrate this methodology, let us consider the following example.

■ EXAMPLE 25.2

Suppose that SFAC contains three attributes (Age, Gender, Season), where Age and Gender belong to the Customer dimension table, whereas Season belongs to Time (D^candidate = {Customer, Time}). The domains of these attributes are Dom(Age) = [0, 120], Dom(Gender) = {“M,” “F”}, and Dom(Season) = {“Summer,” “Spring,” “Autumn,” “Winter”}. We assume that DBA splits domains of these attributes into subdomains as follows: Dom(Age) = d₁₁ ∪ d₁₂ ∪ d₁₃, with d₁₁ = [0, 18], d₁₂ = [18, 60], d₁₃ = [60, 120]. Dom(Gender) = d₂₁ ∪ d₂₂, with d₂₁ = {“M”}, d₂₂ = {“F”}. Dom(Season) = d₃₁ ∪ d₃₂ ∪ d₃₃ ∪ d₃₄, where d₃₁ = {“Summer”}, d₃₂ = {“Spring”}, d₃₃ = {“Autumn”}, and d₃₄ = {“Winter”}. The subdomains of all three fragmentation attributes are represented in Figure 25.4a.

FIGURE 25.4. An example of decomposition of domains in subdomains.

TABLE 25.1. An Example of Partitioning Schema

Domain partitioning of different fragmentation attributes may be represented by multidimensional arrays, where each array represents the domain partitioning of a fragmentation attribute. The value of each cell of a given array representing an attribute A_i^k belongs to (1…n_i), where n_i represents the number of subdomain of the attribute A_i^k (see Fig. 25.4b). Based on this representation, the fragmentation schema of each dimension table D_j is generated as follows:

1. All cells of a fragmentation attribute of D_j have different values: this means that all subdomains will be used to partition D_j. For instance, the cells of each fragmentation attribute in Figure 25.4b are different. Therefore, they all participate in fragmenting their corresponding tables (Customer and Time). The final fragmentation schema will generate 24 fragments of the fact table.
2. All cells of a fragmentation attribute have the same value: This means that it will not participate in the fragmentation process. Table 25.1 gives an example of a fragmentation schema, where all subdomains of Season (of dimension table Time) have the same value; consequently, it will not participate in fragmenting the warehouse schema.
3. Some cells have the same value: Their corresponding subdomains will be merged into one. In Table 25.1, the first ([0, 18]) and the second ([18, 60]) subdomains of Age will be merged to form only one subdomain, which is the union of the merged subdomains ([0, 60]). The final fragmentation attributes are Gender and Age of dimension table Customer.

The above coding (in Table 25.1) may be used by DBA to partition the dimension table Customer and the fact table Sales using the primary partitioning (Range on Age and List on Gender) and referential partitioning modes, respectively:

CREATE TABLE Customer (CID NUMBER, Name Varchar2 (20), Gender CHAR, Age Number) PARTITION BY RANGE (Age)

SUBPARTITION BY LIST (Gender)

SUBPARTITION TEMPLATE (SUBPARTITION Female VALUES (‘F'), SUBPARTITION Male VALUES (‘M')) (PARTITION Cust_0_60 VALUES LESS THAN (61), PARTITION Cust_60_120 VALUES LESS THAN (MAXVALUE));

Since the Customer was partitioned into four fragments, the fact table is also partitioned into four partitions as follows:

CREATE TABLE Sales (customer_id NUMBER NOT NULL, product_id NUMBER NOT NULL, time_id Number NOT NULL, price NUMBER, quantity NUMBER,

TABLE 25.2. Two Ways to Represent the Same Individual

constraint Sales_customer_fk foreign key(customer_id) references Customer(CID))

PARTITION BY REFERENCE (Sales_customer_fk);

25.3.1   Multi-instantiation of Our Coding

Our coding may suffer from multi-instantiation. To illustrate this problem, we consider a set D = {d₁, d₂, d₃}, then every subset in the partition of D, for instance, {{d₁, d₃}, {d₂}}, can be represented by an array of integers. Nevertheless, a given partition can be represented by different arrays of integers (see Table 25.2).

Clearly, arrays 1 and 2 only differ by integers used for representing these subsets: In both solutions, d₁ and d₃ belong to the same subset, and d₂ is in the other subset. Such a problem can be solved by using restricted growth functions:

Let [n] be a set {1,…, n}; a restricted growth function is a function f such as

F: [n]→ [n] such that

f (1) = 0.

f(i + 1) ≤ max f(1),…, f(i) + 1, where f (i) defines the subset index where the item i belongs to. For instance, the partition {{1, 3, 5}, {2, 6}, {4}} is represented by the restricted growth function [0, 0, 0, 1, 1, 2], where 0 is the index of the first subset. There is a one-to-one equivalence between set partitions and restricted growth functions. In our previous example, only array 1 respects the lexicographic order induced by restricted growth functions, while array 2 will never be considered during the set partitioning.

Theorem 25.1 There is a one-to-one correspondence between the set of [n] and the set of restricted growth functions.

Several algorithms are known for generating all partitions of a set D in lexicographic order (see Reference 25, for instance).

■ EXAMPLE 25.3

To show the contribution of the restricted growth function in eliminating multi-instantiation, let us consider the following example. The two top codings of Figure 25.5 represent the same fragmentation schema. The application of the restricted rowth function gives only one schema (the bottom one).

25.4   HARDNESS STUDY

We consider the HP of the data warehouse through a simplified decision problem that considers the derived HP of the fact table based on the partitioning schema of one dimension table using only one attribute. The corresponding optimization problem consists in computing a partition of the fact table so that the number of partitions is bounded by a constant B and the maximum number of input/output (I/O) operations is minimized. We state the decision problem as follows:

FIGURE 25.5. An example of using the restricted growth function.

Problem: One-Domain HP

Instance:

• A set D of disjoint subdomains {d₁,…, d_n} of the fragmentation attribute of the partitioned dimension table and the number of I/O operations in order to read data corresponding to the subdomain d_i in the fact table, denoted l(d_i), 1 ≤ i ≤ n
• A set of queries {q₁,…, q_m}, where each query q_j has a list f(q_j) ⊆ D of used, subdomains until the query completion: {d_j1,…, dj_nj} where n_j is the number of subdomains used in the fact table to run q_j
• Two positive integers, K and L, representing, respectively, the maximum number of partitions that can be created and the maximum number of I/O operations allowed for each query, L ≥ ∑_{d ∈ f(qj)}l(d)

Question: Can D be partitioned in at most K subsets, D₁,…, D_k such that every query requires at most L I/O operations?

The optimal number of I/O operations required by a query q_j is ∑_d∈f(qj)l(d). It assumes that only required data are loaded in memory to run q_j. According to a given partition, the number of I/O operations increases since all data of a partition are loaded when used by a given query, even if that query does not require all data of the partition (i.e., a subset of domains in the partition). Thus, the number of I/O operations required by a query after partitioning does not depend on the used subdomains but only on used partitions. The number of I/O operations while loadinga partition D is defined by l(D) ≥ ∑_d∈D l(d). As a consequence, the number of I/O operations required by running a query can be defined as l(q_j) = ∑_D∈F(qj)l(D), where F(q_j) is the list of partitions used by a query q_j.

The objective is to perform a derived HP of the fact table such that the number of partitions is limited to K and the number of I/O operations is bounded by L for every query. Obviously, if K ≤ n, the optimal HP is achieved by defining exactly one partition to every d_i (d_i ∈ D). In that way, every query only loads required data during its execution. We shall see that our simplified decision problem becomes hard when K < n. We also assume L ≥ ∑_d∈f(qj)l(d) since, otherwise, the answer of the one-domain HP is always false.

Theorem 25.2   One-domain HP is NP-complete in the strong sense.

Proof: One-domain HP clearly belongs to NP since, if one guesses a partition of D, then a polynomial time algorithm can check that, at most, K partitions are used and that every query requires, at most, L I/O operations. We now prove that one-domain HP is NP-complete in the strong sense. We shall use 3-partition that is strongly NP-complete [26]. ■

Problem: 3-Partition

Instance: Set A of 3m elements, a bound B ∈ Z⁺ , and a size s(a) ∈ Z⁺ , for each a ∈ A such that B/4 < s(a) < B/2 and such that ∑_α∈AS(α) = mB

Question: Can A be partitioned into m disjoint sets A₁,…, A_m such that, for 1 ≤ i ≤ m, ∑_a∈AiS(a) = B (note that each A_i must therefore contain exactly three elements from A)?

To prove the NP-completeness of one-domain HP, we reduce from 3-partition. To every 3-partition instance, an instance of one-domain HP is defined as follows:

• To every a_i ∈ A, a subdomain d_i is created so that l(d_i) = s(a_i), 1 ≤ i ≤ 3m.
• 3m queries are created such that every query uses exactly one subdomain: f(q_i) = {d_i}, 1 ≤ i ≤ 3m.
• K = L = B.

Clearly, the transformation is performed in polynomial time since it consists in a one-to-one mapping of 3-partition elements into subdomains and queries. We now prove that we have a solution to the 3-partition instance if and only if we have a solution to the one-domain HP instance.

25.4.1   Necessary Condition

Assume that we have a solution of the one-domain HP, and then it satisfies the following conditions:

• Since B/4 < l (d) < B /2, every subset of D will be defined with exactly three subdomains (as in every 3-partition instance).
• Since we have a feasible solution of the one-domain HP, then no query requires more than I/O operations. By construction we verify that ∑ _d∈D l(d) = mB. As a consequence, every query requires exactly B I/O in the fact tables (otherwise, it is not a solution). Using a one-to-one mapping of subdomains into elements of a 3-partition, a feasible solution of the 3-partition instance is obtained.

25.4.2   Sufficient Condition

Assume that we have a solution to the 3-partition instance. Then, every subset A_i is a total size of B and is composed of exactly three elements of A. Starting from A₁, we define a subdomain partition using subdomains with the same indexes of elements belonging to A₁. Since every query is associated with exactly one subdomain and three subdomains are grouped in every partition, then exactly three queries use a given partition. As a consequence, the number of I/O associated with these three corresponding queries is exactly B. Repeat this process for every remaining subset A_i, and then a feasible solution of the one-dimension HP problem is obtained.

Every subdomain can be used to define a HP of the fact table. As a consequence, the number of solutions (i.e., the number of ways to partition the fact table) is defined by the number of partitions of the set D. For a set of size k, this number is defined by the Bell number. Even if the number of solutions is limited when k is small, it vastly becomes intractable (e.g., if k = 10, then the number of different partitions is 115,975).

25.5   PROPOSED SELECTION ALGORITHMS

Due to the high complexity of the HP selection problem, development of heuristics selecting near-optimal solutions is recommended. In this section, we present the hill climbing and simulated annealing (SA) algorithms [27] with several variants.

25.5.1   Hill Climbing Algorithm

The hill climbing heuristic consists of the following two steps:

1. Find an initial solution.
2. Iteratively improve the initial schema solution by using the hill climbing operations until no further reduction in total query processing time can be achieved and the maintenance bound B is satisfied. Since there is a finite number of fragmentation schemes, the heuristic algorithm will complete its execution.

25.5.1.1   Choices of the Initial Solution   Theoretically, the choice of the initial solution of hill climbing has an impact on the quality of the final solution. We propose three initial solutions: (1) a uniform distribution, (2) a Zipf distribution, and (3) a random distribution. Let C be the cardinal of set of fragmentation attributes SFAC, where each attribute A_k has n_k subdomains.

Uniform Distribution. In this solution, each cell i of fragmentation attribute (A_k) is filled using the following formula: Array[i]_k = ⌊i/n⌋, where n is an integer (1 ≤ n ≤ max _{(1≤ j≤C)}(n_j )). To illustrate this distribution, let us consider three fragmentation attributes: Gender, Season and Age, where n_Gender = 2, n_Season = 4, and n_Age = 3 (see Example 25.2). The coding in Figure 25.6 represents uniform distribution with n = 2(n_Gender), n = 3(n_Age), and n = 4(n_Season). The generated fragments of partitioning schema corresponding to n = 2, n = 3, and n = 4 are 12, 4, and 2, respectively. If aDBA wants an initial fragmentation schema with a large number of fragments, she or he considers n with a low value. In this case, all initial subdomains (proposed bythe DBA) have the same probability to participate on the fragmentation process.

FIGURE 25.6. An example of generation of initial solution with uniform distribution.

FIGURE 25.7. An example of generation of initial solution with direct Zipf distribution.

Zipf Distribution. This distribution is largely used in database physical design [28] and Web access documents [29], where it is used as follows: The relative probability of a request for a document is inversely proportional to its popularity rank I (1 ≤ i ≤ N). The probability P(i) of a request for the i th popular document is proportional to 1/i^α(0 < α ≤ 1).

In our context, we claim that it is appropriate to model the subdomain access using this Zipf-like distribution. Let N₁ be the number of subdomains of the first partition of domain of fragmentation attribute A_k. Each cell of A_k is filled as follows: Array[i]_k = ⌊N_l/i⌋, where N_l is obtained by dividing the number total of subdomains of A_k per 2 and incrementing the result per p (p is an integer 1 ≤ p ≤ max_1≤j≤C(n _j)).

This distribution is called direct (simple) Zipf (see Fig. 25.7). We can imagine two other distributions: random Zipf and inverse Zipf. In the random Zipf distribution, cells of each fragmentation attribute are filled randomly following the direct Zipf law. The final coding is reorganized by applying the restricted growth function. An example of this coding is given in Figure 25.8.

Inverse Zipf distribution is similar to the simple Zipf distribution; the only difference is that the first partition of each domain has a smaller number of subdomains. An example of this coding is illustrated in Figure 25.9.

FIGURE 25.8. An example of generation of initial solution with random Zipf distribution.

FIGURE 25.9. An example of generation of initial solution with inverse Zipf distribution.

We notice that all Zipf variants generate the same number of fragments.

Random Distribution. In this distribution, multidimensional arrays representing fragmentation is filled randomly. Two variants of this distribution are considered: random with renumbering using restricted growth functions and random without renumbering.

Improvement of the Initial Solution   In order to improve the initial solution, two operations, namely, merge and split, are applied to reduce the total query processing cost. They have the same semantic of those used by commercial DBMS (see Section 25.2).

MERGE  This function has the following signature: Merge . It takes two partitions, P_i^k and P_j^k, of the fragmentation attribute A^k of fragmentation schema SF and gives another schema, SF', where P_i^k and P_j^k are merged. The merging process consists in assigning the same number of their respective cells. This operation reduces the number of fragments. This operation is used when the number of generated fragments is greater than the maintenance constraint B.

SPLIT   This function has the following signature: Split It takes one partition P_i^k of the fragmentation attribute A^k of fragmentation schema SF and gives another schema SF', where P_i^k is split into two partitions. This operation increases the number of fragments.

■ EXAMPLE 25.4

Figure 25.10 presents a coding of a fragmentation schema SF generating 12 fragments of the fact table: 2 (fragments generated by Age) × 2 (fragments generated by Gender) × 3 (fragments generated by Season). On this schema, we first apply the merge function on attribute Gender, where subdomains 1 and 2 are merged. We obtain another fragmentation schema SF′ generating six fragments since the attribute Gender will not participate on fragmenting the Customer table. We can apply the split function (which is a dual operation of merge) on the fragmentation schema SF′ on the Gender attribute, where we get the fragmentation schema SF″, which is identical to SF.

FIGURE 25.10. Applying merge and split operations.

25.5.1.2   Problems When Using Merge and Split Operations   When applying these two functions, we have identified three main problems: (1) the order of applying merge and split functions, (2) the choice of starting attributes for merge and split functions, and (3) the choice of subdomains.

1. The Order of Applying Merge and Split Functions. To solve this problem, we have used a feasibility criterion for each solution. A fragmentation schema is feasible if it does not violate the maintenance constraint (the generated fragments should satisfy the maintenance bound B). Therefore, if a solution is feasible, the split function is first applied in order to generate a solution with more fragments than the current one. Otherwise, if the current solution is not feasible, then the merge function is applied in order to reduce the number of generated fragments.
2. Choice of Starting Attributes. Recall that each fragmentation schema solution is coded using multidimensional arrays, where each row represents a fragmentation attribute. In order to apply merge and split, fragmentation attributes are sorted using their access frequencies. The frequency of each attribute is calculated as the sum of query frequencies using that attribute. The merge function is applied on least frequently used attributes in order to reduce their use on the fragmentation process, whereas the split function is used on most frequently used attributes in order to increase their participation on fragmenting the data warehouse schema.
3. Choice of Subdomains Participating on Merge and Split Operations. If an attribute is chosen, all its cells are candidate for merge and split functions. Our choices are realized as follows:

• Merge Function. To apply the merge function on attribute A^k, we do all pairwise subdomain merges. The quality of each merge operation is evaluated using a cost model. If attribute A^k has m_k subdomains, m_k × (m_k − 1)/2 merge operations are possible. In order to select the best merge, we define a function, called BestMerge, with the following signature: BestMerge(A^k, SF) → SF. It takes an attribute A^k and a fragmentation schema SF and gives the best merge among all possible merges.
• Split Function. Generating all possible splits is more complicated compared to merges. In our study, we propose to split subdomains having a high selectivity factor. This choice reduces the size of generated fragments. In order to select the best split, we define a function, called BestSplit, with the following signature: BestSplit (A^k, SF) → SF.

Evaluation of the Quality of Generated Solution The application of these operations is controlled by a cost model computing the number of inputs and outputs required for executing a set of queries on the selected HP schema. A particularity of this model is that it considers buffer size when executing a query.n For lack of space, it cannot be presented in this chapter.n Now we have all ingredients to present our hill climbing algorithm (see Fig. 25.11)

FIGURE 25.11. Hill climbing algorithm description.

25.5.2   Simulated Annealing Algorithm

It is well known that one of the main weaknesses of the hill climbing approach is that it suffers from the problem of local optima. To overcome such a problem, a simulating annealing approach can be applied instead. It is a randomized technique for finding a near-optimal solution of difficult combinatorial optimization problems [30]. It starts with a randomized candidate solution, then it repeatedly attempts to find a better solution by moving to a neighbor with higher fitness until it finds a solution where none of its neighbors has a higher fitness. To avoid getting trapped in poor local optima, simulated annealing allows occasionally uphill moves to solutions with lower fitness by using a temperature parameter to control the acceptance of the moves but also uphill moves with some probability that depends on a number of parameters.

In our context, simulated annealing has an input an initial fragmentation schema as for hill climbing algorithm (random, uniform, and Zipf). It uses a function called RandomTransform which takes a fragmentation schema FS and returns a schema FS′ with better quality. This function applies random changes on the initial schema using the two functions, merge and split (see hill climbing algorithm), but the choice of attributes and subdomains is done randomly. The main structure of this algorithm is described in Figure 25.12.

FIGURE 25.12. Simulated annealing algorithm description.

25.6   IMPACT OF HP ON DATA WAREHOUSE PHYSICAL DESIGN

We have shown that HP is constrained by a threshold representing the number of fragments that the DWA wants to have for her or his application. As a consequence, HP cannot optimize all queries especially those containing selection predicates defined on attributes not used to partition the data warehouse. Therefore, DWA needs to use another optimization technique from the existing ones: materialized views, indexing, compression, and so on. By studying different optimization techniques, we identify a strong similarity between HP and BJI. BJI are multitable indexes proposed to precompute joins between the fact and dimension tables. They are defined on the fact table using one or more dimension attributes. BJI are more suitable for low cardinality attributes since its size strictly depends on the number of distinct values of columns on which it is built [31]. In the next section, we show the similarity between HP and BJI.

25.6.1   Similarity between HP and BJI

To show the similarity between HP and BJI, we consider the following example. Suppose we have a data warehouse represented by three dimension tables (Time, Customer, and Product) and one fact table (Sales). The population of this schema is given in Figure 25.13. Assume that the DWA wants to have the number of sales for customers living in Poitiers for beauty products during June. The query to meetthis need is

SELECT COUNT(*)

FROM Sales S, Customer C, Product P, Time T WHERE S.CID = C.CID AND S.TID = T.TID AND S.PID = P.PID AND C. City = ‘Poitiers 'AND T. Month = ‘June 'AND P. Range = ‘Beauty '

This query has three selection predicates defined on dimension table attributes City, Range, and Month and three join operations. To optimize this query, DWA can use HP or BJI.

a. Optimization Using HP. DWA can partition the dimension tables Customer, Time and Product on attributes City, Month, and Range, respectively:

• Customer is partitioned into three fragments, each corresponding to a city (Poitiers, Paris, and Nantes).
• Product is partitioned into five fragments each corresponding to a range (Beauty, Multimedia, Toys, Gardening, and Fitness).
• Time is partitioned into six fragments each corresponding to one month (January, February, March, April, May, and June).

The fact table Sales can be derived partitioned using the partitioning schema of the previous three dimension tables on 90 partitions (3 × 5 × 6). Each fragment of the table Sales is defined as follows:

Sales _i = Sales ⋉ Customer_j ⋉ Time_k ⋉ Product_p (1 ≤ i 90, 1 ≤ i 3, 1 ≤ j 6, 1 ≤ k ≤ 5).

FIGURE 25.13. A sample of a data warehouse population.

Note that the initial star schema is partitioned on 90 substar schemas. Figure 25.14c shows the substar schema containing the fact fragment Sales_PJB corresponding to sales of beauty products realized by customers living at Poitiers during June. To execute the above query, the optimizer shall rewrite it. Therefore, it loads only the fact fragment Sales_PJB and only counts the number of lines found in this fragment (there are two). The above query is then rewritten as follows:

SELECT Count(*) FROM Sales_PJB By partitioning the data warehouse, the DWA may have two types of improvements: (1) A single partition of the fact table was loaded instead of 90 partitions and (2) no join operation was calculated.

b. Optimization Using BJI. The DWA creates a BJI on three dimension attributes: City, Month, and Range as follows:

FIGURE 25.14. (a) The bitmap join index. (b) The result of AND operation. (c) The substar schema.

CREATE BITMAP INDEX sales_cust_city_prod_range_time_month_bjix ON Sales(Customer.City, Product.Range, Time.Month)

FROM Sales S, Customer C, Time T, Produit P WHERE S.CID = C.CID AND S.PID = P.PID AND S.TID = T.TID

Figure 25.14a shows the generated BJI. To execute the above query, the optimizer just accesses the bitmaps corresponding to the columns representing June, Beauty, and Poitiers and performs an AND operation. It then calculates the number of 1 in the result vector; there are also two (see Figure. 25.14b). By creating the BJI, the DWA may have two types of improvements: (1) Only the BJI was loaded (no tables have been loaded) and (2) any join operation was performed.

This example shows the similarity between HP and BJIs: (1) They reduce the queries'execution cost by reducing the amount of loaded data; (2) they precompute join operations between the fact table and dimension tables; and (3) they share the same resource that is the set of selection attributes. Based on this similarity, we propose a new approach for selecting simultaneously HP and BJIs. To summarize our finding in similarities between HP and BJI, we can say that both BJI and HP are fundamentally similar: Both are structures that speed up query execution, precompute join operations, and are defined on selection attributes of dimension tables. Furthermore, BJIs and HP can interact with one another; that is, the presence of an index can make a partitioned schema more attractive and vice versa. Unfortunately, the identified similarities are not considered during the joint selection of HP and BJI since both selection problems are done in an isolated way. Note that several studies have shown the hardness of BJI selection [32]. In the next section, we propose to exploit these similarities to select BJI schemes and HP schemas [20, 33]. This selection prunes the research space of the BJI problem.

25.6.2   Our Selection Approach of HP and BJI

Our selection approach of HP and BJI (HP & BJI) exploits the similarities between these two techniques, in particular, the sharing of selection attributes [34]. The approach begins by fragmenting the data warehouse using a fragmentation algorithm, then selecting a set of BJI on a fragmented data warehouse using nonprofitable queries and attributes not used by HP. Note that partitioning the data warehouse before selecting BJI reduces the complexity of the BJI selection problem because the number of candidate attributes decreased. Therefore, our approach prunes the search space of BJI using HP. This increases the importance of HP in the physical design of data warehouses. Figure 25.15 shows the architecture of our approach. It is composed of four steps: (1) fragmentation of the data warehouse, (2) identifying no profitable queries, (3) identification of indexable attributes, and (4) selection of a BJI configuration:

1. The selection of a partitioning schema is performed using an algorithm that we proposed (genetic algorithm, simulated annealing, or hill climbing). The algorithm takes as input a workload of queries Q = {Q₁, Q₂,…, Q_m}, the set of selection attributes (SASET), and the threshold B and generates a partitioning schema (PS). PS is defined on a set of fragmentation attributes (FASET).

   

   FIGURE 25.15. Architecture of our approach.

2. Among all m queries, some benefit from the fragmentation and others do not. A query gets benefit from the fragmentation if its execution cost is significantly reduced. To identify the set of profitable queries, we use a rate defined for each query as Rate(Q_j) = Cost(Q_j, PS)/Cost(Q_j, ϕ), where Cost(Q_j, ϕ) and Cost(Q_j, PS) represent the execution cost of the query Q_j on unpartitioned data warehouse and partitioned with PS, respectively. The DWA has the right to set up this rate using a threshold λ: If rate(Qj) ≤ λ, then Q_j is a profitable query, otherwise, no profitable query. The set of no profitable queries is denoted by
3. Indexable attributes are identified among selection attributes (SASET) with low cardinality and which are not used to fragment the data warehouse. The set of these attributes is denoted by BJISET.
4. The selection of BJI configuration is done using a greedy algorithm under storage constraint. This algorithm takes as input the set of no profitable queries Q′, the set of indexable attributes (BJISET), and the constraint storage S and generates a configuration of BJI reducing the execution cost of Q′. This algorithm uses a cost model that estimates the execution cost of queries using BJI [32].

25.7   EXPERIMENTAL STUDIES

We have conducted many experimental studies in order to evaluate and to compare the proposed algorithms: hill climbing and simulated annealing with their variants. We first evaluate each algorithm and then we jointly study them. We have conducted also experiments to evaluate our combined selection approach (HP & BJI).

Data Set: We use the data set from the APB1 benchmark [35]. The star schema of this benchmark has one fact table Actvars (33,324,000 tuples) and four dimension tables: Prodlevel (99,000 tuples), Custlevel (990 tuples), Timelevel (24 tuples), and Chanlevel (10 tuples). This schema is implemented using Oracle 11g.

Workload: We have considered a workload of 55 single block queries (i.e., no nested subqueries) with 40 selection predicates defined on 10 different attributes: Class_Level, Group_Level, Family_Level, Line_Level, Division_Level, Year_Level, Month_Level, Quarter_Level, Retailer_Level, All_Level. The domains of these attributes are split into 4, 2, 5, 2, 4, 2, 12, 4, 4, and 5 subdomains, respectively. We did not consider update and delete queries. Note that each selection predicate has a selectivity factor computed using SQL query executed on the data set of APB1 benchmark. In our coding, cells representing subdomains are arranged in ascended sorted order based on their selectivity factors. Our algorithms have been implemented using Visual C++ performed under Intel Pentium Centrino with a memory of 3 Go.

25.7.1   Evaluation of Hill Climbing Algorithm

Figure 25.16 compares the performance in terms of number of inputs and outputs of our hill climbing algorithm and its variants by varying the threshold. This variation is given in Table 25.3.

FIGURE 25.16. Evaluation of variants of the hill climbing algorithm.

TABLE 25.3. Variation of the Threshold

Six variants of hill climbing heuristic are evaluated: uniform, direct Zipf, inverse Zipf, random Zipf, not renumbered random, and renumbered random (using restricted growth function). Each variant is executed in order to generate the fragmentation schema of the APB1 data warehouse by varying the threshold. All variants are tested against the nonfragmentation case (where the data warehouse is not partitioned). The cost of the 55 queries is estimated using our cost model that uses the size of dimension and fact tables, selectivity factors, buffer size, and so on, over each fragmentation schema generated by each variant. The first observation is that the fragmentation schema obtained by all variants of hill climbing algorithm outperforms the nonfragmentation case, especially when the threshold becomes large. The second observation concerns the maintenance constraint (threshold) on its effect on performance of queries. When the threshold increases, hill climbing gives better results compared with the nonfragmented case. From a threshold varying from 280 and 500, we get fragmentation schemas with the same quality. This result is very interesting since it allows the DBA to choose his or her maintenance constraint from this range to ensure a high performance of his or her queries. Another observation concerns the impact of the initial solution on the quality of generated solution by the hill climbing algorithm. The uniform distribution is the best choice for the hill climbing solution. In our experiments, the uniform distribution is used with n = 4 (Array[i]_k = ⌊i/n⌋). In this case, all initial subdomains have the same probability to participate on fragmenting tables. Zipf inverse distribution has less performance compared to the other variants; since subdomains of each fragmentation attribute are sorted, merge operations are usually done on subdomains with high selectivity. This generates fragments with a large population.

In Figure. 25.17, we study the effect of buffer size on performance of queries. To do so, we vary the buffer size from 0 to 1500 pages and we execute the hill climbing with the uniform variant (since it is the best variant) and we compute the cost of execution all queries. The threshold is fixed at 50. This experiment shows the impact of buffer on query performance, especially when we increase its size. When buffer size is around 900 pages, the behavior of the hill climbing algorithm is stable.

25.7.2   Evaluation of Simulated Annealing Algorithm

Figure 25.18 shows the performance of simulated annealing and its variants (random renumbered, random Zipf, uniform, random not renumbered, and simple Zipf). We conducted the same experiments as for hill climbing. All variants of simulated annealing outperformed largely the nonfragmentation case, contrary to the hill climbing algorithm. We found that uniform distribution outperforms the other variants for all variations of the threshold. We note a stability of performance of simulated annealing when the threshold reaches 200. Augmenting the threshold does not mean improving the performance of queries. Therefore, the threshold should be chosen carefully by the DBA. Even for small thresholds, simulated annealing gives interesting results compared to the no-fragmentation case.

FIGURE 25.17. Effect of the buffer on hill climbing performance.

FIGURE 25.18. Performance of simulated annealing and its variants.

Figure 25.19 gives the running time required by simulated annealing. Note that hill climbing execution is very fast (a most 3 seconds). In this experiment, the threshold value is set from 10 and 200. Simulating annealing is time-consuming compared to hill climbing. When the threshold is very large, the execution time increases rapidly. Based on these experiments, we issue some recommendations that could be exploited by DBA: If the execution time of the partitioning algorithm is the most important criteria, she or he may choose hill climbing.

FIGURE 25.19. Execution time required for simulated annealing and its variants.

FIGURE 25.20. Simulated annealing versus hill climbing (for uniform distribution).

25.7.3   Simulated Annealing Algorithm versus Hill Climbing Algorithm

In Figure 25.20, we compare the performance of hill climbing and simulated annealing using uniform distribution. An interesting result is obtained from this experimentation: Simulated annealing outperforms hill climbing for small threshold (when it varies from 5 to 160), whereas hill climbing gives better performance for a large number of threshold (when it varies from 300 to 500). For small thresholds, hill climbing performs more merge operations in initial solution, which usually increase the sizes of generated fragments. Consequently, HP does not perform well in this situation. For a large number of thresholds, hill climbing performs split operations in initial solution, where the number of generated fragments increases the HP, which is usually the best scenario for HP, especially when their sizes are uniform. Simulated annealing is doing the same task, but split and merge operations are done randomly. Based on this result, the DBA may choose the selection algorithm based on her or his threshold. For large threshold, hill climbing is used with a shorter execution time and high-quality solution. For fewer thresholds, simulated annealing may be used with short execution time.

FIGURE 25.21. Gain in percent obtained by simulated annealing and hill climbing algorithms.

Figure 25.21 shows the percentage of reduction of our algorithms (using a uniform distribution as an initial solution) computed against the nonfragmentation case. The results show the benefit of partitioning in reducing query processing cost. This reduction is almost stable when varying the maintenance cost (threshold). That is why commercial DBMSs advocated massively HP.

25.7.4   Evaluation of Combined Selection of HP and BJI

To evaluate our combined approach against the isolated selection approach, we conduct the following experiment. We use a genetic algorithm with threshold B = 100 and λ = 0.6 (used to identify the profitable queries from HP). After the execution of this algorithm, we identify that 25% of queries are nonprofitable and eight attributes are used to partition the data warehouse. The BJI selection module uses two candidate attributes, the set of no profitable queries Q' and a space bound equal 20 Mo. Two BJIs have been selected. The performance of our approach is shown in Figure 25.22 It reduces the cost obtained by only HP by 12% and without adding extra space cost.

25.8   PHYSICAL DESIGN SIMULATOR TOOL

During our experiments for evaluating the quality of our partitioning and BJI algorithms, we identify the need for development of a tool facilitating the setup of different parameters of the used algorithms during the physical design. By exploring the literature, we identify the existence of such tools owned by the most important commercial DBMS editors: Server Database Tuning Advisor (DTA), Oracle SQL Access Advisor, and DB2 Index Advisor. Their main role is to assist the DWA during their tasks. They allow what-if design exploration and propose DWA useful user interfaces. Other academic tools have been proposed such as PARINDA [36]. The main characteristic of these tools is that they are used when the data warehouse is under exploitation. Also, they suppose the knowledge of the target DBMS. Since physical design could be done without having a precise idea on the target DBMS, the use of simulation may contribute in getting efficient database applications. The main contributions of the use of simulators during the physical design are (1) aiding in guaranteeing an efficient physical design, since the database designer (DBD) can test/evaluate several optimization scenarios and (2) helping the DBD in choosing the target DBMS based on the proposed recommendations (for instance, if the simulator recommends the use of referential HP, which is only supported by Oracle, and if the DBD is convinced by this solution, he or she may adopt Oracle DBMS for his or her application). Based on the discussion, we propose a simulator tool, called SimulPh.D [37], offering DWAs the possibility to choose their favorite optimization technique(s), to evaluate their benefits, and to measure the used resources (e.g., storage). Once these choices are done, SimulPh.D proposes DWA recommendations summarizing different information regarding optimization techniques. If the DWA is satisfied with this recommendation, he or she by a simple click generates appropriate scripts that will execute on the target DBMS (if it is available).

FIGURE 25.22. Performance of our approach.

25.8.1   SimulPh.D Overview

We develop our simulator tool under C++ as a modular application. SimulPh.Dconsists of a set of seven modules (see Fig. 25.23): (1) metabase querying module, (2) managing queries module, (3) horizontal partitioning selection module (HPSM), (4) HP module, (5) query rewriting module, (6) BJI selection module, and (7) indexing module. The metabase querying module is a very important module that allows the tool to work with any type of DBMS. From a type of DBMS, user name, and password, the module allows connection to that account and collection of some information from the metabase. This information concerns logical and physical levels of the data warehouse. Information of the logical level includes tables and attributes in these tables. Information of the physical level includes optimization techniques used and a set of statistics on tables and attributes of the data warehouse (number of tuples, cardinality, etc.). The managing queries module helps the administrator to define the workload of queries (W) on which the selection is based. The module allows manual editing of a query or import from external files. It may also manage the workload, giving the possibility to add, delete, or update queries. This module integrates a parser that identifies syntax errors as well as tables and attributes used by each query. HPSM requires as inputs a schema of data warehouse, a workload, and a threshold B. Using these data, HPSM selects a partitioning schema (PS) to minimize the cost of the workload and to generate a number of fragments not exceeding B. Our tool supports three selection algorithms: genetic algorithm [38, 39], simulated annealing algorithm, and hill climbing algorithm (see previous sections). The HP module fragments physically the data warehouse using partitioning schema obtained from HPSM. From the partitioning schema, this module determines the dimension table(s) to partition by horizontal primary partitioning and the attributes used to perform this fragmentation. The module is also used to partition the fact table by horizontal derived partitioning mode using fragments of dimension tables. The query rewriting module rewrites queries on a fragmented and/or indexed schema. It starts with identifying valid fragments for each query, rewriting the query on each of these fragments, and finally performing union of the obtained results. The BJI selection module selects a configuration of BJI under constraint storage.

FIGURE 25.23. Architecture of SimulPh.D.

FIGURE 25.24. Connection with target DBMS.

This selection can be made on a partitioned or unpartitioned data warehouse. The indexing module generates scripts to create the selected BJI on the data warehouse.

25.8.2   SimulPh.D Features

The main features of SimulPh.D are

1. Displaying the current state of the database (the schema, attributes, size of each table, definition of each attribute, etc.) and the workload (description of queries, number of selection operations, selection predicates, etc.). Figures 25.24 and 25.25 show the connection of SimulPh.D with the target DBMS and the displaying information interface, respectively.
2. Offering personalized or nonpersonalized partitioning of the data warehouse. If the administrator chooses nonpersonalized partitioning (zero administration), SimulPh.D selects a partitioning schema in a transparent manner without designer intervention (this mode is well adapted when the administrator wants an autoadministration of his or her database). In the personalized partitioning, the administrator chooses candidate dimension tables, candidate attributes, and selection algorithms and sets different parameters that he or she considers important. In Figure 25.26, the administrator chooses a personalized administration, where three dimension tables participate in the partitioning process (ChanLevel, ProdLevel, and TimeLevel) and only table Custlevel is not a candidate for partitioning. Among the 10 attributes, the administrator has chosen two attributes of the table ProdLevel, two attributes of the table TimeLevel, and one attribute of the table ChanLevel. Figure 25.27 shows the partitioned dimension tables and the fragmentation attributes.

   

   FIGURE 25.25. Visualization of data warehouse state.

   

   FIGURE 25.26. Personnalized administration.

   

   FIGURE 25.27. Partitioning recommendations.

   

   FIGURE 25.28. (a) Combined selection (HP&BJI) and (b) indexing recommendations.

3. Indexing the data warehouse using two modes: isolated and combined with HP (HP & BJI). In the first mode, the DWA must choose the candidate indexable attributes and storage space S. The BJI selection module supports two selection algorithms, a greedy algorithm, and a data mining-based algorithm. SimulPh.D generates a recommendation that provides some information: BJI selected, cost reduction, indexed tables and attributes, storage cost, and so on (see Fig. 25.28b). In the second mode, the SimulPh.D tool automatically chooses the candidate indexed attributes among the selection attributes with low cardinality not used to partition the data warehouse and that are referenced in no profitable queries. Figure 25.28a shows the HP&BJI interface. For example, attributes Month_level and All_level are not used in BJI selection because they are used to partition the data warehouse.
4. Improving iteratively the selected partitioning and/or indexing schema based on the proposed recommendation based on feedback. SimulPh.D displays the quality of the final partitioning or indexing schema. This quality is based on a cost model estimating the number of inputs outputs required for executing each query [14]. Therefore, if some queries do not benefit from the suggested partitioning schema, the administrator can refine some parameters in order to satisfy them. Figure 25.27 shows an example of recommendations concerning partitioned dimension tables. For example, the tables Custlevel and ProdLevel should not be fragmented, when table TimeLevel is fragmented on seven fragments using the attribute Month_level. Attributes Class_level, Line_level, Division_level, Year_level, and Retailer_level are not used to partition the data warehouse. Therefore, they can be used to index the fragmented data warehouse using HP & BJI approach (see Fig. 25.28a).
5. Generating scripts for primary and derived HP and BJI. They can be directly executed on the data warehouse to partition and/or index it physically, in the case where the administrator is satisfied with the suggested recommendations.

25.9   CONCLUSION AND PERSPECTIVES

Horizontal data partitioning is considered as a precondition for distributed and parallel database design. It has been largely studied by the academic community in the last decades and has recently been massively advocated by most commercial database systems (Oracle, SQL Server, IBM DB2, MySQL, and PostgreSQL), where they offer native DDL support for defining horizontal partitions of a table using several modes. This adoption has been motivated by business intelligence applications. In this chapter, we showed the spectacular evolution of HP on commercial systems, especially in Oracle, which proposes a large variety of partitioning modes of fragmenting a single table using either primary partitioning or referential partitioning. A complete state of the art concerning the different fragmentation algorithms in classical database systems is presented. A classification of these algorithms is presented with a criticism of each approach. Based on this study, a formalization of the referential HP problem in relational data warehouses is presented. We derive the complexity of the problem of selecting an optimal partitioning schema and we study its hardness. To the best of our knowledge, we are the first to study in detail this complexity. In order to select a near-optimal solution, we proposed two algorithms: hill climbing and simulated annealing with various variants. The main characteristic of these algorithms is that they partition simultaneously dimension and fact tables. We presented in this chapter a new interest of HP in physical design. It can be used to prune the search space of BJI. We presented a combined selection approach of HP and BJI (HP&BJI) exploiting the similarities we have identified between these two techniques. Intensive experimental studies have been presented using data sets of the APB 1 benchmark and Oracle11g. The different results show the important role of HP in reducing query processing cost and in pruning the search space of the BJI selection problem. Based on the obtained results, some recommendations are given to help administrators in choosing their favorite algorithm. We identify the need for the development of simulators during the physical design and then we propose a simulator tool, called SimulPh.D, to assist administrators during physical design. It gives recommendations for each workload and the quality of the generated partitioning and/or indexing schemes. Administrators have the possibility to tune algorithms and their parameters to get the best solutions. We are currently working on the deployment of our algorithms on data partitioning Teradata. The initial results are encouraging [40].

REFERENCES

[1] S. Papadomanolakis and A. Ailamaki, “Autopart: Automating schema design for large scientific databases using data partitioning,” in Proceedings of the 16th International onference on Scientific and Statistical Database Management (SSDBM 2004), pp. 383‒392, June 2004.

[2] H. Lei and K.A. Ross, “Faster joins using join indices,” VLDB Journal, 8(1): 1‒24, 1999.

[3] L. Bellatreche, R. Missaoui, H. Necir, and H. Drias, “A data mining approach for selecting bitmap join indices,” Journal of Computing Science and Engineering, 2(1): 206‒223, 2008.

[4] M.T.özsu and P. Valduriez, Principles of Distributed Database Systems: Second Edition. Prentice Hall, 1999.

[5] D. Sacc à and G. Wiederhold, “Database partitioning in a cluster of processors,” ACM Transactions on Database Systems, 10(1): 29‒56, 1985.

[6] L. Bellatreche, A. Cuzzocrea, and S. Benkrid, “Query optimization over parallel relational data warehouses in distributed environments by simultaneous fragmentation and allocation,” in The 10th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP), pp. 124‒135, Busan Korea, May 2010.

[7] G. Eadon, E.I. Chong, S. Shankar, A. Raghavan, J. Srinivasan, and S. Das, “Supporting table partitioning by reference in Oracle,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 1111‒1122, 2008.

[8] A. Sanjay, V.R. Narasayya, and B. Yang, “Integrating vertical and horizontal partitioning into automated physical database design,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 359‒370, June 2004.

[9] K. Tzoumas, A. Deshpande, and C.S. Jensen, “Sharing-aware horizontal partitioning for exploiting correlations during query processing,” PVLDB, 3(1): 542‒553, 2010.

[10] A. Sanjay, C. Surajit, and V.R. Narasayya, “Automated selection of materialized views and indexes in Microsoft SQL Server,” in Proceedings of the International Conference on Very Large Databases, pp. 496‒505, September 2000.

[11] T. Stöhr, H.Märtens, and E. Rahm, “Multi-dimensional database allocation for parallel data warehouses,” in Proceedings of the International Conference on Very Large Databases, pp. 273‒284, 2000.

[12] S. Ceri, M. Negri, and G. Pelagatti, “Horizontal data partitioning in database design,” in Proceedings of the ACM SIGMOD International Conference on Management of Data.SIGPLAN Notices, pp. 128‒136, 1982.

[13] Oracle Corporation, “Partitioning with Oracle Database 11g Release 2,” An Oracle White Paper, 2010. Available at http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-partitioning-11gr2-2010-10-189137.pdf.

[14] L. Bellatreche, K. Boukhalfa, and P. Richard, “Horizontal partitioning in data warehouses: Hardness study, heuristics and Oracle validation,” in International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2008), pp. 87‒96, 2008.

[15] S.B. Navathe and M. Ra, “Vertical partitioning for database design: A graphical algorithm,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 440‒450, 1989.

[16] K. Karlapalem, S.B. Navathe, and M. Ammar, “Optimal redesign policies to support dynamic processing of applications on a distributed database system,” Information Systems, 21(4): 353‒367, 1996.

[17] H. Mahboubi and J. Darmont, “Enhancing XML data warehouse query performance by fragmentation,” in Proceedings of the 2009 ACM Symposium on Applied Computing (SAC), pp. 1555‒1562, 2009.

[18] S. Dimov, D. Pham, and C. Nguyen, “An incremental K-means algorithm,” Journal of Mechanical Engineering Science, 218(7): 783‒795, 2004.

[19] L. Bellatreche, K. Karlapalem, and A. Simonet, “Algorithms and support for horizontal class partitioning in object-oriented databases,” Distributed and Parallel Databases Journal, 8(2): 155‒179, 2000.

[20] L. Bellatreche, K. Boukhalfa, and M.K. Mohania, “Pruning search space of physical database design,” in International Conference on Database and Expert Systems Applications (DEXA '07), pp. 479‒488, 2007.

[21] International Business Machines Corporation, “DB2 partitioning features, an overview for data warehouses,” 2006. Available at http://www.ibm.com/developerworks/data/ library/techarticle/dm-0608mcinerney/.

[22] Microsoft Corporation, “Partitioned tables and indexes in SQL server 2005,” 2005. Available at http://msdn.microsoft.com/en-us/library/ms345146.aspx.

[23] PostgresSQL, “Partitioning,” Available at http://www.postgresql.org/docs/8.1/static/ddl-partitioning.html.

[24] MySQL, “Partition types,” Available at http://dev.mysql.com/doc/refman/5.1/en/ partitioning-types.htm.

[25] M.C. Er, “A fast algorithm for generating set partitions,” The Computer Journal, 31(3): 283‒284, 1988.

[26] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman & Co., 1990.

[27] Y. Ioannidis and Y. Kang, “Randomized algorithms for optimizing large join queries,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 9‒22, 1990.

[28] G. Das, D. Gunopulos, N. Koudas, and D. Tsirogiannis, “Answering top-k queries using views,” in Proceedings of the International Conference on Very Large Databases, pp. 451‒462, 2006.

[29] L. Breslau, P. Cue, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web caching and Zipf-like distributions: Evidence and implications,” in In INFOCOM, pp. 126‒134, 1999.

[30] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, “Optimization by simulated annealing,” Science, 220(4598): 671‒680, 1983.

[31] L. Bellatreche and K. Boukhalfa, “Yet another algorithms for selecting bitmap join indexes,” in 12th International Conference on Data Warehousing and Knowledge Discovery (DaWaK), pp. 105‒116, 2010.

[32] K. Aouiche, O. Boussaid, and F. Bentayeb, “Automatic selection of bitmap join indexes in data warehouses,” 7th International Conference on Data Warehousing and Knowledge Discovery (DAWAK '05), pp. 64‒73, August 2005.

[33] R. Bouchakri and L. Bellatreche, “On simplifying integrated physical database design,” in 15th East European Conference on Advances in Databases and Information Systems (ADBIS '2011), pp. 333‒346, September 2011.

[34] K. Boukhalfa, L. Bellatreche, and Z. Alimazighi, “HP&BJI: A combined selection of data partitioning and join indexes for improving olap performance,” Annals of Information Systems, Special Issue on New Trends in Data Warehousing and Data Analysis, Springer, 3: 179‒2001, 2008.

[35] OLAP Council, Apb-1 OLAP Benchmark, Release II.1998. Available at http://www.olapcouncil.org/research/bmarkly.htm.

[36] M. Cristina, D. Debabrata, A. Ioannis, A. Anastasia, and H. Thomas, “PARINDA: An interactive physical designer for PostgreSQL,” in Proceedings of the 13th International Conference on Extending Database Technology (EDBT), pp. 701‒704, New York: ACM, 2010.

[37] L. Bellatreche, K. Boukhalfa, and Z. Alimazighi, “SimulPh.D.A physical design simulator tool,” in 20th International Conference on Database and Expert Systems Applications (DEXA '09), pp. 263‒270, 2009.

[38] L. Bellatreche and K. Boukhalfa, “An evolutionary approach to schema partitioning selection in a data warehouse environment,” in Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DAWAK 2005), pp. 115‒125, August 2005.

[39] J.H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975.

[40] L. Bellatreche, S. Benkrid, A. Ghazal, A. Crolotte, and A. Cuzzocrea, “Verification of partitioning & allocation techniques on teradata dbms,” in The 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2011), pp. 158‒169, Melbourne, Australia, October 2011.

 

¹http://www.dbms2.com/2009/04/30/ebays-two-enormous-data-warehouses/.