GridTables: A One-Size-Fits-Most H²TAP Data Store

In the last decade, the database research community has focused on challenges for data management and system design implied by the ongoing needs to manage and analyze web-scale, frequently changing, diverse datasets. One key challenge is to minimize the latency between operational and analytical systems [34, 45, 48]. For HybridTransactionalAnalyticalProcessing (HTAP) systems, new architectures were proposed that enable low latency analysis on real-time operational data. A good overview about this topic can be found in a recent survey by Özcan et al. [45]. A key enabling factor for HTAP systems is modern hardware: modern hardware promises novel ways for data processing of relational [14, 25] and non-relational data [42, 49], as well as benefits for several database system components, such as query optimization [26, 41]. Appuswamy et al. even suggested to use the term \(\mathrm{H}^{2}\)TAP whenever hybridization of workloads is combined with heterogeneity of hardware [6], effectively emphasizing the role of modern hardware.

In previous work [50], we questioned whether current database systems on modern hardware are really future-proof and ready for \(\mathrm{H}^{2}\)TAP workloads. We concluded the existence of missing synergy effects in the state-of-the-art since existing solutions are examined in isolation which leaves optimization potential unexplored and unexploited, such as unsatisfactory support of row-wise storage for co-processors, adaptive indexing across multiple devices, or an excellent online re-organization for \(\mathrm{H}^{2}\)TAP workloads for cross-device databases as already studied in depth for CPU-only database systems.

In addition to that, it is not yet clear how to combine novel research suggestions in a unified system, and how such suggestions may affect or benefit from each other. In particular, our research community shows opportunities and challenges of modern hardware in database systems in isolation, among them the need for analysis of novel adaptive data layouts and data structures for operational and analytical systems [6, 7, 9, 55], novel processing, storage and federation approaches on non-relational data models [11, 18, 51, 52, 62], benefits and drawbacks of porting to new compute platforms [12, 16, 33, 63], opportunities and limitations of GPUs and other co-processors as building blocks for storage and querying purposes [8, 14, 33], novel proposals for main memory databases on modern hardware [3, 15, 21, 53, 56], adaptive optimization, and first attempts towards self-managing database systems [17, 36, 43, 46].

In this paper, we aim for a novel storage engine design, called gridstore that manages relations with a data structure that we name gridtables, in order to face the challenges of \(\mathrm{H}^{2}\)TAP on multiple devices by enabling the combination of established solutions so far considered in isolation. Relations in gridtables are flexibly partitioned into a set of self-contained, and placement-aware containers, called grids. Each grid by its own is able to perform local optimizations regarding schema re-ordering, to avoid cache thrashing for wide records (cf. [13] for OLAP-only), and record organization to optimize the data access path and minimize data redundancy (cf. [1]).

A gridtable implements a flexible and adaptive record layout (cf. [4, 9, 23, 55]) to allow zero-cost null-value suppression, to enable the combination of logically distant record fields into physical dense blocks, and to perform global layout adaption. In contrast to existing partitioning capabilities in enterprise systems, a relation can therefore be partitioned to any combination of vertical and horizontal (logical) fragments with a granularity from the table level to tuple-field values, if desired.

gridtables enable a fine-grained physical optimization of a single database by transitioning between a transactional storage, an analytical storage, and a mixed storage based on the actual usage. Transitions respect user-specific data model definitions and constraints, and are executed via local and global optimizations on the gridtable. Analytical query performance is improved by (implicit) denormalization (similar to a widetable, [39]), and transactional query performance is improved by (implicit) normalization.

We begin with an overview picture, showing a feature summary of our data store (Sect. 2). We then continue with sections containing the following contributions:We end this paper with a discussion on related work (Sect. 7), and our conclusion (Sect. 8).

The ultimate vision behind gridtables is to create a storage engine for \(\mathrm{H}^{2}\)TAP database systems that fully supports both multi-core CPUs and many-core GPUs without making any cutbacks in terms of data freshness, isolation, and transactional consistency.

In this paper, we focus on the storage engine and on storage-engine core operations (i.e., scans and materialization) rather than on operations that fall into the domain of the query engine (and thus, are more coupled with the co-processor-aware aspects of our design).

One cannot expect a One-Size-Fits-All design solving every problem in the domain of \(\mathrm{H}^{2}\)TAP in an optimal way, as shown by Athanassoulis in 2016 for optimizations involing read times, update cost, and memory requirements at once [10]. As a consequence, we suggest a One-Size-Fits-Most design under the following requirements:

In addition to the requirements mentioned above, there are a series of technical challenges and needs for \(\mathrm{H}^{2}\)TAP systems on modern hardware.

Recently, Appuswamy et al. pointed to multi-socket multi-core platforms that require careful design for global shared memory, cache coherence and massive parallelism, coining the term \(\mathrm{H}^{2}\)TAP as a new architecture built for this purpose [6].

In Fig. 2, we show the stacked architecture of our proposal, gridtables. Each indirection level is bundled with a particular set of level-specific functions that we explore more in detail in Sect. 5.4.

The three conceptual main components are gridtables, grids, and data fragments. From top to bottom: a gridtable is a data structure that manages multiple layouts for a relation. Each of these layouts is a combination of vertical and horizontal partitioning where a particular partition has no partitioning-related side-effects to adjacent partitions. A grid is a component that realizes one particular partition including its own physical schema, or indexes. Each grid consists of exactly one data fragment which is a plain storage implementation (such as column store or row store) for relational data that accesses host or device memory directly.

To avoid undesired effects by wrongly chosen partitions (such as splitting an OLTP-related tuple into two parts by vertical partitioning), the responsible decision process must consider a range of constraints, e.g., implied by the workload, or by service level agreements with the client. We explore related problems more in detail in Sect. 6, and study a solution option for a decision process that relies on reinforcement learning to improve from experience while seeking to avoiding execution overheads from online partitioning algorithms, in dedicated papers [19, 20].

Data access in complex structures (e.g., in gridtables) is a trade-off design space. On the one hand, a clear conceptual access path is needed that abstracts from low-level details and which solves important design-related requirements, such as reusability and understandability. In this path, safe operations and usability rather than high performance access are the goals. On the other hand, such properties come often with the cost of additional call overhead that is unacceptable for aggregation-heavy operations as typical for analytical queries over huge amounts of columnar data. For these requirements, safe operation and usability play a minor role. Therefore, a gridtable exposes two ways to access raw data, one for definition and manipulation (a safe path) and one for querying purposes (a fast path).

To address our requirements stated in Sect. 3, we provide the following features for gridtables (see Fig. 3) that are, to the point of this writing, instrumented by the client rather than by the system itself: (1) Flexible Partitions that allow highly-flexible intra-tuple data formats, (2) Per-Grid Formats, to format tuplets column-wise or row-wise, (3) Per-Grid Storage enabling the storage of tuplets in host or device memory, (4) Data Packing, enabling the storage of logically distant fields in a physically contiguous manner, and (5) Schema-Reordering, re-ordering per-grid fields for data cache efficiency. In the following, we explore details on these features.

Flexible Partitions. Having a particular order on, or dependencies between partitions w.r.t. their definition is common for existing partitioning schemes [50], which leads to unreachable configurations in the optimization space. The feature of flexible partitions in a gridtable enables to partition a table in an arbitrary manner by freely defining (non-overlapping) regions in a table. In other words, the partition scheme in a gridtable does not force to partition horizontally and then vertically first (or vice versa), but allows to define partition regions independent from other existing partitions.

Removing such dependencies and order restrictions from the partitioning scheme enables a higher degree in flexibility, which in turn promises more fine-grained matches of data layout and data placement for the workload on particular regions of a table, which will lead to a better performance if the right configuration in the now broader optimization space is used.

Clearly, having freely floating partitions is not only more flexible but also more complex from both a description and optimization perspective. To limit that complexity, we restrict a gridtable to not have overlapping regions. An overlapping region may be understood as a particular portion of data that is redundantly stored on different locations and formatted differently due to different and contradicting access patterns at the same time. We assume that having exactly contradicting access patterns on a significant amount of data where there is no trend to one side of an access pattern type, is a special case for real-world workloads. Therefore, we made the design decision to disallow overlapping regions in order to prune the optimization space that must be explored. Extensions to our solution could consider replication, in future work.

Special to note is the encoding of large null-regions for sparse datasets in a gridtable: if there is no grid defined for a particular subset of row and columns, then this region is interpreted as containing null-values only. This tiny definition allows us to zero-out huge regions of null-data without reserving any memory for their encoding additionally.

As pointed out by Lemke et al. during their investigation of compression techniques for columnar business intelligence solutions, optimization tasks involving reordering of elements to maximize the desired effect require heuristics to be practical computable within a reasonable time [38]. The authors defined a process consisting of four stages (analysis, candidate determination, heuristic evaluation, and per-candidate application), where four different strategies for range sorting under different assumptions are used. Similar to the problems described by Lemke et al. determining the best partition for a gridtable is an \(\mathcal{NP}\)-complete problem and cannot be optimally solved in reasonable time. We explore this and related problems in detail in Sect. 6.

Per-Grid Storage. Per-grid storage enables each partition to be stored on a dedicated memory kind, if required, making the gridtable an abstract container that splits and delegates queries into grids and collects results from these grids to construct the final reply. We currently support main-memory (host memory) based partitions and partitions that are stored in the co-processors device memory. Along with the flexible partition feature, per-grid formats allow to emulate in a fine-grained manner any major storage layout presented in the literature so far. For instance, hyrise [23] can be simulated with vertical partitioning only where each partition is either a column store or row store.

However, we are not limited by these types: our abstraction enables to store data on other memory locations that we have not yet explored, such as on SSDs or remote machines.

Data Packing. Data packing is a distinct feature in gridtables that allows to physically cluster records that are logically spread across the table. With data packing, we are able to move continuous physical memory blocks to co-processors (such as a GPUs) instead of managing several distinct memory blocks only because a user-defined structure forces us to do so. Additionally, we use data packing to decrease the memory requirements implied by organizing the gridtable structure itself: we pack data from two into one grid if both grids have the same storage location and record format, effectively reducing the number of grids that must be managed by the gridtable. Further, data packing promises to efficiently manage cold data in the long run: after analysis a gridtable may pack cold records into one grid and perform (heavy-weight) compression on this grid, or evict the grid data to SSD disks.

Schema-Reordering. Schema-reordering is a feature built for row-store-major gridtables that involve a huge amount of attributes similar to widetables but optimized for point-queries rather than range-queries. Having a best-matching ordered attribute schema for row-store records is needed for OLTP queries to optimize execution speed of queries that access a set of fields of a single record (such as the projection operator does). The reasons for an increased execution speed with a reasonable schema order is that a higher data locality of record fields that are accessed together is more cache efficient, and therefore, faster.

Schema-reordering is a per-grid capability to physically rearrange fields of records stored in that partition. The motivation behind this feature is to minimize CPU cache misses for point-queries on same records over a large subset of the records attribute set. A careful re-ordering of record fields in this case promises a higher probability to have the next field already stored in cache: when the majority of queries to that particular grid touches \(n\) out of \(m\) attributes, these \(n\) attributes are moved to the front per-record. Then, seeking between records with providing pre-fetching hints to the CPU raise the probability to have all the next \(n\) attributes already in the cache for settings in which each single records size exceeds the cache line size.

In this section, we focus on engineering and design challenges regarding the gridtable data structure itself. After establishing the problem statement in Sect. 5.1, we continue with our solutions in the following sections.

At the point of this writing, gridtables are a novel concept to enable a unified storage engine in the huge design space of an \(\mathrm{H}^{2}\)TAP database system.

The core question is how to instrumentgridtables capabilities in a way that the system itself smartly and autonomously tunes multiple knobs at once to calibrate itself to the best possible performance in one instant in time.

Record Organization Problem. Given a gridtable\(R\), a set \(\mathcal{Q}\) of \(n\) queries on \(R\) and a cost function \(f\) that determines the costs to access fields in \(R\) in order to answer the query set \(Q\).

The problem is to find a layout \(L(R)\) such that \(f\) is minimal for all queries in \(\mathcal{Q}\) at once.

This problem cannot be solved efficiently in its optimal version in a feasible amount of time. However, a good solution to this problem enables to autonomously determine a suitable layout for one particular time span in which \(\mathcal{Q}\) is issued (cf. [4, 9, 23] for work towards this direction).

Data Placement Problem. Given a gridtable\(R\), an update-ratio \(\alpha\), a workload by a set \(Q\) of queries having a portion of \(\alpha\) update operations contained, a cost function \(f_{Q}\) that determines the costs of accessing fields in \(R\) for \(Q\), and a cost function \(f_{up}\) that determines the costs for updates on the device memory.

The problem is to find a layout \(L(R)\) for \(R\) such that \(f_{Q}\) is minimal for all queries in \(Q\) at once, and that minimizes the \(f_{up}\) for those data fragments that are stored in the device memory for varying \(\alpha\).

In case of a read-only workload (\(\alpha\equiv 0\)), the data placement problem is the Record Organization Problem. In case of any non-read-only workload (\(\alpha> 0\)), selecting the device as storage- and processing-place for some data only yields higher performance if the cost penalty for update propagation to the device is low. Whether this penalty is low or not (even for write-only workloads with \(\alpha\equiv 1\)), depends whether the selected data is target of updates in \(Q\) or not.

A reasonable solution to the problem is to minimize the surface of data in \(R\) stored in the device that is updated by \(Q\) but to maximize the surface of data in \(R\) not modified by \(Q\) stored in the device to increase the processing performance.

Transition Cost Problem. Given a gridtable\(R\), and a layout \(L_{0}(R)\) for \(R\) that is a solution of the Record Organization Problem for one particular time instant \(t_{0}\), and two time instants \(t_{1},t_{2}\) with \(t_{2}> t_{1}> t_{0}\).

The problem is to determine (or forecast) layouts \(L_{1}(R)\) and \(L_{2}(R)\) as a solution of the Record Organization Problem for \(t_{1}\) resp. \(t_{2}\) , to compute the transition costs \(c_{0\to 1}\) for a transition from \(L_{0}(R)\) to \(L_{1}(R),c_{0\to 2}\) for a transition \(L_{0}(R)\) to \(L_{2}(R)\) , and \(c_{1\to 2}\) for a transition \(L_{1}(R)\) to \(L_{2}(R)\) , and to decide at a time instant \(t_{*}\in(t_{0},t_{2}]\) whether to change from \(L_{0}(R)\) to \(L_{1}(R)\) , or to change from \(L_{0}(R)\) to \(L_{2}(R)\) considering \(c_{0\to 1},c_{0\to 2}\) , and \(c_{1\to 2}\) , or to perform no change at all.

Roughly speaking, staying too long on one particular layout or being too slow in layout adaption leaves performance opportunities untouched. At the same time, too aggressive changes will lead to sub-optimal performance compared to moderate or to slow changes due to transition costs.

A suitable solution to this problem must balance the trade-off such that more suitable layouts are adapted as fast as possible, while – at the same time – the number of sub-optimal performance runs (due to transition costs) must be minimized.

Read Set Labeling Problem. Given a workload \(\mathcal{W}\) consisting of \(N\) queries with a particular ratio \(\alpha\) of transactional and analytical operations where \(\alpha\) is unknown to the system.

The problem is to find and optimally classify regions in the read set \(W\) (i.e., the fields accessed for reads or writes) in order to mark them as attribute-centric or row-centric operation regions.

Obviously, this is not a trivial problem efficiently to solve in an optimal way since partition is already \(\mathcal{NP}\)-complete. However, having this classification promising a good hint for a layout optimizer which then immediately is able to compare current regions in a gridtable matching the regions in the read set.

Wide-Partitioning Problem. Given \(m\) tables \(R=\{R_{1},R_{2},{\ldots},R_{n}\}\), and a series of \(m\) read/write queries \(Q_{1},Q_{2},{\ldots},Q_{m}\) on these \(n\) tables with ratio \(r\), a cost function \(f_{Q}\) that determines the costs to access fields in \(R\) to answer \(Q\), a cost function \(f_{\sigma}\) that determines the costs to access fields for a rewritten (scan) query \(\sigma\) for \(Q\) on \(R_{1}\) ⋈ \(R_{2}\) ⋈ … ⋈ \(R_{n}\), a cost function \(f_{\triangleright\!\!\!\!\triangleleft}\) that determines the costs to construct a WideTable \(R^{*}=(R_{1}\) ⋈ \(R_{2}\) ⋈ \({\ldots}\) ⋈ \(R_{n})\), and a cost function \(m_{Q}(X)\) that determine maintenance costs to update table \(X\) if \(Q\) manipulates data in \(X\).

The problem is to find \(i_{0}\in\{1,2,{\ldots},m\}\) such that (if such an \(i_{0}\) exists)

Informally, the problem is to determine a particular threshold \(i_{0}\) in time during processing of \(Q_{1},Q_{2},{\ldots},Q_{m}\) for which it is cheaper to take the effort in constructing \(R^{*}\) once, and then continue with WideTable scans compared to straightforward execution \(Q_{i_{0}+1},{\ldots},Q_{m}\) (by also considering update costs after that threshold).

As shown by Bian et al. in their work on wide tables, rewriting a query \(Q\) on \(R\) to \(\sigma\) on \(R^{*}\) yields excellent performance improvements for pure analytical processing [13]. In context of \(\mathrm{H}^{2}\)TAP this technique therefore promises an excellent performance gain for the analytical part of queries. However, naive adaptions of WideTables is likewise a bottleneck due to memory limitations to hold the denormalized table \(R^{*}\). Additionally, since \(\mathrm{H}^{2}\)TAP inherently implies additional data writes, update costs of \(R^{*}\) compared to (potentially normalized) tables in \(R\) must be taken into account. Finally, \(\mathrm{H}^{2}\)TAP systems are online systems rather than pure analytical offline systems. Therefore, a solution \(i_{0}\) once found, is immediately target for being re-evaluated once time passes \(m\). Perhaps, a decomposition of \(R^{*}\) back into \(R\) will be the better option then.

Attribute Ordering Problem. Given a grid \(G\) in a layout \(L(R)\) of a gridtable\(R\), and \(m\) sets of queries \(Q_{1},Q_{2},\dots,Q_{m}\) for \(G\) at time \(t_{1},t_{2},\dots,t_{m}\) (\(t_{1}<t_{2}<\dots<t_{m}\)), a function \(f_{miss}\) that determines the number of (processor data-) cache-misses for a query set \(Q\) in \(G\) given a fixed (physical) order of tuplet fields in \(G\) defined by the order of attributes \(A_{1},A_{2},\dots,A_{n}\) in the schema of \(G\).

The problem is to find a sequence of permutations \((\sigma(A_{1}),\sigma(A_{2}),\dots,\sigma(A_{n}))_{i}\) for \(i=1,2,\dots,m\) to physically re-order tuplet fields in \(G\) such that \(f_{miss}\) is minimal for \(t_{1},t_{2},\dots,t_{m}\) with \((\sigma(A_{1}),\sigma(A_{2}),\dots,\sigma(A_{n}))_{k}\) is used at time \(t_{k}\) for query set \(Q_{k}\) ( \(1\leq k\leq m\) ).

The interesting aspect of this problem is that queries in a query set \(Q\) are neither required to read/write a particular subset of tuplets in \(G\), of tuplet fields or of fields in common in a particular order. Consequently, this problem ranges from trivial configurations (such as entire \(Q\) reads all tuplets fields of all tuplets in natural order) to contradicting configurations (such as the first half of \(Q\) reads all tuplet fields of all tuplets in natural order, while the second half of \(Q\) does the same but in inverse natural order).

Finding an optimal solution \(\sigma(A_{1}),\sigma(A_{2}),\dots,\sigma(A_{n})\) for a given \(Q\) is challenging, especially for an online sequence of queries as given in the problem statement.

Null-Region Maximization Problem. Let \(R\) be a a sparse gridtable, \(L(R)\) a layout for \(R\), \(Q\) a set of queries, \(f\) a cost function that determines the costs for accessing fields in \(R\), and \(\varepsilon\) a small threshold from the domain of costs.

The problem is to re-order tuplets in \(R\) and to re-order attributes in the schema of each grid in \(L(R)\) such that for the new layout \(L^{*}(R)\) holds: \(L^{*}(R)\) maximizes the regions that contains null-only values (e.g., by minimizing the number of null-only regions), and the costs for \(Q\) using \(f\) in \(L(R)\) are the same as the costs for \(L^{*}(R)\pm\varepsilon\).

A region in a gridtable\(R\) that completely covers a null-value block of data, does not require additional space for encoding these null-values (cf. Sect. 5.2). This potentially saves space in very sparse data sets. Given the way how regions and grids are managed in a gridtable, the most memory efficient configuration is a small number of regions that are null-value data data only, but each of these regions cover a maximum number of values.

Compression Problem. Given a layout \(L(R)\) of a gridtable\(R\) with \(k\) grids \(G_{1},G_{2},{\ldots}G_{k}\), a set \(C\) of \(n\) compression techniques \(C=\{c_{1},c_{2},{\ldots},c_{n}\}\), a set \(Q\) of queries \(Q=\{Q_{1},Q_{2},{\ldots},Q_{m}\}\) with a query performance of \(p\), and a user-defined lower bound \(\tau<p\) that sets the least acceptable query performance.

The problem is to determine a candidate set \(X\subseteq C\) and \(j=1,{\ldots},k\) permutation \(\pi^{j}:\{1,2,{\ldots},n\}\to\{1,2,{\ldots},n\}\) such that for each \(i\in\{1,2,{\ldots},k\}\) the per-grid compression \((c^{i}_{\pi(n)}\circ\cdots\circ c^{i}_{\pi(2)}\circ c^{i}_{\pi(1)})(G_{i})\) minimizes the space requirements for the entire layout \(L(R)\) while the query performance for \(Q\) must not drop below the threshold \(\tau\).

In the challenging aspect of this problem is not only the determination of the \(i=1,{\ldots},k\) permutations \(\pi_{i}\) to determine the order in which a particular set of compression techniques are applied one after the another to compress a particular grid, which by its own is a computational expensive problem, but that this decision must run for \(k\) grid concurrently while there is a (potential) variety of access pattern in \(Q\) and queries in \(Q\) must not access all grids in \(L(R)\) equally.

In sum, a unified architecture promises the best of all worlds. For instance, the synergy of the compression problem and the attribute ordering problem promises a better solution than both in isolation (cf. [38]). To fulfill the promise of a truly unified architecture, our stated open research challenges must be continuously solved at once during runtime, which is a challenging task.

The field of adaptive data stores is a hot research topic with a series of novel approaches, such as the popular database cracking [22, 24, 28, 29], its variations and analysis [30, 58‐60], advanced partitioning [32, 44, 61] or adaptive resp. holistic indexing [5, 47, 57]. Latest research is done on navigation through the entire data structure design space, and systems adapting to workload and hardware by using machine learning [20, 27, 31], or Just-In-Time data structures as proposed by Kennedy et al. [35]. On the other side of the spectrum, there are also advanced techniques operating on fixed data layouts, such as PAX [2] or Fractured Mirrors [54].

An academic database system that pioneers a notable amount of \(\mathrm{H}^{2}\)TAP features for the relational model is hyper [34]. Originally motivated by the challenge to engineering an \(\mathrm{H}^{2}\)TAP system with competitive performance to pure operational and pure analytical systems by using the UNIX’s fork system call, its storage engine nowadays supports combined horizontal and vertical partitioning including advanced compression of cold data [37]. However, this is in contrast to the partition technique in gridtables: while hyper forces vertical partitioning to a relation first, in our approach it is up to the system whether to start first with horizontal partitioning, or vertical partitioning instead.

A young system is l‑store, a main-memory \(\mathrm{H}^{2}\)TAP database system that supports historic queries [55]. l‑store is powered by a storage engine that performs physical reformatting of tuples on-demand. For this, the primary data container incorporates multiple base pages and tail pages that are used to form an actual tuple. A relation is managed by sub-relations such that each attribute of a table is mapped to one vertical fragment. Although gridstore does not support time-travel (historic) queries in the sense of l‑store, the flexibility of gridstore allows to mimic partitioning to pure-vertical fragments.

Another direction is taken for the development of the database system peloton [9]: its storage engine is built from ground up to support a novel tile-based architecture that manages tables in terms of tile groups. Each such group is a horizontal fragment which may be further vertically partitioned into (inner) partitions called logical tiles. The partition schema of peloton is more restrictive than the one we present in this paper, but shares important ideas such as the autonomous self-adaption of the layout depending on workload optimization. One special feature of peloton is its ability to forecast changes in the workload and to trigger adaption proactively [40]. At this point of this writing, gridtables do not support the orthogonal feature of forecasting, or adopting learned optimization models, but we are researching in this direction [19].

An adaptive storage engine veteran is hyrise [23], which organizes a relation by \(n\) sub-relations, called containers. Each container holds a certain amount of attributes: when a container incorporates exactly one attribute, the sub-relation becomes de facto a columnar format. hyrise allows both formats for records columnar and row-wise. This storage engine automatically changes the number of attributes particular containers own in order to improve cache efficiency in face of changing workloads. Similar, the \(\mathrm{H}_{2}\mathrm{O}\) [4] storage engine manages both, columnar and row-wise formatted partitions for a single table following a strict horizontal partitioning similar to hyrise. \(\mathrm{H}_{2}\mathrm{O}\) applies changes in that the partitioning is done in a lazy fashion when compared to hyrise by applying a new partitioning schema after careful evaluation in the background. gridtables and both, hyrise and \(\mathrm{H}_{2}\mathrm{O}\) share the required idea of autonomous adaption of partitions without manual tuning by a human administrator. However, the space of potential partitions for a single table in gridtables is far larger compared to these approaches since gridtables allows for an arbitrary order of horizontal and vertical partitioning.

In this paper, we propose a novel concept to manage records for \(\mathrm{H}^{2}\)TAP database systems, called gridtables. We showed how mixed workloads affect the query performance. Then, we stated requirements for an \(\mathrm{H}^{2}\)TAP store, and showed our proposal of a stacked architecture built on a set of well-engineered indirection levels for secure, safe and well-defined data access in face of arbitrary data placement and formatting. Based on our concept for a One-Size-Fits-Most architecture, we explored our list of formally defined open research challenges that focus on automatic instrumentation of gridtable features: (i) Read Set Labeling to label workload parts as analytical resp. transactional, (ii) Record Organization to find layout for table to optimize for read set, (iii) Wide-Partitioning to decide on (de-)normalize action for infinite horizon (iv) Data Placement to find optimal placement of data, (v) Attribute Ordering to find optimal order of attributes, (vi) Null Maximization to find maximum regions for null-data, and (vii) Transition Costs to approximate data moving & partitioning action costs, and (viii) Compression to compress grids individually while not sacrificing performance. To fulfill the promise of best performances, we motivated for further investigation these eight open research challenges for storage structures as flexible as gridtables.