有效地合并大数据表

Question

我有两个相当大的data.table对象要合并。

• dt1 在5列上有500.000.000观察值。
• dt2 在2列上有300.000个观察值。

这两个对象具有相同的key叫id。

我想left_join从信息dt2到dt1。

例如：

dt1  <- data.table(id = c(1, 2, 3, 4),
               x1 = c(12, 13, 14, 15),
               x2 = c(5, 6, 7, 8),
               x3 = c(33, 44, 55, 66),
               x4 = c(123, 123, 123, 123))

dt2 <- data.table(id = c(1, 2, 3, 4),
              x5 = c(555, 666, 777, 888))
setkey(dt1, id)
setkey(dt2, id)

dt2[dt1, on="id"] 

> dt2[dt1, on="id"]
   id  x5 x1 x2 x3  x4
1:  1 555 12  5 33 123
2:  2 666 13  6 44 123
3:  3 777 14  7 55 123
4:  4 888 15  8 66 123

但是，合并我的原始数据时，R无法再分配内存。但是，合并的输出适合RAM。

完成此大型合并的最有效方式（速度与内存限制）是什么？

我们应该拆分应用合并吗？

我们应该使用数据库库来完成此工作吗？

您将如何有效地做到这一点？

Answer 1

键控分配应节省内存。

dt1[dt2, on = "id", x5 := x5]

我们应该使用数据库库来完成此工作吗？

那可能是个好主意。如果设置和使用数据库很麻烦，请尝试使用该RSQLite软件包。很简单

我的实验

tl; dr：对于一个玩具示例，与合并和替换相比，键分配所使用的内存减少了55％。

我编写了两个脚本，每个脚本都提供一个安装脚本，dt-setup.R以创建dt1和dt2。通过“ merge”方法dt-merge.R更新dt1了第一个脚本。第二个dt-keyed-assign.R使用密钥分配。这两个脚本都使用该Rprofmem()功能记录了内存分配。

为了不折磨我的笔记本电脑，我有dt1500,000行和dt23,000行。

脚本：

# dt-setup.R
library(data.table)

set.seed(9474)
id_space <- seq_len(3000)
dt1  <- data.table(
  id = sample(id_space, 500000, replace = TRUE),
  x1 = runif(500000),
  x2 = runif(500000),
  x3 = runif(500000),
  x4 = runif(500000)
)
dt2 <- data.table(
  id = id_space,
  x5 = 11 * id_space
)
setkey(dt1, id)
setkey(dt2, id)

# dt-merge.R
source("dt-setup.R")
Rprofmem(filename = "dt-merge.out")
dt1 <- dt2[dt1, on = "id"]
Rprofmem(NULL)

# dt-keyed-assign.R
source("dt-setup.R")
Rprofmem(filename = "dt-keyed-assign.out")
dt1[dt2, on = "id", x5 := x5]
Rprofmem(NULL)

在工作目录中使用所有三个脚本后，我在单独的R进程中运行了每个加入脚本。

system2("Rscript", "dt-merge.R")
system2("Rscript", "dt-keyed-assign.R")

我认为输出文件中的行通常遵循该模式"<bytes> :<call stack>"。我还没有找到好的文档。但是，前面的数字永远不会低于128，这是默认的最小字节数，低于该数字时，R不malloc用于矢量。

请注意，并非所有这些分配都加到 R 使用的总内存中。R可能会重用垃圾回收后已经拥有的某些内存。因此，这不是衡量在任何特定时间使用多少内存的好方法。但是，如果我们假设垃圾回收行为是独立的，那么它确实可以作为脚本之间的比较。

内存报告的一些示例行：

cat(readLines("dt-merge.out", 5), sep = "\n")
# 90208 :"get" "[" 
# 528448 :"get" "[" 
# 528448 :"get" "[" 
# 1072 :"get" "[" 
# 20608 :"get" "["

也有类似new page:"get" "["页面分配的行。

幸运的是，这些很容易解析。

parse_memory_report <- function(path) {
  report <- readLines(path)
  new_pages <- startsWith(report, "new page:")
  allocations <- as.numeric(gsub(":.*", "", report[!new_pages]))
  total_malloced <- sum(as.numeric(allocations))
  message(
    "Summary of ", path, ":\n",
    sum(new_pages), " new pages allocated\n",
    sum(as.numeric(allocations)), " bytes malloced"
  )
}

parse_memory_report("dt-merge.out")
# Summary of dt-merge.out:
# 12 new pages allocated
# 32098912 bytes malloced

parse_memory_report("dt-keyed-assign.out")
# Summary of dt-keyed-assign.out:
# 13 new pages allocated
# 14284272 bytes malloced

重复实验时得到的结果完全相同。

因此，键分配又分配了一页。页面的默认字节大小为2000。我不确定该如何malloc工作，相对于所有分配，2000很小，因此我将忽略这种差异。如果这很蠢，请责骂我。

因此，忽略页面，键分配分配的内存比合并少55％。

Answer 2

如果您必须采用拆分合并方法，并且以下操作对您的内存有效，请确保尽可能多地预分配以加快迭代速度。因此，当解决类似问题时，这样的事情是我能想到的最有效的解决方案：

dt1  <- data.table(id = c(1, 2, 3, 4),
                   x1 = c(12, 13, 14, 15),
                   x2 = c(5, 6, 7, 8),
                   x3 = c(33, 44, 55, 66),
                   x4 = c(123, 123, 123, 123))

dt2 <- data.table(id = c(1, 2, 3, 4),
                  x5 = c(555, 666, 777, 888))

dt1_id <- sort(unique(dt1$id)) # extract all ids that are in dt1
dt1_l_split <- length(dt1_id) # get number of iterations
dt2_l_split <- length(unique(dt2[id %in% dt1_id]$id))

split_dt1 <- vector(mode = "list", length = length(unique(dt1$id))) # preallocate vector
split_dt1 <- lapply(1:dt1_l_split, function(x) dt1[id %in% dt1_id[[x]]]) # fill list with splits

rm(dt1); gc() # remove the large data table to save memory and clean up RAM

dt1 <- lapply(1:dt1_l_split, function(i) {
  print(Sys.time())
  print(i)

  tmp <- dt2[id %in% dt1_id[[i]]] # load relevant parts from dt2
  merge(tmp, split_dt1[[i]], all = TRUE) # merge dt1 and dt2
})
rbindlist(dt1)

您可以尝试mclapply从parallel软件包中使用它来加快计算速度，尽管结果好坏参半，有时它确实可以加快速度，有时会更慢，所以我认为最好尝试一下。

另外（也是最简单的解决方案imo）只需将项目推送到您的Dropbox / Google云端硬盘/您喜欢的任何云中，然后设置一个具有52GB RAM，几个CPU和Windows Server的Google Cloud VM（可以，但无需进行设置） GUI等）。花了我10分钟左右的时间完成所有设置，第一年的预算为300美元，这基本上是免费的。