每行80个字符在今天(2020年)依然合理!

很多代码库每行长度最多为 80,这是因为古老的打孔纸的最大长度是 80,一开始的显示器每一行显示的字符也并不是特别多。这一 Max Length = 80 的传统被一直延续下来了。

IBM 打孔纸

现在宽屏显示器非常流行,有一种声音说在代码中将每行的字符限制为 80 是没有必要的,因为这会浪费显示器的空间。

但是我认为行长度设置为 80 依然有道理:

“浪费宽屏显示器的空间” 是不实的。基本上所有的编辑器都有“分屏”的功能,80个字符更有利于分屏展示代码。相反,如果行长度太长,反而会给分屏带来麻烦,比如10行代码中有1行是100多个字符,那么分屏的时候会将这一行“折行”(wrap),显示的很糟糕;如果行长80,可以自由的分屏。

相反,行太长才是“浪费显示器的空间”,屏幕的右边只是偶尔出现几行,大部分都是空白。分屏才能有效利用宽屏显示器。

另外,笔记本的屏幕依然没有“那么大”,如果短行在哪里显示都是OK的,但是长行在小屏幕下显示很糟糕。

Vim 分屏

80字符为一行更容易阅读代码。每行字符更少,分一行来表达一个操作,容易理解。(阮一峰的博客,读起来比较轻松,他比较喜欢用短句,来表达比较复杂的东西,比如你现在在阅读的,括号里面的这段文字)

再比如以下 Java 代码,从 items 中随机选择 5 个。(可能有更简单的方法,这里只是为了举个例子)。

不限制行的长度

增加换行使代码更易读。

80 个字符可以让代码在其他阅读器上阅读更友好。代码并不总是在 Vim 中打开的,比如你躺在床上,打开 ipad,将 more-itertools 的代码放大到和屏幕同样宽度,阅读这些短小巧妙的函数,非常惬意。

用 ipad 在 Github 上阅读代码

当然,死板的遵守 80 个字符也是没有意义的(比如 URL)。Kernel 代码中就有超过 80 的行。Linux 说(2012年的邮件):

有时候打破 80 比强行拆成两行要好。所以代码库中有超过80的情况,这并不是说应该行长100,而是 80+ 在这种情况下是最好的选择。

所以这是一个折中的方案。把 80 想象成是一个 Hard Limit 是不对的,试图将这个 Hard Limit 扩展到 100 也是不对的。

 

综上,一行代码的最大长度依然是 80 !

 

Use the Index, Luke! 笔记2 性能、Join操作

这是读 use-the-index-luke 的第二篇笔记,是 Testing and ScalabilityThe Join Operation 两章的内容。

存储大小和请求量对性能的影响

在开发环境工作很好的 SQL 到了生产环境可能执行的很慢,主要会受两个方面的影响:

  1. 数据量:同样一个查询,在几百条开发数据里面跑和几亿的数据里面跑,效果是不一样的;
  2. 请求量:开发环境只有几个连接查询,在生产环境中可能同时有几百个并发查询,速度也会显著下降。

分析 Execution Plan 的结果会比简单的 Benchmark 更有自信(要格外注意 Predicate Information 中的 filter,filter 随时可能爆炸)。完全的压测也是有必要的,但是通常成本很高。

有人认为生产环境的机器配置更高,机器更多,可以解决查询慢的问题。但是大部分的慢查询都不能通过增加硬件来解决。21世纪以来 CPU 的性能没有很大提升,CPU 厂商都开始用多核技术来提高 CPU 的性能。如果仅仅是一个任务,那么开发用的笔记本和服务器效果是差不多的。生产环境就像高速公路,可以允许更多的车在上面跑,而它本身并不会让车跑的更快。相反的,生产环境的设施更加复杂,服务器之间的交互更多,加上防火墙等设施,在生产环境运行更有可能更慢。NoSQL 宣称解决一切问题,但是本质上它是用最终一致性换取了水平扩展写的能力。如果一个查询在关系型数据库很慢,那么即使迁移到 NoSQL 也会很慢。加快查询最靠谱的方法是利用好 B-Tree 索引。

另一个导致查询慢的原因是硬盘磁头 Seek 的次数太多了,虽然一次 Seek 只需要几毫秒,一次索引查询(B-Tree)最多也只会 Seek 4次,但是如果 join 表太多的话,就会 Seek 几百次。

所以再次强调,最靠谱的验证方式还是看执行计划。否则很容被开发环境小量数据的效果“欺骗”。

Join 操作

先来两个笑话吧(No hard feelings)。

笑话1:

SQL 走进了一家酒吧,看到有两张桌子(Table),他问:我能加入(Join)你们吗?

笑话2:

为什么前端程序员总是独自吃饭?

因为他们不懂 Join Tables.

回到正题,join 可以将分散在多个表中的数据重新组合起来。因为 join 需要聚合分散的数据,所以 join 操作对磁盘的 seek 非常敏感。正确的索引可以加快 join 操作,如何索引取决于使用哪种 join 算法。常用的一共有 3 种。但是这些算法的一个共同点是:一次只能 join 两个 Table。如果有多个 Table,那么先 join 起来前两个 Table,然后作为中间表,再去和后面的 join。所以下文在讨论的时候,都是讨论两张表之间的 join。

虽然 join 的顺序对最后的结果没有什么影响,但是对查询性能是有影响的。优化器需要从所有的可能中选一个最优的查询计划出来。在这种情况下,光优化查询的参数是不够的,因为优化器做选择本身就会花一些时间(n! 复杂度,n是查询条件)。当然,如果使用 bind parameters 就没有这个问题啦(参考我的第一篇笔记),所以参数越多,使用 bind parameters 就越有必要。

接下来介绍 3 种最常用的 join 算法:

  1. Nested Loops – 用循环来 join 两张表;
  2. Hash Join – 将一张表构建出来 Hash 表,然后对表2中的每一行记录,找到 hash 表中对应的行;
  3. Sort Merge – 将两张表排好序,然后用 Merge Sort 算法进行 join;

Nested Loops

这是实现起来最简单的一种方法:Join 表1 和表2,只要遍历表1中每一行,去表2 Select 就行了。

如果你使用 ORM 的话,可能遇到过一个经典的问题:N+1 select ——错误做法:从两张表查询 N 行记录,先在表1中查出来所有的行,然后用一个循环 Select 表2中的行。因为一共会执行 N + 1次 Select(第一次查询出所有记录,然后遍历N次),所以叫做 N+ 1 Select 问题。这样做可能在上线之后引起性能问题,因为执行了大量的 Select。

通过上面这个问题,可以比较好的理解 Nested Loops. 可以看出,join 的条件有没有索引,对 join 的性能影响很大。因为相当于执行的是 select。

通过 Nested loops 来进行 join 虽然和 ORM 这种 N+1 Select 的原理是相同的,但是用 SQL join 会更加高效。这是因为 join 是直接在数据库服务里面做的,而 N + 1 Select 要客户端和服务器来来回回对每一条 Select 进行请求和响应。

性能一般反应在两个方面:Response Time 和 Throughput,在网络上反应为延迟和带宽。对于数据库来说,延迟更加关键,带宽并不是很重要。

所以最好打开执行的 SQL 日志(一般的 ORM 都有这种选项),来看一下类似的操作是否是通过 SQL 来 join 的。

如果 join 条件有索引,并且数据集不大的话,Nested Loops 的性能是不错的。如果数据量大的话,优化器就会选择其他的 join 方式。

Hash Join

Hash Join 的原理是对一个表执行 Full table scan,将这个表 load 进 hash 表中,以 join 的条件作为这个 hash 表的 key;然后选出第二张表中,符合 where 查询条件的行,在 hash 表中找到对应的第一张表的数据。

将一张表加载到内存中,来避免了 join 的过程中多次 select。因为 join 的条件会被作为 hash 表的 key,本身就是 O(1) 的速度了,所以对 join 的条件建立索引,在 hash Join 中并不会起作用。

优化 Hash Join 速度的方法主要有两个:

  1. 加速遍历第二章表的速度,即对 where 条件建索引;
  2. 尽量减少 join 的内容的数量,这样降低 load 进内存的大小;水平角度,我们可以用 where 语句过滤出尽量少的行;垂直角度,我们只 select 需要的 column,而不是 select *

Sort Merge

Sort Merge 的原理很简单,将两张表排好序,然后用 sort merge 的算法将两张表 join 起来。

Sort Merge 所需要的索引和 Hash join 一样,尽可能加速查询,对 where 语句索引。join 的条件是没有必要索引的。

Sort Merge 对 join 的顺序完全不感冒,A join B 和 B join A 的结果是完全一样的,性能也是一样;

因为 Sort Merge 要将两边的表都排好序,所以代价很高,相比之下,Hash Join 只需要处理一边的表。所以 Hash Join 实际上更常用一些。但是有一种情况,就是如果输入的数据已经是排好序的,那么 Sort Merge 是非常快的。

 

集合里的元素怎么“不见了”?

昨天花时间在 debug 一个非常诡异的问题,Java 代码里面的一个 HashSet 集合里面命令包含我这个元素,equals hashCode 都一样,甚至对象的 id 都是一样的,但是 contains 方法返回的结果总是 false 的!最后花了很多时间,百思不得其解,一度怀疑我生活在 Matrix 里面。最后发现问题的一刻也恍然大悟,发现这是一个我早就知道的问题。这必定成为我职业生涯的一个污点,所以我打算记录一下这个问题。

先卖个关子吧,我来描述一下问题的背景,看你能否想到答案。

问题是这样的,我们用 JGraphT 来解决一个图的问题。这个图是我们从应用的调用关系链中生成的,生成之后会导出到 json,放到一个地方。然后所有的计算节点都可以通过这个 json 来 load 图,就不用每个节点都去清洗一遍了。一个节点清洗过后,所有的节点都从这里加载。问题主要出现图的导出和导入,图中每个节点都有一个 id,一开始我用应用的名字作为 id,导出到 json,但是导入的时候发现 Importer 会重新生成 ID,图的关系是对的,但是节点的 ID 从字符串变成了重新生成的 id 了,那么应用名字的信息就丢失了。我又给节点加上 name 属性,期望这个属性 import 之后还是好的。结果发现 import 只是 import 图的关系,并没有 import 进来其他属性。(这个库看起来很 nice 啊,不知道为啥文档这么差,import 的细节都没有文档)于是我参考 Test 里面的做法,用一个 Map 存下来节点的其他属性。然后在 import 完成之后,将这些属性 set 进去。

OK,总结一下,简单来说就是,我先从 json 导入进图,导入的时候也存下来每个节点的属性(其实就是name),导入之后遍历图的节点,将每个属性设置进去。

问题就出现了,我用图来找最短路径的时候,报错:节点不存在!

定位到库里面,判断节点不存在的 contains 函数是这么写的:

我 debug 了这个 Set 和 v 的关系,发现 Set 中的一个元素,跟 v 是一模一样的!对象 id 都是一样的。

equals 返回值是一样的:

hashCode 返回值是一样的:

但是这个 contains 函数就是返回 false.

为了让这个问题更明显一些,我将这个问题简化成以下可以直接运行的一段 Java 代码:

运行结果如下:

明明 equalshashCode 都一样,为什么 contains 就是 false 呢?


答案就在查找 Hash 表的方式。我之前写过一篇文章,介绍如果发生 hash 碰撞,那么 hash 表一般会通过某种方式存放 hash 相同的元素。这就要求,在 hash 表中查找元素的时候,必须满足以下两个条件,才算是找到了元素:

  1. 按照 hash 值能找到这个元素所在的 hash 位置,但是这个位置存放着很多 hash 值相同的元素,所以还要满足2;
  2. 必须满足相等(equals)

HashSet 其实就是没有 value 的 HashMap,本质上也是个 hash 表,所以 contains 要返回 true,也必须满足上面两个条件。元素在存进去的时候,name 是空的,按照 namenull 得到了一个 hash 值,放到了 HashMap 的一个地方,记做位置A。然后我后来修改 name 的值,再 hash 的时候,就会得到另一个 hash 值,记做位置B. 然后 contains 去位置 B 一看,这个位置是个null,就认为这个元素不在集合中了。

为什么 hashCode 和 equals 返回都是相等的呢?因为我们先按照 name = null 保存了进去,保存的时候 hash 值已经确定了,后来修改了 name,hash 值已经不会修改(不会在 HashSet 里面移动的)。虽然对象即使是同一个对象,但是 hash 值已经和放进去的时候变了。拿现在的对象(Set里面的那个对象,和现在的要确定是否被 contains 的对象,都是“现在的对象”,name 已经被修改了的)来对比 hash 值肯定是相等的,但是已经和放进去的时候的那个 hash 值不同了。去看 HashSet 中,现在的这个 hash 值的位置,肯定是个 null,所以判断为元素不存在。

简单总结一下,就是放入 Hash 中的元素,一定要是不可修改的(这个和 Python 为什么list不能作为字典的key?的原理是一样的)。如果修改了,那这个元素就从集合中找不回来了。

最后,从这个故事中我们能学到什么呢?

感觉学不到什么,现在回想起来就跟自己的智商收到了降维打击一样。

哦对了,如果你看懂了这个问题,那么就会理解,之所以找不到这个元素是因为这个元素放进去的时候的 hashCode 和现在的这个元素的 hashCode 已经不一样了。我不禁回忆起另外一个问题:

有三个人去住旅馆,住三间房,每一间房$10元,于是他们一共付给老板$30,第二天,老板觉得三间房只需要$25元就够了,于是叫小弟退回$5给三位客人。

谁知小弟贪心,只退回每人$1,自己偷偷拿了$2,这样一来便等于那三位客人每人各花了九元,于是三个人一共花了$27,再加上小弟独吞了不$2,总共是$29。可是当初他们三个人一共付出$30那么还有$1呢?

 

IRedis 1.0 发布

这算是 IRedis 开发系列的第4篇笔记吧。这篇文章来聊一下 IRedis 最近发布 1.0 带来的新 Feature,一些开发过程中的思考,以及最后贴一下发布之后的一些“成就” (炫耀)。上次提到的介绍一些开发中使用的 tricks,就让我再拖到下一篇博客吧!

PS: 如果您还不知道 IRedis 的话,可以理解成是 redis-cli 的一个替代品。类似于 IPython 相比于 python 官方的 REPL,专注于用户体验,支持语法高亮,命令提示,自动补全等。全部的 Feature 可以参考项目 Readme,以及官网。

New Features

Changelog 是从 0.8 开始记录的,这里说一下几个两点功能:

支持了 Peek 命令,用 Redis 的时候不需要先用 type 看一下 key 的类型,然后再去选择对应的命令来操作了;

支持了配置文件 ~/.iredisrc.

支持了 Redis 所有的命令,支持了时间戳补全(没有人想在命令行输入时间戳!),支持了 int 类型补全。(我发现实现补全器很有意思呢!)

更多的功能演示 gif 可以见这个页面

Coming Features

  1. 支持用 URL 来传入 Redis 连接参数,比如 iredis --url redis://username:[email protected]:6379/5 lyqsmy 正在实现这个 Feature
  2. 支持通过 alias_dsn 连接 redis,比如把上面这个 url 保存在 ~/.iredisrc 里面,然后在命令行通过 iredis --dsn main 去连接。
  3. 将 IRedis 打包成单个文件,通过 curl 就可以下载到机器上执行。目前采用的方案是 PyOxidizer,遇到不少问题,mac-chaffee 正在做这项工作

开发思考

最想分享的是单元测试了,开发一个又一个Feature的时候,测试挂了 N 多次,每次挂了我都庆幸一次幸亏写了测试。分享一下 piglei 的文章,以及我在评论里留下的一些想法:

我也想分享一些有关测试的想法。我很喜欢写测试,最近在写的 https://github.com/laixinta… 搞了一年多,测试挂了无数次。测试这个事情很反直觉的一点是,你觉得测试会增加开发成本,而事实相反。我知道我的测试覆盖了哪些地方,所以,我可以放心大胆的重构,主要测试pass了,我就敢发布新版本。随着代码越写越多,开发效率一点也没有降低,有什么新功能直接写就行了,之间的函数抽象不够直接重构,然后修复测试。这个项目到今天还是能保持着只要合并了master就可以作为新的feature立即发布,甚至我的发布流程也是交给CI的,我只要打tag push就好了。

另外有几点感受:

  1. 写稳定的测试是很重要的,有时候我们会因为assert 的list顺序不一样而导致测试随机挂掉,一定要找到原因,保持测试的可信度;
  2. 稳定的CI服务很重要,我从 circleCI 换到travis,现在用Github Action,CircleCI因为自身问题挂过3次,travis从没挂过,Github挂过1次(目前),如果CI变成“这次挂了,但可能不是我的问题,我要re-run试试”,体验是很糟糕的;
    CI的速度很重要。现在有200+测试,刚开始需要5min在CI跑完,后来我对venv加了cache,测试3个Python版本只要1min了;
  3. 覆盖率不重要。盲目追求100%是没有意义的。比如有些代码你写了 re.match("xxx", str) 你知道这个正则需要match很多种情况,但是其实只要你写1种,对覆盖率检测来说,它就以为你覆盖了,但其实需要更多的case来发现问题。还有一种情况,在函数的入口做参数检查,比如两个 kwargs 不能同时出现,这种代码很难出错,其实没必要测试(当然写一个也就几行)。所以,我现在觉得100%的测试覆盖并不能说明一个库是质量好的,覆盖率70%也并不能说明这个库测试不够完全;
  4. 应该一开始就写测试。以前我的想法是先写好功能,写的完善了,到1.0了,再开始写测试。这种想法是不对的,应该在POC的时候就写POC的测试,这样可以保证开发质量,和开发效率。有一个额外的好处是,这时候的测试可以作为样例代码,供用户或同事参考。
  5. 我觉得理想的开发团队(虽然我没遇到过)应该用测试来保护自己的代码,如果别人修改了我的部分,并且全通过了我的测试,但是引入了BUG,那我会认为是我的责任。

—— on 《游戏《蔚蓝山》教我的编程道理

另外,我发现 Python 里面的 Generator 很容易被忽略。

第一种情况是很容易忽略很多内置的函数返回的是 Generator,只能迭代一次。比如我在写 Completer 的时候写过的下面这个代码:

导致这个 Completer 只在第一次使用的时候有用,这个现象很奇怪,我花了几十分钟才意识到这 reversed() 返回的不是 list,只是 generator,只能用一次。

另外情况就是一个函数很长,中间出现了一个 yield,就从一个 function 变成 generator maker 了(我觉得很多地方搞混了“生成器”和“生成器 maker”,def foo(): yield "hello" 这其实不是 generator,只是制造出 generator 的一个东西,每次调用都会出现一个新的 generator,所以我把它叫做 generator maker)。然后现象也很奇怪,就是这个函数根本没跑。找了好久才找到原来是没用 next() 激活。

说到底,说他“坑”的原因就是这种情况完全不会报错,不会有任何错误,完全隐藏在了程序的逻辑中。很难排查。


以下是发布之后受到的关注:

1.0 之后我在 Hackernews 贴了一下,但是一直都没什么人,感觉在 HN 发帖子很难受到关注,结果第二天起床一看,竟然被顶上了首页:

上Top10了, 没有截图到,放个Twitter吧

还没有写完的时候,RedisWatch就推荐过一次,80期

被 RedisWatch 第二次推荐 (第84期)

还有两个哥们跟我说他们在微博看到有人转发我的项目了,开心

PyCoders推荐了

本来想让DB Weekly推荐一下的,但我还没联系他们,下一期就出来了,封面竟然是IRedis!

IRedis的Itamar的评价

prompt-toolkit 作者的评价

 

Use the Index, Luke! 笔记1

这篇文章是我读 https://use-the-index-luke.com/ 第一章的笔记。这对开发者来说是一本不错的教材,读起来也非常轻松,在捕蛇者说的节目中也推荐过。我阅读的时候会做一些简略的笔记,逐步分享在博客上。

SQL 写起来就像英语(比 Python 更像)。SQL 只要求你描述你想要的数据,而不要求你关心数据库如何把这些数据库查出来。在这方面,这个语言的抽象很好。但是涉及到性能,这种抽象就不完美了。写 SQL 的人必须了解一些数据库的工作原理才能写出性能比较好的 SQL 语句。

影响数据库性能最关键的因素是数据库的索引,而要建立合适的索引,不是运维或者 DBA 的职责,而是开发者的。因为建立索引需要的最关键的信息是查数据的“路径”,这些信息正好开发是最熟悉的。

这本书就是面向开发的索引教程。不涉及其他数据库的复杂知识。

这一系列的笔记一共 6 篇,第一篇写了基本的原理,后面的内容基本都是基于第一篇的原理的,聪明的人应该可以通过索引的原理推理出来后面的内容,以及那么做的道理。第2篇性能和 Join,第4篇 sort group,第5篇部分查询以及第6篇DML,都很简单,基本上让你实现一个数据库你也会直觉地那么选择。第3篇非常有技巧性,不可错过。英语水平足够好可以直接阅读原文,只想看一些可以 take away 的知识的话我觉得我整理的笔记也可以。我删去了我觉得的一些比较啰嗦的解释,如果看不懂的话,可能还是需要回去读原文:)

最后,我也是一遍学习一遍记的,如果有不懂的,或者文中有错误,欢迎留言交流。

  1. Use the Index, Luke! 笔记1
  2. Use the Index, Luke! 笔记2 性能、Join操作
  3. Use the Index, Luke! 笔记3:避免回表
  4. Use the Index, Luke! 笔记4:sorting 和 grouping
  5. Use the Index, Luke! 笔记5:查询部分结果
  6. Use the Index, Luke! 笔记6:增删改的索引

1. 索引

索引在数据库中,跟 table 中的数据是分开的,重复的数据。假如删掉索引,也不会丢失任何数据。类似一些专业书籍最后面的名词索引,会单独占用很多页,但是没有额外的信息,只是加速读者的查阅速度。

但是索引还要比“附录”复杂的多,因为附录不需要更新,只需要下一次印刷重新排版就好了。但是索引要面临和数据共同更新、增加、删除,并且保持一致。还需要解决中间部分的空间放不下新的索引的问题。

数据库一般结合两种数据结构:双向链表,加一个树,来解决这个问题。

索引要解决的根本问题是,提供一种有序的数据,这样查找起来更快。

如果使用连续的数组的话,那么插入数据的时候,需要顺序移动后面所有的元素。太慢了,这是无法接受的。所以这里数据库维护的是一个“逻辑顺序”。实际存储的索引在内存中并不是连续的,但是一个节点指向下一个节点,保持了一个逻辑上的顺序。

每个节点都保存了上一个节点和下一个节点的位置,这样数据库可以向前或向后查找。这个数据结构叫做双向链表(doubly linked list)这样每次插入和更新数据的时候,只要修改前后节点的指向就好了。

数据库将这些节点存放在文件系统的 block 中,这也是文件系统读写的最小单位。在一个 block 中存储尽可能多的 block。这样,索引就有两层,要找一个特定的索引,首先要找到它在哪个 block,然后读出来这个 block,找到这个 block 中的索引。

B-Tree(省略)

这部分对我是已知内容,所以忽略了,读者如果有兴趣可以去搜索一下相关的资料,比较丰富的。


2. 使用索引也可能很慢

即使使用索引,也可能查询很慢。有些人说重建索引可以解决问题,但长期来看并没有用。为什么使用了索引还可能很慢呢?原因有以下几点:

  1. 存在多个相同的值。这个时候会有多个 B-Tree 的叶子节点是相等的,为了确保找到其他叶子节点符合查询条件的数据,还要遍历把这些叶子节点都遍历一遍。所以除了 Tree 遍历的时间,还有顺着叶子节点找到最终的叶子节点的时间;
  2. 找到索引之后,还要去表中查找数据。这些数据散落在磁盘的不同地方,读比较耗时;

所以通过索引查找数据实际上是分 3 步:

  1. 遍历树;
  2. 顺着命中的叶子节点找相邻的叶子节点;
  3. 拿到索引中保存的数据的问题,读数据;

很多人认为,如果命中索引,查询还很慢,一定是由于索引腐坏了。实际上不是这样的。

甚至有时候,命中索引的情况可能比 TABLE SCAN 还要慢。举个例子,假如有一个人名的数据库,对 Lastname 建立索引,但是 Lastname 相同的人很多。在下面这个 SQL 中,TABLE SCAN 可能比按照索引查询还要快。

因为在索引查找的过程中,虽然 Tree 遍历很快,但是还要遍历一个 Linked List,找到所有的符合 lastname = "Pinkman" 的数据,然后将这些 ROW 全部都读出来,依次判断它们是否符合另一个条件 firstname = "Jesse"。相比于 TABLE SCAN,这两个操作都很耗时,而且 TABLE SCAN 虽然扫的数据量要大一些,但它是顺序读的,硬盘顺序读更快,而且可以利用一些 Kernel 的 read ahead 的技术。注意 TABLE SCAN 比 INDEX RANGE SCAN 快的条件并不是数据量有多少,而是索引中相等的值有多少。

很多数据库提供命令,可以查看索引的使用方式。比如 Oracle:

  1. INDEX UNIQUE SCAN:只遍历数,用于检查数据是否已经存在;
  2. INDEX RANGE SCAN:遍历树+遍历相邻叶子节点;
  3. TABLE ACCESS BY INDEX ROWID:根据索引中的 ROWID 读出数据(完整的3步)。

3. 什么时候会使用索引

当使用 INDEX UNIQUE SCAN 的时候,一般不会出现 slow query。因为要找的数据只会命中一条,不会需要遍历叶子节点,Table Access  也只需要一次。

串联索引(Concatenated Indexes,某些地方可能翻译成联合索引,但是联合这个词丢失了“必须按顺序”这个关键的信息,所以 Concatenated Index 这个词可能比 esmulti-column, composite or combined index 更合适)

如果一个索引有相同的值,那么如果要作为主键的话,就要和其他列一起,作为串联索引了。

什么时候会通过串联索引查询,什么时候不会,这个细节必须要明白。

串联索引也只是一个索引,以两列的串联索引为例,与单列索引不同的是,如果第一列的值相同,就会使用第二列索引排列这些第一列相同的索引。类似于一本书的目录同一个章节下的小结。你可以按照章节、小结两列一起搜索,也可以搜索某一章的所有小结。但是不能在没有章节的情况下直接搜索小结。即,不能使用串联索引后面的列进行搜索。这样不会走到串联索引,而是会扫全表。

所以在建立索引的时候要根据查询场景,建立联合索引的时候,列的顺序很重要,将需要单独查询的 Column 放到前面。

同样的,如果建立 3 列的串联索引,那么以下三种情况可以走索引,其他的不可以:

  1. 根据第一列查询;
  2. 根据第一列和第二列查询;
  3. 根据三列查询;

虽然串联索引可以带来更好的性能,但是第一列重复数据不多的情况下,尽可能使用单列的索引。因为这样可以1)节省空间;2)使数据的增加,修改,删除更快。因为索引也需要空间来存储,并且每次数据更新都需要更新索引。

但是,并不一定是有索引可用,就会用。上面我们说过,在某些情况下,使用索引可能要比不使用索引更慢。

数据库会有一个专门的组件,叫做“优化器”,当有很多选择的时候,优化器会决定选择哪一种。优化器有两种,一种给所有的可用查询方案进行评分(Cost-based optimizers, CBO);另一种通过固定的、提前设定的规则决定使用哪种方案(Rule-based optimizers, RBO)。第二种不灵活,很少用了。在前面提到的这种 TABLE SCAN 可能比 INDEX RANGE SCAN 更快的情况,优化器会使用表的统计数据(关键的数据比如 row 的量级,index tree 的深度等),来决定方案。如果在某种情况下没有统计数据的话,优化器会使用默认数据。如果提供了准确的统计数据,优化器通常会工作的很好。Oracle 数据库在新建索引之后,不会自动更新统计数据,最好手动更新一下。


4. 口吞玻璃而不伤身体

使用索引可以提高查询速度,但是有一些限制,比如必须大小写准确。

这里提供一种既可以使用索引,又可以大小写不敏感的方法。

数据库之所以无法使用索引,是因为如下的查询函数对它来说是和黑盒。

它看到的是这样:

而且它的索引是基于比较字符串建立的大小写敏感的索引,所以无法在索引树中进行忽略大小写的遍历。

解决方法非常简单,我们建立索引的时候,使用大写简历索引即可。这种索引叫做基于函数的索引,function-based index (FBI).

如果优化器发现索引的字段一模一样的出现在了查询语句中,就会使用索引。

MySQL 和 SQL Server 不支持 FBI,但是有另一种方法,就是增加一个字段,对这个字段建索引。

除了 UPPER 这种函数,你还可以使用其他的函数建索引,甚至可以使用用户自己定义的函数。但是通过 FBI 的原理,很显然可以联想到,你所使用的函数必须在任何情况下执行都得到相同的结果。因为 FBI 的原理不过是用同样的函数处理查询条件,和索引数据,相当于基于一个 mapping 索引了 mapping 之后的数据。下面是一个反例,其余用一个用了外部变量(时间)的函数做 FBI。

这样的问题是,随着时间增加,人的年龄会变,但是索引好的数据不会变。

数据最终会腐烂。

不要 Over indexing!

第一次听说 FBI 的人,可能倾向于索引 Everything。每一个索引都不是零成本的,都需要维护。尽量优化索引和查询路径,使一种索引能够尽可能用于很多查询。

5. Parameterized Queries

这个东西简单来说,就是我们在执行 SQL 的时候,我们并不是直接告诉数据库我们要执行的 SQL。而是先告诉数据库我们要执行的语句是什么,再告诉数据库这个语句中某些变量是什么。一般 ORM 会这么做,因为 ORM 都是在执行相同的 SQL 语句,只不过每次执行的语句中的一些变量不同。

比如下面这个例子:

我们告诉数据库 Statement 是什么,但是里面有一个 ? 作为占位符(也可以是其他的字符)。然后再通过一个函数告诉它每一个位置的 ? 分别是什么。

这么做有两个好处:

  1. 防止 SQL 注入。你无法使用一个 ; 结束当前的 SQL 然后再插入恶意的 SQL,无论这个地方填上什么都会作为一个“参数”;
  2. 加速选择执行方案。如果每次都是执行相同的语句,只是中间有一些值不同。那么数据库每次都会选择相同的执行方案,这节省了每次都要选择执行方案的时间;

但是这也不是完全免费的。前面说过有些情况下,使用索引可能更慢。要选择最佳的执行计划,需要根据表中重复数据的分布决定。如果使用 Bind parameters 的话,因为数据库是根据 ? 占位符的 SQL 语句来选择执行计划的,考虑下面这样的 SQL:

如果 subsidiary_id 重复的很多的话,使用 TABLE SCAN 会快一些,如果重复很少的话,使用索引会快一些。这个时候数据库并不知道这个 ? 会是什么,也就无法选择执行计划。这时数据库会假设这个分布是均匀的,每次通过索引会得到相同数量的 ROW,从而选择一种查询计划。

和编译器类比的话,bind variables 就像是代码中的变量,直接写的 SQL 就像是常量。编译器可以对常量进行优化,甚至在编译的时候将它们计算好。但是变量,直到程序运行之后,编译器都不知道这个值是什么,也就无法做针对的优化。

简单来说,对一个 SQL 语句使用固定的查询计划可以减少评估查询计划的时间。对每个 SQL 都评估查询计划,可以总是使用最优的查询计划。举个例子,TODO List 中,大部分数据都是 Done 的状态,小部分数据是 Todo 的状态。所以查找 Done 的数据用 TABLE SCAN,查询 Todo 的数据使用索引,是比较合适的。所以开发者应该是最了解数据获取方式的角色。


6. Range 查找

上文中已经提到,INDEX RANGE SCAN 的瓶颈在于要遍历叶子节点,要提高性能,就要让需要遍历的叶子节点越少越好。即索引中相等的值越少越好。

考虑下面的 SQL:

假设我们对搜索的这两列( date_of_birth & subsidiary_id )建立索引的话,怎么建才能让查询更快呢?

这里的顺序很重要。假如是 date_of_birth & subsidiary_id 这样的顺序的话,那么查询先使用第一列 date_of_birth 的索引过滤出来一些 ROW,然后再这些 ROW 中寻找合适的 subsidiary_id。这个时候,第二列 subsidiary_id 是无法用上的,因为我们前面已经说过,只有在第一列的数据相同的时候,才会使用第二列索引。对于 date_of_birth 不同的这些 ROW 来说,subsidiary_id 的索引用不上。这个时候会有很大一个范围的  TABLE SCAN 了。但是如果我们建立的顺序是 subsidiary_id & date_of_birth 呢?由于第一列的 WHERE 条件是 =,那么在进行后面的 WHERE 条件的时候,即使还是有很多 ROW,但是这些 ROW 的第一列索引都是相同的,所以我们在选择第二列的数据的时候依然可以命中 date_of_birth 的索引。

简单来说,就是建立多列索引的时候,将需要用 = 查询的列的索引放在最左侧,RANGE 搜索的列往后放。

LIKE 查询

LIKE 可能使用索引,也可能不使用,通配符的位置很重要。

因为索引是按照字符串对比来建立的,所以很显然,% 并不能用于索引匹配。简单来说,% 之前的内容会通过索引 access,% 开始就不会了。

比如下面这个例子:

Postgres 的查询计划如下:

% 开始就要 RANGE SCAN 了,所以 % 放的越往后越好。

% 不同的几个位置的查询对比:

如果 % 在很前面,要 INDEX RANGE SCAN 一大部分数据的话,那就没有 TABLE SCAN 快了。所以优化器要决定是否走索引。

当使用上文提到的 Bind Parameters 的时候,就比较麻烦了。因为优化器并不知道传进来的 LIKE 参数,% 在什么地方。大多数数据库在这种情况下都假设 % 不会出现在开头的地方,从而使用索引。如果需要全文查询的话,只能不使用 Bind Parameters,自己拼接 SQL 查询了。但是这样优化器的成本要高一些,并且用户需要自己防止 SQL 注入。但是 Postgres 数据库除外,Postgres 假设 % 会出现在前面,从而不使用索引。所以如果是 PG 的话,要走索引才需要拼接 SQL。不同的数据库有不同的行为,这个时候用执行计划确认一下最靠谱。

Index Merge

某些情况下,无论怎么建立索引都避免不了  RANGE SCAN,比如下面这个查询:

如果数据分布是平局的,那么对这两列建立索引的话,总是避免不要 RANGE SCAN 一大部分的数据。

这种情况其实分别对这两列建立索引更好。数据库会分别用两列的索引查出数据,然后将两个结果合并,这样就避免了大量的读表。

7. 部分索引

Postgres 和 Oracle 支持部分索引,这样有什么好处呢?

考虑实现一个任务队列,最常用的操作是从队列中取出未处理过的任务,而处理过的任务很少需要读。

因为这两个 WHERE 条件都是 = ,所以在这里索引的顺序无所谓。如果我们这样建立索引,是可以通过索引查询的。

考虑到我们要查询的目标行是 processed = 'N' 的,而这个表中大部分的数据都是已经处理过的,都不是我们要找的。那能否只对这部分数据建立索引呢?

这样只索引了一部分数据,查询未处理过的数据才会用到这个索引。另外注意到我们索引的字段也改变了,之前要索引 (receiver, processed) 两个字段,现在只索引 receiver 一个字段。因为索引本身已经包含一个信息:“使用索引查找的都是 processed = 'N' 的,这个字段也就不需要保存了。

综上,部分索引从两个维度节省了空间:

  1. 索引的行数变少了,只索引为处理过的;
  2. 索引的列变少了,因为被索引的都是未被处理过的数据;

其他一些不会使用索引的情况:

Date 类型

有些数据库(比如 Oracle ),没有 Date 类型,只有带 Time 的表示时间的类型。所以要查询日期的时候,常用的一个函数是 TRUNC,这个函数将时间部分设置为 Midnight。比如,查询昨天的销售额:

这个时候如果有 sale_date 的索引的话,是不会使用的。原因在上文 FBI 已经介绍个过了,函数对于数据库来说是个黑盒,不同的函数以为着不同的索引。

解决方法是使用 TRUNC 函数建立 FBI。或者直接指定查询范围到时间精度。但是要注意,BETWEEN 包含查询边界,所以这里手动拼接 SQL 的时间范围话,一定是从开始时间,到下一天的时间减去 1 个最小的时间精度单位。

以下是用 Postgres 实现的一个例子:

当然,更准确的一种方法是在应用的代码内拼接 SQL 的时间边界。或者不要用 BETWEEN,用 >= start_date AND < end_date.

数字和字符串

原理类似的,数据数据库用字符创(TEXT, VARCHAR)来保存数字的话(当然这是一个 bad practice),那么查询的时候也要格外小心。

这样查询,是走不到索引的。

原理是数据库发现要查的 = 的值,和数据库里面的列值是不一样的,就会进行隐式的类型转换,效果其实类似下面这样:

如此,就和我们前面提到过的 FBI 一样,函数对于优化器来说是一个黑盒的存在,所以优化器会决定 TABLE SCAN。

要解决这个问题也很简单,只要避免隐式的类型转换(避免使用函数就好了)。我们在查询的时候就转换好类型。

使用冗余的 where 语句暗示走索引

有时候我们要结合多列来查询,举个简单的例子,比如一列存了日期,一列存了时间,查询过去 24 小时的数据,需要以下的 SQL:

这个查询显然是无法使用任何一列的索引的。当然,最好是将时间和日期存到一列中,但是在修改表结构比较麻烦的情况下,我们可以想办法让这个查询走索引(即使是部分索引)。

这里的技巧是多使用一个 where,优化器会决定先用索引过滤出一部分数据,然后再扫表。

类似的技巧也可以用在 Bind Parameters 上。

还记得下面这个查询吗?

由于事先不知道这两列的分布情况,所以优化器无法做出选择。但是假如我们知道 LIKE 总是会有 % 的话,我们可以用一个 trick 暗示优化器不要走索引。

虽然和一个空字符串连接是冗余的,但是优化器会因为这个,不考虑 last_name 这一列的索引。

Smart Logic

SQL 强大的一个功能是支持嵌套查询。这个功能之所以可能,是因为优化器是作用在运行时,可以动态的给出查询计划。但是每次选择查询计划也带来了开销,这个开销可以使用 Bind Parameter 来解决。

有一个常见的错误,是想用静态 SQL 来替代动态 SQL。

举下面的例子,假设有一个表,这个表的三列中任何一列都可能用于查询。有人就想出用下面这个 SQL 代替:

这个静态 SQL,可以实现使用三列中的任何一(二/三都可)查询,只要将其他没有用到的列设置为 NULL 就好。

但是优化器在面对这个 SQL 的时候,只能按照最坏的 Case 准备,所以它做出的选择是扫全表。

所以最好的使用方式,应该 SQL 中只写用到的 filter:

The most reliable method for arriving at the best execution plan is to avoid unnecessary filters in the SQL statement.

Math

最后一个经常引起误解的带有数学计算的 SQL,考虑下面这个 SQL,能使用索引嘛?

下面这个呢?

如果换个角度考虑问题,如果你是一个数据库开发者,你会在你的数据库里面加一个计算器吗?大多数的回答,都是 No。所以以上两个查询都无法使用索引。

类似的,为了暗示优化器不要使用索引,你可以在查询中加0.

如果必须要用的话,可以使用 FBI 对这个表达式创建索引。