Make Database Queries Without the Database

So far, this project looked like a typical database application, and there was no shortage of candidate persistence strategies. But maybe it was possible to avoid the complexity of using a database for persistence -- the crawler was only going to visit a few tens of thousand of pages. This number was few enough that it was possible to keep the whole database in memory, and persistence, if needed, could be achieved through serialization. (Yes, the load and save operations would take a long time, but they did not have to be performed frequently.) Laziness had yielded a dividend -- not having to deal with persistence can greatly reduce the amount of time to develop an application, resulting in a significant savings in terms of development effort. Building and manipulating an in-memory data structure is just a lot easier than having to go to the database for every operation that adds, fetches, or analyzes data. No matter which persistence model you choose, it always constrains how you structure any code that touches the data.

The in-memory data structure had a sort of tree structure, as shown in Listing 1, rooted at the home pages of the various sites being crawled, so the Visitor pattern was ideal for searching it or extracting data from it. (It was not too hard to build a base Visitor class that prevented getting stuck in cycles of links -- A links to B, B links to C, C links back to A.)

public class Site {

    Page homepage;

    Collection<Page> pages;

    Collection<Link> links;

}



public class Page {

    String url;

    Site site;

    PageMetrics metrics;

}



public class Link {

    Page linkFrom;

    Page linkTo;

    String anchorText;

}

The crawler application had a dozen or so Visitors, which did things like selecting pages for further analysis, selecting pages that had unfollowed links, selecting pages with errors, tabulating the "most linked" pages, and so on. Because all of these operations were so simple, the Visitor pattern, shown in Listing 2, worked quite well, and because the data structure could fit into memory, even exhaustive searches were cheap enough:

public interface Visitor {

    public void visitSite(Site site);

    public void visitLink(Link link);

}

Oops, forgot about reporting
The Visitor strategy worked just great for accessing the data, until it was time to run the reports. One of the benefits of using a database for persistence is that the power of SQL really shines when it comes to generating reports -- you can pretty much let the database do all the work. Even better, prototyping reports with SQL is easy -- you run your prototype report, and if the results aren't what you need, you tweak the SQL query or write a new query, and try again. The edit-compile-run cycle, when all you are changing is a SQL query, can be pretty quick. If the SQL isn't stored in the program, you can even skip the compile part of the cycle, which gives the ability to rapidly prototype your reports. Once you've found the reports you want, then it is easy enough to build them into your application.

So, the in-memory data structure, which was great for adding new results, finding a specific result, and all sorts of ad-hoc traversals, had become a liability when it came to reporting. For any report whose structure was not similar to that of the database, a Visitor would have to create a whole new data structure to hold the report data. Therefore, each type of report would require its own report-specific intermediate data structure for holding the results, a visitor for populating the intermediate data structure, and then post-processing code for turning the intermediate data structure into the final report. This approach seemed like a lot of work, especially when most of the prototyped reports were going to be thrown away. For example, let's say you wanted a report that listed all the pages from other sites linked to from a given site, and for each of those external pages, a list of pages on the site that link to it, and then sort the report by number of links, so the most-linked pages appear first. This plan basically turns the data structure inside-out. To accomplish this sort of data transformation with a Visitor, you need to take the list of external page links reachable from a given site and sort them by the linked-to page, as shown in Listing 3:

public class InvertLinksVisitor {

    public Map<Page, Set<Page>> map = ...;

    

    public void visitLink(Link link) {

        if (link.linkFrom.site.equals(targetSite) 

            && !link.linkTo.site.equals(targetSite)) {

            if (!map.containsKey(link.linkTo))

                map.put(link.linkTo, new HashSet<Page>());

            map.get(link.linkTo).add(link.linkFrom);

        }

    }

}

The Visitor in Listing 3 produces a map that associates each external page with a list of internal pages that link to it. To prepare the report, you would then have to sort the entries by the size of the associated page set, and then create the report. While none of these steps is all that difficult, the amount of report-specific code for each report is significant, and given that rapid report prototyping was an important goal (because there were no stated reporting requirements), the overhead of trying out a new report was higher than ideal. Many reports required multiple passes on the data to select, aggregate, and sort the data.

 |