英文版刊载于Flexport Engineering Blog

简介

个别普遍认为索引能进步SQL性能，但这并不总是成立， 因为只有高效的索引能力真正进步SQL性能。事实上，过多的索引甚至会减慢写操作的速度。咱们之前的文章探讨了一个低效的索引是如何拖慢零碎性能的，但那里的示例是不罕用的GIN索引。这一次，咱们介绍的示例是低效的BTREE索引。在这两种示例中，高性能SQL的独特要害都是索引抉择度。

提醒：若一个索引能帮忙与它无关的查问在索引扫描中过滤掉大部分的行，就说这个索引有较好的抉择度。有较差的抉择度的索引常常会使索引扫描的性能升高到全表扫描的程度。

问题

Flexport平台让Flexport经营人员（客户经营团队和供应链经营团队），客户和货运合作伙伴能在咱们的各个应用程序中发送音讯。当一个音讯被发送，它的接管方会收到告诉。Flexport的一个经营人员有可能每周收到几千个告诉，为了帮忙他们治理好告诉，咱们开发了一些工具如：导航栏的“告诉”下拉菜单，容许用户按多种条件（工夫范畴、货运信息、客户信息）来查问相干告诉的“收件箱”。

值得器重的是，零碎设计应满足将来的业务规模而不产生性能降级。这些工具面对着残酷的性能挑战：因为业务的迅速增长，有些用户收到了几百万个告诉，于是他们的查问耗时居然超过了1分钟。

表构造

告诉表的构造大抵如下所示：

上图的表中各个列的含意是：

  • id：主键
  • user_id：外键，指向接管方用户
  • notification_type_id：外键，指向NotificationType
  • subject_id：外键，指向执行了某个操作而引起此告诉的用户
  • object_id：外键，指向被执行了某个操作而引起此告诉的对象
  • created_at：告诉创立工夫
  • updated_at：告诉批改工夫
  • read_at：告诉被标为“已读”的工夫
  • details：告诉的文字内容

接下来，咱们具体介绍几个慢SQL的例子和解决方案（文中的SQL和查问打算都有所批改，以暗藏商业敏感信息）。

例1: 未读告诉计数

SQL
SELECT COUNT(*)FROM notificationsWHERE notifications.user_id = ? AND read_at IS NULL

“read_at IS NULL”意为“未读”，因而这个查问会计算某用户的未读告诉数。在user_id列上有一个BTREE索引服务于此查问。

一个用户的告诉数能够是几千到几百万。对于少数用户，数量是几千，因而这个查问很快（毫秒级）。但客户经营团队的多数用户可有几百万个告诉，因而这个查问很慢（秒级乃至分钟级），因为索引扫描须要更多工夫来遍历几百万个索引项。能够称之为“数据歪斜”问题。

解决方案

咱们发现只有不到10%的告诉是未读的，因而索引扫描能够靠跳过已读告诉来提速。PostgreSQL反对一种名为“局部索引”的个性。咱们把user_id索引替换为“user_id WHERE read_at IS NULL”的局部索引。这个新索引只记录那些满足“read_at IS NULL”条件的行，因而大部分的行都被排除了，索引的大小缩小了90%。由此，这个查问就总是毫秒级的快了。

例2: 最近告诉列表

SQL
SELECT *FROM notificationsWHERE notifications.user_id = ?ORDER BY notifications.created_at descLIMIT ? OFFSET ?

这是一个分页查问，因而它查问的是某用户的最近一些告诉（按创立工夫降序排列）。与计数的例子类似，这个查问也是对少数用户快而对多数用户慢。又是“数据歪斜”问题。

解决方案

咱们发现(user_id, created_at)上的“多列索引”比user_id单列索引体现得更好。索引项在被存储时是按值排序的。在这个查问中，对于多列索引的扫描会在此索引空间中先定位到满足user_id值的索引子集，而后依序遍历这个按created_at值排序的子集并且在找到足够多（满足LIMIT子句）的项后立刻进行。请留神，此前已有一个(user_id, object_id, created_at)索引，但它的效率不如(user_id_ created_at)索引，因为其中的object_id列岂但无用甚至无害于这个查问。在它这，满足user_id值的索引项子集不是按created_at排序，而是按(object_id, created_at)的组合排序的，因而对它的遍历（冀望按created_at程序）会在不同的object_id上跳来跳去。

多列索引（又称为复合索引或组合索引）由一组列（list of columns）组成。这些列的排列程序很重要。正确的索引设计应该依照想要应用的搜寻模式来从左到右摆放这些列。个别地，若一个查问用一些列来过滤，又用另一些列来排序，那么你能够创立一个多列索引，申明中靠左边的是用于过滤的列，靠右边的是用于排序的列。

一个教训法令是，把首要的过滤条件放在多列索引中的第一位，它之后的列用于辅助过滤。例如用户姓名表偏向于采纳形如(last_name, first_name)的多列索引。

例3：按多种条件（工夫范畴、货运信息、客户信息）来查问相干告诉

SQL
SELECT notifications.*FROM notificationsINNER JOIN notification_types ON notification_types.id = notifications.notification_type_idJOIN messages ON messages.id = notifications.object_id AND notification_types.object_type = ‘message’JOIN shipments ON messages.messageable_id = shipments.id AND messages.messageable_type = ‘Shipment’WHERE notifications.user_id = ?AND notification_types.domain = ?AND shipments.status = ?AND shipments.client_id IN (?)AND (messages.assignee_id = ? OR messages.assignee_id IS NULL)AND messages.created_at >= ?AND notifications.created_at >= ?ORDER BY notifications.created_at DESC, notifications.id DESC

这个查问很简单。与之前的查问不同，这个查问即便以雷同的参数调用（当然，是对于同一个用户，因为user_id也雷同）也时快时慢。

慢的查问打算
以下是一个慢的查问打算：

QUERY PLAN----------------------------------------->  Sort  (cost=58696.04..58696.04 rows=1 width=553) (actual time=34338.192..34338.192 rows=0 loops=1)        Sort Key: notifications.created_at DESC, notifications.id DESC        Sort Method: quicksort  Memory: 25kB    ->  Nested Loop  (cost=3800.49..58660.11 rows=1 width=20) (actual time=34338.162..34338.162 rows=0 loops=1)        ->  Gather  (cost=3800.35..58659.94 rows=1 width=24) (actual time=34338.161..34339.487 rows=0 loops=1)                Workers Planned: 2                Workers Launched: 2                ->  Nested Loop  (cost=2800.35..57659.84 rows=1 width=24) (actual time=34328.555..34328.555 rows=0 loops=3)                    ->  Nested Loop  (cost=2799.78..57401.65 rows=31 width=20) (actual time=1684.157..34318.009 rows=1581 loops=3)                            ->  Parallel Bitmap Heap Scan on shipments  (cost=2799.21..46196.17 rows=138 width=12) (actual time=1365.688..1385.022 rows=7047 loops=3)                                Recheck Cond: (client_id = ANY (?::integer[]))                                Filter: (status = ?)                                Heap Blocks: exact=5882                                ->  Bitmap Index Scan on index_shipments_on_client_id  (cost=0.00..2799.13 rows=22114 width=0) (actual time=1364.729..1364.729 rows=22367 loops=1)                                        Index Cond: (client_id = ANY (?::integer[]))                            ->  Index Scan using index_messages_on_messageable_type_and_messageable_id on messages  (cost=0.56..81.19 rows=1 width=12) (actual time=4.341..4.672 rows=0 loops=21142)                                Index Cond: (((messageable_type)::text = 'Shipment'::text) AND (messageable_id = shipments.id))                                Filter: (((assignee_id = ?) OR (assignee_id IS NULL)) AND (created_at >= ?::timestamp without time zone))                                Rows Removed by Filter: 8                    ->  Index Scan using index_notifications_on_user_id_and_object_id_and_created_at on notifications notifications_1  (cost=0.57..8.32 rows=1 width=12) (actual time=0.006..0.006 rows=0 loops=4743)                            Index Cond: ((user_id = ?) AND (object_id = messages.id) AND (created_at >= ?::timestamp without time zone))        ->  Index Scan using notification_types_pkey on notification_types  (cost=0.14..0.17 rows=1 width=4) (never executed)                Index Cond: (id = notifications_1.notification_type_id)                Filter: (((object_type)::text = 'message'::text) AND (domain = ?)) Planning Time: 116.579 ms Execution Time: 34339.810 ms

其中的要害一步是

-> Index Scan using index_messages_on_messageable_type_and_messageable_id on messages (cost=0.56..81.19 rows=1 width=12) (actual time=4.341..4.672 rows=0 loops=21142)Index Cond: (((messageable_type)::text = ‘Shipment’::text) AND (messageable_id = shipments.id))Filter: (((assignee_id = ?) OR (assignee_id IS NULL)) AND (created_at >= ?::timestamp without time zone))Rows Removed by Filter: 8

这一步是一个Nested Loop Join，它的每一次loop都对指标表做一次索引扫描。每一次loop的均匀工夫为4.5毫秒(4.341..4.672)。从“loops=21142”可知总共有21142次loop，所以这一步的总工夫应为4.5 * 21142 = 95139毫秒，但整个查问执行的总工夫也只有34338毫秒。为什么？

咱们能从查问打算中看到这个信息：

Workers Planned: 2Workers Launched: 2

它示意并行度为3，即由1个领导过程和2个工作过程并行处理此查问（以后正在执行查问的过程为领导过程，还有两个额定的工作过程被启动）。因而，这一步的的理论总工夫要除以并行度，即4.5 * 21142 / 3 = 31713毫秒，这就能匹配查问执行的总工夫了。因为这一步耗费了大部分工夫，咱们要设法优化它。

快的查问打算
当咱们用雷同参数再次执行雷同查问时，失去了一个很相像但快得多的查问打算：

QUERY PLAN----------------------------------------......    ->  Index Scan using index_messages_on_messageable_type_and_messageable_id on messages  (cost=0.56..76.04 rows=1 width=12)        (actual time=0.012..0.012 rows=0 loops=20463)        Index Cond: (((messageable_type)::text = 'Shipment'::text) AND (messageable_id = shipments.id))        Filter: (((assignee_id = ?) OR (assignee_id IS NULL)) AND (created_at >= ?::timestamp without time zone))        Rows Removed by Filter: 8...... Planning Time: 4.771 ms Execution Time: 105.937 ms

它惟一的不同就是每一次loop的工夫(0.012..0.012)，比之前的快了375倍(4.5 / 0.012 = 375)。如果咱们这时换一组不同的参数来再次执行此查问，就又会失去一个慢的查问打算。简而言之，同一组参数对应的第一次执行较慢，而之后的再次执行就较快。快的查问打算与慢的查问打算简直雷同，而只有要害的那步的工夫不同。由此景象能揣测到什么呢？是的，有一个缓存。

剖析

这个慢查问有两个次要问题：

一个问题是，当缓存未命中时，对messages表进行索引扫描的loop太慢。这个索引扫描的条件只是一个简略值，却花了4.5毫秒，难以承受呢。咱们留神到，对notifications表的索引扫描就很快(慢至0.006毫秒，快至0.002毫秒)，这才比拟正当。那么是什么让它们有此差距呢？

咱们能够看到，对messages表的索引扫描有“Index Cond”和“Filter”这两种条件，而对notifications表的索引扫描则只有“Index Cond”这一种条件。messages表上的索引笼罩了messageable_type和messageable_id两列，所以此查问对它的扫描必须先加载索引文件，按messageable_type和messageable_id来过滤，而后加载表文件，再按assignee_id和created_at来过滤。表文件的加载须要屡次很耗时的读盘，但能够受害于缓存（这也就是为什么此查问用雷同参数再次执行就会变快）。要想让查问打算蕴含缓存信息，你能够执行“EXPLAIN (ANALYZE, BUFFERS) #{sql}”。索引查问的耗时能够通过索引抉择度来改良。

另一个问题是，查问打算器低估了shipments表按client_id过滤后的预期行数。以下信息宣称预期行数为138(rows=138)，但理论行数为21141(rows=7047 loops=3)：

-> Parallel Bitmap Heap Scan on shipments (cost=2799.21..46196.17 rows=138 width=12) (actual time=1365.688..1385.022 rows=7047 loops=3)

Hash Join会创立一个hashmap，对于行数较多的状况会速度更快，但耗费更多空间。Nested Loop Join只对于行数较少的状况更快，但节俭空间。查问打算器会对预期行数较多的状况抉择Hash Join，而对于预期行数较少的状况抉择Nested Loop Join。此例中，它认为只会有138行，因而抉择了Nested Loop Join。若采纳Hash Join，这一步应该会有所改进吧。

解决方案

SQL查问不应该依赖缓存的善良。缓存的确很棒！但在思考缓存之前，你的SQL查问应做到打铁还需本身硬。

首先咱们要改良索引抉择度。若messages表上的索引能通过笼罩更多列来取得更好的抉择度，那么就能缩小甚至罢黜表文件加载。因为“assignee_id IS NULL”条件过于宽泛而不合适缓存，所以咱们抉择只给现有索引追加一个created_at列。作为一个小优化，咱们还把抉择度较强的messageable_id提前为索引构造中的第一列。当初这个索引是在messages表的(messageable_id, messageable_type, created_at)列组上。每次loop的均匀工夫从4.5毫秒降到了0.338毫秒，查问执行的总工夫从34339毫秒降到了3893毫秒，快9倍。

那么，咱们能通知查问选择器“请抉择Hash Join”么？PostgreSQL不反对SQL hints，因而咱们只能设置“SET enable_nestloop = off”选型。这一选项强制PostgreSQL不许选Nested Loop Join，从而使其选Hash Join。查问执行的总工夫从34339毫秒降到了5568毫秒，快6倍。事实上，因为这一起因，MySQL 8放弃了Nested Loop Join而全面转向Hash Join。

索引抉择度的优化曾经足够好了。Hash Join的优化须要批改数据库设置，因而在生产环境不是很敢用，而且其成果也不能线性叠加在索引抉择度的优化成果上（1+1<2)。因而，咱们决定只采纳索引抉择度的优化。

生产环境的实在改善

以下图表展现了对“收件箱”施行优化之后，生产环境的显著改善。

因为业务增长带来高负载， API端点的错误率（优化前）高达11.8%

API端点的错误率（优化后）仅为0.8%，15倍改善（咱们在重构代码以进一步改善它）

论断

咱们探讨了对于BTREE索引性能的3个例子，它们都受害于索引抉择度的改良。抉择度不佳的索引岂但会耗费更多的内存和存储空间，而且也会升高SQL性能。作为一个准则，当设计业务关键性的数据库查问时，请留神和改良索引抉择度。

致谢

感激Joker Ye对相干工程工作的奉献，也感激Dylan Irlbeck，Vinod Kumar，David Goussev和其余Flexport共事对文章的评阅。