Performance and correctness are two independent concerns with overlapping solutions.

How do you design, implement, maintain, and test complex filter logic as part of out-of-process (e.g. database) queries?

One option is to implement parts of the filtering logic twice: Once as an easily-testable in-memory implementation to ensure correctness, and another, possibly simpler, query using the query language (usually, SQL) of the data source.

Does this not imply duplication of effort? Yes, to a degree it does. Should you always do this? No, only when warranted. As usual, I present this idea as an option you may consider; a tool for your software design tool belt. You decide if it's useful in your particular context.

Motivation #

When extracting data from a data source, an application usually needs some of the data, but not all of it. If the software system in question has a certain size, the subset required for an operation is only a miniscule fraction of the entire database. For example, a user may want to see his or her latest order in a web shop, but the entire system contains millions of orders. Another example could be a system for managing help desk requests: Each supporter may need a dashboard of open cases assigned to him or her, but the system holds millions of tickets, and most of them are closed.

If a data store supports server-side querying, for example with SQL or Cypher, it's reasonable to let the data store itself do the filtering.

As anyone who has worked professionally with SQL can attest, SQL queries can become complicated. When this happens, you may become concerned with the correctness of a query. Does it include all the data it should? Does it exclude irrelevant data? If you later change a query, how can you verify that it still works as intended? How do you even version it?

Automated testing can address several of these concerns, but testing against a real database, while possible, tends to be cumbersome and slow. Do alternatives, or augmentations, exist?

How it works #

If a server-side query threatens to become too complicated, consider shifting some of the work to clients. You may retain some filtering logic in the server-side query, but only enough to keep performance good, and simple enough that you are no longer concerned about its correctness.

Implement the difficult filtering logic in a client-side library. Since you implement this part in a programming language of your choice, you can use any tool or technique available in that context to ensure correctness: Test-driven development, static code analysis, type checking, property-based testing, code coverage, mutation testing, etc.

Using a funnel as a symbol of filtering, this diagram depicts the idea:

Normally a funnel is only useful when the widest part faces up, but on the other hand, we usually depict application architectures with the database under the the application. You have to imagine data being 'sucked up' through the funnels.

In reality, the two filters will differ, but have overlapping functionality.

If based on a relational database, the server-side query will still hold table joins and column projections that are effectively irrelevant to the client-side Domain Model. On the other hand, while the server-side query may apply a rough filter, the more detailed selection of what is, and is not, included happens in the client.

The server-side query is defined using the query language of the data store, such as SQL or Cypher. The client-side query is part of the application code base, and written in the same programming language.

When to use it #

Use this pattern if a server-side query becomes so complicated that you are concerned about its correctness, or if correctness is an essential part of a Domain Model's contract.

While it is conceptually possible to load the entire data store's data into memory, this is often prohibitively expensive in terms of time and memory. It is often necessary to retain some filtering logic (e.g. one or more SQL WHERE clauses) on the server to pare down data to acceptable sizes. This implies a degree of duplicated logic, since the client-side filter shouldn't assume that any filtering has been applied.

Duplication comes with its own set of problems, even if this looks like the benign kind. Alternatives include keeping all logic on the database server, which is viable if the logic is simple, or can be sufficiently simplified. Another alternative is to perform all filtering in the client, which may be an attractive solution if the entire data set is small.

Encapsulation #

If a Domain Model is composed of pure functions, data must be supplied as normal input arguments. In a more object-oriented style, data may arrive as indirect input. In both object-oriented and functional architecture, encapsulation is important. This entails being explicit about invariants and pre- and postconditions; i.e. contracts.

To enforce preconditions, a Domain Model must ensure that input is correct. While it could choose to reject input if it contains 'too much' data, a Tolerant Reader should instead pare the data down to size. This implies that filtering should be part of a Domain Model's contract.

This further implies that a Domain Model becomes less vulnerable to changes in data access code.

Implementation details #

Server-side filtering (with e.g. SQL) is often difficult to test with sufficient rigour. The point of moving the complex filtering logic to the Domain Model is that this makes it easier to test, and thereby to maintain.

If no filtering takes place on the server, however, the entire data set of the system would have to be transmitted to, and filtered on, the client. This is usually too expensive, so some filtering must still take place at the data source. The whole point of this exercise is that the 'correct' filtering is too complicated to maintain as a server-side query, so whatever filtering still takes place on the server only happens for performance reasons, and can be simpler, as long as it's wider.

Specifically, the simplified server-side query can (and probably should) be wider, in the sense that it returns more data than is required for the correctness of the overall system. The client, receiving more data than strictly required, can perform more sophisticated (and testable) filtering.

The simplified filtering on the server must not, on the other hand, narrow the result set. If relevant data is left out at the source, the client has no chance to restore it, or even know that it exists.

Motivating example #

The code base that accompanies Code That Fits in Your Head contains an example. When a user attempts to make a restaurant reservation, the system must look at existing reservations on the same date to check whether it has a free table. Many restaurants operate with seating windows, and the logic involved in figuring out if a time slot is free is easy to get wrong. On top of that, the decision logic needs to take opening hours and last seating into account. The book, as well as the article The Maître d' kata, has more details.

Based on information about seating duration, opening hours, and so on, it seems as though it should be possible to form an exact SQL query that only returns existing reservations that overlap the new reservation. Even so, this struck me as error-prone. Instead, I decided to make input filtering part of the Domain Model.

The Domain Model in question, an immutable class named MaitreD, uses the WillAccept method to decide whether to accept a reservation request. Apart from the candidate reservation, it also takes as parameters existingReservations as well as the current time.

public bool WillAccept(
    DateTime now,
    IEnumerable<Reservation> existingReservations,
    Reservation candidate)

The function uses the existingReservations to filter so that only the relevant reservations are considered:

var seating = new Seating(SeatingDuration, candidate.At);
var relevantReservations =
    existingReservations.Where(seating.Overlaps);

As implied by this code snippet, a specialized Domain Model named Seating contains the actual filtering logic:

public bool Overlaps(Reservation otherReservation)
{
    if (otherReservation is null)
        throw new ArgumentNullException(nameof(otherReservation));
 
    var other = new Seating(SeatingDuration, otherReservation.At);
    return Overlaps(other);
}
 
public bool Overlaps(Seating other)
{
    if (other is null)
        throw new ArgumentNullException(nameof(other));
 
    return Start < other.End && other.Start < End;
}

Notice how the core implementation, the overload that takes another Seating object, implements a binary relation. To extrapolate from Domain-Driven Design, whenever you arrive at 'proper' mathematics to describe the application domain, it's usually a sign that you've arrived at something fundamental.

The Overlaps functions are public and easy to unit test in their own right. Even so, in the code base that accompanies Code That Fits in Your Head, there are no tests that directly exercise these functions, since they only grew out of refactoring the implementation of MaitreD.WillAccept, which is covered by many tests. Since the Overlaps functions only emerged as a result of test-driven development, they might as well have been private helper methods, but I later needed them for verifying some unrelated test outcomes.

The filtering performed in WillAccept will throw away any reservations that don't overlap. Even if existingReservations contained the entire data set from the database, it would still be correct. Given, however, that there could be hundreds of thousands of reservations, it seems prudent to perform some coarse-grained filtering in the database.

The ReservationsController that calls WillAccept first queries the database, getting all the reservation on the relevant date.

var reservations = await Repository
    .ReadReservations(restaurant.Id, reservation.At)
    .ConfigureAwait(false);

Now that I write this description, I realize this query, while wide in one sense, could actually be too narrow. None of my test restaurants have a last seating after midnight, but I wouldn't rule that out in certain cultures. If so, it's easy to widen the coarse-grained query to include reservations for the day before (for breakfast restaurants, perhaps) and the day after, assuming that no seating lasts more than 24 hours.

All that said, the point is that ReadReservations(restaurant.Id, reservation.At) (which is an extension method) performs a simple, coarse-grained query for reservations that may be relevant to consider, given the candidate reservation. This query should return a 'gross' data set that contains all relevant, but also some irrelevant, reservations, thereby keeping the query simple. An indeed, the actual database interaction is this parametrised query:

SELECT [PublicId], [At], [Name], [Email], [Quantity]
FROM [dbo].[Reservations]
WHERE [RestaurantId] = @RestaurantId AND
      @Min <= [At] AND [At] <= @Max

This range query should be simple enough that a few integration tests should be sufficient to give you confidence that it works correctly.

Consequences #

The main benefit from a design like this is that it shifts some of the burden of correctness to the Domain Model, which is easier to test, maintain, and version than is typically the case for query languages. An added advantage is improved separation of concerns.

In practice, server-side filtering tends to mix two independent concerns: Performance and correctness. Filtering is important for performance, because the alternative is to transmit all rows to the client. Filtering is also important for correctness, because the code making use of the data should only consider data relevant for its purpose. Exclusive server-side filtering performs both of these tasks, thereby mixing concerns. Moving filtering for correctness to a Domain Model can make explicit that these are two separate concerns.

While a Domain Model can implement in-memory filtering, it can only deal with data that is too wide; that is, it can identify and remove superfluous data. If, on the other hand, the dataset passed to the Domain Model lacks relevant records, the Domain Model can't detect that. The above discussion about the reservation system contains a concrete discussion of such a problem. Thus, Domain-based filtering does not alleviate developers from the burden of ensuring that any server-side filtering is sufficiently permissible.

Another consequence of this design is that as server-side queries become more coarse-grained, this could increase potential cache hit ratios. If you somehow cache queries, when queries become more general, there will be less variation, and thus caches will need fewer entries that will statistically be hit more often. This applies to CQRS-style architectures, too.

Consider the restaurant reservation example, above. Since queries are only distinguished by date, you can easily cache query results by date, and all reservation requests for a given date may go through that cache. If, as a counter-example, all filtering took place in the database, a query for a reservation at 18:00 would be different from a query for 18:30, and so on. This would make a hypothetical cache bigger, and decrease the frequency of cache hits.

Test evidence #

When I originally decided that WillAccept should perform in-memory filtering, my motivation was one of correctness. I was concerned whether I could get the seating overlap detection correct without comprehensive testing, and I thought that it would be easier to test a function doing in-memory filtering than to drive all of this via integration tests involving a real SQL Server instance. (Not that I don't know how to do this. The code base accompanying the book has examples of tests that exercise the database. These tests are, however, more work to write and maintain, and they execute slower.)

As discussed in Coupling from a big-O perspective, I much later realized that I actually had no test coverage of edge cases related to querying the database. It was only after attempting to write such a test that I realized that the design had the consequence that a marginal error in the database query had no impact on the correctness of the overall system. Here's that test:

[Fact]
public async Task AttemptEdgeCaseBooking()
{
    var twentyFour7 = new Restaurant(
        247,
        "24/7",
        new MaitreD(
            opensAt: TimeSpan.FromHours(0),
            lastSeating: TimeSpan.FromHours(0),
            seatingDuration: TimeSpan.FromDays(1),
            tables: Table.Standard(1)));
    var db = new FakeDatabase();
    var now = DateTime.Now;
    var sut = new ReservationsController(
        new SystemClock(),
        new InMemoryRestaurantDatabase(twentyFour7),
        db);
    var r1 = Some.Reservation.WithDate(now.AddDays(3).Date);
    await sut.Post(twentyFour7.Id, r1.ToDto());
 
    var r2 = Some.Reservation.WithDate(now.AddDays(2).Date);
    var ar = await sut.Post(twentyFour7.Id, r2.ToDto());
 
    Assert.IsAssignableFrom<CreatedAtActionResult>(ar);
    // More assertions could go here.
}

This test is an attempt to cover the edge case related to how the system queries the database, just like the Moq-based test shown in Greyscale-box test-driven development. The idea is to create a reservation that just barely touches a reservation the following day, and thereby trigger a test failure when a change is made to the query, similar to how the Moq-based test fails. Even with a custom restaurant, I can't, however, get this test to fail, because of the Domain-based filtering, which keeps the system working correctly.

It was then that I realized that what I had inadvertently done was to strengthen the contract of WillAccept, compared to a more stereotypical design. Who knew test-driven development could lead to better encapsulation?

Conclusion #

Some queries may become so complicated that they are difficult to maintain. Bugs creep in, you address them, only to reanimate regressions. When this happens, consider moving the complicated parts of data filtering to the client, preferably to a Domain Model. This enables you to test the filtering logic with as much rigour as is required.

For small databases, you may read the entire dataset into memory, but usually you will need to retain some coarse-grained filtering on the database server.

This design, while more complicated than letting a query language like SQL handle all filtering, can lead to better encapsulation and separation of concerns.