In this paper we introduce the objective function for vertical partitioning in database systems. It has been built with the new evaluative criterion: cache hit probability. Testing the validity of the derived evaluative formula via program simulation shows its high accuracy. Index terms: vertical partitioning, objective function, evaluation criterion, cache hit probability.
Vertical partitioning of a table splits it into two or more tables (which we refer to sub-tables), each of which contains a disjoint subset of the attributes of the original table, except for the key attributes. Since a subset of attributes is more frequently accessed by transactions than the subset of the rest attributes, so vertical partitioning can reduce the amount of data that needs to be scanned to answer the transactions.
As indicated in [1], many data partitioning algorithms have been developed basing on statistical and pattern classification and analysis. They cluster data using various criteria. The most common used criterion is the square-error. The lack of these algorithms is that they don’t estimate the “goodness” of partition schemes in the relation with an index of system performance. In [2], authors develop the complex method, in which they first create a set of “candidate” partition schemes, and then analyze each of them via optimization unit of database system to find the best scheme. The work is of great interested, but it is too complicated. On the other hand the performance of optimization unit strongly depends on the current tuning of database system.
In this paper we will build the objective function for vertical partitioning with the evaluative criterion: the cache hit probability. As many algorithms in this area we use an attribute usage matrix (AUM) as the input data. We will consider that number of sub-relations equaling to two, and both of them being located in the same site.
and database system
Let’s consider a table T in a database system. Tuples of T have M attributes, and cache memory for its caching is limited to L bytes.
Assume that each transaction queries a subset of attributes of a tuple by its record number in the table. It means that a transaction is a sequence of three operations: select table, select a subset of attributes and select a tuple by record number in table. Then a transaction can be defined as a triplet (T, Δ j , ID j ), where, T – table name, Δ j – the sub-set of query attributes, ID j – the query record number. Assume that these selects are independent between one and the others, and the select of record number obeys uniform law. Let us have Q different transactions and there attribute usage is described in table 1:
Tr1 Tr2 … TrQ
A1 u11 u21 … uQ1
A2 u12 u22 … uQ2 … … … … …
AM u1M u2M … where uij equals either pi or 0, and pi is the execution probability of transaction Tri. Thus the following expressions are the case: p1 + p2 + K + pQ = 1 , 0 ≤ pi ≤ 1, 1 ≤ i ≤ Q .
Cache is divided into parts, each of which contains tuples of one table. Write to cache and read from it are executed per tuple. A tuple is loaded into cache if at least one of its attribute is claimed. At first time cache is empty. In operation it is filled with tuples. For the current transaction if copy of the query tuple is in cache, then it is fetched from cache to answer the query. Otherwise it is fetched from disk and its copy is inserted into cache. In the first case we say that it was a cache hit, in the last case – a cache miss. After cache having been filled, a new tuple will substitute one among the present tuples. We will consider that the cache replacement strategy being randomized. Since the period, while cache hasn’t been filled yet, is a transitional period, we can derive the objective function, having skipped this period.
The assumptions, are described in this section, has been made as a result of deductive analysis the literature [1], [2], [3], [4]. Note that these assumptions, except for the attribute usage matrix, are only for the purpose of mathematical deriving and validity testing of the estimated formula, but not for implemented areas of the derived objective function.
In this and in the following sections we will consider the vertical partitioning of table T into two sub-tables T1, T2. Attribute sets of tables T, T1, T2 are S, S1, S2 correspondingly. These following expressions are the case:
S1 ∪ S 2 = S , S1 ∩ S 2 = SKT ,
S1 > SKT ,
S 2 ≥ SKT , where, SKT – the sub-set, containing all key attribute of table T.
Then the table T is replaced with two sub-tables T1, T2. Using method simulating the vertical partitioning [2], we create regular tables, one for each sub-table. The queries referencing the original table T, is rewritten to execute against the sub-tables T1, T2. If assume that any query contains at least one of non-key attributes, then a query (T, Δ j , ID j ) is replaced only in one of three variants: • • • attributes are in S1, i.e. (Δ j ⊂ S1 ); 1-st variant: by one query, referencing subtable T1, (T1, Δ j , ID j ) , if all the query attributes are in S2, i.e. (Δ j ⊂ S ) 2 ; 2-nd variant: by one query, referencing subtable T2, (T2 , Δ j , ID j ) , if all the query 3-rd variant: (T1, Δ j ∩ S1 , ID j )and (T2 , Δ j ∩ (S 2 \ SKT ), ID j ) simultaneously in the rest cases, i.e.
((Δj ∩ S1) ≠ ∅)∧ ((Δj ∩ S2 ) ⊄ SKT ).
by two queries
The cache allocated for caching the table T is now divided into two parts for caching its sub-tables. Sizes of these parts are the parameters for partitioning algorithm.
In this section we will derive the objective function, which estimate the cache hit probability for caching the original table and its sub-tables. The cache system and database system have been specified in section 2. The method implementing the vertical partitioning was described in section 3.
The following are used in derivation of the objective function.
N – the tuple count of table T as well as T1 and T2. M – the attribute count of tuples of table T. li – length of attribute i of table T for i = 1, 2, …, M. lT, lT1, lT2 – tuple length of table T, T1, T2.
L, L1, L2 – size of part of cache memory, allocated for caching table T, T1, T2. L1, L2 – the parameters, which satisfy the restriction (L1 + L2 ≤ L).
K, K1, K2 – number of tuples of table T, T1, T2, which can exist in the corresponding part of cache memory at the same time.
Operation [ ] – operation achieving the integer part of a fraction.
In this case any transaction queries a tuple of table T, which may be one among K tuples, copy of which has already existed in cache, or may be one among the rest (N – K) tuples, which have not any copies in cache. If the first occurrence is the case, finding of query tuple in cache will successfully finish, i.e. it will be a cache hit. Since the select of tuples obeys the uniform law, the cache hit probability is estimated by expression: K
(
N where, K = min⎛⎜⎜ N , ⎡⎢ L ⎤⎥ ⎞⎟⎟ = min⎜⎛⎜ N , ⎢⎡⎢ L ⎥⎤⎥ ⎟⎞⎟ .
⎝ ⎣ lT ⎦ ⎠ ⎜⎜⎝ ⎢⎢⎣ ∀r:∑Ar∈lrS ⎥⎥⎦ ⎟⎟⎠
Let’s mark the occurrence, when the original query is replaced in the first, the second, the third variant, the event C1, C2, C3; the occurrence, when the finding of query tuple in cache finishes successfully, the event B. According to formula of complete probability, cache hit probability is estimated by expression:
3 PT1T2 = ∑ ( p(B / Ci )⋅ p(Ci ))
i=1 For i = 1: p(C1 ) =
∑ ∀j:Δ j ⊂S1
p j ;
since the query (T, Δ j , ID j ) is replaced by the
query (T1, Δ j , ID j ) , then the cache accessing
for the original query is successful, if and only
if the cache accessing for the substituting query
is successful. Similarly to (
N with
K1 = min⎜⎜⎝⎛ N , ⎢⎣⎡ lLT11 ⎦⎤⎥ ⎠⎟⎞⎟ = min⎜⎜⎜⎜⎝⎛ N , ⎢⎢⎢⎡⎢⎣ ∀r:L∑Ar1∈lSr1 ⎥⎥⎥⎥⎦⎤ ⎟⎟⎟⎟⎠⎞ .
For i = 2: in the same way we can achieve p(C2 ) = ∑ p j ;
∀j:Δ j ⊂S2 p(B / C2 ) = K 2
N with
K 2 = min⎜⎜⎛⎝ N , ⎢⎡⎣ lLT22 ⎤⎥⎦ ⎟⎞⎟⎠ = min⎜⎜⎜⎜⎛⎝ N , ⎢⎢⎢⎡⎢⎣ ∀r:LA∑r2∈lSr2 ⎥⎥⎥⎤⎥⎦ ⎟⎟⎟⎟⎞⎠ .
For i = 3: query (T2 , Δ j ∩ (S 2 \ SKT ), ID j ),
(T1, Δ j ∩ S1 , ID j ) p(C3 ) = 1− p(C1 )− p(C2 ) ; since the query (T, Δ j , ID j ) is replaced by and then query cache accessing for the original query is successful, if and only if the cache accessing for both of the substituting queries are successful.
p(B / C3 ) = p(BT1 )⋅ p(BT 2 ) = K1 ⋅ K 2
N N p(B / C3 ) = K1 ⋅ K 2 .
N 2
PT1T2 = KN1 ⋅ p(C1 )+ KN2 ⋅ p(C2)+ K1N⋅ 2K 2 ⋅ p(C3 ) (
a = p(C1) ;
N
Formula (
N
c =
p(C3 )
N 2
PT1T2 = a ⋅ K1 + b ⋅ K2 + c ⋅ K1 ⋅ K2
(
Notice: if S2 = SKR, then p(C2) = p(C3) = 0. In this
case the partition is not the case. So the cache memory
allocated for table T is completely assigned to table T1.
As a result of (
For a table T, a usage matrix of its attributes, lengths of
its attributes and limited to L (bytes) cache memory,
allocated for its caching, the best scheme of partitions is
defined as the result of the programming problem (*):
P(S1, K1, K2 ) = a ⋅ K1 + b ⋅ K2 + c ⋅ K1 ⋅ K2 → max (
SKT ⊂ S1 , S1 ⊆ S , K1 ⋅ lT1 + K 2 ⋅ lT 2 ≤ L ,
K1 , K 2 are the integers (8)
Since the estimated formula is easy for computation, the programming problem (*) can be solved via full search algorithm for input data with small dimensionality. For large dimensionality it’s necessary that the more effective algorithm have been developed.
Validity testing of the derived estimated formula has been carried out via program simulation. The program has been written in Delphi. It uses the exhausted search algorithm to solve the programming problem (*). It allows simulating the performance of cache system and database system, which have been defined in section 2. It also allows registering the cache hit rate. Using the program, we have carried out a number of experiments with randomized data input. For all that we randomized the value of M and Q in interval [5..10]. The relative error in all these experiments is less than 2.5%. This confirms the high accuracy of derived formula.
For example let’s consider the table T with 6 attributes, where A1 is key attribute. Lengths of attributes are 30, 37, 51, 21, 46, 11 (bytes). The attribute usage matrix is defined in table 2.
\Attrs
Tr1 Tr2 Tr3 Tr4 Tr5
A1 .194 .089 .281 .157 .279
A2
The cache size is 2000 (bytes), and the tuple count is 200 (tuples).
For this example the best scheme of partitions is
S1 = { A1 , A2 , A5 , A6 }, S2 = { A1 , A3 , A4 } , and cache lengths for T1, T2 are
K1 = 16,
K 2 = 0 .
With this scheme the cache hit probability is 0.0649, and it has increased to 1.27 (times) according to non-partitioning case.
Simulation has been carried out with 10000 runthroughs, in each of which has been executed 5000 queries. Result gives the average value of cache hit rate equaling to 0.065. In this paper we have derived the objective function for vertical partitioning with a new estimated criterion: cache hit probability. We also have carried out validity testing of the achieved formula via program simulation. The simplicity of the achieved formula and its high accuracy confirm the availability of its using in database design and database reconstruction to achieve the significant enhancement of system performance.
We are currently developing a heuristic algorithm for solving the programming problem (*). We will discuss it in future work.