7
\$\begingroup\$

Using the sample data from here, I'm attempting to write JS code (to the ES6 standard) that is equivalent to an SQL inner join. The solution below works fine, but it seems rather long. Is there a more concise approach?

const employees = [
    {name: 'Alice', department_id: 12},
    {name: 'Bob', department_id: 13},
    {name: 'Chris', department_id: 13},
    {name: 'Dan', department_id: 14},
    {name: 'Eve', department_id: null}
];

const departments = [
    {department_id: 12, name: 'Sales'},
    {department_id: 13, name: 'Marketing'},
    {department_id: 14, name: 'Engineering'},
    {department_id: 15, name: 'Accounting'},
    {department_id: 16, name: 'Operations'}
];

const ij1 = employees.flatMap(employee =>
    departments.map(department => {
        if (employee.department_id == department.department_id) {
            return {
                employee_name: employee.name,
                employee_department_id: employee.department_id,
                department_id: department.department_id,
                department_name: department.name
            }
        }
    }).filter(Boolean)
);

console.log(ij1);

\$\endgroup\$
6
  • \$\begingroup\$ Why do you need to do this? I can't find it, but there's an old blog post along the lines of "Are you doing SQL in the browser? Don't." Generally, the backend should be doing these operations on the database, so it'd be good to provide some context about why you're doing this, or how often this "function" will be called. If you're doing it more than once, you probably want objects keyed by id for faster lookups. In any case, there's not much code to review here--I'm surprised you think this is long, because it's just a few lines of code. There are probably bigger issues than length here. \$\endgroup\$
    – ggorlen
    Commented Apr 25 at 17:30
  • \$\begingroup\$ The data is coming from an external API. \$\endgroup\$
    – knot22
    Commented Apr 25 at 17:56
  • \$\begingroup\$ Thanks, but can you provide more details? Which API? How large are the structures? How often are you doing joins? Why not make those requests from a proxy API and cache them server side? Most third-party APIs block cross origin requests, and you'd want to keep your key safe on the server anyway. Like I said, I can maybe trim off a line of code here, but without understanding the full use case, it's probably not going to do you much good without seeing the whole forest from this one tree. \$\endgroup\$
    – ggorlen
    Commented Apr 25 at 17:58
  • \$\begingroup\$ Current use case - API is to access the company's ERP system data (this ERP system is a third party application), structure sizes vary depending on endpoint. Data from API is being consumed in a Vue app without a database. \$\endgroup\$
    – knot22
    Commented Apr 25 at 18:15
  • \$\begingroup\$ OK, thanks. How often are you running this join? One time or multiple? Are the sizes large enough that performance is a concern, or are these mostly small (less than a couple hundred items)? \$\endgroup\$
    – ggorlen
    Commented Apr 25 at 18:18

4 Answers 4

4
\$\begingroup\$

Use a Map

Existing answers are using Object.groupBy to create a map of departments grouped by id.

This is inappropriate as there is only a one to one relationship between department id and departments. Object.groupBy creates groups using arrays to hold members of each group. One to many.

Using a more appropriate Map to get departments by id will simplify the code a little as there is no need to do the additional array indexing when locating a department.

Don't duplicate data

Nor can I see why you duplicate the department_id as employee_department_id which is redundant information.

const employees = [{name: 'Alice', department_id: 12}, {name: 'Bob', department_id: 13}, {name: 'Chris', department_id: 13}, {name: 'Dan', department_id: 14}, {name: 'Eve', department_id: null}];
const departments = [{department_id: 12, name: 'Sales'}, {department_id: 13, name: 'Marketing'}, {department_id: 14, name: 'Engineering'}, {department_id: 15, name: 'Accounting'}, {department_id: 16, name: 'Operations'}];

console.log(innerJoinEmpDep(departments, employees));

function innerJoinEmpDep(deps, emps) {
    const depsById = new Map(deps.map(dep=> ([dep.department_id, dep])));
    const innerJoin = [];
    for (const emp of emps) {
        const dep = depsById.get(emp.department_id);
        if (dep) {
            innerJoin.push({
                employ: emp.name, 
                department: dep.name,
                depId: dep.department_id
            });
        }
    }
    return innerJoin;
}

\$\endgroup\$
7
  • \$\begingroup\$ Agreed on the data duplication point. The duplication here was a sanity check to make sure things were working as expected. \$\endgroup\$
    – knot22
    Commented Apr 26 at 12:27
  • \$\begingroup\$ Great answer, but new Map(deps.map(dep=> ([dep.department_id, dep]))) is two passes, and allocates an array for every element that gets thrown away to build the map. groupBy reads nicely, is succinct and is one-pass, with per-element allocation overhead (hence the reduce option I provided, which is one pass and has no allocation overhead), and the downside of having to use [0], but I provided a couple of alternatives that are 1 to 1. Using a traditional loop and push rather than reduce is probably a good call; less clever than reduce. \$\endgroup\$
    – ggorlen
    Commented Apr 26 at 13:55
  • \$\begingroup\$ Is a for...of loop preferable to .forEach()? If so, why? \$\endgroup\$
    – knot22
    Commented Apr 26 at 13:56
  • \$\begingroup\$ for ... of is generally better because it reads more nicely and looks more native--less parentheses, no function call overhead, cleaner syntax (more imperative, less functional). I generally only use .forEach if it's at the end of a chain or if I need an index. \$\endgroup\$
    – ggorlen
    Commented Apr 26 at 13:57
  • 1
    \$\begingroup\$ Sometimes I like to return early. While you can do it with a forEach, its easier to do that with a for ... of. Personal opinion mostly, as probably for other answers as well. There's no better, it's situational. \$\endgroup\$
    – Caramiriel
    Commented Apr 26 at 13:59
6
\$\begingroup\$

Based on your follow up comments, you're only running this once when the app loads, but you may have 10k+ items, so performance is a concern. Your current algorithm is quadratic and uses unnecessary passes.

Generally, you want to filter first, then map. The reason is that mapping first results in processing a bunch of items you may well be throwing away in the filter step.

.filter(Boolean) at the end of a chain is an antipattern. Generally, it's a lazy way to remove falsey values that could have been more properly handled earlier in the chain. Specifically, rewrite:

departments.map(department => {
    if (employee.department_id == department.department_id) {
        return {
            employee_name: employee.name,
            employee_department_id: employee.department_id,
            department_id: department.department_id,
            department_name: department.name
        }
    }
}).filter(Boolean)

as:

departments
  .filter(department =>
    employee.department_id === department.department_id
  )
  .map(department => ({
    employee_name: employee.name,
    employee_department_id: employee.department_id,
    department_id: department.department_id,
    department_name: department.name
  });

This is more performant and idiomatic: the filtering does only filtering, and the mapping only does mapping, rather than smushing both into map and then using filter later to remove undefined elements.

Similarly, using flatMap to filter by smushing empty arrays together involves an unnecessary inner array allocation for every item, regardless of whether the array is empty or not. This is OK for small pieces of data, but it's a lot of unnecessary overhead on larger datasets and isn't particularly easy to read anyway. Generally avoid flatMap for filtering and use it for flattening.

Even though you're only doing this operation once, I'd still use a lookup table to avoid repeated loops over the inner array:

const employees = [
  {name: 'Alice', department_id: 12},
  {name: 'Bob', department_id: 13},
  {name: 'Chris', department_id: 13},
  {name: 'Dan', department_id: 14},
  {name: 'Eve', department_id: null}
];

const departments = [
  {department_id: 12, name: 'Sales'},
  {department_id: 13, name: 'Marketing'},
  {department_id: 14, name: 'Engineering'},
  {department_id: 15, name: 'Accounting'},
  {department_id: 16, name: 'Operations'}
];

const departmentsById = Object.groupBy(
  departments,
  e => e.department_id
);

const ij1 = employees.reduce((a, e) => {
  const d = departmentsById[e.department_id];

  if (d) {
    a.push({
      employee_name: e.name,
      employee_department_id: e.department_id,
      department_id: d[0].department_id,
      department_name: d[0].name,
    });
  }

  return a;
}, []);

console.log(departmentsById);
console.log(ij1);

Assuming O(1) lookups, the time complexity is now O(n + m) rather than O(nm).

Note that I've avoided filter and map entirely in favor of a single reduce. I prefer avoiding reduce in favor of a filter and map pair, but in this case, reduce allows us to avoid a second pass over the data, so it's a worthwhile performance tradeoff.

If departments is guaranteed to be pretty small, say, 10 or 20 items, then there may be no reason to use the lookup table and a nested loop and separating reduce into separate map and filter calls can be acceptable from a performance standpoint.

I'll keep _ in the variable names because that's probably how your API is returning the data, but keep in mind this isn't standard JS style. Normalize to camelCase rather than snake_case as soon as possible. ij1 is also a poor variable name--1 looks like l and I, and i and j are usually used for indexes, but I assume you picked this due to some domain-specific reason that makes sense from the context. Nonetheless, there should be another option generally comprehensible to anyone.

Always use ===, never ==, which performs surprising type coercion that can lead to subtle, silent bugs.

If you're in an environment that doesn't have Object.groupBy, you can use reduce:

const departmentsById = departments.reduce((a, e) => {
  a[e.department_id] = e;
  return a;
}, {});

Also possible (cleaner, but requires two passes and likely higher heap allocation overhead):

const departmentsById = Object.fromEntries(
  departments.map(e => [e.department_id, e])
);

In both cases, you'll need to make a small modification later in the code. Instead of d[0].department_id, use d.department_id, since groupBy makes array values (but here, we're guaranteed to have unique ids, so the arrays are superfluous).

Speaking of which, groupBy will incur some allocation overhead for those unnecessary arrays. I'd expect reduce to be fastest, but this is just a hunch and I haven't benchmarked anything. It probably doesn't matter a whole lot since it's back in linear time complexity territory either way, and departments is probably on the small side, but worth keeping in mind.


I fully endorse the approach in this answer, avoiding the duplicate ID and using a loop rather than a reduce. The Map suggested there is a perfectly reasonable alternative to plain objects or groupBy as well.

\$\endgroup\$
4
  • \$\begingroup\$ Can you add console.log(departmentsById); to make its result visible in the code snippet? I seem to be having some difficulty with that part. \$\endgroup\$
    – knot22
    Commented Apr 25 at 20:53
  • \$\begingroup\$ Done. What difficulty are you having? Maybe I can help. Object.groupBy is fairly new, so you may want to use a traditional reduce to group there. One downside of groupBy is that the values are arrays, assuming multiple things will be grouped together, but in this case it's guaranteed to be one item since the ids are unique, so you'll always need to use d[0] to access the first item in each grouping. \$\endgroup\$
    – ggorlen
    Commented Apr 25 at 21:21
  • \$\begingroup\$ Thanks. I was doing some basic testing using Node to run the JS and Object.groupBy() wouldn't work. I have used this pattern in the past to create lookups: const departmentLookup = Object.assign({}, ...departments.map(department => ({ [department.department_id]: department }))); and, using this as the lookup source, did some minor refactoring of your original code in my test code to get it to work. However, maybe a .reduce() approach to create the lookup is better/more efficient than Object.assign()...? \$\endgroup\$
    – knot22
    Commented Apr 25 at 21:34
  • 1
    \$\begingroup\$ See the update. I've added alternate approaches that don't use groupBy. \$\endgroup\$
    – ggorlen
    Commented Apr 25 at 21:49
3
\$\begingroup\$

You told us there are 1e4 employees in 1e4 departments, in some unspecified distribution, presumably pretty sparse with lots of un-staffed departments.

The solution below works fine,

Really?!?

but it seems rather long. Is there a more concise approach?

Yeah, 1e8 seems on the "long" side. An M × N cartesian cross product gets ugly fast when your inputs get big.


For the input sizes you contemplate, this approach makes little sense.

Instead, read in all the employees, and devote \$O(M \log M)\$ effort to sort them by department_id. Next read all departments and sort them, with \$O(N \log N)\$ effort. Finally exploit 2-way merge to emit all relevant emp+dept result objects.

driving table

If, as seems likely, there's more employees than departments, it would make more sense to first read in all departments. And sort them. (If you can obtain "number of employees in department" at the same time, containing many zeros, then use that to filter out useless departments from the get go.)

Now scan across all employees in whatever random order they appear, doing binary search to find matching department, emitting emp+dept records as appropriate. This has a smaller memory footprint, given that we only sorted the smaller table. (\$M > N\$) Notice that \$M × O(\log N) + O(N \log N) < O(M \log M) + O(N \log N)\$ under that condition.

\$\endgroup\$
3
\$\begingroup\$

An alternative approach (inspired by this thread), for which some feedback would be appreciated, is as follows. One bonus I see to this object merging approach is it's possible to create a left outer join equivalent or an inner join equivalent with just 1 line of code that's different.

// original data
const employees = [
    {name: 'Alice', department_id: 12},
    {name: 'Bob', department_id: 13},
    {name: 'Chris', department_id: 13},
    {name: 'Dan', department_id: 14},
    {name: 'Eve', department_id: null}
];

const departments = [
    {department_id: 12, name: 'Sales'},
    {department_id: 13, name: 'Marketing'},
    {department_id: 14, name: 'Engineering'},
    {department_id: 15, name: 'Accounting'},
    {department_id: 16, name: 'Operations'}
];

// prepare source data for use -
// 1. renaming keys within objects before merging preserves all key/value pairs in final result
// 2. putting all key names in "left" object displays them for all resultant objects
const employees2 = employees.map(employee => ({
    employee_name: employee.name,
    employee_department_id: employee.department_id,
    department_id: null,
    department_name: null
 }));

const departments2 = departments.map(department => ({
    department_id: department.department_id,
    department_name: department.name
}));

// left outer join equivalent
const loj5 = employees2
    .map(employee => Object.assign({}, employee, departments2.find(department => department.department_id == employee.employee_department_id)));

// inner join equivalent
const ij5 = employees2
    .filter(employee => employee.employee_department_id != null)
    .map(employee => Object.assign({}, employee, departments2.find(department => department.department_id == employee.employee_department_id)));

console.log('left outer join equivalent\r\n', loj5, '\r\nLength:', loj5.length);
console.log('inner join equivalent\r\n', ij5, '\r\nLength:', ij5.length);

\$\endgroup\$
1
  • 1
    \$\begingroup\$ It's worth mentioning that this is still quadratic, maybe OK if departments is guaranteed to be small, but overhead-heavy. I'm surprised in benchmarks all the time, though. \$\endgroup\$
    – ggorlen
    Commented Apr 25 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.