范式和反范式

范式在有些本科的教材中将的其实挺晦涩的,比如《数据库系统概论》,后来在知乎上看到一个很好的答案: 关于范式

在最理想的范式化的数据库中,每个数据只会出现一次,而在反范式化的数据库中,信息是冗余的,可能会存在许多的地方。

举个经典的例子,一个包含雇员,部门,部门领导的表:

1
2
3
4
5
6
EMPLOYEE | DEPARTMENT | HEAD
---------|-------------|-----
Jones | Accounting | Jones
Smith | Engineering | Smith
Brown | Accounting | Jones
Green | Engineering | Smith

这个表主要的问题就是修改数据时可能会发生不一致,需要修改多处数据。比如更换Accounting部门领导的时候,就需要修改多行数据。比较麻烦。

所以可以对这个表进行范式化,将表分为雇员表和部门表来进行存储:

1
2
3
4
5
6
7
8
9
10
11
12
13
雇员表
EMPLOYEE | DEPARTMENT
---------|-------------
Jones | Accounting
Smith | Engineering
Brown | Accounting
Green | Engineering
部门表
DEPARTMENT | HEAD
------------|-----
Accounting | Jones
Engineering | Smith

这样设计的表就符合第二范式了,针对上一个问题,就可以很简单的解决了,修改部门表即可。

范式的优点和缺点

范式化的数据库在写密集型的场景,是很好的,因为:

  1. 范式化的更新操作通常比反范式化要快
  2. 当数据较好地范式化时,就只有很少或者没有重复数据,所以只需要修改很少的数据。
  3. 范式化的表通常更小,可以更好的放在内存里,所以执行操作会更快
  4. 检索列表数据时更少需要DISTINCT或者GROUP BY语句

但是范式化设计的schema的缺点就是通常需要关联,而关联的代价昂贵,也可能使一些索引策略失效。比如多列索引,如果数据都放在一个表中,是可以使用多列索引来解决的。

反范式化的优点和缺点

反范式化的schema因为所有数据都在一张表中,可以很好地避免关联。

如果不需要关联表,就算对于没有使用索引的查询情况,全表扫描也可能比关联要快的多,因为避免了很多随机IO。(一般全表扫描都是顺序IO)。

混用范式化和反范式化

在真实的业务场景中,很少会有完全的范式化和完全反范式化的schema。都是根据具体的查询场景来冗余一部分列到需要查询的表中,这样就可以优化查询的性能。

InnoDB中的多列索引

对于单列索引,在介绍索引的时候已经说过。现在说说多列索引的实现。

假如有如下数据表:

1
2
3
4
5
6
7
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum('m', 'f')not null,
key(last_name, first_name, dob)
);

那么索引的数据存储结构如下:
多列索引

可以看到,在索引的非叶子节点中,都存有索引的每一列的值,而且都是有序的(对于前缀列都一致的情况)。

在使用多列索引进行查找时的一些查询方式如下:

  1. 全值匹配
    全值匹配指的是和索引中的所有的列进行匹配。比如查找姓名为Cuba Allen,生于1960-01-01的人。

  2. 匹配最左前缀
    对于前面索引,可以只使用索引的某一些列,比如只按照姓名来查找。
    最左前缀匹配应该是大家都很熟悉的。对于多列索引,在使用的时候有些地方还是需要注意。

    • 要想使用索引,只能从索引的最左列开始查找,否则无法使用索引。比如不能用索引查找名字为Allen的人,也无法查找某个特定生日的人。
    • 同时也不能跳过索引中的列。也就是无法用于查找姓为Cuba,并且生日为某一个特定日期的人,如果不指定名,那么只能使用索引的第一列。
    • 如果查询中有某个列的范围查询,则其右边的所有列都无法使用索引优化查找。比如WHERE last_name='Smith' AND first_name LIKE 'J%' AND dob='1976-12-23'.这个查询只能使用索引的前两列,因为LIKE是一个范围条件。
      所以索引列的顺序是很重要的,在设计索引的时候,需要考虑到以后可能得查询的方式。
  3. 匹配列前缀
    可以职匹配某一列的的值的开头部分,比如查找所有以J开头的姓的人。

  4. 精确匹配某一列并范围匹配另外一列
    比如查找所有姓为Allen,并且名为K开头的人。

  5. 只访问索引的查询
    B-tree支持只访问索引,不访问数据行的查询。比如覆盖索引。

关联查询的执行方式

很多时候,大家都会说不要使用关联查询,这样性能不好。这里说一下关联查询的执行方式。

比如说UNION查询,Mysql先将一系列的单个查询结果放到一个临时表中,然后在重新读取出临时表的数据来完成UNION的查询。

对于多表的关联查询,当前Mysql的关联查询的策略也很简单:对于任何关联都执行嵌套循环关联操作,即Mysql会现在一个表中循环取出单条数据,然后再嵌套循环到下一个表中寻找匹配的行,依次下去,直到找到所有表中匹配的行为止。然后根据各个表匹配的行,返回查询中需要的各个列。

举个例子,有一个简单查询:

1
2
3
4
SELECT tbl1.col1, tbl2.col2
FROM tbl1
INNER JOIN tbl2 USING(col3)
WHERE tbl1.col1 IN(5,6);

那么按照前面说的嵌套循环的关联操作,可以用下面的伪代码来表示Mysql将如何完成这个查询:

1
2
3
4
5
6
7
8
9
10
outer_iter = iterator over tbl1 where col1 IN(5,6)
outer_row = outer_iter.next
while outer_row
inner_iter = iterator over tbl2 where col3 = outer_row.col3 inner_row = inner_iter.next
while inner_row
output [ outer_row.col1, inner_row.col2 ]
inner_row = inner_iter.next
end
outer_row = outer_iter.next
end

对于外连接的查询,比如:

1
2
3
4
SELECT tbl1.col1, tbl2.col2
FROM tbl1
LEFT OUTER JOIN tbl2 USING(col3)
WHERE tbl1.col1 IN(5,6);

对应的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
outer_iter = iterator over tbl1 where col1 IN(5,6)
outer_row = outer_iter.next
while outer_row
inner_iter = iterator over tbl2 where col3 = outer_row.col3 inner_row = inner_iter.next
if inner_row
while inner_row
output [ outer_row.col1, inner_row.col2 ]
inner_row = inner_iter.next end
else
output [ outer_row.col1, NULL ]
end
outer_row = outer_iter.next
end

主要区别在于左外连接,如过第二张表中没有数据,需要把相应的列补NULL。当然,碰到右外连接时,mysql会将右外连接改为等价的左外连接。

另一种可视化查询执行计划的方法就是根据优化器执行的路径绘制出对应的泳道图(swim-lane diagram),如下图所示:
泳道图

对于多表关联的查询,mysql的执行计划如下图所示,是一颗左侧深度优先的树:
多表关联

从上面这些信息可以看出,这就是为什么关联查询会影响性能的原因,也是为什么大家常说要使用小表驱动大表的原因,因为小表驱动达标会减少外层循环的数目。