为什么哈希索引在 SQL 中使用 "Less than" 会变慢

Question

我已经完成了大学水平 SQL 课程的第一个学期，我们在该课程中使用了“SQL Mere Mortals 的查询”第 3 版。

长期我想从事数据治理或数据科学家的工作，因此需要更深入地挖掘，我找到了斯坦福 SQL 课程。今天参加第一个小测验，我答对了，但在这两个问题上我不明白为什么我答对了。

我的 'SQL for Mere Mortals' 书甚至没有涵盖哈希或基于树的索引，所以我一直在网上搜索它们。

我主要是根据她所说的猜测，但感觉更像是运气，而不是“我完全理解为什么”。所以我订购了 Thomas Cormen 的“算法导论”第 3 版，它上周就到了，但我需要一些时间才能通读全部 1,229 页。

在另一个 Whosebug 中找到那本书 link =>

斯坦福课程 => https://www.edx.org/course/databases-5-sql

我认为 College.enrollment 上的哈希索引不会加速，因为它们将其限制为小于实际数字的数字？？我根据这个 link Better to use "less than equal" or "in" in sql query 猜测如果我们使用 "<=" 而不是 "<" 查询会更快？

这只是一个排除过程，因为它提到了 WHERE 子句后的第一项，但后来却令人困惑，因为它提到了 Apply.cName = College.cName 的最后一部分。

我的问题：

我猜这类似于具有分子和分母、商和许多其他术语的代数，这些术语使用技术术语专门描述方程的一部分。您会如何使用技术术语来描述为什么这些答案是正确的。
关于第二个问题，为什么引用第二行的第一部分和引用同一行的最后部分作为答案。为什么他们不选择每一个的第一部分和最后一部分？

就上下文而言，我的大部分 SQL 查询都是为 PostgreSQL 编写的，现在在 PyCharm on python 中，但我使用 PgAgmin4 或MySqlWorkbench 桌面平台。

我欢迎您对纸质书籍或 pdf 的任何推荐，因为许多网站都有漏洞或令人困惑的参考技术细节。

谢谢

Answer 1

1.哈希索引仅对等式匹配有用，而树索引可用于不等式（< 或 >= 等）。

考虑到这一点，College.enrollment < 5000 不能使用哈希索引，因为它是不等式。所有其他选项都是完全相等匹配。

这就是为什么大多数 RDBMS 只允许您创建基于树的索引。

2。这个几乎悬而未决。

“WHERE 子句后的第一项” 不相关。 大多数 RDBMS 会根据他们认为合适的方式重新排序连接和过滤器，以便匹配索引和 table 统计数据。

我注意到给定的查询写得不好。 它应该使用正确的 JOIN 语法，它更清晰，并且已经使用了 30 年已经.

SELECT *   -- you should really specify exact columns
FROM Student AS s    -- use aliases
JOIN [Apply] AS a ON a.sID = s.sID   -- Apply is a reserved keyword in many RDBMS
JOIN College AS c ON c.cName = a.aName
WHERE s.GPA > 1.5 AND c.cName < 'Cornell';

现在很难说编译器会在这里做什么。很大程度上取决于基数（tables 的绝对值和相对值，以及 s.GPA 和 c.cName.

中的数据偏差

还要看是否加了secondary key（或者确实是INCLUDE）列，这个显然没有考虑。

鉴于上面的索引选项，没有其他索引（显然不现实），我们可以猜测：

Student.sID, College.cName
这可能会导致从 'Cornell' 开始对 College 进行有效的向后扫描，但是 Apply 需要与散列或简单的嵌套循环（每次扫描索引）连接。
Student 上的索引将意味着具有索引查找的高效嵌套循环。
Student.sID, Student.GPA 这是一个索引还是两个？如果它是两个单独的索引，则将使用第二个，而第一个显然将无用。 Apply 和 College 仍需要大量连接。
Apply.cName, College.cName
这可能会让你在这两列上进行合并连接，但是 Student 需要一个大连接。
Apply.sID, Student.GPA
Student 可以从 1.5 中有效地扫描，并且 Apply 可以被搜索到，但是 College 需要一个大连接。

在这些选项中，第一个或最后一个可能更好，但如果没有进一步的信息很难说。

在真实系统中， 我会在 all table 上有索引，并使用 INCLUDE明智地列，以避免键查找。您可能想要更好地了解哪些 table 是需要及早过滤的

Answer 2

第一题

A hash-index is not linearly-searchable（参见幻灯片 7），即，您不能使用哈希索引执行范围比较。这是因为（一般而言）散列函数是单向的：给定散列函数的输出，您无法确定输入，并且输出将显然随机顺序（具有随机顺序有利于确保散列集 table bin 上的负载均匀。

现在，举一个人为和过于简单的例子：

假设您有这些行：

PK | Enrollment
----------------
 1 |          1
 2 |         10
 3 |        100
 4 |       1000
 5 |      10000

这个 table 的完美哈希索引看起来像这样：

假设1的散列为0xF822AA896F34253E，10的散列为0xB383A8BBDAA41F98，依此类推...

EnrollmentHash     | PhysicalRowPointer
---------------------------------------
0xF822AA896F34253E |                  1
0xB383A8BBDAA41F98 |                  2
0xA60DCD4E78869C9C |                  3
0x49B0AF769E6B1EB3 |                  4
0x724FD1728666B90B |                  5

因此给定此散列table 索引，查看散列您无法确定哪个散列代表较大的注册值与较小的值。但是散列 table 索引确实可以让您 O(1) 查找单个特定值，这就是为什么它最适合离散的、非连续的数据值，尤其是 JOIN 条件中使用的列。

虽然树形哈希确实保留了有关值的相对排序信息，但具有 O( log n ) 查找时间。

第二题

首先，我需要重写查询以使用现代 JOIN 语法。旧样式（使用逗号）从 1992 年的 SQL-92 开始就已经过时了，那已经快 30 年了。

SELECT
    *
FROM
    Apply
    INNER JOIN Student ON Student.sID = Apply.sID
    INNER JOIN College ON Apply.cName = Apply.cName
WHERE
    Student.GPA > 1.5
    AND
    College.cName < 'Cornell'

现在，一般来说，回答此类问题的最佳方法是了解 table 的 STATISTICS（基数、值分布等）是什么。但如果没有它，我仍然可以做出一些猜测。

我假设 College 是最小的 table（~500 行？），Student 可能有 1-2m 行，并假设每个学生提出 4-5 份申请那么 Apply table 将有 ~5m 行。

...有了这个推论，我们可以推断出：

Student.sID = Apply.sID 是 ID 匹配 - 因此在大多数情况下哈希索引会更好（除非 PK 聚类很重要，但我不会离题）。
Student.GPA > 1.5 - 这是一个范围搜索，因此在这里使用基于树的索引会有所帮助。
College.cName < 'Cornell' - 同样，这是一个范围比较，因此这里基于树的索引也有帮助。

所以 best 索引将是 Student.GPA 和 College.cName，但这不是一个选项 - 所以让我们看看每个选项的好处是...

（当我写这篇文章时，我看到@charlieface 发布了他们的答案，其中已经涵盖了这个，所以我只是 link 到他们的答案以节省我的时间：）

为什么哈希索引在 SQL 中使用 "Less than" 会变慢

Why is hash index slower using "Less than" in SQL

sql-server

indexing

hash

binary-search-tree

第一题

第二题