在data.table中设置键的目的是什么？

Question

我正在使用 data.table，有很多函数需要我设置键（例如X[Y]）。因此，我希望了解键的作用，以便正确设置数据表中的键。

---

我读过的一些资料中包括?setkey。

setkey() 对一个data.table进行排序并标记。排序后的列就是键。键可以是任意顺序的任意列。列总是按升序排序的。表是原位更改的。除了临时工作内存（至少一个列大小）之外，不进行任何副本复制。

我的理解是，键将“排序”data.table，导致与order()具有非常相似的效果。然而，它没有解释设置键的目的。

---

数据表FAQ 3.2和3.3解释了：

3.2 我在一个大表上没有键，但分组仍然非常快。为什么？

data.table使用基数排序。这比其他排序算法快得多。基数排序专门用于整数，参见?base::sort.list(x,method="radix")。这也是为什么setkey()很快的原因。当没有设置键或者我们按不同于键的顺序进行分组时，我们称之为“adhoc by”。

3.3 为什么按键列进行分组比临时分组快？

因为每个分组在RAM中都是连续的，从而最大限度地减少了页面获取，并且内存可以批量复制（C中的memcpy）而不是循环处理。

从这里，我猜测设置键可以让R使用“基数排序”而非其他算法，这就是为什么它更快的原因。

---

10分钟的快速入门指南也有关于键的指南。

1. 键

让我们从考虑data.frame开始，特别是行名（或英文中的row names）。也就是说，一个单独的行可以拥有多个名称。这不是我们在data.frame中习惯于看到的。我们知道每行最多只有一个名称。一个人至少有两个名字，一个名和一个姓。例如，按姓氏排序，然后按名字排序的电话簿就很有用。但是，在data.frame中，每一行只能有一个名字。

键由一列或多列行名组成，这些行名可以是整数、因子、字符或其他某些类别，而不仅仅是字符。此外，通过键对行进行排序。因此，一个data.table最多只能有一个键，因为它不能以多种方式排序。

唯一性未得到强制执行，即允许重复的键值。由于行按键排序，因此键中的任何重复值都将连续出现。

电话簿有助于理解什么是键，但与具有因子列相比，键似乎没有什么不同。此外，它并没有解释为什么需要键（尤其是要使用某些函数），以及如何选择要设置为键的列。此外，在具有时间列的data.table中，将任何其他列设置为键可能会破坏时间列，这使得它更加令人困惑，因为我不知道是否允许将其他列设置为键。请问有人可以帮助我理解吗？

- Wet Feet

---

我猜设置一个键可以让R使用“基数排序”而不是其他算法，但从帮助中并没有得到这个信息。我的理解是通过设置键进行排序。你可以通过其他列进行“临时”排序，速度很快，但不如已经排序的快。 - Ari B. Friedman

我认为在选择行时，二分查找比向量扫描更快。我不是计算机科学家，所以我不知道这实际上意味着什么。除了常见问题解答之外，还可以参考介绍。 - Frank

Answer 1

除了这个答案以外，请还参考一下vignettes Secondary indices and auto indexing 和 Keys and fast binary search based subset。

这个问题强调了我们计划提到的其他vignettes。

---

我更新了这个答案（2016年2月），考虑到新的on=功能，它允许进行即席连接。请查看历史记录以获取早期（过时的）答案。

setkey(DT, a, b)具体做了什么？

它有两个作用：

1. 通过所提供的列（a，b）按引用以递增的顺序重新排列数据表 DT 的行。
2. 通过将名为sorted的属性设置为DT，将这些列标记为关键字列。

重新排序由于data.table内部的基数排序是快速的，而且节省内存（只分配一个额外的double类型的列）。

setkey()什么时候需要？

对于分组操作，setkey()从来没有是绝对必要的。也就是说，我们可以执行一个cold-by或者adhoc-by操作。

## "cold" by
require(data.table)
DT <- data.table(x=rep(1:5, each=2), y=1:10)
DT[, mean(y), by=x] # no key is set, order of groups preserved in result

然而，在v1.9.6之前，形式为x[i]的连接需要在x上设置key。 从v1.9.6+开始，使用新的on=参数不再需要这样做。因此，在此处设置键也不是绝对要求。

## joins using < v1.9.6 
setkey(X, a) # absolutely required
setkey(Y, a) # not absolutely required as long as 'a' is the first column
X[Y]

## joins using v1.9.6+
X[Y, on="a"]
# or if the column names are x_a and y_a respectively
X[Y, on=c("x_a" = "y_a")]

注意，即使是keyed join，也可以显式指定on=参数。

唯一需要绝对设置key的操作是foverlaps()函数。但我们正在开发一些更多功能，完成后将消除此要求。

• 那么为什么要实现on=参数呢？

  有很多原因。

  1. 它允许清楚地区分作为涉及两个data.tables的操作。仅执行X[Y]并不能很好地区分这一点，尽管通过适当命名变量可能会清楚。

  2. 它还允许立即通过查看代码行（而不必回溯到相应的setkey()行）理解正在执行join/subset的列。

  3. 在添加或更新by reference的列的操作中，on=操作更加高效，因为它不需要重新排序整个数据表才能添加/更新列。例如，

      ## compare 
      setkey(X, a, b) # why physically reorder X to just add/update a column?
      X[Y, col := i.val]
     
      ## to
      X[Y, col := i.val, on=c("a", "b")]
     

     在第二种情况下，我们不需要重新排序。计算顺序并不耗时，而是在RAM中对数据表进行物理重新排序，通过避免它，我们保留了原始顺序，并且性能也得到了保证。

     除非您在重复执行连接操作，否则除键控和特别指定的连接之间没有明显的性能差异。

     这引出了一个问题，现在键入data.table有什么优势呢？

     键入data.table会根据RAM中的列对其进行物理重新排序。计算顺序通常不是耗时的部分，而是重新排序本身。但是，一旦我们在RAM中对数据进行排序，同一组的行都是连续的，因此非常高效。排序有助于加速针对键入数据表的操作。

     因此，必须确定重新排序整个数据表所花费的时间是否值得以高速缓存为基础的连接/聚合的时间。通常，除非在对同一键入数据表执行重复分组/连接操作，否则不应该有明显的区别。

     因此，在大多数情况下，不再需要设置键。我们建议尽可能使用on=，除非设置键具有您想要利用的性能显着提高。

     如果您使用setorder()重新排序data.table并使用on=，相对于键控连接，您认为性能会如何？如果到目前为止您已经跟随了这个问题，应该可以回答它 :-）。

- Arun

---

好的，谢谢！直到现在，我还没有意识到"二分查找"究竟是什么意思，也不太理解为什么要使用它而不是哈希。 - Frank

@Arun，DT[J(1e4:1e5)] 真的等同于 DF[DF$x > 1e4 & DF$x < 1e5, ] 吗？你能告诉我 J 的含义吗？此外，由于 sample(1e4, 1e7, TRUE) 不包括大于1e4的数字，因此该搜索不会返回任何行。 - fishtank

@fishtank，在这种情况下，应该使用>=和<=——已修复。J（和.）是list的别名（即它们是等效的）。在内部，当i是一个列表时，它会被转换为一个data.table，随后使用二进制搜索来计算行索引。将1e4更正为1e5以避免混淆。感谢您的发现。请注意，我们现在可以直接使用on=参数来执行二进制子集，而不是设置键。从新的HTML文档中阅读更多信息。并且请关注该页面以获取有关连接的vignettes。 - Arun

也许这个内容需要更全面的更新？“根据需要”部分似乎已经过时了，例如。 - MichaelChirico

哪个函数可以告诉你正在使用的键？ - skan

Answer 2

关键字基本上是一个数据集的索引，它允许非常快速和高效的排序、过滤和连接操作。这些可能是使用数据表而不是数据框架的最好理由（使用数据表的语法也更加用户友好，但这与关键字无关）。

如果您不理解索引，请考虑以下例子：电话簿通过姓名进行“索引”。因此，如果我想查找某个人的电话号码，这很简单。但是假设我想按电话号码搜索（例如查找谁拥有特定的电话号码）？除非我可以通过电话号码“重新索引”电话簿，否则将需要很长时间。

考虑以下示例：假设我有一个包含美国所有邮政编码的表格ZIP（>33,000），以及相关信息（城市、州、人口、中位收入等）。如果我想查找特定邮政编码的信息，如果我首先 setkey(ZIP, zipcode)，则搜索（过滤）大约快了1000倍。

另一个好处与连接有关。假设我有一个人员名单和他们所在邮政编码的数据表（称为“PPL”），我想附加来自ZIP表的信息（例如城市、州等）。以下代码可以实现：

setkey(ZIP, zipcode)
setkey(PPL, zipcode)
full.info <- PPL[ZIP, nomatch = FALSE]

这是一种“连接”的方式，我将基于一个公共字段（邮政编码）从2个表中获取信息。对于非常大的表来说，使用数据框架进行此类连接非常慢，但使用数据表格非常快速。在一个真实的例子中，我不得不对完整的邮政编码表执行超过20,000次此类连接。使用数据表格，脚本运行大约需要20分钟。我甚至没有尝试使用数据框架，因为这将需要超过2周的时间。

在我看来，你不应该仅仅阅读，而是要学习FAQ和入门材料。如果您有一个实际的问题可以应用它，那么就更容易理解。

[对@Frank的回应]

关于排序 vs. 索引 - 基于这个问题的答案，看起来setkey(...)确实重新排列了表中的列（例如物理排序），并且没有创建数据库意义上的索引。这有一些实际的影响：首先，如果在具有setkey(...)键的表中设置键，然后更改键列中的任何值，data.table仅将表声明为不再排序（通过关闭sorted属性）; 它不会动态地重新索引以保持正确的排序顺序（就像在数据库中发生的那样）。此外，使用setkey(DT, NULL)“删除键”不会将表恢复到其原始的未排序状态。

关于筛选 vs. 连接 - 实际上的区别是，筛选从单个数据集中提取子集，而连接基于公共字段合并来自两个数据集的数据。有许多不同种类的连接（内部、外部、左侧）。上面的示例是一个内部连接（仅返回两个表都具有相同键的记录），这与筛选具有许多相似之处。

- jlhoward

---

关于你的第一句话...它已经排序了，对吧？而且连接不是过滤器的特殊情况（或者说是以过滤为第一步的操作）吗？看起来“更好的过滤”总结了整个优点。 - Frank

或者更好的扫描，我想。 - Wet Feet

@jlhoward 谢谢。我之前的看法是，设置键值并不是排序的好处之一（因为如果你想要排序，你应该直接排序），而且 setkey 实际上会对行进行不可逆转的重新排序。如果仅仅是为了显示目的，那么我如何根据“真实”的顺序打印前十行（在设置键值之前我所看到的顺序）？我很确定 setkey(DT,NULL) 并不能做到这一点...（续） - Frank

此外，我还没有查看包的代码，但要加入 X[Y,...]，您需要使用键“过滤”X的行。当然，在此之后会发生其他事情（Y的列可用，并且有一个隐含的按照-without-by），但我仍然不认为这是一个概念上独特的好处。我猜你的答案是以您可能想要执行的操作为术语，尽管在这种区别可能有所帮助。 - Frank

@Frank - 所以 setkey(DT,NULL) 移除了键但不影响排序顺序。在这里提出了一个问题 here。让我们看看。 - jlhoward