Quickest way to retrieve information from database

Question

I am trying to resolve a problem which i am currently facing. I am trying to find out which is the fastest way to retrieve information from a database.

So a managers name is passed in, what i need to do is return all the users who's manager is passed in, but if any of these users happen to be a manager, i have to return all the user names (List<String>) they manage also... this will repeat until i return everyone

here is a small example of what i need to return

manager --> manager --> manager --> manager --> employee
        --> manager --> employee
        --> manager --> manager --> manager --> employee
        --> employee

so in the example above the code would be returning 12 names

i know i could do this a number of different ways but i do not know which would be the best way (recursive for loop, for loop recursively calling method, SQL statement, HQL statement ... etc.)

As this list can be any size depending on the manager passed in, i need to find which would be the quickest way to retrieve this as i have coded this to use recursive for loops and it takes 1 minute 20 seconds which is WAY too long

Any ideas?

Answer 1

What you need is to perform a performance analysis, in order to know if the latency comes from the database, the application server, or the network (latency due to many loops). According to your figures, I think you are doing too many queries, but this is an hypothesis you should verify.

In my company, which is a big company, there is no more than 15 levels between the Big Boss and any employee. Therefore, you shouldn't have to do more than 15 request.

I suspect that you do one loop for each people, in order to know it's employee. Get where manager = name What you could do is doing one HQL request to get all the employees on a list "get where manager IN (list of manager)". It should dramatically reduce the time spent, because you would do 15 request recursively instead of 13k for the big boss.

Request 1    Request 2   Request 3 ...
manager   --> manager --> manager --> manager --> employee
          --> manager --> employee
          --> manager --> manager --> manager --> employee
          --> employee

Otherwise, if you want to use an SQL statement, you might conisder using the keyword WITH.

Answer 2

See this similar question.

Also see this presentation about database antipatterns by Bill Karwin. From slide 48 onwards the 'Naive Tree' antipattern is discussed.

Solution #1: Path enumeration. Store the path of ancestors (managers in your case):

ID, PATH, NAME
1, 1/, george
2, 2/, peter
3, 1/3, harry
4, 1/3/4, bertrand

Easy to query descendants of george:

SELECT * from Employee WHERE path LIKE '1/%';

The presentation also mentions other solutions which I think are less useful in your case:

• Solution #2: Nested sets
• Solution #3: Closure table

EDIT: here's another idea mixing two database queries with a recursive in-memory search.

    public static class Employee {
        private Long id;
        private boolean isManager;
        private Employee manager;

        public Long getId() {
            return id;
        }

        public void setId(Long id) {
            this.id = id;
        }

        public boolean isManager() {
            return isManager;
        }

        public void setIsManager(boolean isManager) {
            this.isManager = isManager;
        }

        public Employee getManager() {
            return manager;
        }

        public void setManager(Employee manager) {
            this.manager = manager;
        }
    }

First get all managers in the database. If the total number of Employees is 16k then the number of managers should be manageable (no pun intended).

    // gets all existing managers from the database
    private static List<Employee> getAllManagers() {
        //  SELECT * FROM Employee WHERE isManager = true;
        return new ArrayList<>();
    }

Then iterate over all managers and recursively determine which managers work under the query manager.

    private static Set<Employee> findSubordinateManagers(Employee queryManager) {
        List<Employee> allManagers = getAllManagers();
        Set<Employee> subordinateManagers = new HashSet<>();
        for (Employee employee : allManagers) {
            if (isSubordinateTo(employee, queryManager)) {
                subordinateManagers.add(employee);
            }
        }
        return subordinateManagers;
    }    

    // determines if the given employee is subordinate to the given manager
    private static boolean isSubordinateTo(Employee employee, Employee manager) {
        if (employee.getManager() == null) {
            return false;
        }
        if (employee.getManager().getId().equals(manager.getId())) {
            return true;
        }
        return isSubordinateTo(employee, employee.getManager());
    }

Then do a second SQL query to get all the employees directly managed by the set of selected managers:

    // finds all employees directly subordinate to the given set of managers
    private static Set<Employee> findEmployees(Set<Employee> managers) {
        // SELECT * from Employee WHERE manager IN (managers);
        return new HashSet<>();
    }