3

我正在尝试设计一个带有索引的数据库表的内存模拟。我已经实现了一个简洁的 DSL 来查询看起来像这样的表

table.select do
  age > 44
  name == "Adam"
end

并产生一堆Condition类的实例，比如EqCondition，GteCondition等等。嗯，这很容易。Table检查这些条件并选择适当的索引来执行查询。我坚持的是应该Index#select接受什么样的参数？如果它接受与 Table 的 select 方法相同的参数，它会执行两次相同的工作。假设我们需要选择年龄大于 25 岁的所有人。首先，Table 类确定 (age, name) 上有一个可以使用的索引。然后，索引应该确定这是一个仅涉及部分键的范围查询并相应地执行它。

我在询问有关如何正确设计它的一些想法（也许是在真实数据库中如何完成的一些更简单的版本）？

PS。这是Ruby，但我认为它不相关。在 Java/C# 中，它看起来像table.select(new GtCondition("age", 44), new EqCondition("name", "Adam"))

4

1 回答 1

0

考虑到 DBMS 上索引的目的是：

  • 减少IO
  • 优化连接
  • 并作为副作用：帮助执行一些约束（如 PK/FK）

当您处理内存中的所有数据时，有时只需进行线性扫描就足够了:)

如果您有疑问，请使用分析器……您会发现内存中包含 1000 个元素的集合非常小。如果您的代码没有任何 JOIN，则使用简单collection.filter(condition)的可能就足够了。

但它如何在数据库上工作？这是一个粗略的想法：

  • 首先，SELECT 表达式被转换为“规范树”。例如SELECT A.NAME,B.SOMETHING FROM A, B WHERE A.NAME=B.NAME AND B.OTHER > 10可以表示为：

    PROJECT(A.NAME, B.SOMETHING)
           |
FILTER(A.NAME=B.NAME, B.OTHER>10)
           |
    CARTESIAN PRODUCT
     |              |
PROJECT(A.NAME)     PROJECT(B.OTHER,B.SOMETHING)

  • 从那个表达式树中，有一些代数规则可以应用。目标是避免笛卡尔积，因为效率很低：

    PROJECT(A.NAME, B.SOMETHING)
           |
    EQ-JOIN A,B USING NAME
     |              |
PROJECT(A.NAME)     FILTER B.OTHER>10     
                    |
       PROJECT(B.OTHER,B.SOMETHING)

  • DBMS 引擎分析树和数据库的元数据（如索引类型、记录数），并更改树以优化它（即查询计划）。例如，如果 B 按 OTHER 排序，最好先做 FILTER：

    PROJECT(A.NAME, B.SOMETHING)
           |
    EQ-JOIN A,B USING NAME (NESTED LOOP JOIN)
     |              |
 PROJECT(A.NAME)    PROJECT(B.OTHER,B.SOMETHING)
                    |
                  FILTER B.OTHER>10 (UNSING INDEX ON OTHER)

  • 但是如果你这样做，并且你在内存中有 B 的缓冲区，那么你可能会丢失索引信息并且你不能再使用索引（并且连接的唯一选择是使用嵌套循环）。所以引擎可以检测到，并选择更好的计划，也许：

    PROJECT(A.NAME, B.SOMETHING)
           |
     FILTER B.OTHER>10
           |
    EQ-JOIN A,B USING NAME (HASH INDEX EQ-JOIN)
     |              |
 PROJECT(A.NAME)    PROJECT(B.OTHER,B.SOMETHING)

一旦计划就绪。它就像一个程序：引擎只是盲目地跟随它。

对于内存引擎，您如何使用它？您可以检测 EQUI JOINS，并将“计划”转换为使用哈希表。也许您可以使用平衡树来实现其他类型的索引，但可能并没有太大帮助：内存中的 O(n) 算法很好，O(nxm) 顺序是您必须避免的，这意味着避免笛卡尔积。

您可以这样做的启发式方法是：

  • 检测所有相等的过滤器（即 name=="Adam"），如果您的表有该字段的哈希索引...首先使用它，例如：table.findUsingHash('name', 'Adam')。

  • 然后只需扫描并过滤结果（即年龄> 44）：filter(table.findUsingHash('name', 'Adam'), function (e) { return e.age > 44 })

这个想法是首先做最具选择性的索引，所以 O(n) 扫描有一个小的 n。

注意：我很久没有做这种 DBMS 的东西了。所以我的树形图可能包含一些错误......请参阅 DBMS 书籍（如此）以获得更好的资源。

于 2013-01-18T01:21:31.470 回答