[CMU-15-445/645] Database Storage - Part 2

这是我在学习Databases Systems CMU 15-445/645/ Fall 2019过程记录的一些笔记，这次学习的第四课，主要是关于数据库存储的第二部分，主要是分析了 tuple 的不同存储方式。

数据表现方式 Data Representation

Tuple Storage

在内部存储的时候， tuples 只是一系列的字节数组，在使用的时候 DBMS 根据其内部存储的 schema 数据去推断 tuple 的组织方式来读取它。

数据的表现形式在不同层面有不同表现：

C/C++ 表现方式： INTEGER/BIGINT/SMALLINT/TINYINT
IEEE-754 标准和定点小数（浮点 vs. 定点）：
- FLOAT/REAL vs. NUMERIC/DECMAL
表头： VARCHAR/VARBINARY/TEXT/BLOB
时间表现方式（Unix epoch 之后的（微）秒数）：TIME/DATE/TIMESTAMP

数字的存储方式

DBMS 的用户只需要关注最后两种，前两种由开发者考虑（主要是第二个两种表现方式的区别），对于第一种而言，这种数据类型主要是用了原生的 C/C++ 的数据类型，也是符合 IEEE-754 标准的，通常来说操作会比较快（CPU 有写好的指令，不需要额外操作），但是有的时候会有 rounding 的问题，具体参考以下两段代码。

#include <stdio.h>

int main() {

    float x = 0.1;
    float y = 0.2;

    // not rounding
    printf("x + y = %f\n", x + y);
    printf("0.3 = %f\n", 0.3);

    // rounding, error occurs!
    printf("x + y = %.20f\n", x + y);
    printf("0.3 = %.20f\n", 0.3);
}

他的输出是：

x + y = 0.300000
0.3 = 0.300000
x + y = 0.30000001192092895508
0.3 = 0.29999999999999998890

出现这样问题主要是因为硬件没办法存储固定位数的小数，为了解决 rounding 的问题，我们需要考虑用定点小数去存储数据，这个时候我们考虑用一种类似VARCHAR 的方式（不过不是存成字符串）去存储一组定长的二进制表示并且有元数据（存储位数等等）说明的方式去存储。

Postgres 内部的数字存储方式如下（也是一种定点数存储方法）,对于这种方式存储，数字的操作方式会需要很多额外的考虑（为什么比浮点数计算速度慢的原因）：

typedef unsigned char NumbericDigit;
typedef struct {
    int ndigits; // # of digits
    int weight; // weight of 1st digit
    int scale; // scale factor
    int sign; // positive/negative/NaN
    NumericDigit *digits; // digit storage
} numeric;

大尺寸的值的存储

通常来说， DBMS 不允许单个 tuple 的尺寸超过一定值，对于 tuple 里面某些比较大的参数，有不同的处理方式：

将超过规定的值存在一个单独的页面（overflow page）里，在 tuple 内部用一个指针指向它，如下图所示，这样做的原因是当 tuple 崩溃的时候不希望会影响到这个参数，通常比较大的参数大部分时候不需要 update，常用的操作是 read，常用的 DBMS 的 overflow page 有：
- Postgres: TOAST (>2KB)
- MySQL: Overflow (>½ size of page)
- SQL Server: Overflow (>size of page)
还有一种做法是将内容存在外部文件( BLOB 类型)里面，然后用指针指向该文件的位置，如下图所示。但是 DMBS 不能更改外部文件，只能读取，而且没办法对文件保护（如果其他进程对文件进行修改的话），用这种方法的 DBMS 有：
- Oracle: BFILE data type
- Microsoft: FILESTREAM data type

System Catalogs

一个 DBMS 会将与数据有关的一些元数据存储到它内部的目录里：包括表格，列，索引，用户和权限还有内部统计数据等等。同时这个目录会和数据库的内容一起存在 DBMS 里。

用户可以通过查询 DBMS 的 INFORMATION_SCHEMA 目录来获得关于该数据库的内部信息：这是 ANSI 的标准规定一个只读的方式来提供关于数据库的信息。同时，不同的 DBMS 也有自己的方式（快捷键）来获得信息，如下图所示。

关系模型没有规定我们必须将 tuple 的所有参数都存放在一个单独page上，因为在某些情况下这样未必是最好的布置方式，下面以 Wikipedia 举个例子：

下图是三个 table:

我们主要考虑两种工作模式（workload）：

On-line Transaction Processing (OLTP): 每次查询从外部读取一小部分数据然后存入（更新）本地数据库中，通常是用户第一次搭建（安装）应用要做的步骤，对应的维基百科例子操作如下所示：

// 更新页面
SELECT P.*, R.*
    FROM pages AS P
  INNER JOIN revisions AS R
    ON P.latest = R.revID
  WHERE P.pageID = ?

// 登陆账户
UPDATE useracct
    SET lastLogin = NOW(),
        hostname = ?
    WHERE userID = ?

1
2
3

// 插入数据
INSERT INTO revisions
    VALUES (?,?…,?)

另一种工作模式是 On-line Analytical Processing (OLAP): 一次读取大量数据计算计算处理，但是不对数据进行更新，对应的维基百科例子如下：

// 计算一些统计数据
SELECT COUNT(U.lastLogin),
    EXTRACT(month FROM
        U.lastLogin) AS month
  FROM useracct AS U
 WHERE U.hostname LIKE '%.gov'
 GROUP BY
  EXTRACT(month FROM U.lastLogin)

两种工作方式和读写关系如下图，这里不讨论HTAP：

Storage Models

在了解两种工作方式，我们可以开始考虑存储模型。DBMS 针对 OLTP 或者 OLAP 工作方式可以有不同的方式去存储 tuples。目前我们假定统一用 n-ary 存储方式（行存储）。

N-ary Storage Model (NSM)

用这种模型 DBMS 连续存储 tuple 的所有参数在一页里，tuple 之间也是连续存放。这种方式对 OLTP 比较有利，因为大部分时间只需要读取/更新/插入单条信息（tuple），如下图所示。

下面是一个简单的查询过程演示，这种情况下每次只插入一个 tuple，这种存储方式比较快捷：

对于下面的例子，NSM 的存储方式比较不好，因为查询过程不得不访问（读取）所有的 tuple，哪怕我们只需要其中两个参数，效率比较低

总结一下， NSM 的优缺点分别是：

优点：

快速插入，更新和删除
对于需要整个 tuple 的查询指令比较友好

缺点：

对于扫描某组参数的查询指令不友好（效率低）

DECOMPOSITION STORAGE MODEL (DSM)

针对上面的问题，还有第二种存储模型，这种存储模型按参数将所有值连续存放（也被称为列模型），对于 OLAP 工作模型（需要扫描（只读取）所有 tuple 的某个参数）比较友好，对应的例子如下所示：

在这种情况下，我们怎么识别哪个参数对应哪个 tuple 呢？有两种方法选择：

固定长度的偏移（fixed-length offsets）:每个值保存成相同的长度；
嵌入 id（embedded tuple ids）每个值额外存储一个 tuple id 值用于识别，比较浪费空间。

总结一下， DSM 的优缺点分别是：

优点：

减少需要的I/O数（只读取需要的数据）
因为同一个page 保存的是相同的类型，所以可以有数据压缩的方法

缺点：

对于查询（插入，更新，删除）单个 tuple 效率较低。

目前绝大部分系统都有 DSM 存储方式。