T-plotter: A new data structure to reconcile OLAP and OLTP models

Abstract

Classical databases represent the traditional DBMS’s and the most widely used DBMS in the world of databases and information systems; they have been regarded as the best systems for managing data. Today with the growth of data for both applications and consumers, and its openness to the public, traditional databases are not able to meet the needs of a large number of applications, including Online Analytical Processing models: OLAP data processing and Business Intelligence analysis. As a result, many dedicated DBMS have emerged like: Column Store, In Memory and NoSQL databases. They meet users’ expectations and fit well with current needs. Consequently, the scope of classical databases has become increasingly restricted to handle Online Transaction Processing OLTP models and small problems. However, those dedicated solutions hardly cope with rich features of DBMS like simplicity, flexibility or scalability. They remain limited to mainly process single database models, and users cannot deal with both OLTP and OLAP queries in a single environment. To deal with this problem, vertical fragmentation is the best way to effectively handle the OLAP model, but this technique fails to handle some analytical queries with low selectivity, presenting poor results in some cases. In this perspective, we propose a new vertical fragmentation design T-Plotter which makes it possible to deal effectively with the whole of analytical queries and improve the performance of DBMS’s to process the OLAP data models.

Keywords

OLAP databases OLTP databases vertical fragmentation physical design TPCH benchmark

1. Introduction

In the last two decades, the amount of information and volume of data have literally exploded, with this growth, the traditional databases are faced with performance problems related to their physical data structures and techniques used for optimization that are sometimes unsuited to their needs for analysis and decision-making purposes, heavy interrogations, aggregation and joins become complex, difficult to execute or even impossible to solve with the traditional systems, especially when executing OLAP-type queries (Online Analytical Processing), on large masses of data tables oversize with hundreds of columns, and billions of rows [18].

Traditional physical designs used in Row-Store databases put a real challenge to designers. In fact, storing a huge table in one physical structure rises efficiency issues in query processing [4, 9]. New trends to distributed architectures, in memory databases and column-oriented architectures [2] have emerged and have fixed this problem, and have found their place in the world of databases even for business issues like C-Store, MonetDB [23], and Vertica, etc., but in another hand, they are also known to present bad results for processing OLTP models [3, 16, 17] (Online Transaction Processing).

Nevertheless, traditional solutions remain competitive in the market, particularly due to the need for OLTP models and requests. Indeed, the exchange of data, updates and interactions with the database remain paramount in the definition of an information system, and the OLTP model still widely used in the field of information computing.

In this work, we are interested in providing a solution that deals with both the performance of classical databases to better process OLAP and OLTP models, and also able to rebuild them efficiently by taking advantage of the properties inherent in data storage. Thus, without having to go through materialized views, heavy tuple reconstructions or multiple index updates, we bring a solution capable of responding both models.

This approach provides a solution dedicated to information systems, without changing the data model, optimizing data storage by losing consistency, and consequently rewriting queries.

The main contributions of our approach can be summarized in:

•
A data management approach that reconciles both OLTP and OLAP models under a same environment,
•
A new high-level data structure named T-Plotter facilitating data reconstruction and indexed access to multiple different structures,
•
A formal cost model for query rewriting integrated to an elegant framework optimized taking advantage of the flexibility of T-Plotter.

This paper is organized as follows. First section talks about the vertical fragmentation on classical databases in order to position our solution, the second section develops the T-Plotter architecture, and third section explains and details the implementation of our approach and its functioning in the database. Implementation and testing are presented in the fourth section. Finally, we will conclude with a conclusion and future works.
2. Literature review

Vertical fragmentation is a technique used to perform the OLAP model efficiently in centralized or distributed architectures, and queries that invoke some columns from the table. As mentioned OLAP queries are complex and require aggregate operations, and generally needs to full scan only few columns of the table, so the vertical fragmentation technique helps to work on a set of columns [11], instead of invoking the whole table with the classical DBMS, and this naïve way of processing has a bad impact on time of query processing, especially on large tables or big data.

The vertical fragmentation has the advantage of processing efficiently the analytical queries on voluminous tables, but after experiments, this technique fails to process some type of queries, due to the tuple reconstruction operation, this operation does consume a lot of time processing of the CPU and I/O operations to disk [9]. Our challenge is to optimize and reduce this processing time, so that the vertical fragmentation gives better results to the whole queries in a centralized architecture context.

Vertical fragmentation has been widely studied, and it can solve a lot of problems that the designers and users of databases face but rarely proposed by classical database designers [11, 17], especially when they switch from OLTP to the OLTP/OLAP model, due to the needs of companies for the analytical and Data Mining requirements. Since the vertical fragmentation technique was forgotten, our motivation is to bring a solution and help to promote and revive the vertical fragmentation technique, so it will be generalized and more used in the world of DBMS and help to fill some gaps.

2.1 Vertical fragmentation implementation

In this section we will discuss several different techniques that can be used to implement a vertical fragmentation [4] on a classical DBMS. There exists three main ways to perform this goal: a fully vertically partitioned design, an index-based design, and materialized views.

Fully vertically partitioned design.

The simplest way to implement vertical fragmentation on a classical DBMS is to partition relationship vertically into sub-tables, each sub-table must be composed of at least one attribute of the fragmented relation. A mechanism must reconstruct the fields of the same rank in the correct order. To do so, the simplest method is to add a rank attribute to each vertical fragment indicating the position, which is often preferable to consider as the primary key because original primary keys can be large and sometimes composite. This solution provides a good way to minimize resources allocation or access for each attribute. Moreover it can be distributed quite easily. However, this solution brings a strong drawback with tuple reconstruction or evolution of fragmentation since this approach physically stores fragmented relations. The re-fragmentation of those relations can be costly.

Index-based plans.

The idea is to create a B-Tree index for each vertical fragment of the table, so that for any query of a given attribute the compiler must go through the index, reducing access time to attributes of the fragment. Although this approach is interesting from a theoretical point of view, it poses some practical problems. First, the row attribute is required for each column to allow the initial table to be rebuilt, which increases the storage space and will have a negative impact on the index path. Also the indexes do not store the values of the attributes, which implies for each predicate or access to an attribute by index we will have an additional cost to access the index and to access the value of the attribute, this approach requires the analysis of the index to extract the values, which can be slower than the path of a stacked table (as would happen in the sub table approach). And finally, rebuilding tuples requires a join on the indexes of the relevant attributes, and it has been noticed that this operation is very expensive compared to an ordinary join between sub-tables. This approach can be interesting in order to avoid huge computations on the underlying fragments and simplify modifications. However it adds a heavy cost on space consumption and time processing for tuple reconstruction in some cases.

Materialized views.

The third approach is based on materialized views. We create an optimal set of materialized views for each type of query in the workload. The optimal materialized view can be defined by a materialized view with only the relevant columns that respond to a set query of the same type, which requires a workload analysis and a ranking of queries into several categories. The goal is to reduce disk access, avoiding the impact of the cost of storing a column positions for reconstruction, by the way reducing the storage of tuple headers, a single header per tuple per view. But this requires that the query workload must be known in advance, making this strategy interesting only in limited situations. The other disadvantage is that each materialized view is suited for one query or some queries, so if in our system we have a large number of queries, we will need many materialized views, which saturates the storage space and especially for masses of large data, and requires a lot of operations to maintain a simple update or insertion, and finally if, unfortunately, a new query requires a join between two views, we can expect a great fail of performance. However, it hardly scales up since it requires a huge amount of space and update issues.

Abadi et al. [4] concluded from those approaches that the best compromise for efficiency and feasibility to simulate vertical fragmentation is the fully vertically partitioned method, which seems to be the least costly way in terms of disk storage and the fastest way in terms of query processing. In the following, we will study the way to generate automatically vertical fragments.

2.2 Vertical fragmentation optimization

Complementary to the implementation of Vertical Fragmentation, several strategies try to optimize this problem [8]. The optimization issue of Vertical Fragmentation resides in the combination of attributes that compose underlying tables. The vertical fragmentation optimization is an NP-complete problem [12]; this is due to the huge number of possible alternatives to resolve the problem. For example, with a table composed of m attributes, the number of alternatives obtained is calculated by Eq. (1) (the Bell number):

$\displaystyle B(m+1)=\sum_{k=0}^{n}C_{n}^{k}B_{k}$ (1)

For large values of m, we calculate the number thanks to Eq. (2):

$\displaystyle(m\gg 0)=m^{m}$ (2)

Following values allow us to have an idea about the vastness of the Bell number.

Table 1

Bell numbers

${m}$	5	10	15	22	50
$B(m)$	52	115,975	$1.38\times 10^{9}$	$4.50\times 10^{15}$	$50\times 10^{48}$

So for a relation with 15 columns we have $1.38\times 10^{9}$ , which raises a huge problem of choice of the best plan, to deal with that we have studied different algorithms, and proposed our algorithm to resolve this NP-Problem. Thus, vertical fragmentation on databases has been subject to several studies which can be classified into three categories.

Algorithms based on data mining.

Some works try to extract knowledge, valid and exploitable information from divert data sources, these are algorithms that generate attribute groups based on the methods of data mining [5, 10, 11, 19]. Data mining algorithms narrows the scope of vertical fragmentation to knowledge extraction, consequently those structures cannot deal with updates and new end-user requirements change the structure.

Algorithms based on the cost model.

Those solutions evaluate each fragmentation scheme with a cost model formula that estimates the response time of queries and applications running on the database, genetic algorithms use the cost model as a fitness function [10, 12, 15, 19]. Due to the NP-complete issue, this solution is not scalable and needs a heuristic to reduce the scope of research of a relevant fragmentation.

Algorithms based on affinity.

This class of algorithms calculate the affinity between attributes and regroup the most attributes with high affinity in the same fragment, several authors have studied this approach [13, 15, 16]. Our work relies on the Affiner [8] algorithm which proposes the analysis and evaluation of the affinity between each attribute and the combination of high affinity attributes. The Affiner algorithm seems well respond to the resolution of the problem of Vertical Fragmentation; as perspective this algorithm can be compared with other algorithms based on affinities and tested on distributed databases or even adapted on other models of physical design techniques, such as horizontal fragmentation. Algorithms based on affinity seems to be a good compromise for vertical fragmentation, since its concepts remain close to end-user needs, allow updates. However, this approach must face with the tuple reconstruction issue.

Discussion.

Theses solutions give interesting propositions to implement the vertical fragmentation, but based on the study of [8] vertical fragmentation is limited to optimally process some kind of queries but fails in processing other set of queries. Consequently, vertical fragmentation will only make sense if we find the right and easy solution to apply it on classical databases and obtain good results on all different types of queries, same like horizontal fragmentation. This has motivated us to continue in this way and contribute to providing a suitable architecture for the Vertical Fragmentation on classical databases, a solution for both OLTP model and OLAP model or OL*P-like systems, so we propose a new design T-Plotter.

3. T-plotter, the new vertical fragmentation design

T-Plotter is the abbreviation of tuple plotter; that reflects the notion of indexing tuple multiple on separate fragments, that helps to reconstruct tuples stored in separate fragment, this solution meets the needs of OLAP databases and OLAP-oriented queries, applicable on a vertically fragmented architecture, this technique that can be applied not only for classical databases but can be applied on different physical design databases.

3.1 T-plotter concept

Our approach consists in adding a layer on a vertically fragmented table, for each fragment (sub-table) we add a column with attribute number referring to the record number tuple_id allowing reconstruction of tuple by using the natural join operation on the match of tuple_id, where tuple_id reflect the rank of the tuple in the logical table.

T-Plotter ensure the possibility of fast access to the data of the different fragments sorted in same or different order, which considerably reduces the cost of queries execution, unlike a classic reconstruction which is very expensive in terms of CPU processing and number of inputs outputs, but with our approach, just browse T-Plotter according to the list of the relevant tuple_id, is sufficient to obtain the data directly stored on several fragments, and the operation of reconstruction of tuples is finished, with no join operation, or access with other indexes.

3.2 T-plotter architecture

Our approach consists in adding a layer on a vertically fragmented table, for each fragment (sub-table) we add a column number referring to the record number tuple_id allowing reconstruction of tuple by using the natural join operation on the match of tuple_id, where tuple_id reflects the rank of the tuple in the logical table.

These advantages ensure the possibility of fast access based on the tuple_id to the data of the different fragments sorted in different orders, which considerably reduces the cost of executing queries, and for huge amount of data responding to query result that cannot be held in memory, Requires a path of several indexes to recover the data based on the fragment and grace hash join or sort join to tables, heap files and even more like distributed sources (through drivers), etc. reconstruct the final result, which is very expensive in terms of CPU processing and number of inputs outputs, but with our approach, just browse T-Plotter according to the list of the relevant tuple_id, is enough, and we obtain the data directly stored on several fragments, and the operation of reconstruction is finished.

T-Plotter is a flexible and dynamic technique, it can be applied to different kinds of physical designs. Moreover, T-Plotter does not restrict access to attributes physically stored separately, since the @V attributes of T-Plotter allow referencing different storage structures, which we quote materialized views, tables, fragments stored on a distributed structure, C-Store projections. This interesting extension opens the perspectives to other implementations and other applications, and does not reduce their application to dedicated structures, we believe that this face will promote this technique and will facilitate the integration of T-Plotter to different DBMS.

Those fragments are generally sub-tables from a given table; however, we can imagine a composition between fragments of various tables, sources, and types.

To deeply understand the T-Plotter we will explain how T-Plotter is structured, how it can be used to reconstruct tuples on-demand, and how to query data on it.

Figure 1.

T-plotter data structure.

3.3 T-plotter structure

The structure of T-Plotter is represented in Fig. 1. T-Plotter is a data structure whose purpose is to link the different data sources, and to reconstruct rows or tuples from required data sources. The physical structure of T-Plotter is presented as follows: it is a table made up of several attributes (tuple_id, @1, @2… @n); where the tuple_id attribute represents the record rank in the fragment and matches its original rank in the table before its fragmentation. The @V attributes represent pointer attributes on physical addresses often called ROWID, which allows direct and fastest access to an attribute on the desired fragment, in the same way as an index access.

T-Plotter presents several advantages:

•
Accessing to data on demand. It allows late materialization and data compression.
•
Every fragment is independent from each other’s. Specific physical organizations can be defined for each fragment and thus optimization treatments on it (ordered, hashed, super-columns, etc.).
•
Result obtained by accessing T-Plotter represents directly a reconstructed tuple.

The ROWID is a specific data structure that stores a logical pointer on a tuple position in a data file. It allows the database accessing directly to a given record which is the fastest way to do so (except caching).

We will detail in the following, the basis of tuples reconstruction which leads to some substantial gains in query processing, especially for multi-column projections which should require multiple join operations.

To build up T-Plotter on-the-fly, a single query is required:
CREATE TABLE TP AS SELECT tuple_id, F1.ROWID AS f1, F2.ROWID as f2, F3.ROWID AS f3, F4.ROWID as f4 FROM F1, F2, F3, F4 WHERE F1.tuple_id = F2.tuple_id AND F1.tuple_id = F3.tuple_id AND F1.tuple_id = F4.tuple_id

Figure 2.
T-plotter query processing.

3.4 T-plotter materialization

Our strategy to access fragments relies on T-Plotter tuples stored in a unique structure. Each filtering predicate is accessed to reduce this set of T-Plotter tuples. At the same time, in case of multiple accesses, ROWIDs can be replaced by the filtering values (and linked attributes of the fragment), this feature corresponds to the Early Materialization [1]; when all filtering predicates are processed, we access directly (through related ROWID’s) to projected attributes to complete required attributes, corresponding to the Late Materialization.

Figure 2 gives a global view on the T-Plotter materialization process. It works as in the following steps:

Step 1 Step 1
In the beginning, brings only the attributes required in predicates part, for example (A, B, C),
Step 2
Filter (A, B, C) on the predicates to obtain bitmap files (A’, B’, C’) indicating the positions of the relevant tuples,
Step 3
Combine bitmap files with an intersection to obtain a single bitmap file,1
Step 4
Use the T-Plotter structure to access the relevant tuples of attributes (D, E) based on the final bitmap positions and give in output (D’, E’).

Note that this process does not require a unique order on fragments. Moreover, this strategy benefits from both Early and Late Materialization, depending on the required fragments from the query. Thus, we reduce the amount of data to be held in main memory to compute a query by keeping only mandatory attributes, but also keeping them for re-accessed attributes (instead of combining bitmaps) [6]; to get efficiently T-Plotter tuples, the structure is indexed to optimize accesses on tuple_id (common attribute). The T-Plotter structure is also maintained in main memory since it is required in every single operation. Thus only one index is required to be cached permanently to make the system efficient for every execution plan.

T-plotter materialization[1] $\mathcal{F}$ set filtering predicates (ordered by selectivity), $\mathcal{P}$ set of projected attributes, $\mathcal{T}$ set of T-Plotter tuples $\mathcal{F}:=\emptyset$ $f\in\mathcal{F}$ $!materialized(\mathcal{T},f.attributes)$ $S:=access(f)$ $\mathcal{T}=\emptyset$ $s\in S$ $t:=s\Join TP(s.\texttt{tuple\_id})$ $\mathcal{T}:=\mathcal{T}\cup t$ $\mathcal{T}:=\mathcal{T}\cap S$ $filter(\mathcal{T},f)$ $p\in\mathcal{P}$ $!materialized(\mathcal{T},p)$ $t\in\mathcal{T}$ $m:=access(ROWID(t,p))$ $t:=t\Join m$ t

Algorithm 3.4 details the tuple reconstruction process. We can see that every filtering predicates are processed first (lines 2–16) and projections in the second step (lines 17–24). To filter out T-Plotter tuples, we need to check if required attributes are already materialized (line 3), if not, the access to this predicate is done (line 4) according to the underlying organization and statistics (clustered index, hash tables, B-Tree or full access if necessary).

Then if it is the first time to access to T-Plotter, we get every instance that corresponds to the first filter (lines 6–9) by merging accessed tuples to T-Plotter (via tuple_id); otherwise we produce an intersection between previous step and the new filter (line 11) thanks to tuple_id values. If the required attributes are already materialized (thanks to fragmentation), we can process the filter directly in main memory (line 14). To materialize attributes that are required for the projection, we need to check if those attributes have already been materialized (line 18), if not we access to corresponding fragments by using ROWID’s that are present in T-Plotter tuples (line 20). Then a merge join between them is applied (line 21).

We must notice that the materialization step benefits from the clustering factor effect. In fact, ROWID’s of following T-Plotter tuples have a high probability to point to continuous data blocks and consequently few accesses to those blocks are required since they are already available in main memory. To maximize this step, we sort subsets of ROWID’s (this subset has a fix size to fit in memory).

Since Late Materialization can be insufficient in case of low selectivity predicates, we need to discard it. An alternative algorithm is then applied where step 1 is replaced by a global access to T-Plotter. The predicate is applied during Early Materialization by accessing to required fragments (second step). We will show the gain of this alternative algorithm in the experiments.
3.5 T-plotter tuple reconstruction

T-Plotter performs a tuple reconstruction in a very simple way, this reconstruction can be based on fragments not necessarily ordered on the same key, a simple index access to the T-Plotter structure allows us to get the reconstructed tuples, T-Plotter is stored on the primary key tuple_id which allows indexed and direct access to relevant data without resorting to multiple indexes, once relevant tuple positions are obtained, simply access T-Plotter to retrieve the data addresses on stored on the other fragments, the result obtained is a reconstructed tuple, without any other necessary operation.

T-Plotter supports early materialization and Late Materialization, on data structures not necessarily organized on the same sorting key, and on compressed data and non-compressed data.

4. Cost model analysis

To calculate or estimate the time processing of a query it is necessary to detail each operation of the execution plan of the query; this operation is called cost model calculation. The cost model analysis is based essentially on the calculation of the number of disk accesses in and out, because it is the most expensive operation compared to the other operations like cost of processor treatment, or cost access to the main memory. In order to study the impact of T-Plotter “TP” on join operation, we will focus on the two important physical designs: classical vertical fragmentation “VF” and T-Plotter, referring to the cost models we can compare the performance of T-Plotter with the classical vertical fragmentation; For optimization, we restricted this comparison on the access cost of only one vertically fragmented table, and we have focused our study on the join part for tuple reconstruction, which represents the main difference between FV and T-Plotter and the desired performance gain obtained by T-Plotter.

Notations:

$R_{tp}$ : the T-Plotter fragment.

$|R|$ : number of blocks in the relation R.

$\|R\|$ : number of tuples in R, the same for all fragments, such that: $\|R_{tp}\|=\|R_{i}\|$ .

$0\leqslant sel\leqslant 1$ : query selectivity on a given attribute.

$\|R^{\prime}\|$ : number of relevant tuples in R, such that $\|R^{\prime}\|=sel\times\|R\|$ .

$|Index|$ : Index height.

Rank index height: the indexes are based on the attributes rank, so the indexes of each fragment are of identical size, and each index is of type B-Tree, the rank attribute is an integer of size 4 bytes.

Index ${}_{i}$ : represent the index based on fragments, $I$ where Height index ${}_{i}=log_{ordrei}(\|R_{i}\|)=log_{200}(6\times 106)=2.9457\sim 3$ .

To access one data in each fragment using the index we have to read three blocks. We calculate the cost model for the tuple reconstruction part, where $\{R_{1},\ldots,R_{n}\}$ , represent the necessary fragment to the sorting attribute to the query.

4.1 Vertical fragmentation (VF) design

VF Design is calculated by the cost of accessing the fragments plus their indexes as developed in Eq. (3).

$\displaystyle\textit{Cost}_{\textit{VF}}=\sum_{i=1}^{n}\Big{(}(|\textit{index}% _{i}|\times\textit{Sel}\times\|R_{i}\|)+\|R_{i}^{\prime}\|\Big{)}=\sum_{i=1}^{% n}\Big{(}(3\times\textit{Sel}\times\|R_{i}\|)+\|R_{i}^{\prime}\|\Big{)}=\sum_{% i=1}^{n}(3\times\textit{Sel}\times\|R_{i}\|)+\sum_{i=1}^{n}\|R_{i}^{\prime}\|$ (3)

4.2 T-plotter design

To calculate the cost model of T-Plotter we distinguish two cases, the first one when the selectivity is very low then to access the T-Plotter by a full scan (Eq. (4)), the second case when the selectivity is high (Eq. (5)); here it is more interesting to use an index to access the T-Plotter.

1.
Low selectivity is verified when: $\textit{Sel}>\frac{|R_{tp}|}{\|R_{tp}\|}$ In this case the cost is a full scan of the T-Plotter table TP, plus access to other fragments.

$\displaystyle\textit{Cost}_{\textit{TP}}=|R_{tp}|+\sum_{i=1}^{n}\|R_{i}^{% \prime}\|$ (4)
2.
High selectivity is verified when: $\textit{Sel}<\frac{|R_{tp}|}{\|R_{tp}\|}$ Here the cost is composed of the cost of the index scan to T-Plotter, plus access to other fragments.

$\displaystyle\textit{Cost}_{\textit{TP}}=(|\textit{index}_{tp}|\times\textit{% Sel}\times\|R_{tp}\|)+\|R_{tp}^{\prime}\|+\sum_{i=1}^{n}\|R_{i}^{\prime}\|=(3% \times\textit{Sel}\times\|R_{tp}\|)+\|R_{tp}^{\prime}\|+\sum_{i=1}^{n}\|R_{i}^% {\prime}\|$ (5)

4.3 Models comparison

To compare the two designs, we study the behavior of the equation $\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}$ , when this equation is positive, this means that the T-Plotter is less time costly than the VF design, and when $\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}<0$ , the VF design is the best choice:

•
Low selectivity: $\textit{Sel}>\frac{|R_{tp}|}{\|R_{tp}\|}$ . We combine Eqs (3) and (4).

$\displaystyle\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}=\Bigg{(}% \sum_{i=1}^{n}(3\times\textit{Sel}\times\|R_{i}\|)+\sum_{i=1}^{n}\|R_{i}^{% \prime}\|\Bigg{)}-\Bigg{(}|R_{tp}|+\sum_{i=1}^{n}\|R_{i}^{\prime}\|\Bigg{)}=% \sum_{i=1}^{n}(3\times\textit{Sel}\times\|R_{i}\|)-|R_{tp}|$
•
High selectivity: $\textit{Sel}<\frac{|R_{tp}|}{\|R_{tp}\|}$ . We combine Eqs (3) and (5).

$\displaystyle\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}=\Bigg{(}% \sum_{i=1}^{n}(3\times\textit{Sel}\times\|R_{i}\|)+\sum_{i=1}^{n}\|R_{i}^{% \prime}\|\Bigg{)}-\Bigg{(}(3\times\textit{Sel}\times\|R_{tp}\|)+\|R_{tp}^{% \prime}\|+\sum_{i=1}^{n}\|R_{i}^{\prime}\|\Bigg{)}=\sum_{i=1}^{n-1}(3\times% \textit{Sel}\times\|R_{i}\|)-\|R_{tp}^{\prime}\|$

.

The T-Plotter index can enhance the gain for any selectivity. It relies on both the number of fragments “n”, and the query selectivity, “Sel’’.

Proof The T-Plotter index can enhance the gain for any selectivity when $\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}>0$ .

•
For low selectivities, the gain relies on the selectivity property: $\textit{Sel}>\frac{|R_{tp}|}{\|R_{tp}\|}$

$\displaystyle\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}>0% \Rightarrow\sum_{i=1}^{n}(3\times\textit{Sel}\times\|R_{i}\|)-|R_{tp}|>0% \Rightarrow\sum_{i=1}^{n}(3\times\textit{Sel}\times\|R_{i}\|)>|R_{tp}|% \Rightarrow\textit{Sel}>\frac{|R_{tp}|}{\sum_{i=1}^{n}(3\times\|R_{i}\|)}% \Rightarrow\textit{Sel}>\frac{|R_{tp}|}{(3n\times\|R_{i}\|)}\Rightarrow\textit% {Sel}>\frac{|R_{tp}|}{(3n\times\|R_{tp}\|)}$

Thus, we obtain in case of a low selectivity:

$\displaystyle\forall\enspace n\in\mathbb{N}|n\geqslant 1:\frac{|R_{tp}|}{\|R_{% tp}\|}>\frac{|R_{tp}|}{3n\times\|R_{tp}\|}$ (6)

So Eq. (6) above is always verified since there is at least one fragment. This means that the T-Plotter design is more optimal than VF for a low selectivity.
•
For a high selectivity, the gain is based on the selectivity bounds: $0\leqslant\textit{Sel}<\frac{|R_{tp}|}{\|R_{tp}\|}$

$\displaystyle\textit{Cost}_{\textit{VF}}-\textit{Cost}_{\textit{TP}}>0% \Rightarrow\sum_{i=1}^{n-1}(3\times\textit{Sel}\times\|R_{i}\|)-\|R_{tp}^{% \prime}\|>0\Rightarrow\|R_{tp}^{\prime}\|<\sum_{i=1}^{n-1}(3\times\textit{Sel}% \times\|R_{i}\|)\Rightarrow\|R_{tp}^{\prime}\|<(n-1)\times\|R_{tp}\|\times 3% \times Sel\Rightarrow\frac{\|R_{tp}^{\prime}\|}{3(n-1)\times\|R_{tp}\|}<Sel% \Rightarrow\frac{Sel\times\|R_{tp}\|}{3(n-1)\times\|R_{tp}\|}<Sel\Rightarrow% \frac{1}{3(n-1)}<1$ (7)

Equation (7) is true for a high selectivity only if $\forall\enspace n\in\mathbb{N}|n>1$ . Which means that T-Plotter is more efficient than VF only if there are at least 2 fragments from $R$ .

Conclusion. based on the theoretical calculation of the cost model, we deduce that T-Plotter is more efficient than classical vertical fragmentation, both for low or high selectivity.

Table 2
TPC-H fragments

Fragment Attributes

F1 Tuple_id, L_ORDERKEY, L_PARTKEY, L_SUPKEY

F2 Tuple_id, L_LINENUMBER, L_COMMENT

F3 Tuple_id, L_QUANTITY

F4 Tuple_id, L_EXTENDPRICE, L_DISCOUNT

F5 Tuple_id, L_TAX, L_RETURNFLAG, L_LINESTATUS

F6 Tuple_id, L_COMMITDATE, L_RECIEPTDATE, L_SHIPINSTRUCT, L-SHIPMODE

F7 Tuple_id, L_SHIPDATE

5. Implementation

Fragment	Attributes
F1	Tuple_id, L_ORDERKEY, L_PARTKEY, L_SUPKEY
F2	Tuple_id, L_LINENUMBER, L_COMMENT
F3	Tuple_id, L_QUANTITY
F4	Tuple_id, L_EXTENDPRICE, L_DISCOUNT
F5	Tuple_id, L_TAX, L_RETURNFLAG, L_LINESTATUS
F6	Tuple_id, L_COMMITDATE, L_RECIEPTDATE, L_SHIPINSTRUCT, L-SHIPMODE
F7	Tuple_id, L_SHIPDATE

To put into practice our solution we have chosen the well-known TPCH benchmark that offers OLAP tests. It is composed of a suite of 22 business oriented ad hoc queries [21]. It consists of eight tables: part, partsupp, lineitem, orders, customer, supplier, nation, and region. The TPCH benchmark is designed to stress performances of the DBMS as well as the system. The 22 queries reflect specific implementations and relative interrogation combining aggregations, joins and sort operations, with varying selectivities.

5.1 TPCH vertically fragmented

The fact table Lineitem contains 13 columns and is queried by 16 of the 22 queries. To shed light T-Plotter performances, we will focus only on those queries in the following. Since Lineitem is a large table (both number of attributes and number of tuples). Of course, this optimization can be put into practice on every table or even more on different types of architecture. In order to produce efficient execution plans based on sub-tables [20], we need to split Lineitem into fragments. To achieve this, we rely on the Afinner algorithm [8] which proposes a good compromise between a full decomposition and tuple reconstruction. For this it computes a set of frequent queries. In our case we used the 16 TPCH queries.

Table 2 shows the Vertical Fragmentation (VF) of Lineitem into 7 distinct fragments. We can see that the tuple_id attribute is present in every fragment to reconstruct tuples. Moreover, except tuple_id, no attributes are duplicated into the fragments.

For all of them, clustered indexes on tuple_id have been chosen to enhance the clustering factor for tuple reconstruction. Of course, other physical storage should have been chosen according to a different set of queries.

5.2 Query rewriting process

Due to the Lineitem fragmentation, TPCH queries need to be rewritten for a proper evaluation according to the new physical design. For each queries’ attributes, the related fragment is added in the FROM clause. This simple task requires in further steps to stick to Algorithm 3.4. To achieve tuple reconstruction with T-Plotter; Nested Loop Joins are processed between fragments and the T-Plotter structure. Thanks to the latter ROWID’s are already available and no index scan is necessary for each tuple. In other words, this nested loop corresponds to the one with an index where list of ROWID’s is already made.

To illustrate the rewriting step, we chose to focus on two queries of the TPCH benchmark: Q1 and Q14. They help to shed light two kinds of behavior on T-Plotter execution plan. Q1 has two main characteristics. It processes only one predicate with a poor selectivity of 56.86%, but also need to project several attributes before aggregating. Those characteristics are shown in Table 3 which gives for each query, the number of fragments required to filter and project attributes, but also the selectivity of the predicates.

Consequently, we can see that query Q1 requires only one fragment (F1) to filter the T-Plotter structure, and three fragments (F3, F4, F5) for projection. As said in Section 3.3, T-Plotter materialization behaves differently with poor selectivity predicates. Then query Q1 must be rewritten as if it does not contain any predicates, only projections. Consequently, the following rewritten query uses T-Plotter to access projections (F3, F4, F5) but also filters (F1) with ROWID’s. The HINTs will be detailed in the following.

Query Q14 contains one fragment (F1) for filtering and one other for projection (F5). The joining attribute with the Part table is already contained into F1. With the selectivity of 0.013%, we can apply Algorithm 1 (as for other queries). Thus, we access to the F1 fragment and get the tuple_id value to get the T-Plotter tuples in TP. Then F5 is accessed when necessary to apply the late materialization.

In the following the TPCH Q14:

SELECT 100.00 * SUM(CASE WHEN p_type LIKE 'PROMO%' THEN l_extendedprice * (1 - l_discount) ELSE 0 END) / SUM(l_extendedprice * (1 - l_discount)) AS promo_revenue FROM Lineitem, Part WHERE l_partkey = p_partkey AND l_shipdate>= '1995-08-01' AND l_shipdate< '1995-09-01';

TPCH: rewritten Q14:

SELECT /*+index(TP) leading(F1 TP F5 part) use_nl(F5 TP)*/ 100.00 * SUM(CASE WHEN p_type LIKE 'PROMO%' THEN l_extendedprice * (1 - l_discount) ELSE 0 END) / SUM(l_extendedprice * (1 - l_discount)) AS promo_revenue FROM F1, F5, TP, Part WHERE F1.tuple_id = TP.tuple_id AND TP.F5 = F5.ROWID AND l_shipdate >= '1995-08-01' AND l_shipdate< '1995-09-01' AND l_partkey = p_partkey;

5.3 Execution plan

Last but not least, Hint’s must be added to the query to enforce the optimizer to behave in the proper way. In fact, the optimizer does not know how to process the T-Plotter structure naturally with multiple ROWID’s selection and the proper order to process fragments. As a matter of facts, most of the time the proposed execution plan leads to poor performances. By introducing Hint’s, the produced execution plan corresponds to requirements of Algorithm 3.4.

Query Q1 uses the hint use_nl to access fragments with a NESTED LOOPS with a specific order: TP for T-Plotter initialization, F1 to filter it (intersection) with the poor selectivity, and finally other fragments for late materialization. The resulting execution plan in Fig. 3 for query Q1 shows that NESTED LOOPS are used with the required order. We can notice that the accesses to fragments are done with a TABLE ACCESS BY USER ROWID which is given by the TP table. The execution plan behaves classically for the end of the query to process the aggregate functions.

Figure 3.

Execution plan for query Q1.

Figure 4.

Execution plan for query Q14.

Query Q14 enforces the usage of the index on TP to ensure that the filtering step use properly the tuple_id. Then, a precise order is given for the process; F1 to get filtering tuples, TP to get the corresponding T-Plotter tuples, F5 to project attributes and then part of the required join operation. To finish with, a use_nl hint is used to enforce the access by ROWID’s for TP and F5. No hints are given to process the final join with Part.

Figure 4 shows the execution plan for query Q14. We can follow the algorithm process for the filtering fragment and the late materialization for F5. We can notice that F1 is accessed with a standard index whcih can be exchanged by another one according to the characteristics of the involved predicate (e.g., a clustered index or a hash table).

5.4 Experiments

The T-Plotter index has been integrated to an Oracle 11gR2 database in which we have simulated the behavior of a Vertical Fragmentation. To show the efficiency of our system, we have tested it in a constrained environment with a whole main memory of only 4 GB (shared with the operating system) and a CPU Intel i5 2430 M with 2.4 GHz. A classical Hard Drive with 7200 rpm was used. This setting wishes to prove that we can stress a database with OLAP queries even within a poor environment. The TPCH benchmark has been set to a scale factor of 1 which leads to 6 million tuples into the Lineitem table. This scale factor produces a database of 1 GB.

The resulting tables have been stores into three distinct databases:

1.
Row Store: A traditional Row-Store database with classical indexes to optimize relevant queries.
2.
VF: A Vertical Fragmentation of the Lineitem table as explained previously.
3.
T-Plotter: Our index has been put on top of the VF database in order to show the gain of performances and benefits. The T-Plotter index which plots on the 6 fragments can be cached into the Oracle PGA for obvious performances requirements. Its size is of 0.34 GB which fits more easily in main memory.

Table 3
Query statistics

Filter Frag. Sel. % Project Frag.

Q1 1 56.86 3

Q3 1 0.005 1

Q4 2 0.009 0

Q5 1 0.001 1

Q6 3 0.019 0

Q7 1 0.001 1

Q8 1 0.001 1

Q9 1 0.054 2

Q10 2 0.038 1

Q12 2 0.005 0

Q14 1 0.013 1

Q17 2 0.0001 1

Q18 1 0.1647 1

Q19 3 0.0001 1

Q20 2 0.00003 1

Q21 2 0.000001 0

Table 4
Query time processing (s)

Row store VF Project Frag.

Q1 15.87 25.40 13.62

Q3 24.25 11.50 10.61

Q4 22.60 9.03 8.21

Q5 74.25 6.26 6.36

Q6 19.89 1.43 1.57

Q7 24.00 8.79 8.76

Q8 23.25 4.26 4.42

Q9 25.81 5.37 5.17

Q10 24.28 9.36 12.34

Q12 20.60 2.46 11.12

Q14 0.53 0.81 1.00

Q17 19.17 2.42 2.70

Q18 52.29 28.65 29.45

Q19 19.85 2.32 2.39

Q20 21.78 4.79 4.42

Q21 53.43 10.98 11.42

5.5 Processing time

	Filter Frag.	Sel. %	Project Frag.
Q1	1	56.86	3
Q3	1	0.005	1
Q4	2	0.009	0
Q5	1	0.001	1
Q6	3	0.019	0
Q7	1	0.001	1
Q8	1	0.001	1
Q9	1	0.054	2
Q10	2	0.038	1
Q12	2	0.005	0
Q14	1	0.013	1
Q17	2	0.0001	1
Q18	1	0.1647	1
Q19	3	0.0001	1
Q20	2	0.00003	1
Q21	2	0.000001	0

	Row store	VF	Project Frag.
Q1	15.87	25.40	13.62
Q3	24.25	11.50	10.61
Q4	22.60	9.03	8.21
Q5	74.25	6.26	6.36
Q6	19.89	1.43	1.57
Q7	24.00	8.79	8.76
Q8	23.25	4.26	4.42
Q9	25.81	5.37	5.17
Q10	24.28	9.36	12.34
Q12	20.60	2.46	11.12
Q14	0.53	0.81	1.00
Q17	19.17	2.42	2.70
Q18	52.29	28.65	29.45
Q19	19.85	2.32	2.39
Q20	21.78	4.79	4.42
Q21	53.43	10.98	11.42

We have executed the 16 queries from TPCH that involve the Lineitem table. Let remind that characteristics presented in Table 2 show the number of fragments used for filtering (first step of Algorithm 1) and for projections (second step). It also provides the predicates selectivity for each query which will help to understand what happens during the evaluation process. Table 3 gives the resulting time for each query according to the physical structure. We can identify two different kinds of queries Q1 and others. Q1 is very different from other ones. In fact, as we saw previously three fragments are accessed for projection and only one for filtering with a poor selectivity (56.86%).

It has a huge impact on the VF implementation. In fact, time is four times bigger than the Row Store one. This is due to four required fragments with more than half the number of tuples which does not fit in a HASH JOIN operation. Consequently, a high latency is obtained to process the three joins.

T-Plotter exploits those characteristics to provide an alternative execution plan. It accesses to required fragments through ROWID’s, it filters tuples on-the-fly, then gathers remaining attributes. The clustering factor effects help to avoid accessing to a data block twice during the evaluation process. Since the filter reduces the number of required data blocks, even if it is higher than 56%, the global time is drastically reduced. The final result is better than the Row Store storage while remaining close to it. This result shows that our strategy benefits from Row Store advantages with a high number of projecting fragments and a poor selectivity.

Query Q3 has a high selectivity and requires only one fragment to be projected. As a result, the processing time is divided by four. We can see that T-Plotter is slightly better than VF, it is due to the fact that no index is required to reconstruct tuples since it is already in main memory with the T-Plotter index while VF process by an INDEX UNIQUE SCAN to access tuples referred by the tuple_id value. Query Q14 has the same type of results. The time difference is due to the fact that only one join operation is required leading to an interesting processing time. Queries Q5, Q7 and Q8 have similar behaviors but with more tables to join with.

Table 5
VF+ query processing time (s)

	Row store	VF	T-plotter	VF $++$
Q1	15.87	25.40	13.62	13.62
Q3	24.25	11.50	10.61	10.61
Q4	22.60	9.03	8.21	8.21
Q5	74.25	6.26	6.36	6.26
Q6	19.89	1.43	1.57	1.43
Q7	24.00	8.79	8.76	8.76
Q8	23.25	4.26	4.42	4.26
Q9	25.81	5.37	5.17	5.17
Q10	24.28	9.36	12.34	9.36
Q12	20.60	2.46	11.12	2.46
Q14	0.53	0.81	1.00	0.81
Q17	19.17	2.42	2.70	2.42
Q18	52.29	28.65	29.45	28.65
Q19	19.85	2.32	2.39	2.32
Q20	21.78	4.79	4.42	4.42
Q21	53.43	10.98	11.42	10.98

Query Q4, since it contains an “exists” nested query on Lineitem, requires processing fragments as much as the “orders” table needs it. Consequently, the Row Store implementation takes some time. In T-Plotter and VF implementations, only two fragments are necessary: one for the join operation (nested one) and one for the predicate on Lineitem. Those two steps reduce drastically the number of accesses necessary to be done. Here again, index scans are avoided in the T-Plotter implementation.

Query Q10 behaves similarly is a preliminary filter in an external table then process to a second filter. However, it requires here one more fragment to be accessed for projection and a higher selectivity.

Query Q6 is really interesting in a fragmentation point of view. In fact, three fragments are accessed for filtering and every attribute are already present for projection. As a matter of facts, VF shows very good performances. T-Plotter has a slightly higher time processing since it requires more CPU usage to access to the index structures in main memory and then computes intersections, while CF only computes intersections. This effect is minimized in other queries since no projections are required in Query Q6.

Query Q12 can be compared to Q6 for multi-filtering fragments and no projections required. Even with a stronger selectivity, the processing time is higher. This is due to a very particular feature of this query which involves two attributes which are present in two distinct fragments (l_shipdate and l_commitdate). This particularity involves a second treatment which must be done after accessing to the fragments (so less filtering than expected). Finally, the filter is applied in main memory.

Query Q9 contains several join operations with the selectivity of 0.054% (higher than others). However only one fragment is needed for those joins, but two fragments are required for the projection. Finally, fragmentation halves time processing by reducing the amount of accessed data (as expected in late materialization). Query Q19 is a disjunctive query with three similar predicates where only one predicate is changing. This feature is very interesting in our case since all the filters are identical in a first step and the last fragment is applied to produce the disjunction. Even if the selectivity is really interesting, this multi-filter, combined to a join provides average processing time.

In the end, T-Plotter does not replace the vertical fragmentation design but it is a complementary to this design, fill the gaps where naïve VF fail, for some kind of queries, so we propose to combine the two solution VF and T-Plotter, so to bring a general solution to the hole query, so to be the best, this combination is presented in Table 4.

Figure 5.

Total processing time.

Experiments conclusion analysis.

According to this panel of queries, we can conclude that the number of fragments accessed for projection has a higher impact on processing time than for filtering fragments. Selectivity influences it also but especially for very high ones. Moreover, using a fragment for joining two tables is also attractive with a lower amount of data in the join operator.

We can notice that T-Plotter avoids spending time in indexes for tuple reconstruction which brings better performances than Vertical Fragmentation for some type of queries. Finally, as we can see in Table 4 global time has been divided by three. According to Row Store, queries with a strong selectivity, obtain most of the gain. At the opposite, for Vertical Fragmentation the gain is done exclusively on poor selectivity (Q1).

5.6 Update queries

The second set of experiments tries to enlighten performances gains in terms of updates. In facts, classical Column Store databases rely on materialized views and temporary structures to optimize treatments but have an impact on updates. We show here that with a single index, this time is drastically reduced leading to interesting results.

Table 6 shows three update queries that especially show the impact of various number of fragments. Respectively one for U1, two for U2, and three for U3. We also executed those three queries on varying selectivity (0.00001%, 0.16% and 13.76%) to see how much selectivity has an impact on update time. Table 7 gives the results for each query, selectivity and physical storage strategy.

Table 6
Update queries on lineitem (initial schema)

	Query
U1	UPDATE Lineitem SET l_quantity $=$ l_quantity $+$ 10 WHERE l_shipdate BETWEEN date1 AND date2
U2	UPDATE Lineitem SET l_quantity $=$ l_quantity $+$ 10, l_extendedprice $=$ l_extendedprice $+$ 100 WHERE l_shipdate between date1 and date2
U3	UPDATE Lineitem SET l_quantity $=$ l_quantity $+$ 10, l_extendedprice $=$ l_extendedprice $+$ 100, l_commitdate $=$ l_commitdate $+$ 100 WHERE l_shipdate BETWEEN date1 AND date2

Table 7

Updates processing time (in seconds)

	Selectivity	Row store	VF	T-plotter
U1	0.00001%	0.359	0.031	0.062
	0.16%	0.986	0.063	0.064
	13.76%	38.251	2.605	4.050
U2	0.00001%	0.343	0.037	0.036
	0.16%	0.960	0.390	0.406
	13.76%	42.620	3.212	4.742
U3	0.00001%	0.375	0.047	0.041
	0.16%	1.103	0.515	0.577
	13.76%	34.991	13.526	18.392

We can see that VF and T-Plotter outperforms the Row Store. For one fragment the result is obvious, but this gain is similar when leveling the number of updated fragments. This major issue corresponds to the fact that tuples are stored in data blocks which are managed in cache while updated. Since data are fragmented according to a subset of attributes, more tuples are stored in a same data block, so the probability of two updated tuples done on a same data block is higher and consequently maximizes cache usage.

This gain is lower for U3, even if VF and T-Plotter are better than Row Store. This effect comes from the specificity of fragment F6 (containing l_commitdate). This fragment contains textual attributes (l_shipinstruct and l_shipmode) which reduces drastically the probability for higher length of fragmented tuples. Consequently, the amount of updated data blocks is higher.

6. Conclusion

In this paper we point the fact that all previous studies have focused on how to fragment the database as it is a NP-complete difficult problem, but not on the physical model of vertical fragmentation. Indeed we have pinpointed the weak point of vertical fragmentation, we have provided a solution to easily adapt and use this technique on traditional databases.

T-Plotter is a unique data structure for tuple reconstruction and an algorithm to handle it efficiently according to its cost model and the fragmentation layer. This simple but powerful structure helps to compose fragmented tables into original tuples. It targets the benefits from both late and early materialization, late to access as late as possible data in order to reduce memory consumption, early to avoid multiple accesses to an attribute. It also allows storing fragments in independent physical orders which can be a crucial need for specific filtering queries. It reduces all queries processing time that exploit large amount of data, especially for wide column-oriented tables. It maximizes usage of filters and late materialization which tackles the tuples reconstruction issue.

This solution is not a competitor to Column Store databases; in fact, it aims at enhancing every kind of database as a top layer to recompose fragmented data. So, it proposes a complementary index to other kinds of databases. It can exploit optimization techniques often used in columnstore storage like compression [12], materialization, or BAT file for MonetDB [7, 6, 22].

The main point of this study is that T-Plotter has made it possible to fill the gaps in implementing vertical fragmentation on Classical Vertically fragmented databases for processing OLAP models. The tuple reconstruction still a heavy cost for Column Store databases [16, 14], even for In-Memory ones [6]. Our experiments showed that T-Plotter can fit in main memory even if standard databases do not fully exploit available places (e.g., PGA memory has to be maximized). Likewise, Column-Store databases that takes full advantages of the machine setting for both CPU and memory [18].

In our case T-Plotter index can be considered as a bulky structure, since it takes about a third of the size of the fragmented table which cannot be suitable in some cases. As a perspective, we plan to compress the T-Plotter structure by reducing ROWID’s to the minimum size since for each fragment, object and file identifiers are constant values. We estimate that T-Plotter size can be reduced to one fiftieth of that original size, which is an interesting gain. Even if compressing the T-Plotter structure can reduce its size, this feature will level up the CPU charge and can reduce gains of performances. It should have bad impacts on the database performances.

Another possibility is to change the way to reconstruct tuples. The key idea is to store in fragment with distinct values, and T-Plotter tuples point to those values (several tuples on a same value). The reconstruction facility focuses on reconstructing values and not attribute values. This can reduce every fragment size, and enhance every grouping operation which can be done on ROWID’s instead of values. We can see this feature as a later materialization, but after the aggregation step (not the case in CS databases).

Some other weak points of T-Plotter can be improved in future works: 1) Joins that are used during tuples reconstruction can be optimized since they do not take into account join cardinalities. Join indices methods can be used to tackle this issue. 2) Distributed environments like for wide column oriented databases propose a complementary approach by parallelizing treatment. Our data structure could be spread on a cluster to optimize tuples reconstruction in a distributed context. 3) One last issue is the evolution of the affinity of fragments with queries on the database. It requires to add or remove fragments from both storage and T-Plotter. However, this issue remain complex on all strategies: cost-model, data mining and affinity.

Footnotes

If the attributes (A, B, C) are not sorted on the same order, it will be necessary to sort the results (A’, B’, C’) in the same order to obtain a correct result.

Authors’ Bios

Hichem Chaalal is a researcher at the University of Mohamed Boudiaf/Oran in Algeria. He is a teacher at the University of Tissemsilt in Algeria, he is preparing a PhD in collaboration with Pr Hafida Belbachir and Pr Nicolas Travers University of Sciences and Technology of Oran-Mohamed Boudiaf (USTO-MB) in Algeria, interested in the field of development and research in the design of databases and information systems.

Nicolas Travers is professor of Computer Sciences at ESILV Engineering School, Paris la Défense. At DVRC laboratory, he heads the Digital Group, dedicated to digital analysis in both Computer Science and Marketing domains. He was habilitated (HDR) from Sorbonne Universités in 2018. His main topics deal with database management and optimization, in distributed environments as NoSQL databases, as well as ad hoc databases design like Digital Tourism, Musical Scores or Multimodal libraries.

Hafida Belbachir is professor of Computer Sciences at the University of Sciences and Technology of Oran-Mohamed Boudiaf (USTO-MB) in Algeria. She received her PhD in Computer Science at University of Oran in 1990. She heads the Database System Group in the LSSD Laboratory. Her research interests include Advanced DataBases, DataMining and Data Grid. She is the author of more than 80 papers in reviews and proceedings.

References

Abadi

D.J.

Myers

D.S.

DeWitt

D.J.

and Madden

S.R.

, Materialization Strategies in a Column-Oriented DBMS, in: IEEE International Conference on Data Engineering (ICDE), Istanbul, Turkey, 2007, pp. 466–475. https://doi.org/10.1109/ICDE.2007.367892.

Abadi

D.J.

Boncz

P.A.

Harizopoulos

Idreos

and Madden

, The design and implementation of modern column-oriented database systems, Foundations and Trends in Databases 5(3) (2013), 197–280. https://doi.org/10.1561/1900000024.

Abadi

D.J.

Madden

and Ferreira

, Integrating compression and execution in column-oriented database systems, in: International Conference on Management of Data (SIGMOD), ACM, New York, USA, 2006, pp. 671–682. https://doi.org/10.1145/1142473.1142548.

Abadi

D.J.

Madden

and Hachem

, Column-stores vs. row-stores: How different are they really? in: ACM International Conference on Management of Data (SIGMOD), Vancouver, BC, Canada, 2008, pp. 967–980. https://doi.org/10.1145/1376616.1376712.

Agrawal

and Srikant

, Fast algorithms for mining association rules in large databases, in: International Conference on Very Large Data Bases (VLDB), San Francisco, CA, USA, 1994, pp. 487–499.

Boissier

Spivak

and Meyer

, Improving tuple reconstruction for tiered column stores: A workload-aware ansatz based on table reordering, in: Proceedings of the Australasian Computer Science Week Multiconference (ACSW), ACM, Geelong, Australia, 2017, pp. 25:1–25:10.

Boncz

P.A.

Zukowski

and Nes

, MonetDB/X100: Hyper-Pipelining Query Execution, in: Biennial Conference on Innovative Data Systems Research (CIDR), CA, USA, 2005, pp. 225–237.

Chaalel

and Belbachir

, An optimized vertical fragmentation approach, IJITEE International Journal of Innovative Technology and Exploring Engineering 3(4) (2013), 33–39.

Chaudhuri

and Dayal

, An overview of data warehousing and olap technology, International Conference on Management of Data (SIGMOD) Rec 26(1) (1997), 65–74. https://doi.org/10.1145/248603.248616.

10.

Cheng

C.H.

Lee

W.-K.

and Wong

K.-F.

, A genetic algorithm-based clustering approach for database partitioning, IEEE Trans Systems, Man, and Cybernetics, Part C 32 (2002), 215–230.

11.

Gorla

and Betty

P.W.

, Vertical fragmentation in databases using data-mining technique, International Journal of Data Warehousing and Mining (IJDWM) 4(3) (2008), 35–53.

12.

Hammer

and Niamir

, A heuristic approach to attribute partitioning, in: Proceedings of the International Conference on Management of Data (SIGMOD), ACM, New York, NY, USA, 1979, pp. 93–101. https://doi.org/10.1145/582095.582110.

13.

Hoffer

J.A.

and Severance

D.G.

, The use of cluster analysis in physical data base design, in: International Conference on Very Large Data Bases (VLDB), Framingham, Massachusetts, USA, 1975, pp. 69–86.

14.

Idreos

Kersten

M.L.

and Manegold

, Self-organizing tuple reconstruction in column-stores, in: International Conference on Management of Data (SIGMOD), ACM, New York, USA, 2009, pp. 297–308. https://doi.org/10.1145/1559845.1559878.

15.

Navathe

S.B.

Ceri

Wiederhold

and Dou

, Vertical partitioning algorithms for database design, ACM Trans Database Syst 9 (1984), 680–710.

16.

Navathe

S.B.

and Ra

, Vertical partitioning for database design: A graphical algorithm, in: Proceedings of International Conference on Management of Data (SIGMOD), ACM, New York, NY, USA, 1989, pp. 440–450. https://doi.org/10.1145/67544.66966.

17.

Petraki

Idreos

and Manegold

, Holistic indexing in main-memory column-stores, in: Proceedings of International Conference on Management of Data (SIGMOD), ACM, Melbourne, Victoria, Australia, 2015, pp. 1153–1166. https://doi.org/10.1145/2723372.2723719.

18.

Plattner

, The impact of columnar in-memory databases on enterprise systems: Implications of eliminating transaction-maintained aggregates, Proc VLDB Endow 7(13) (2014), 1722–1729. https://doi.org/10.14778/2733004.2733074.

19.

Song

S.-K.

and Gorla

, A genetic algorithm for vertical fragmentation and access path selection, The Computer Journal 43(1) (2000), 81–93. https://doi.org/10.1093/comjnl/43.1.81.

20.

Stonebraker

Abadi

D.J.

Batkin

Chen

Cherniack

Ferreira

Lau

Lin

Madden

O’Neil

E.J.

O’Neil

P.E.

Rasin

Tran

and Zdonik

, C-store: A column-oriented DBMS, in: Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker, 2019, pp. 491–518. https://doi.org/10.1145/3226595.3226638.

21.

Transaction Processing Performance Council (TPC), TPCH: ad-hoc, decision support benchmark (1999), Standard Specification Revision 218.0., http://www.tpc.org/tpch.

22.

Vermeij

Quak

Kersten

and Nes

, MonetDB, a novel spatial columnstore DBMS, in: Academic Proceedings of the 2008 Free and Open Source for Geospatial (FOSS4G) Conference, OSGeo, Cape Town, South Africa, 2008, pp. 193–199.

23.

Zukowski

Boncz

P.A.

Nes

and Héman

, Monetdb/x100 – A DBMS in the CPU cache, IEEE Data Eng Bull 28(2) (2005), 17–22. ftp://ftp.research.microsoft.com/pub/debull/A05june/mzukowski.ps.

T-plotter: A new data structure to reconcile OLAP and OLTP models

Abstract

Keywords

1. Introduction

2.1 Vertical fragmentation implementation

2.2 Vertical fragmentation optimization

3.1 T-plotter concept

3.2 T-plotter architecture

4. Cost model analysis

4.1 Vertical fragmentation (VF) design

.

5.1 TPCH vertically fragmented

5.2 Query rewriting process

5.3 Execution plan

Table 5 VF+ query processing time (s)

Table 6 Update queries on lineitem (initial schema)

Footnotes

Authors’ Bios

References

Table 5
VF+ query processing time (s)

Table 6
Update queries on lineitem (initial schema)