Understanding Indexing

Without Needing to Understand Data Structures

MySQL UC 2011 – April 12, 2011

Zardosht Kasheff

什么是表？

（key,value）对集合的词典

1. 确保你可以 修改 这个词典（插入、删除、修改）和 查询（点查询、范围查询）词典
2. B-Tree和Fractal Tree是两个词典的例子
3. 哈希则不是（不支持范围查询）

例子：

CREATE TABLE foo (a INT, b INT, c INT, PRIMARY KEY(a));

然后我们插入一批数据

a	b	c
100	5	45
101	92	2
156	56	45
165	6	2
198	202	56
206	23	252
256	56	2
412	43	45

一个key定义了词典的排序规则

1、对于数据结构和存储引擎我们会认为，在排序上进行范围查询是 快速 的

2、在其它顺序上的范围查询会进行表的扫描，这个操作是 很慢 的

3、点查询需要检索一个特定的值也是 慢 的

一个点查询是快速的，但是读取一批行用这种方法会比使用按顺序的范围查询慢2个数量级

词典 T 上的索引 I 也是一个词典

1、同样我们需要定义一个（key,value）对

2、索引上的key是主词典上的列的子集

3、索引I的值是T的主KEY

还有其它的方法去定义这个值，但我们还是坚持使用T的主KEY来定义这个值

例子：

ALTER TABLE foo ADD KEY(b);

然后我们得到

Primary

a	b	c
100	5	45
101	92	2
156	56	45
165	6	2
198	202	56
206	23	252
256	56	2
412	43	45

Key(b)

b	a
5	100
6	165
23	206
43	412
56	156
56	256
92	101
202	198

问题：COUNT( * ) WHERE a<120;

100 5 101 92

=>

2

问题：COUNT( * ) WHERE b>50;

56 156 56 256 92 101 202 198

=>

4

问题：SUM( c ) WHERE ｂ >５０;

快 56 156 56 256 92 101 202 198

=>

慢 156 56 45 256 56 2 101 92 2 198 202 56

=>

１０５

索引的好处？

１、索引使得查询变得快速

索引会提升部分查询请求的速度

２、需要在心里根据查询设计索引

选出最重要的查询给它们设计索引

考虑索引本身的代价

设计一个好的索引有３个规则可以参考

1、避免任何数据结构的细节

Ｂ树和分形树对于计算机科学家来说是有趣和好玩的，但这三个规则同样适用于其它数据结构

所有我们需要考虑的是范围查询是快速的（对每行）而点查询则慢的多（对行）

2、世界上没有绝对的规则

索引像是一个数据问题

规则有帮助，但每个方案都有自己的问题，需要分析解决问题的方法

3、也就是说规则有很大的帮助

三个规则

１、查询较少的数据

少的带宽，少的处理…

２、减少点查询

数据访问成本是不一样的

顺序访问数据比无序访问  **快的多**

３、避免排序

GROUP BY和ORDER BY查询需要后期的检索工作

索引在这种查询中可以帮助获得ＲｏｗＩＤ

我们来分别看下这三种规则

规则１：查询较少的数据

Rule１：慢查询的例子

表：（100万行数据，没有索引）

CREATE TABLE foo (a INT, b INT, c INT);

查询（匹配１０００行数据）

SELECT SUM(c) FROM foo WHERE b=10 and a<150;

查询计划：

行b=10 AND a<150可以在表的任何地方

没有索引的帮助，整个表都会被扫描

执行速度慢：

检索１００万行数据仅仅查询１０００行数据

Rule１：如何去添加一个索引

1、我们应该怎么去做？

减少检索到的数据
分析远少于１００万的数据行

2、怎样做（对于一个简单的查询）？

设计索引时着眼于WHERE子句
    由查询关注那些行来决定
    其它行的数据对于这个查询来说并不重要

对于查询 SELECT SUM( c ) FROM foo WHERE b=10 and a<150;

Rule１：那个索引？

选择１：Key(a)

选择２：Key(b)

那个更好？由select来决定：

如果WHERE a<150的数据行更少，key(a)更好

如果WHERE b=10的数据更少，key(b)更好

选择３：key(a) AND key(b),然后MERGE我们稍后会进行讨论

Rule１：选择最好的索引

key(a)与key(b)都不是最佳的

考虑：

WHERE a<150有20万行数据

WHERE b=10有10万行数据

WHERE b=10 AND a<150有1000行数据

然后key(a)和key(b)都会检查很多的数据

为了获得更好的性能，索引必须尝试尽量优化WHERE条件

我们需要复合索引

复合索引可以减少数据检索

WHERE条件：b=5 AND a<150

选择１：key(a, b)

选择２：key(b, a)

问题又来了那种选择更好？

Key(b, a)！

索引规则：

当创建一个复合索引，需要对每个列进行检查，条件b是相等判断，但在a上不是。

问题：WHERE b=5 and a>150;

a b c 100 5 45 101 6 2 156 5 45 165 6 2 198 6 56 206 5 252 256 5 2 412 6 45

b,a a 5,100 100 5,156 156 5,206 206 5,256 256 6,101 101 6,165 165 6,198 198 6,412 412

复合索引：没有平等的条件

如果WHERE条件是这样的：

WHERE a>100 AND a<200 AND b>100;

那个更好？

key(a),key(b),key(a,b),key(b,a)?

索引规则：

只要复合索引不被用于相等查询，复合索引的其它部分不会减少数据检索量

key(a,b)不再比key(a)好

key(b,a)不再比key(b)好

问题：WHERE b>=5 AND a>150;

a b c 100 5 45 101 6 2 156 5 45 165 6 2 198 6 56 206 5 252 256 5 2 412 6 45

b,a a 5,100 100 5,156 156 5,206 206 5,256 256 6,101 101 6,165 165 6,198 198 6,412 412

=>

5,156 156 5,206 206 5,256 256 6,101 101 6,165 165 6,198 198 6,412 412

复合索引：另一个例子

WHERE条件：b=5 AND c=100

key(b,a,c)和key(b)一样好
因为a没有在条件中使用，所以在索引中包含c并不会有帮助，key(b,c,a)会更好

a b c 100 5 100 101 6 200 156 5 200 165 6 100 198 6 100 206 5 200 256 5 100 412 6 100

b,a,c a 5,100,100 100 5,156,200 156 5,206,200 206 5,256,100 256 6,101,200 101 6,165,100 165 6,198,100 198 6,412,100 412

=>

5,100,100 100 5,156,200 156 5,206,200 206 5,256,100 256

规则１：总结

根据查询条件设计复合索引

把相等条件的查询列放在复合索引的开始位置

保证第一个非相等条件的列在索引中越有选择性越好

如果复合索引的第一个列没有被相等条件来使用，或者没有在条件中使用，复合索引的其它列对于减少数据的检索没有帮助

    是否就表明它们是无用的呢？

    它们在规则２中可能有用

规则２：避免点查询

表：

CREATE TABLE foo (a INT,b INT,c INT,PRIMARY KEY(a), KEY(b);

查询：

SELECT SUM( c ) FROM foo WHERE b>50;

查询计划：使用key(b)

因为随机的点查询的原因，对每个行都进行检索的代价很大

问题：SUM( c ) WHERE b>50;

a b c 100 5 45 101 92 2 156 56 45 165 6 2 198 202 56 206 23 252 256 56 2 412 43 45

b a 5 100 6 165 23 206 43 412 56 156 56 256 92 101 202 198

56 156 56 256 92 101 202 198	=>	156 56 45 256 56 2 101 92 2 198 202 56	=>	105

还是这张表，但查询计划不同了

SUM(c) WEHRE b>50;

查询计划：扫描主表

每行的检索成本低

但是需要检索很多行

问题：SUM( c ) WEHRE b>50;

a b c 100 5 45 101 92 2 156 56 45 165 6 2 198 202 56 206 23 252 256 56 2 412 43 45

=>

105

如果我们添加了另一个索引会怎么样？

如果添加key(b, c)呢？

由于我们在b上有索引，我们只检索我们需要的行

由于索引包含Ｃ的信息，我们不再需要再去检索主表了。  **没有点查询了**

覆盖索引：索引覆盖一个查询，如果这个索引包含足够的信息来回答这个查询。

例子：

问：SELECT SUM( c ) FROM foo WHERE b<100;

问：SELECT SUM( b ) FROM foo WHERE b<100;

索引：

key(b, c): 对第一个查询是覆盖索引

key(b, d)：对第二个查询是覆盖索引

key(b, c, d)：对每个索引都是覆盖索引

如何去构建一个覆盖索引

把检索的每个列都包含进去，并不仅仅是查询条件

问：SELECT c,d FROM foo WHERE a=10 AND b=100;

错误：ADD INDEX(a, b)

并不是覆盖索引。仍然需要点查询去检索c和d的值

正确：ADD INDEX(a, b, c, d)

包含所有相关的列

按照规则１规定把 a 和 b 放在索引开始位置

如果主键匹配ＷＨＥＲＥ条件呢？

问题：SELECT sum(c) FROM foo WHERE b>100 AND b<200;

SCHEMA:CREATE table foo (a INT, b INT, c INT, ai INT AUTO_INCREMENT, PRIMARY key(b, ai));

查询在主词典上做了范围查询

只有一个词典会按顺序访问到

这个查询很快

主键覆盖所有查询

如果排序规则匹配查询条件，问题得到解决

什么是聚簇索引

如果主键不匹配查询条件呢？

理想的情况下，必须确保辅助索引包含所有列

存储引擎不会让你去这样做

有一个例外。。。。TokuDB可以

TokuDB允许你定义任何聚簇索引

一个聚簇索引包含所有的查询，就像主键做的一样

聚簇索引的实践

问：SELECT SUM(c) FROM foo WHERE b<100;

问：SELECT SUM(b) FROM foo WEHRE b>200;

问：SELECT c,e FROM foo WEHRE b=1000;

索引：

key(b, c)：第一个查询

key(b, d)：第二个查询

key(b, c, e)：第一个和第三个查询

key(b, c, d, e)：所有的三个查询

索引需要大量的查询分析

考虑那个会涵盖所有的查询：

聚簇索引 b

聚簇索引可以让你更加关注于查询条件

它们减少了点查询并且使查询更加快

聚簇索引更多的信息：索引合并

例子：

CREATE TABLE foo (a INT, b INT, c INT);

SELECT SUM(c) FROM foo WHERE b=10 AND a<150;

假设：

a<150有２０万行数据

b=10有10万行数据

b=10 AND a<150有１０００行数据

如果我们使用key(a)和key(b)然后把结果集合合并会怎样？

合并计划：

查询２０万行数据从key(a)中，where a<150

查询１０万行数据从key(b)中，where b=10

合并结果集合，然后找到查询标识的1000行数据

执行１０００行数据的点查询去得到c

这比没有索引好一点

和没有索引相比，减少了扫描行的数量

和没有合并相比，减少了点查询的数量

那么聚簇索引会对合并有帮助么？

考虑key(a)是个聚簇索引

查询计划：

扫描key(a)２０万行数据，where a<150

扫描结果集合得到b=10的结果

使用得到的１０００行的数据去检索Ｃ的值

一次得到，没有点查询

更好的选择还有没有？

聚簇索引(b, a)!

规则２总结：

避免点查询

确保索引覆盖查询

包含查询涉及到的所有列，并不仅仅是查询条件中的

使用聚簇索引

使用聚簇索引包含所有查询
允许用户把关注点集中在查询条件上
给多个查询提速，包括还没有预见到的查询－－简化数据库设计

规则３：避免排序

简单的查询不需要后续的处理

select * from foo where b=100;

仅仅取得数据然后返回给用户

复杂的查询需要对数据进行后续的处理

GROUP BY 和 ORDER BY 会排序数据

选择正确的索引可以避免这些排序的步骤

考虑：

问：SELECT COUNT(c) FROM foo;

问：SELECT COUNT(c) FROM foo GROUP BY b, ORDER BY b;

查询计划１：

当进行表扫描时，给Ｃ计数

查询计划２：

扫描表把数据写到临时表中

对临时表按Ｂ进行排序

重新扫描排序后的数据，对每个b，使用c进行计数

如果我们使用key(b, c)会怎么样呢？

通过添加国所有需要的字段，我们覆盖了查询。 快速

通过提前对Ｂ进行排序，我们避免了排序 快速

总结：

通过给GROUP BY或者ORDER BY使用预先排序了的索引

把它们都放到一起：

简单查询

*

SELECT COUNT(

) FROM foo WHERE c=5, ORDER BY b;**

key(c, b):

把c放在索引第一个位置去减少行检索 R1

然后通过剩余的行排序去避免排序 R3

因为相等的检查在c上，所以剩余的行数据会被按b排好序

SELECT SUM(d) FROM foo WHERE c=100, GROUP BY b;

key(c, b, d)：

c在索引的第一个位置可以减少行数据的检索 R1

然后其它的数据在b上排好序去避免查询 R3

确保了查询覆盖所有的查询，避免了点查询 R2

在一些情况下，并没有明确的答案

最优的索引是和数据相关的

*

问：SELECT COUNT(

) FROM foo WHERE c<100, GROUP BY b;**

索引：

key(c, b)

key(b, c)

key(c, b)的查询计划：

使用c<100对数据进行过滤

仍然需要对数据进行排序

    *检索的行不会被b进行排序

    *查询条件不需要对c进行相等的检查，因此b的值分布在不同的c值块中

key(b, c)的查询计划

按b进行排序，Ｒ３

列WHERE c>=100同样需要处理，因此没有Ｒ１的优势

那个更好一些呢？

答案依赖于数据是什么样的

如果c>=100有更多的数据，节省时间不去检索无用的行。使用key(c, b)

如果c>=100没有多少行，执行查询的时间是以排序为主，那么使用key(b, c)

问题的关键是，通常情况下，规则会有帮助，但它通常只是帮助我们去思考查询和索引，而不是给我们一个配方。

另一个重要的问题：为什么不把所有的加载都添加上索引呢？

需要跟上插入的负荷更多的索引 ＝ 更小的系统负荷

索引的代价：

空间：

问题
    每个索引都会增加存储的需求

选项
    使用压缩

性能：

问题
    B-trees在某些索引任务中执行的很快（内存中，顺序的key），但是在其它类型的索引（辅助索引）会慢２０倍

选项
    分形树索引对于所有的索引类型都很快速
        很容易索引
        可经常索引

范围查询性能：

问题
    规则２依赖于范围查询足够快
    B-tree会比较容易碎片化（删除、随机插入…），碎片化的B-tee在范围查询上会变慢

选项
    对于Ｂ-tee可以优化表，导出然后导入（时间和离线）
    对于Fractal Tree索引，不是问题，它不会碎片化

PS. 文档翻译自：

Understanding Indexing

Without Needing to Understand Data Structures

MySQL UC 2011 – April 12, 2011

Zardosht Kasheff

For more information…

• Please contact me at zardosht@tokutek.com for any

thoughts or feedback

• Please visit

Tokutek.com

for a copy of this presentation

to learn more about the power of indexing, read about

Fractal Tree indexes, or to download a free eval copy of

TokuDB

PS. 正确设计数据库索引并不只是DBA的事情，每个合格开发者都必须具备这样的能力，但最近老是发现乱使用索引和不使用索引的情况，很明显是不理解索引，希望这篇译文能够帮助到这部分开发者吧。另外还有一篇不错的文章，有时间也会翻译出来，敬请期待。

数据分析工作负载VS事务性工作负载证明商业和技术可靠的大规模分布式数据库，支持ACID、有效存储PB级别数据的系统

分析数据库的架构，关注与C-Store不同的点 实施和部署的经验，为什么引入那些不同 现实世界的经验可以引导未来大规模数据分析系统研究的方向
2.背景 2.1.1设计目标：分析工作负载不是事务工作负载 事务工作负载：每秒事务数多，每个事务会影响少数几个元组，大部分的事务是增加一个新行或者修改部分已存在的列 分析工作负载：每秒事务数少，每个事务检查很多表中的元组，比如分析用户的行为，行处理每秒很多
数据量级的增加，即使是小公司

最初就是设计一个分布式数据库 1、新节点加入系统性能有线性的扩展。使用共享磁盘的架构也能获得这样的扩展，但这很快会成为系统的瓶颈 2、优化和执行的引擎避免大量的网络数据传输，以避免内部互联成为系统瓶颈 3、查询和加载数据每秒都会有很多，必须关注支持高插入，否则只能有限的应用，批量的加载应该很快而又不能影响并行的查询 4、操作可在线，管理和维护任务不应该停止或暂停查询 5、易于使用是一个明确的目标。用CPU换时间，形式上减少复杂的网络和磁盘设置，减少性能的调优，自动化的物理设计和管理
3数据模型 3.1 （列）计划 属性排序子集（经过编码和压缩并按某种次序排序和分割的纵列集合） 加载过程中自动维护 每个Projection都有自己的排序，数据是完全排序的 任意数量、带有不同排序的推算或表列的子集是被允许的，可针对不同的查询进行优化。
不同排序规则，可被看成物化视图，但它们是物理数据结构，不是辅助索引。它不包含聚集、连接、额外的查询，认为它们在现实的分布式数据库中是不切实际的。

2.2连接索引，没有被实现，代价比带来的优势要少，实现复杂，执行代价在重现全元组在分布式查询时很高。 明确存储行ID，会点用很多空间，我们高效的压缩实现有助于减少这种开销，但没有计划实现它 3.3预连接推算 没有预期使用的多和重要：在小表连接操作上已经够好（高度优化的hash和合并算法），用户一般不愿意减慢 批量数据加载数据去优化查询速度。在加载数据时比连接查询时能够进行的优化机会要少，因为数据库在加载流中没有什么先验。
3.4 编码和压缩 不同列有不同的编码，同样的列在他们的每个推测中也可有不同的编码 自动：根据类型和配置，当使用场景不同确时 替换：低基数列
3.5 分区 c-store节点内水平分区，在单个节点使用并行提升性能 获得节点性并行并不需要硬盘物理分隔，在运行时逻辑分区，然后并行处理。尽管能够自动并行化，也提供根据value保持在物理上隔离 分区原因：快速批量删除（其它系统分区也是如此），否则需要查询所有物理文件要删除的行，添加删除标记，比起直接删文件慢的多 增加了存储的需求，在元组没有执行合并操作前影响查询性能。如果分区在所有推算上都一致，批量删除才是快速的，所以它是表层次的，而不是推算层次的
分区原因：增加查询性能，它保存最小值和最大值在每个ROS中，在做计划时就能够修剪容器。分区使这种技术更高效，分区使列数据不混合

3.6 分割：集群分布 可以指定列做hash到段 c-store根据projection的排序字段的第一个列分割物理存储到段 完全的分布式存储系统，分配存储元组到不同计算结点 节点内水平分区和节点外水平分区（分割） 分割对每个推算在排序方式上可能不同，推算分割提供决定把元组映射到节点，可以做许多重要的优化。（ 完全本地分式连接，高效的分布式聚合，计算高基数不同的集合特别高效 复制推算在每个node上分布，分割推算一个元组在单个推算节点上存储 保持元组物理隔离为本地段，以方便集群的在线扩展与收缩
3.7读写优化存储 写在内存中，读在磁盘中 读：完整的依据推算排序排序的元组，列存储为一系列文件，两个文件1真实列数据2列数据索引 （大约1／1000，包含MetaData，如，开始位置，最大，最小值，固定不变故没有采用B-Tree） 写：内存，行列格式无关紧要，无编码和压缩，为缓冲数据操作（增、删、改）保证操作有足够多的行数以减少写的代价， 会随时间在行列模式下切换（和性能无关，只是软件工程考虑） 但它会以推算的分段表达式进行分段 3.7.1数据修改删除象量 不直接修改，当U和D操作时，创建D象量，它是要删除行的位置的列表，可能会有多个 DVWOS－》DVROS 高效的压缩 修改＝删除＋插入
4、无组移动：提高数据存储和查询效率 异步把数据从写优化到读优化，当WOS饱和mover操作没有完成之前，加载的数据直接入ROS，直到WOS重新获得足够的能力。mover平衡工作，避免产生小的ROS 读优化文件合并，减少ROS文件数量 写填满－》自动开始移动操作（随后的数据直接写到读优化，直到写有足够的空间）－》移动操作不能过多也不能过少 小文件影响压缩、减慢查询，需要更多文件句柄、seek和更多的全并排序文件的操作。 合并操作：回收已标记为删除的元组 没有限制ROS Containers大小，但它不会创建超过一定大小的（当前2T），足够大（每文件开销分摊，管理不笨重） ROS层在Node间是私有的，不会在集群内协调
5、修改和事务 每个元组都和提交时间关联（纪元）（隐式64bit的列或删除象量） 所有节点在事务提交都同意其包含的纪元，就相当于有了全局的一致性快照，读无需要加锁 有一个分析工作量的表锁定模式 不使用传统的两阶段提交 共享锁：限制并发修改表，用来实现序列化隔离 插入锁：插入数据时到表使用，和自己兼容，支持匹量插入和加载同时发生，以保持高插入加载速度。但仍然提供事务语义 共享插入锁：读写 独占锁：删改 元组移动锁：和所有锁兼容除了X锁，在元组移动同时操作删除象量时 使用锁： 拥有锁：
分布式和组成员协议来协调集群内结点之间操作，使用广播和点对点来保证所有控制消息成功送达所有node提交在集群中成功如果它在选定数据的结点上成功，ROS与WOS创建的事务完成后其它事务才能看到

5.1纪元管理 纪元模型：纪元包含给定时间窗口所有提交了的事务 Last Good Epoch:所有数据都成功从WOS移动到ROS Ancient History Mark:
5.2宽容失败 Vertica的数据复制通过使用Projection分段机制，以提供容错 每个Projection，必须至少有一个伙伴projection含有相同的列和分割以确保任何行被存储在同一样节点的Projection，当节点故障，伙伴projection会做为故障节点的源。 不需要传统的事务日志，数据＋纪元自己就做为过去系统活动日志。vertica使用这些历史数据，去重放节点丢失的DML。节点会从正常的伙伴projection数据段恢复数据，
恢复，更新，重新平衡和备份都是在线操作;在执行这些操作同时可进行数据的加载和查询。影响的只是计算和带宽资源。

5.3 以元数据目录在节点间管理状态，它记录着表、用户、节点、纪元等的信息。 没有保存在数据库表中，因为它的表设计无法恰当的通过catalog访问和修改。它采用自定义的内存结构中，然后通过它自己的事务机制保存到磁盘中。 k-safety：当有小于或等于K个节点故障，集群仍然可用。 数据库projection必须确保有K＋1个每个段的拷贝在不同的节点上。当有一半节点故障，集群会保护性关闭。集群必须保证有n/2+1个节点确保脑裂后的两个集群继续提供服务。
6 查询的执行 私有扩展标准的SQL声明的查询语言。 Vertica的公司扩展设计使可轻松地查询在SQL时过于繁琐或不可能的时间序列和日志型数据。
6.1查询操作符和计划格式 执行引擎为完全天量化，并且在同时查询一块行数据而不是同时查询单一行 标准操作树，每个操作执行一个特定的算法。一个操作者的输出做为下面操作者的输入。 执行引擎是多线程和流水线的 在一个时间请求一块行数据而不是请求一条数据。 使用上拉处理模型，直到一个操作从磁盘或网络读到数据。 扫描、分组（有多个算法依据性能最大化、内存需求、操作是否必须产生单独的组决定使用那个，并且实现了管道聚合方式可选择是否保持数据编码）、连接（实现了hash join和merge join算法，能够在必要时外部化）、表达式执行、排序、分析、发送／接收
特别处理和复杂的实现，确保可直接操作未解码的数据，这对于扫描、joins、低级聚集操作很重要。

SIP：Sideways Infomation Passing，侧面消息传递，采用在查询计划中尽可能早的过滤数据来优化join性能。（可在优化查询计算时就构建SIP filter，然后在执行时使用。在执行时，扫描操作会扫描join的hash table，SIP会用来判断outer key值在hash 表中是否存在。）

运行期间分析数据调整算法（内存不够hashtable->sort-merge join；生成预处理操作，并发执行，最后根据它们的结果生成最终数据）

晚物化、压缩的成本和估算、流聚合、消除排序、合并连接、不可见索引（每列按选择性排序，不需要索引来减少IO和更快查找值），数据die dai（L2缓存，更好的利用二级缓存和多核并发的特性）

使用pipeline执行引擎带来挑战是共享公共资源，可能造成不必要的yi chu到磁盘。vartica会把计划分成多个不会在同一时间执行的区，下游操作会回收上游操作的资源。

不同表的projection的数据被复制到所有节点上或者在join key上分割相同的范围，使得计划可以在每个节点的内部执行，然后结果发送到客户端连接的结点。

6.2 优化

选择和连接projections，保证scan和join更快(保证之后join的数据被减少)

收集性能数据（压缩I／O，CPU，网络使用）