英文版刊载于 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 notifications
WHERE 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 notifications
WHERE notifications.user_id = ?
ORDER BY notifications.created_at desc
LIMIT ? 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 notifications
INNER JOIN notification_types ON notification_types.id = notifications.notification_type_id
JOIN 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: 2
Workers 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 共事对文章的评阅。