# Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads

## Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads

### 引言

 We also present a technique to continuously evolve the database’s physical storage layout by analyzing the queries’ access patterns and choosing the optimal layout for different segments of data within the same table. To evaluate this work, we implemented our architecture in an in-memory DBMS. Our results show that our approach delivers up to 3× higher throughput compared to static storage layouts across different workloads.


### 基本思路

#### Logical Tile

A logical tile succinctly represents values spread across a collection of physical tiles from one or more tables. The DBMS uses this abstraction to hide the specifics of the layout of the table from its execution engine, without sacrificing the performance benefits of a workload-optimized storage layout.


#### Logical Tile Algebra

• Bridge Operators，大部分的在logical tile上面的关系代数都是直接使用的logical tile，对下面的physical tile不敏感。这里存在两种情况需要直接感知存储的具体情况，一个就是在上面的查询树的最下面的操作和最上面的操作。这里将这些操作叫做bridge operators(它们需要联系logical tiles和physical tile)。这样的操作包括对表的顺序扫描和根据索引查找。以顺序扫描为例，这个操作会生成为每一个tile group 一个logocal tile，每一个logical tile只会有一行，每一行是一个这个tile tuple在这个group中保存的偏移值，

In Figure 5, the sequential scan (σ) operator associated with R emits logical tiles that represent the tuples that satisfy the predicate a=1. The index scan operator identifies the tuples matching the predicate using the index, and then constructs one or more logical tiles that contain the matching tuples.


DBMS可以通过materialize将logical tile转化为physical tile。在上面的表示查询树的图中，最上面的聚合操作之后，需要将结构发送给客户端，就是使用 materialize operator (Ω)获取physical tile。这里不需要重新构造physical tile，直接处理下面的physical tile就可以了。

### 并发控制

• TxnId: A placeholder for the identifier of the transaction that currently holds a latch on the tuple.

• BeginCTS: The commit timestamp from which the tuple becomes visible.

• EndCTS: The commit timestamp after which the tuple ceases to be visible.

• PreV: Reference to the previous version, if any, of the tuple.


### 布局重排

• 决定哪些字段分在一个tile tuple，这里使用的是基于监控过去查询历史的方式.算法分为两个部分，如下面的图所示。第一个部分是使用一个clustering algorithm决定哪些字段应该被放到一个tile tuple。在第二步，使用第一步得到的数据使用基于贪心的算法计算出最终的存储布局，

Our approach leverages the query statistics to compute the layout in two stages. As shown in Algorithm 1, it first employs a clustering algorithm to determine which set of attributes should be stored together in the same physical tile. It then uses a greedy algorithm that uses the output of the clustering algorithm to generate a workload-aware tile group storage layout.

• 如果在运行的时候改变布局，这里使用了渐进式的办法。每次移动一个数据到新的布局上面，然后使用原子指令相关结构，旧的数据会被DBMS在适当的时候回收，

Any concurrent delete or update operation only modifies the versioning metadata that is stored separate from the physical tiles. The newly constructed tile group refers to the versioning metadata of the older tile group. The storage space consumed by the physical tiles in the older tile group is reclaimed by the DBMS only when they are no longer referenced by any logical tiles. Due to its incremental nature, the overhead of data layout reorganization is amortized over multiple queries.


## 拓展

### PAX

PAX(Partition Attributes Across)的思路其实很简答，就是将一个Page再划分为更加小的Page。叫做Mini-Page。这里就是将不同的属性放在不同的Mini-Page里，可以理解为这里就是在一个Page里面的数据的重新组织。

## 参考

1. Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads, SIGMOD’16.