作者都是各自领域经过审查的专家,并撰写他们有经验的主题. 我们所有的内容都经过同行评审,并由同一领域的Toptal专家验证.
Mirko设计和开发大规模、极端工作负载的数据库. 他还对软件开发人员进行数据库和SQL方面的培训.
如果使用得当,SQL数据库索引可以非常有效,就像魔术一样. 但是,下面的一系列练习将展示大多数SQL索引的逻辑 正确使用它们-很简单.
在这个系列中, SQL索引说明, 我们将介绍使用索引访问数据的动机,以及按照所有现代rdbms的方式设计索引的动机. 然后,我们将查看用于为特定查询模式返回数据的算法.
你不需要知道很多关于索引的知识 SQL索引说明. 只有两个先决条件:
主要议题 SQL索引说明 将进入:
这不仅仅是一个SQL索引教程—它深入了解了索引的底层机制.
我们将通过练习和分析解决问题的方法来了解RDBMS是如何使用索引的. 我们的练习材料由只读的Google表格组成. 要做练习,你可以复制Google Sheet (文件→复制)或将其内容复制到您自己的Google Sheet中.
在每个练习中,我们都会展示an SQL 使用Oracle语法的查询. 对于日期,我们将使用ISO 8601格式, YYYY-MM-DD
.
第一个任务(先不要做)是找到from的所有行 预订电子表格 对于酒店预订系统的特定客户, 然后把它们复制到你自己的电子表格中, 模拟执行以下查询:
SELECT
*
FROM
Reservations
WHERE
ClientID = 12;
但我们要遵循一个特定的方法.
对于第一次尝试,不要使用任何排序或过滤功能. 请记录下花费的时间. 生成的工作表应该包含73行.
下面的伪代码演示了不排序完成任务的算法:
对于reservation中的每一行
如果预订.ClientID = 12则获取reservation.*
在本例中,我们必须检查所有841行以返回并复制满足条件的73行.
对于第二次尝试,根据的值对工作表进行排序 ClientID
column. 不要使用过滤器. 记录时间,并将其与在不排序数据的情况下完成任务所需的时间进行比较.
排序后,方法看起来像这样:
对于reservation中的每一行
如果ClientID = 12,则获取reservation.*
Else if ClientID > 12 exit
这一次,我们只能检查780行. 如果我们能跳到第一行,那就更省时了.
但是如果我们要为这个任务开发一个程序, 这种解决方案甚至比第一种解决方案还要慢. 这是因为我们必须先对所有的数据进行排序, 这意味着每一行至少要被访问一次. 这种方法只有在表已经按照期望的顺序排序时才有效.
现在的任务是统计2020年8月16日的入住次数:
SELECT
COUNT (*)
FROM
Reservations
WHERE
DateFrom = TO_DATE('2020-08-16', 'YYYY-MM-DD')
使用练习1中的电子表格. 衡量和比较在有排序和没有排序的情况下完成任务所需的时间. 正确的数字是91.
对于不排序的方法,算法与练习1中的算法基本相同.
排序方法也类似于前面练习中的方法. 我们将把循环分成两部分:
—假设:表预订按DateFrom排序
查找2020年8月16日起的第一个预订.
Repeat
读下一行
直到日期日期= '2020-08-16'
——计算计数
While date = '2020-08-16'
增加计数
读下一行
警方检查员要求查看2020年8月13日和14日抵达酒店的客人名单.
SELECT
ClientID
FROM
Reservations
WHERE
日期(之间)
To_date ('2020-08-13', ' yyyy-mm-dd ')和
TO_DATE (' 2020-08-14 ', ' YYYY-MM-DD ')
)
AND HotelID = 3;
检查员要尽快拿到名单. 我们已经知道,我们最好根据到货日期对表格/电子表格进行排序. 如果我们刚刚完成练习2,我们很幸运,因为表已经排序了. 因此,我们应用类似于练习2中的方法.
Please, 试着记录时间, 需要读取的行数, 以及列表上项目的数量.
—假设:表预订按DateFrom排序
查找2020年8月13日起的第一个预订.
Repeat
读下一行
Until DateFrom >= '2020-08-13'
——准备清单
While DateFrom < '2020-08-15'
如果HotelID = 3,则写下ClientID
读下一行
使用这种方法,我们必须读取511行才能编译一个包含46个来宾的列表. 如果我们能精确地滑下去, 我们实际上并不需要从重复循环中执行324次读取来定位8月13日的第一个到达点. 然而,我们仍然需要读取100多行来检查客人是否带着 HotelID
of 3
.
检查员一直在等,但不会高兴:而不是客人的名字和其他相关数据, 我们只提供了一份毫无意义的身份名单.
我们将在本系列后面的文章中回到这方面. 让我们先找到一种更快地准备列表的方法.
对行进行排序 HotelID
then DateFrom
,我们可以选择所有列,然后使用Google Sheets菜单选项 数据→排序范围.
—假设:根据HotelID和DateFrom进行排序
查找HotelID = 3的第一个预订.
Repeat
读下一行
Until HotelID >= 3
——查找8月13日第一个到达酒店的客人
而HotelID = 3 and DateFrom < '2020-08-13'
读下一行
——准备清单
而HotelID = 3 and DateFrom < '2020-08-15'
写下ClientID
读下一行
我们不得不跳过前338个到达的人,然后找到第一个到达我们酒店的人. 在那之后,我们查看了103个更早到达的人,找到了8月13日的第一个. 最后,我们复制46个连续的值 ClientID
. 它帮助我们在第三步,我们能够复制一个连续的id块. 可惜我们不能从那个块跳转到第一行.
现在用排序的电子表格做同样的练习 HotelID
only.
该算法应用于按排序的表 HotelID
这比我们排序的效率要低 HotelID
and DateFrom
(按此顺序):
—假设:根据HotelID分类
查找HotelID = 3的第一个预订.
Repeat
读下一行
Until HotelID >= 3
——准备清单
而HotelID = 3
日期从2020-08-13到2020-08-14
写下ClientID
读下一行
在这种情况下,我们必须读取所有到达酒店的166个 HotelID
of 3
,并检查每个 DateFrom
属于请求的时间间隔.
我们是否按顺序排序真的重要吗 HotelID
and then DateFrom
反之亦然? 让我们来看看:先按顺序排序 DateFrom
, then by HotelID
.
—假设:根据DateFrom和HotelID排序
8月13日第一个到货
While DateFrom < '2020-08-13'
读下一行
找到第一个到达酒店的人
While HotelID < 3 and DateFrom < '2020-08-15'
读下一行
Repeat
如果HotelID = 3
写下ClientID
读下一行
Until DateFrom > '2020-08-14' or (DateFrom = '2020-08-14' and HotelID > 3)
我们找到了第一行相关日期, 然后继续读下去,直到我们找到第一个到达酒店的人. After that, 对于许多行, 两个条件都满足了, 正确的日期和正确的旅馆. 然而,在3号酒店抵达后,我们又有客人在同一天抵达4号、5号等酒店. After them, 我们不得不再次读取第二天酒店1和2的行, 直到我们能够读到我们感兴趣的酒店的连续到达.
我们可以看到, 所有方法在完整的行集中间都有一个连续的数据块, 表示部分匹配的数据. 方法2和方法4是逻辑允许我们在到达部分匹配结束之前完全停止算法的唯一方法.
方法4在两个区块中完全匹配数据, 但是方法2是唯一一个目标数据都在一个连续块中的方法.
Approach 1 | Approach 2 | Approach 3 | Approach 4 | |
---|---|---|---|---|
初始可跳过行 | 324 | 338 + 103 = 441 | 342 | 324 |
要检查的候选行 | 188 | 46 | 166 | 159 |
算法停止后可跳过的行 | 328 | 353 | 332 | 357 |
可跳过行的总数 | 652 | 794 | 674 | 681 |
从数字上看,在这种情况下,方法2显然具有最大的优势.
做这些练习应该使以下几点变得清晰:
现在,表的排序副本听起来很像数据库索引. 下一篇文章 SQL索引说明 covers 基本的索引实现. 感谢阅读!
数据库索引是一种重要的辅助数据结构,有助于加快数据检索速度. 执行SQL查询所访问的数据量是影响执行时间的主要因素. 使用设计良好的索引可以最大限度地减少访问的数据量.
主要用例是基于类型为“列值在X和Y之间”的条件返回数据的查询.列上的索引允许RDBMS快速找到满足条件的第一行, 从给定范围中读取连续的行, 无需读取任何其他数据即可停止.
索引可以通过几种方式分类:它的结构(B-tree), hash table, binary, column-store, full-text, etc.),是否集群,是否分区(本地、全局或根本不分区). 有些存储整行,有些存储派生值,有些存储直列副本.
典型的索引是使用平衡树结构实现的. 索引的叶级是根据列值排序的. So, 当我们想要查找索引列的特定值的所有行时, 我们能够快速找到第一个,并读取连续的行,只要它们匹配的值.
适当的索引可以显著减少SELECT语句访问的数据量, 哪个是影响查询执行时间的主要因素.
现代数据库经常保存和发布大量数据. 当用户试图检索没有适当索引的一小部分数据时, (大海捞针)要花好几个小时.
布拉格,捷克共和国
2020年6月18日成为会员
Mirko设计和开发大规模、极端工作负载的数据库. 他还对软件开发人员进行数据库和SQL方面的培训.
世界级的文章,每周发一次.
世界级的文章,每周发一次.