table join implementations (via http://garysieling.com/blog/six-join-implementations-in-javascript)

cartesian_join.js

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]];
  }});
}

hash_join.js

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;
}
 

nested_loop_join.js

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})
}

sort_merge_join.js

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;
}

symmetric_hash_join.js

function symmetric_hash_join(a, b, keys, select) {
  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;
}