行存表实现原理

EMR Serverless StarRocks 的行存能力，提供高QPS的点查和点更新能力，适用于在线服务服务场景。本文将介绍行存的实现原理和基本特性。

1 实现原理

StarRocks中行存表的数据，会根据建表语句中指定的Key字段，将数据划为Key和Value两组，并分别属于Key组的和Value组的数据按照一定编码格式进行编码，最后转化为key-value方式进行存储：

行存表提供较高的点查QPS，离不开行存表的实现特性。

2 特性

2.1 短路读写

SQL 执行一般要经过优化器、分布式调度、分布式执行引擎等多个组件，会占用较多资源。行存表对于包含全部主键的查询或包含主键前缀的查询，通过短路径，可以跳过这些组件，减少额外的开销。同时减少并发调度资源的浪费，可以大幅提高执行效率和并发能力。
例如，行存表 R(pk1, pk2, pk3, v1, v2, ...) 的主键为 (pk1, pk2, pk3)。

• 单行 / 多行点查

SELECT * FROM table WHERE pk1 = 1 AND pk2 = 2 AND pk3 = 3;
SELECT v1, v2, v3,... FROM table WHERE pk1 IN (1,2) AND pk2 = IN(3,4} AND pk3 = 5;

• PrefixScan 范围查询

SELECT col1,col2,col3,... FROM table WHERE pk1 = 1;
SELECT col1,col2,col3,... FROM table WHERE pk1 = 1 AND pk2 < 2 limit 10;

• 单行 / 多行写入 / 更新 / 删除

INSERT INTO table(v1, v2, v3,...) VALUES(?,?,?..);
INSERT INTO table(v1, v2, v3,...) VALUES(?,?,?..),(?,?,?..);
UPDATE table SET v1 = 4, v2 = 5 WHERE pk1 = 1 AND pk2 = 2 AND pk3 = 3;
DELETE FROM table WHERE pk1 = 1 AND pk2 = 2 AND pk3 = 3;

2.2 Preparestmt

为了减少 SQL 解析和表达式计算的开销， 在 FE 端提供了与 MySQL 协议完全兼容的PreparedStatement特性。开启PreparedStatement后，SQL 对应的计划会缓存在 Session 级别的缓存中，后续的查询直接使用缓存对象。

• JDBC使用Preparestmt

  ## URL中添加useServerPrepStmts配置
  "jdbc:mysql://${FE地址}:9030/?useServerPrepStmts=true";
  

• SQL使用Preparestmt

  PREPARE stmt1 FROM INSERT INTO demo.prepare_stmt VALUES (?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?);
  SET @i = 1;
  SET @v = '1';
  SET @b = true;
  SET @t = '2021-02-01 00:00:12';
  EXECUTE stmt1 USING @i, @i, @i, @i, @v, @b, @t, @v, @t, @v, @i;
  DROP PREPARE stmt1;
  

2.3 查询范式

2.3.1 前缀查询

当查询的 Where 条件中指定了所有主键的 eq 或 in 条件时，行存的短路读能力可以精确定位需要读取的数据。若查询的 Where 条件只制定了部分主键的条件，且这些主键构成行存表主键的前缀，那么前缀查询能力有助于减少扫描的数据量，从而加速查询相应时间。
例如，行存表 R(pk1, pk2, pk3, v1, v2, ...) 的主键为 (pk1, pk2, pk3)。

• 查询 A

select * from R where pk1 = 1 and pk2 = 2 and pk3 = 3
触发短路读，会扫描主键 (1, 2, 3) 对应的行。

• 查询 B

select * from R where pk1 = 1 and pk2 = 2
是前缀查询，会扫描主键 (1, 2, MIN) .. (1, 2, MAX) 范围内的行。

• 查询 C

select * from R where (pk1 between 1 and 10) and pk3 = 3
是前缀查询，会扫描主键 (1, MIN, MIN) .. (10, MAX, MAX) 范围内的行。

条件pk3 = 3不是前缀的一部分，因此无法帮助减少扫描量。建议将过滤效果好的列排列于建表语句中主键列靠前的位置。

• 查询 D

select * from R where pk1 = 1 and pk2 in (2,4) and (pk3 between 3 and 10)
是前缀查询，其前缀包含了所有主键，但不是 eq 或 in 条件。这个会扫描两个范围

• 主键 (1, 2, 3) .. (1, 2, 10) 范围内的行

• 主键 (1, 4, 3) .. (1, 4, 10) 范围内的行

2.3.2 Limit裁剪

如果行存上的查询存在 Limit，且没有其他的过滤条件时，在实际执行时会自动优化将并发度设置为 1，只会调度到一台机器上，减少数据扫描量和并发调度资源的浪费。Limit 裁剪类似于短路优化，但作用于正常优化器链路中，优化调度策略，可以覆盖短路链路无法覆盖的场景。

SELECT * FROM R LIMIT 10;
SELECT * FROM (SELECT * FROM R WHERE R.pk1 = 1 limit 10), S WHERE R.pk1 = S.a AND S.b = 1

2.3.3 TopN优化

暂时无法在飞书文档外展示此内容

行存在存储上是按照 Key 有序的，如果查询的 Order By 字段是表 Key 的前缀，会自动优化消除 Order By，减少扫描量。
例如，行存表 R(pk1, pk2, pk3, v1, v2, ...) 的主键为 (pk1, pk2, pk3)。

SELECT * FROM table WHERE pk1 = 1 AND pk2 = 2 AND pk3 = 3 order by pk1 limit 10;
SELECT * FROM table WHERE pk1 = 1 AND pk2 = 2 AND pk3 = 3 order by pk1, pk2, pk3 limit 10;

2.3.4 Key Only Scan

行存的底层存储格式是 key-value 形式，key 对应表中的主键，value 是剩下的字段。如果行存表上的查询中只涉及到主键，那么就可以只扫描 key 对应的主键，无需扫描和返回 value 对应的字段，大幅优化数据扫描、网络、解码开销。 对于 count(*) 类似的查询还会进一步优化，跳过对 key 的处理逻辑，进一步优化查询时间。
例如，行存表 R(pk1, pk2, pk3, v1, v2, ...) 的主键为 (pk1, pk2, pk3)。

select count(distinct pk1) from R where pk2 > 1;

2.3.5 RuntimeFilter

Runtime Filter 是一种特殊的 Filter。Filter 中的谓词并非由 SQL 直接指定，而是在执行时动态产生。具体实现原理是：当两表进行 Join 关联查询时，会先扫其中较小的一张表，从而得到能够参与 Join 的 Join Key 范围，并以此为条件对另一张表（大表）进行过滤，以进行数据裁剪，减少IO和网络开销。先扫的小表称为 Runtime Filter 的 Build 端，大表称为 Probe 端。

Runtime Filter 有多种分类方式。例如，当 Join Key 较少时，StarRocks 会构建 In 值的 Runtime Filter，过滤效果最好。当 Join Key 较多时，会构建额外开销较低的 Bloom Filter 或 Min-Max Runtime Filter。

此外，如果 Build 端的数据是通过 broadcast 广播到所有节点上的，那么每个节点都能获得全量数据用于构建 Runtime Filter，此时 Probe 端会确保 Build 端执行完成才开始执行，这种 Runtime Filter 称为 Local Runtime Filter。反之，如果 Build 端的数据是通过 shuffle 均分到各个节点上，那么每个节点只能构建出部分数据的 Runtime Filter，他们必须经过汇总才能被 Probe 端使用。这种 Runtime Filter 称为 Global Runtime Filter。

如果 Runtime Filter 作用在主键的前缀上，那么行存表支持对 Runtime Filter 进行下推。这一点和前缀查询类似。
例如，行存表 R(pk1, pk2, v1, v2, ...) 的主键为(pk1, pk2)；表S(a, b)为一张小表。考虑查询
select * from R join S where R.pk1 = S.a and S.b = 1
该查询会先用条件S.b = 1扫描表 S，并构建出 S.a 上的 Runtime Filter，比如 S.a in {1, 2}。行存表会将这个条件下推，虽然查询没有对 R 表指定任何谓词，但是实际扫描 R 表时只会扫描主键 (1, MIN, MIN) .. (2, MAX, MAX) 范围内的行。

如果 Runtime Filter 包含了所有主键，且每个主键都指定了 in 范围，那么还支持把范围查询转为多点查询。考虑查询
select * from R, S1, S2 where R.pk1 = S1.a and R.pk2 = S2.a
其中 S1，S2 为小表。执行时，会先扫表 S1 和 S2，并构建出 Runtime Filter。假设构建出 S1.a in {1, 10} 和 S2.a in {2, 100} 这样两个 Runtime Filter。那么行存表会通过两个条件得出 4 个主键点：(1,2), (1,100), (10,2), (10,100)，从而大幅加速查询。

如果 Join 条件不包含任何主键，或不是主键的前缀，那么生成的 Runtime Filter 无法下推存储以减少 IO 量。但是执行时，依然会在数据扫出后利用 Runtime Filter 进行一次过滤，以减少网络开销。

您可以通过一些参数配置 Runtime Filter 的行为：

您可以通过以下指标监测 Runtime Filter 是否成功下推。
未下推：从原表扫描 73k 行，经过 Runtime Filter 后保留 366 行

成功下推：从原表扫描 366 行，更多详情请参考：https://forum.mirrorship.cn/t/topic/1530

2.3.6 LookupJoin

2.4 事务原理

行存表支持一定的事务能力：支持单行数据的插入、更新、删除的事务性。由于在表级别加写锁，会导致同一个表中多个事务只能串行执行，影响读写效率，所以行存表没有提供表级别加写锁，因此不支持多行数据的写、更新等事务能力。

2.4.1 Compare-and-Swap (CAS)能力

对于行存表进行Update操作时，会对行存表的值进行检查，如果行存表中存储的信息和发送Update请求时存储的信息相同时，则更新行存表数据，否则不更新，并将部分冲突的信息返回控制台。该过程称之为 compare-and-swap (CAS)，该过程类似于下面的代码。该功能用于多并发之间数据的同步。

prevValue = get(key);
if (prevValue == request.prevValue) {
    put(key, request.value);
}

示例

1. 步骤1：创建行存表，并插入一定数据：

CREATE TABLE IF NOT EXISTS demo.t1
(k1 int, k2 int, v1 varchar(16), v2 DATE, v3 TINYINT)
ENGINE=ROW_STORE
PRIMARY KEY (k1, k2);

INSERT INTO demo.t1(k1, k2, v1, v2, v3) VALUES (1, 2, 'a', "2222-12-22", 33);
INSERT INTO demo.t1(k1, k2, v1, v2, v3) VALUES (1, 3, 'b', "2222-12-22", 34);
INSERT INTO demo.t1(k1, k2, v1, v2, v3) VALUES (1, 4, 'c', "2222-12-22", 35);
INSERT INTO demo.t1(k1, k2, v1, v2, v3) VALUES (2, 3, 'd', "2222-12-22", 36);

2. 步骤2：启动3个并发，执行Update操作

let i=1
while [ $i -le 3 ];do
  mysql -h{FE地址}  -P 9030 -u{Your User}  -p{Your Password} -e "UPDATE demo.t1 set v1 = 'a$i' WHERE k1 = 1" -vvv &
  let i+=1
done

3. 查看上述命令的执行日志

Query OK, 3 rows affected (0.026 sec)
{'label':'update_5992032d-5924-11ee-833b-00163e241380', 'status':'VISIBLE', 'txnId':'-1'}

ERROR 1064 (HY000) at line 1: There were some key conflicts during updating: (k1:1, k2:3), (k1:1, k2:4)

Query OK, 3 rows affected (0.029 sec)
{'label':'update_5992514e-5924-11ee-833b-00163e241380', 'status':'VISIBLE', 'txnId':'-1'}

从这个日志看出，在第二次执行Update操作时，发现数据有冲突了，此时不会对数据进行更新。