Статьи

Шесть Присоединяющихся Реализаций в Javascript

Июнь 8, 2018

Объединение — это операция между двумя таблицами данных, объединяющая результаты путем поиска ключей из одной таблицы во второй таблице. Несмотря на простую концептуальную операцию, есть много способов сделать это, и понимание вариаций важно для понимания поведения базы данных (обсуждение выбора алгоритмов см. В разделе « Планы выполнения SQL в Javascript »).

Очевидно, что это важно для настройки, так как в нем рассказывается, как вы можете повлиять на результат, но также объясняется одна из многих причин, по которой выход строки строки базы данных не гарантируется от запуска к выполнению одного запроса.

Чтобы представить, как это работает, мы сначала настроили простой эквивалент таблицы базы данных в Javascript:

schema = {
  tables: {
    people: [
      {
       first_name: 'gary',
       last_name: 'sieling',
       company: 1
      },
      {
       first_name: 'bob',
       last_name: 'sieling',
       company: 1
      },
      {
       first_name: 'ella',
       last_name: 'sieling',
       company: 2
      }
    ],
   companies: [
     {
       id: 1,
       company_name: 'acme corp'
     },
     {
       id: 2,
       company_name: 'bubble'
     }
   ]
  }
}

Самый простой тип объединения — это соединение с вложенным циклом, которое выполняет foreach для каждой таблицы, возвращая только совпадающие строки. Если в таблице A есть m строк, а в таблице B — n строк, это mxn операций.

Обратите внимание, что это внутреннее соединение — чтобы выполнить внешнее соединение, на каждом уровне необходимо отслеживать, была ли добавлена ​​строка, и при необходимости вставлять дополнения.

function nested_loop_join(a, b, keys, select) {
  output = [];
 
  second = [];
  while(row_b = b()) {
    second[second.length] = row_b;
  }
 
  var idx = 0;
  while(row_a = a()) {
    $.each(second, function(i, row_b) {
      if (row_a[keys[0]] === row_b[keys[1]]) {
        var new_row = {};
 
        $.each(select, function(k, col) {
          // cheat here for simplicity - should handle aliasing
          new_row[col] =
            (row_a[col] ? row_a[col] : row_b[col])
        })
 
        output[idx++] = new_row;
      }
    })
  }
 
  return s({from: output})
}
 
joined = nested_loop_join(
  s({from:schema.tables.companies}),
  s({from:schema.tables.people}),
  ["id", "company"],
   ["last_name", "company_name"])

Второй вариант — декартово соединение. Это объединяет каждую строку в таблице A с каждой строкой в ​​таблице B, не сравнивая, а затем фильтрует результаты до нуля. Это также операции mxn, и, как правило, это плохая идея, хотя, если две таблицы маленькие, их иногда выбирает база данных.

function cartesian_join(a, b, keys, select) {
  output = [];
  second = [];
  while(row_b = b()) {
    second[second.length] = row_b;
  }
 
  var cols = select;
  if (cols) {
    $.each(keys, function(i, c) {
      if ($.inArray(c, select) === -1) {
        cols[cols.length] = c;
      }
    });
  }
 
  var idx = 0;
  while(row_a = a()) {
    $.each(second, function(i, row_b) {
      var new_row = {};
 
      $.each(cols, function(k, col) {
        // cheat here for simplicity - should handle aliasing
        new_row[col] =
          (row_a[col] ? row_a[col] : row_b[col])
      });
 
      output[idx++] = new_row;
    })
  }
 
  return s({from: output, where: function(row) {
    return row[keys[0]] === row[keys[1]];
  }});
}

Третий вариант — поместить одну из таблиц в хэш-карту, где ключами являются идентификаторы поиска, а значения указывают на строки. Эта операция требует m + n операций — в идеале, большая из двух таблиц должна быть индексированной, так как предварительная сборка превращает ее в n операций.

function hash_join(a, b, keys, select) {
  var use_first = a.length < b.length;
  var lookup = {};
 
  var table_to_join = use_first ? a : b;
  var key_to_join = use_first ? keys[0] : keys[1];
 
  var table_to_hash = use_first ? b : a;
  var key_to_hash = use_first ? keys[1] : keys[0];
 
  for (var i = 0; i < a.length; i++)
    lookup[key_to_hash] = table_to_hash[i][key_to_hash];
 
  var idx = 0;
  output = [];
  for (var j = 0; j < table_to_join.length; j++) {
    var new_row = {};
    var left_row = table_to_join[j];
    var key = left_row[key_to_join];
    var right_row = table_to_hash[key];
 
    $.each(select, function(k, col) {
      new_row[col] =
        (left_row[col] ? left_row[col] : right_row[col])
    });
 
    output[idx++] = new_row;
  }
 
  return output;
}
 
hash_join(
  schema.tables.people,
  schema.tables.companies,
  ["company", "id"],
  ["last_name", "company_name"])

Первый вариант этого метода — симметричное хеш-соединение. Обратите внимание, что эта реализация слишком упрощена — я предполагаю, что каждый столбец идентификатора является первичным ключом в своей таблице, а не элементом, который может иметь много различных значений.

Самое замечательное в этом типе объединения состоит в том, что вы можете делать это целиком из индексов, а не из табличных данных, поэтому потенциально гораздо меньше для чтения в память. Если значения повторяются много раз, это будет очень быстро — в этом случае база данных платит за выборку значений для поддержания гистограммы.

function symmetric_hash_join(a, b, keys, select) {
  debugger;
  var lookup_a = {};
  var lookup_b = {};
 
  for (var i = 0; i < a.length; i++)
    lookup_a[a[i][keys[0]]] = a[i];
 
  for (var i = 0; i < b.length; i++)
    lookup_b[b[i][keys[1]]] = b[i];
 
  var output = [];
  var idx = 0;
  $.each(lookup_a, function f(key, row_a) {
    var row_b = lookup_b[key];
    if (row_b) {
      var new_row = {}
 
      $.each(select, function(k, col) {
        if (row_a[col]) new_row[col] = row_a[col]
      });
 
      $.each(select, function(k, col) {
        if (row_b[col]) new_row[col] = row_b[col]
      });
 
      output[idx++] = new_row
    }
  });
 
  return output;
}

Это объединение требует, чтобы все хэш-карты помещались в память, часто это неверное предположение, особенно при выборе больших таблиц. Альтернативный подход состоит в том, чтобы хэшировать записи, а затем использовать хеш для разделения данных (например, диапазонов или наиболее значимых цифр) — это позволяет загрузить два блока каждой таблицы, которые гарантированно содержат данные, а затем выполнить объединение. В этом посте я остановился на простых реализациях, но если вы хотите посмотреть, как будет работать элемент управления памятью, посмотрите  Масштабирование DataFrame в Javascript .

Последний подход — соединение сортировки-слияния. Это хорошо работает, если вы знаете, что ваши данные отсортированы заранее. Это занимает где-то между операциями max (m, n) и m + n и дает преимущество, заключающееся в том, что вы можете выполнять потоковую передачу записей — в памяти одновременно требуется не более одной строки.

function sort_merge_join(a, b, keys, select) {
   var sorted_a = a.sort(function f(x, y) {
     return
       x[keys[0]] === y[keys[1]] ? 0 :
       x[keys[0]] > y[keys[1]] ? 1 : -1
   });
 
   var sorted_b = b.sort(function f(x, y) {
     return
       x[keys[0]] === y[keys[1]] ? 0 :
       x[keys[0]] > y[keys[1]] ? 1 : -1
   });
 
   var a_pos = 0;
   var b_pos = 0;
 
   var a_len = a.length;
   var b_len = b.length;
 
   var output = [];
   var idx = 0;
 
   while (a_pos < a_len && b_pos < b_len) {
    var row_a = a[a_pos];
    var row_b = b[b_pos];
 
    var id_a = row_a[keys[0]];
    var id_b = row_b[keys[1]];
    if (id_a === id_b) {
      var new_row = {};
      $.each(select, function(k, col) {
        if (row_a[col]) new_row[col] = row_a[col]
      });
 
      $.each(select, function(k, col) {
        if (row_b[col]) new_row[col] = row_b[col]
      });
 
      output[idx++] = new_row;
 
      a_pos++;
      b_pos++;
    } else if (id_a < id_b) {
      a_pos++;
    } else {
      b_pos++;
    }
  }
 
  return output;
}

49
Share: