返回主题:存储常用数据结构

知识卡片

普通读书笔记卡 · 2280.j.11.a

列存的排序与写入

理解等级:高级

排序:列存储默认按插入顺序存,追加最简单;也可以像 SSTable 一样指定顺序作为索引机制。但不能每列各自排序,否则无法知道哪些值属于同一行——必须整行一起排序,由管理员根据常用查询选排序键:

  • 第一排序键:如常按日期范围查询,就用 date_key,查询只需扫描相关时间段;
  • 第二排序键:如 product_sk,让同一天同一产品的销售聚在一起;
  • 排序还帮助压缩:第一排序键若取值不多,排序后形成长串重复值,游程编码可把数十亿行的列压到几 KB;第二、三排序键效果递减,排序优先级低的列基本随机,难以压缩。

多个排序顺序(C-Store 提出,Vertica 采用):数据本来就要复制到多台机器防丢失,不如让各副本按不同顺序排序,查询时选最匹配的版本。这类似行存中的多个二级索引,区别在于列存中没有指向数据的指针,只有包含值的列。

写入:压缩、排序的列无法像 B 树那样就地更新,在排序表中间插一行可能要重写所有列文件。解决方案是 LSM 树:写入先进入内存中的有序结构(行存还是列存无所谓),积累够了再与磁盘列文件合并、批量写新文件(Vertica 的做法);查询同时检查磁盘列数据和内存中的新写入,由优化器对分析师隐藏差别。

相关澄清:

  • Cassandra、HBase 的“列族”继承自 Bigtable,但每个列族内把一行所有列与行键存在一起且不做列压缩,本质上仍面向行,称为面向列有误导性;
  • 列存还能更好利用 CPU:把压缩列数据放进 L1 缓存,在没有函数调用的紧凑循环中处理,按位与、或直接作用于压缩块,即向量化处理。
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据密集型应用系统设计》第03章《第三章:存储与检索》列存储·列存储中的排序顺序;写入列存储(源文件:extracted/数据密集型应用系统设计/_epub-src/ch3_split_004.html,来源项目 book-sources) - 结论依据:第三章“列存储中的排序顺序”说明不能逐列独立排序、按常用查询选排序键、排序对游程压缩的作用和C-Store/Vertica的多排序顺序;“写入列存储”说明用LSM树解决列存写入;“面向列的存储和列族”与“内存带宽和向量处理”澄清列族仍面向行并介绍向量化处理。 - 原始内容:注意,每列独自排序是没有意义的,因为那样我们就不会知道列中的哪些项属于同一行。