Finding top N entries per group in Arango

Question

I'm trying to efficiently find the top entries by group in Arango (AQL). I have a fairly standard object collection and an edge collection representing Departments and Employees in that department.

Example purpose: Find the top 2 employees in each department by most years of experience.

Sample Data:

"departments" is an object collection. Here are some entries:

_id	name
departments/1	engineering
departments/2	sales

"dept_emp_edges" is an edge collection connecting departments and employee objects by ids.

_id	_from	_to	years_exp
dept_emp_edges/1	departments/1	employees/1	3
dept_emp_edges/2	departments/1	employees/2	4
dept_emp_edges/3	departments/1	employees/3	5
dept_emp_edges/4	departments/2	employees/1	6

I would like to end up with the top 2 employees per department by most years experience:

department	employee	years_exp
departments/1	employee/3	5
departments/1	employee/2	4
departments/2	employee/1	6

Long Working Query

The following query works! But is a bit slow on larger tables and feels inefficient.

FOR dept IN departments
    LET top2earners = (
        FOR dep_emp_edge IN dept_emp_edges
            FILTER dep_emp_edge._from == dept._id
            SORT dep_emp_edge.years_exp DESC
            LIMIT 2
            RETURN {'department': dep_emp_edge._from,
                    'employee': dep_emp_edge._to,
                    'years_exp': dep_emp_edge.years_exp}
        )

    FOR row in top2earners
        return {'department': dep_emp_edge._from,
                'employee': dep_emp_edge._to,
                'years_exp': dep_emp_edge.years_exp}

I don't like this because there is 3 loops in here and feels rather inefficient.

Short Query

However, I tried to write:

FOR dept IN departments
    FOR dep_emp_edge IN dept_emp_edges
        FILTER dep_emp_edge._from == dept._id
        SORT dep_emp_edge.years_exp DESC
        LIMIT 2
        RETURN {'department': dep_emp_edge._from,
                'employee': dep_emp_edge._to,
                'years_exp': dep_emp_edge.years_exp}

But this last query only outputs the final department top 2 results. Not all of the top 2 in each department.

My questions are: (1) why doesn't the second shorter query give all results? and (2) I'm quite new to Arango and ArangoQL, what other things can I do to make sure this is efficient?

Tom Regner Tom Regner · Accepted Answer · 2021-09-22T13:56:25

Your first query is incorrect as written (Query: AQL: collection or view not found: dep_emp_edge (while parsing)) - as I could only guess what you mean, I ignore it for now.

Your smaller query limits the overall results to two - counter intuitively - as you are not grouping by department.

I suggest a slightly different approach: Use the edge collection as central source and group by _from, returning one document per department, containing an array of the two top resulting employees (should they exist), not one document per employee:

FOR edge IN dept_emp_edges
  SORT edge.years_exp DESC
  COLLECT dep = edge._from INTO deps
  LET emps = (
    FOR e in deps
       LIMIT 2
       RETURN ZIP(["employee", "years_exp"], [e.edge._to, e.edge.years_exp])
  )
  RETURN {"department": dep, employees: emps}

For your example database this returns:

[
  {
    "department": "departments/1",
    "employees": [
      {
        "employee": "employees/3",
        "years_exp": 5
      },
      {
        "employee": "employees/2",
        "years_exp": 4
      }
    ]
  },
  {
    "department": "departments/2",
    "employees": [
      {
        "employee": "employees/1",
        "years_exp": 6
      }
    ]
  }
]

If the query is too slow, an index on the year_exp-field of the dept_emp_edges collection could help (Explain suggests it would).

Finding top N entries per group in Arango

Sample Data:

Long Working Query

Short Query

1 Answers