作者都是各自领域经过审查的专家,并撰写他们有经验的主题. 我们所有的内容都经过同行评审,并由同一领域的Toptal专家验证.
Mirko designs and develops massive, extreme-workload databases. He also trains software developers on databases and SQL.
如果使用得当,SQL数据库索引可以非常有效,就像魔术一样. 但是,下面的一系列练习将展示大多数SQL索引的逻辑 正确使用它们-很简单.
在这个系列中, SQL索引说明, 我们将介绍使用索引访问数据的动机,以及按照所有现代rdbms的方式设计索引的动机. 然后,我们将查看用于为特定查询模式返回数据的算法.
You don’t have to know much about indexes to be able to follow SQL索引说明. 只有两个先决条件:
主要议题 SQL索引说明 将进入:
这不仅仅是一个SQL索引教程—它深入了解了索引的底层机制.
我们将通过练习和分析解决问题的方法来了解RDBMS是如何使用索引的. Our exercise material consists of read-only Google Sheets. To do an exercise, you can copy the Google Sheet (文件→复制) or copy its contents into your own Google Sheet.
在每个练习中,我们都会展示an SQL 使用Oracle语法的查询. For dates, we will use the ISO 8601 format, YYYY-MM-DD
.
The first task—don’t do it just yet—is to find all rows from 预订电子表格 for a specific client of a hotel reservation system, 然后把它们复制到你自己的电子表格中, simulating the execution of the following query:
SELECT
*
FROM
预订
WHERE
ClientID = 12;
但我们要遵循一个特定的方法.
For the first try, do not use any sorting or filtering features. 请记录下花费的时间. 生成的工作表应该包含73行.
下面的伪代码演示了不排序完成任务的算法:
对于reservation中的每一行
如果预订.ClientID = 12则获取reservation.*
在本例中,我们必须检查所有841行以返回并复制满足条件的73行.
For the second try, sort the sheet according to the value of the ClientID
column. 不要使用过滤器. 记录时间,并将其与在不排序数据的情况下完成任务所需的时间进行比较.
After sorting, the approach looks like this:
对于reservation中的每一行
如果ClientID = 12,则获取reservation.*
Else if ClientID > 12 exit
This time, we had to check “only” 780 rows. If we could somehow jump to the first row, it would take even less time.
But if we would have to develop a program for the task, this solution would be even slower than the first one. That’s because we would have to sort all the data first, which means each row would have to be accessed at least once. 这种方法只有在表已经按照期望的顺序排序时才有效.
现在的任务是统计2020年8月16日的入住次数:
SELECT
COUNT (*)
FROM
预订
WHERE
DateFrom = TO_DATE('2020-08-16', 'YYYY-MM-DD')
使用练习1中的电子表格. 衡量和比较在有排序和没有排序的情况下完成任务所需的时间. 正确的数字是91.
对于不排序的方法,算法与练习1中的算法基本相同.
排序方法也类似于前面练习中的方法. We will just split the loop into two parts:
-- Assumption: Table reservation is sorted by DateFrom
-- Find the first reservation from the 16th of August 2020.
Repeat
读下一行
直到日期日期= '2020-08-16'
——计算计数
While date = '2020-08-16'
增加计数
读下一行
警方检查员要求查看2020年8月13日和14日抵达酒店的客人名单.
SELECT
ClientID
FROM
预订
WHERE
日期(之间)
To_date ('2020-08-13', ' yyyy-mm-dd ')和
TO_DATE (' 2020-08-14 ', ' YYYY-MM-DD ')
)
AND HotelID = 3;
检查员要尽快拿到名单. 我们已经知道,我们最好根据到货日期对表格/电子表格进行排序. 如果我们刚刚完成练习2,我们很幸运,因为表已经排序了. So, we apply the approach similar to the one from Exercise 2.
Please, 试着记录时间, 需要读取的行数, 以及列表上项目的数量.
-- Assumption: Table reservation is sorted by DateFrom
-- Find the first reservation from the 13th of August 2020.
Repeat
读下一行
Until DateFrom >= '2020-08-13'
——准备清单
While DateFrom < '2020-08-15'
如果HotelID = 3 then write down the ClientID
读下一行
使用这种方法,我们必须读取511行才能编译一个包含46个来宾的列表. 如果我们能精确地滑下去, 我们实际上并不需要从重复循环中执行324次读取来定位8月13日的第一个到达点. 然而,我们仍然需要读取100多行来检查客人是否带着 HotelID
of 3
.
检查员一直在等,但不会高兴:而不是客人的名字和其他相关数据, we only delivered a list of meaningless IDs.
We’ll get back to that aspect later in the series. Let’s first find a way to prepare the list faster.
对行进行排序 HotelID
then DateFrom
, we can select all columns, then use the Google Sheets menu option 数据→排序范围.
-- Assumption: Sorted according to HotelID and DateFrom
-- Find the first reservation for the HotelID = 3.
Repeat
读下一行
Until HotelID >= 3
-- Find the first arrival at the hotel on 13th of August
而HotelID = 3 and DateFrom < '2020-08-13'
读下一行
——准备清单
而HotelID = 3 and DateFrom < '2020-08-15'
写下ClientID
读下一行
我们不得不跳过前338个到达的人,然后找到第一个到达我们酒店的人. 在那之后,我们查看了103个更早到达的人,找到了8月13日的第一个. Finally, we copied 46 consecutive values of ClientID
. 它帮助我们在第三步,我们能够复制一个连续的id块. Too bad we couldn’t somehow jump to the first row from that block.
Now try the same exercise using the spreadsheet ordered by HotelID
only.
The algorithm applied to the table ordered by HotelID
only is less efficient than when we sort by HotelID
and DateFrom
(按此顺序):
-- Assumption: Sorted according to HotelID
-- Find the first reservation for the HotelID = 3.
Repeat
读下一行
Until HotelID >= 3
——准备清单
而HotelID = 3
If DateFrom between '2020-08-13' and '2020-08-14'
写下ClientID
读下一行
In this case, we have to read all 166 arrivals to the hotel with a HotelID
of 3
,并检查每个 DateFrom
属于请求的时间间隔.
Does it really matter whether we sort first by HotelID
and then DateFrom
反之亦然? 让我们来看看:先按顺序排序 DateFrom
,然后是 HotelID
.
-- Assumption: Sorted according to DateFrom and HotelID
-- Find the first arrival on 13th of August
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)
We located the first row with the relevant date, then read more until we located the first arrival to the hotel. 在那之后, 对于许多行, 两个条件都满足了, 正确的日期和正确的旅馆. 然而,在3号酒店抵达后,我们又有客人在同一天抵达4号、5号等酒店. 在他们之后, we had to again read rows for the next day for hotels 1 and 2, 直到我们能够读到我们感兴趣的酒店的连续到达.
我们可以看到, 所有方法在完整的行集中间都有一个连续的数据块, 表示部分匹配的数据. 方法2和方法4是逻辑允许我们在到达部分匹配结束之前完全停止算法的唯一方法.
方法4 has fully matched data in two blocks, 但是方法2是唯一一个目标数据都在一个连续块中的方法.
方法1 | 方法2 | 方法3 | 方法4 | |
---|---|---|---|---|
初始可跳过行 | 324 | 338 + 103 = 441 | 342 | 324 |
要检查的候选行 | 188 | 46 | 166 | 159 |
算法停止后可跳过的行 | 328 | 353 | 332 | 357 |
可跳过行的总数 | 652 | 794 | 674 | 681 |
从数字上看,在这种情况下,方法2显然具有最大的优势.
Doing these exercises should make the following points become clear:
Now, a sorted copy of a table sounds almost like a database index. 下一篇文章 SQL索引说明 covers 基本的索引实现. 感谢阅读!
数据库索引是一种重要的辅助数据结构,有助于加快数据检索速度. 执行SQL查询所访问的数据量是影响执行时间的主要因素. The use of well-designed indexes minimizes the volume of accessed data.
主要用例是基于类型为“列值在X和Y之间”的条件返回数据的查询.列上的索引允许RDBMS快速找到满足条件的第一行, read consecutive rows from the given range, and stop without needing to read any other data.
索引可以通过几种方式分类:它的结构(B-tree), 哈希表, binary, 柱形储存, 全文, etc.),是否集群,是否分区(本地、全局或根本不分区). 有些存储整行,有些存储派生值,有些存储直列副本.
A typical index is implemented using a balanced tree structure. Leaf levels of an index are sorted based on column values. So, 当我们想要查找索引列的特定值的所有行时, 我们能够快速找到第一个,并读取连续的行,只要它们匹配的值.
适当的索引可以显著减少SELECT语句访问的数据量, which is the main factor contributing to query execution time.
Modern databases often keep and publish massive volumes of data. 当用户试图检索没有适当索引的一小部分数据时, the retrieval (of a needle in a haystack) could take hours.
世界级的文章,每周发一次.
世界级的文章,每周发一次.