具有编辑距离的BigQuery查询UDF引发错误

Question

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

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

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

我想知道是不是因为BigQuery在调用UDF时无法处理大量数据。编辑距离算法不是“便宜”的操作，可原因呢？

为此目的使用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

我想知道是不是因为BigQuery在调用UDF时无法处理大量数据。

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

分配失败 - JavaScript堆内存不足

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