Schema Design, Normalization and Joins

// Denormalized: every order repeats its customer's name and city.
// Normalized: the customer is stored once and orders point at it with customerId.
export function normalize(flatOrders) {
  const customers = new Map();
  const orders = flatOrders.map(({ id, customerId, name, city, total }) => {
    customers.set(customerId, { name, city }); // the last row seen wins, which is exactly the drift problem
    return { id, customerId, total };
  });
  return { customers, orders };
}

// Customers whose orders disagree about their own city: the update anomaly, found after the fact.
export function inconsistentCustomers(flatOrders) {
  const cities = new Map();
  for (const o of flatOrders) {
    if (!cities.has(o.customerId)) cities.set(o.customerId, new Set());
    cities.get(o.customerId).add(o.city);
  }
  return [...cities].filter(([, set]) => set.size > 1).map(([id]) => id);
}

// Three ways to join users (n rows, unique id) with orders (m rows) on user id.
// Each returns the matching rows and how many comparisons or hash operations it used.
const pair = (u, o) => ({ name: u.name, total: o.total });

// Nested loop: for every user, scan every order. n x m steps (fast only when the inner side has an index).
export function nestedLoop(users, orders) {
  const rows = [];
  let steps = 0;
  for (const u of users) {
    for (const o of orders) {
      steps += 1;
      if (o.userId === u.id) rows.push(pair(u, o));
    }
  }
  return { rows, steps };
}

// Hash join: build a hash table on one side, probe it with the other. n + m steps, needs memory for the table.
export function hashJoin(users, orders) {
  const rows = [];
  const byId = new Map();
  let steps = 0;
  for (const u of users) {
    steps += 1;
    byId.set(u.id, u);
  }
  for (const o of orders) {
    steps += 1;
    const u = byId.get(o.userId);
    if (u) rows.push(pair(u, o));
  }
  return { rows, steps };
}

// Merge join: both inputs already sorted by key, so walk them together once. n + m steps, no extra memory.
export function mergeJoin(users, orders) {
  const rows = [];
  let i = 0;
  let j = 0;
  let steps = 0;
  while (i < users.length && j < orders.length) {
    steps += 1;
    if (users[i].id < orders[j].userId) i += 1;
    else if (users[i].id > orders[j].userId) j += 1;
    else {
      rows.push(pair(users[i], orders[j]));
      j += 1; // ids are unique on the user side, so only the order side advances
    }
  }
  return { rows, steps };
}