karldmoore development

A development oriented blog, containing anything I've been working on, reading or thinking about.

Posts Tagged ‘Bugs’

SQL n + 1 Selects Explained

Posted by karldmoore on February 5, 2009

The SQL n + 1 selects problem is extremely common but I have often found that many people have either never heard of it or simply don’t understand it. It is actually very easy to introduce a problem like this into your code, but it’s also very easy to resolve as well. Problems like this are best explained with an example; so imagine we have a table called users and another called user_roles. These tables are setup with a one-to-many relationship, meaning that one user (e.g. jsmith) can have many roles (e.g. Administrator, Auditor, Developer). Many people might implement something like this;

public Iterable<User> allUsers() {
    final String selectUsers = "select users.username, users.email, " +
        "users.last_password_change from users";
    return getJdbcTemplate().query(selectUsers, new Object[] {},
                new ParameterizedRowMapper<User>() {
        public User mapRow(ResultSet resultSet, int rowNumber) throws SQLException {
            String username = resultSet.getString("username");
            String email = resultSet.getString("email");
            Date lastPasswordChange = resultSet.getDate("last_password_change");
            User user = new DefaultUser(username, email, lastPasswordChange);
            addRolesToUser(user);
            return user;
        }
    });
}

private void addRolesToUser(final User user) {
    final String selectUserRoles = "select role_name from user_roles where username = ?";
    getJdbcTemplate().query(selectUserRoles, new Object[] { user.getPrincipalName() },
                new RowCallbackHandler() {
        public void processRow(ResultSet resultSet) throws SQLException {
            String rolename = resultSet.getString("role_name");
            user.addRole(rolename);
        }
    });
}

Reviewing the code we can see one query is executed to retrieve the users, the problem here is for each user another SQL statement needs to be executed to retrieve the roles. If the first query retrieved one user, this would require one additional query to retrieve the roles. If the first query retrieved a hundred users, this would require one hundred additional queries to retrieve the roles. The pattern will always be the same, one query for the users and n queries dependent on the number of users found, thus n + 1. Although this solution is functional, it does result in many unnecessary SQL statements being executed.

select users.username, users.email, users.last_password_change from users;
select role_name from user_roles where username = ?;
select role_name from user_roles where username = ?;
select role_name from user_roles where username = ?; 
...

Shared resources are typically the bottleneck in most applications, so expensive or unnecessary SQL should be avoided if possible. As the application attempts to scale, this bottleneck can become extremely problematic and severely inhibit application performance. Fortunately this is a simple solutions to this problem; introducing a join into the query.

public Iterable<User> allUsers() {
    final String selectUsers =
        "select users.username, users.email, users.last_password_change, user_roles.role_name "
            + "from users left join user_roles on (users.username = user_roles.username)";
    final Map<String, User> users = new HashMap<String, User>();
    getJdbcTemplate().query(selectUsers, new Object[] {}, new RowCallbackHandler() {
        public void processRow(ResultSet resultSet) throws SQLException {
            String username = resultSet.getString("username");
            if (!users.containsKey(username)) {
                String email = resultSet.getString("email");
                Date lastPasswordChange = resultSet.getDate("last_password_change");
                User user = new DefaultUser(username, email, lastPasswordChange);
                users.put(username, user);
            }

            String rolename = resultSet.getString("role_name");
            if (!StringUtil.isNull(rolename)) {
                User user = users.get(username);
                user.addRole(rolename);
            }
        }
    });
    return users.values();
}

Although the code and SQL statement are slightly more complex that the original example, it results in much fewer SQL statements being executed. Instead of the n + 1 statements executed in the first example, one statement is executed that fetches all the required data. This typically results in much improved performance and as the numbers scale the improvement in performance can become much more apparent.

select users.username, users.email, users.last_password_change, user_roles.role_name
    from users left join user_roles on (users.username = user_roles.username);

As with all performance optimizations the most important thing is to measure the effect of the improvement. Performance optimizations aren’t always predictable so by taking measurements before and after the change, you can accurately know if you have actually improved the performance (or made it worse). A SQL join may be the most appropriate way of solving a problem such as this, but there are other alternatives such as caching the data instead. Although the SQL n + 1 selects is an extremely common problem, is not always well understood and is often still found within code. It is very easy to introduce a problem like this into your code, but it’s also very easy to resolve as well. Next time you are viewing your debug output, see if you can spot SQL n + 1 selects.

References

Database access using Spring JdbcTemplate
Preventing the n + 1 select problem when using Hibernate

Advertisements

Posted in Development, Refactoring, Spring, SQL | Tagged: , , , , , , , , , | 5 Comments »

Google Reports The Entire Internet As Malware

Posted by karldmoore on January 31, 2009

For about twenty minutes today google has been reporting every single website as malware. Any search within google returned the normal search results, but every result also included a report that this site may harm your computer. Attempting to click on the search result and progress to the actual website returns a warning page with no possible way of clicking through to the resulting page. Google was effectively blocking every single search result from reaching it’s destination.

googlemalware

I read a thorough discussion of the malware behaviour many months ago, but I don’t think this is quite what google were looking for when they implemented the feature. I’m sure there are a great many retailers who are cursing at potentially lost revenue and users who are now unsure if a website is harmful or not. False positives are never helpful to users who are unsure about their actions at the best of times. Thankfully, the problem seems to be sorting itself out and only seemed to last for twenty minutes. It’s not yet apparent whether the issue has been rectified or simply that the feature has been disabled altogether. It will be very interesting to see how this one is explained!

Update: It seems the problem was bigger than I thought.

Posted in Opinion | Tagged: , , | Leave a Comment »