具有编辑距离 UDF 的 BigQuery 查询抛出错误

Question

我正在尝试使用编辑距离算法比较文章之间的内容。我在标准查询中创建了一个 UDF。当文章数量较少时（例如 10 篇文章，总比较为 10X10 = 100），它工作正常。

如果文章总数很大，比如100篇（总比较是100 x 100 = 10000）。 BigQuery UI 抛出以下错误：

错误：发生内部错误，请求无法完成。职位编号：newspapers-142716:US.bquijob_cfbb316_161c359b4ec

不知道是不是BigQuery在调用UDF的时候处理不了那么多的数据。 Edit Distance算法不是"cheap"运算，难道也是这个原因？

为此目的使用 UDF 是正确的方法吗？还有其他选择吗？

下面是我的 UDF 代码：

CREATE TEMPORARY FUNCTION
  editDistance(a STRING, b STRING)
  RETURNS FLOAT64
  LANGUAGE js 
  AS 
"""
  if(a.length == 0) return b.length; 
  if(b.length == 0) return a.length; 

  var matrix = [];

  // increment along the first column of each row
  var i;
  for(i = 0; i <= b.length; i++){
    matrix[i] = [i];
  }

  // increment each column in the first row
  var j;
  for(j = 0; j <= a.length; j++){
    matrix[0][j] = j;
  }

  // Fill in the rest of the matrix
  for(i = 1; i <= b.length; i++){
    for(j = 1; j <= a.length; j++){
      if(b.charAt(i-1) == a.charAt(j-1)){
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
                                Math.min(matrix[i][j-1] + 1, // insertion
                                         matrix[i-1][j] + 1)); // deletion
      }
    }
  }

  distance = matrix[b.length][a.length]
  
  return distance/Math.max(a.length, b.length)
  
  //return matrix[b.length][a.length];
    
"""
;

Answer 1

I wonder if it is because BigQuery can't handle that much amount of data when calling the UDF.

你是对的 - 你工作的实际错误是

Allocation failed - JavaScript heap out of memory

我想每篇文章都很长，可能只有几 KB，所以 matrix 你在函数内部构建的是几 MB。这种类型的 CROSS JOIN 处理可能更适合 DataFlow 或其他一些批处理工具。要在 BigQuery 中执行此操作，您需要将 table 分成更小的部分，或者将每篇文章运行作为单独的查询与其他所有文章进行对比（但这会导致多次扫描，并且可以昂贵）。

具有编辑距离 UDF 的 BigQuery 查询抛出错误

BigQuery Query with Edit Distance UDF Throws Error

user-defined-functions

sql-standards

google-bigquery