Design a Search/Filter Engine for an E-Commerce Catalog

Core classes

class Product { String id; String name; String category; BigDecimal price; int stock; }
interface FilterCriteria { boolean matches(Product product); }
interface SortStrategy { Comparator<Product> comparator(); }

FilterCriteria as an interface (rather than a bundle of boolean flags checked in one giant method) is what lets individual filters — price range, category, in-stock — be defined, tested, and composed INDEPENDENTLY, each as its own small, focused implementation.

Composite pattern: combining filters as AND

class CompositeFilter implements FilterCriteria {
    private final List<FilterCriteria> filters;
    CompositeFilter(List<FilterCriteria> filters) { this.filters = filters; }
    public boolean matches(Product product) {
        return filters.stream().allMatch(f -> f.matches(product)); // ALL filters must pass — AND semantics
    }
}

class PriceRangeFilter implements FilterCriteria {
    BigDecimal min, max;
    public boolean matches(Product p) { return p.getPrice().compareTo(min) >= 0 && p.getPrice().compareTo(max) <= 0; }
}

CompositeFilter itself IMPLEMENTS FilterCriteria — this is the defining trait of the Composite pattern: a composite of filters is INDISTINGUISHABLE, from the caller's perspective, from a single filter. "Price range AND category AND in-stock" becomes simply new CompositeFilter(List.of(priceFilter, categoryFilter, stockFilter)), and code applying filters to products never needs to know or care whether it's dealing with one filter or many combined — it just calls matches().

SortStrategy: separating filtering from ordering

class PriceAscending implements SortStrategy {
    public Comparator<Product> comparator() { return Comparator.comparing(Product::getPrice); }
}

Keeping sort logic as its own Strategy (rather than baked into the filter or the query method) means adding a new sort order ("newest first," "best rating") is purely additive — implement one new class, no existing filter or query code needs to change, the same Open/Closed benefit that shows up throughout this course's Strategy Pattern discussions.

How this feeds into an HLD-scale search engine

This class model is exactly the LOGICAL shape a real, HLD-scale search system (Search Engine, in the System Design track) needs to expose to callers — but at genuine scale, matches() being called against EVERY product in a naive linear scan doesn't work against millions of products. The HLD version replaces the linear scan with an INVERTED INDEX (Search Engine's core data structure) that can jump directly to candidate matches — but the FilterCriteria/CompositeFilter shape still describes the QUERY itself; it's the EXECUTION strategy underneath that changes from "scan and check" to "index and retrieve" as scale grows.

From predicates to indexes: making filtering fast

Evaluating every filter against every product is O(products × filters) per query, which is fine for a few thousand items, but too slow for a large catalogue behind a busy search page. The next step, still at class-design level, is to precompute inverted indexes for the filterable attributes, and intersect sets of product IDs instead of scanning:

class CatalogIndex {
    private final Map<String, Product> byId = new HashMap<>();
    private final Map<String, Set<String>> byCategory = new HashMap<>();
    private final Map<String, Set<String>> byBrand = new HashMap<>();
    private final TreeMap<BigDecimal, Set<String>> byPrice = new TreeMap<>();   // sorted, for range queries

    void add(Product p) {
        byId.put(p.id, p);
        byCategory.computeIfAbsent(p.category, k -> new HashSet<>()).add(p.id);
        byBrand.computeIfAbsent(p.brand, k -> new HashSet<>()).add(p.id);
        byPrice.computeIfAbsent(p.price, k -> new HashSet<>()).add(p.id);
    }

    Set<String> category(String c) { return byCategory.getOrDefault(c, Set.of()); }
    Set<String> brand(String b)    { return byBrand.getOrDefault(b, Set.of()); }

    Set<String> priceBetween(BigDecimal min, BigDecimal max) {
        Set<String> ids = new HashSet<>();
        byPrice.subMap(min, true, max, true).values().forEach(ids::addAll);      // O(log n + matches)
        return ids;
    }

    Product get(String id) { return byId.get(id); }
}

Each filter now produces a set of matching IDs, and combining filters becomes set algebra: AND is intersection, OR is union. Always intersect starting from the smallest set, since intersecting a 50-item brand set with a 200,000-item category set costs 50 lookups, not 200,000.

interface IndexedFilter { Set<String> matchingIds(CatalogIndex index); }

record AndFilter(List<IndexedFilter> parts) implements IndexedFilter {
    public Set<String> matchingIds(CatalogIndex idx) {
        List<Set<String>> sets = parts.stream().map(f -> f.matchingIds(idx))
                .sorted(Comparator.comparingInt(Set::size)).toList();          // smallest first
        Set<String> result = new HashSet<>(sets.get(0));
        for (int i = 1; i < sets.size() && !result.isEmpty(); i++) result.retainAll(sets.get(i));
        return result;
    }
}

record OrFilter(List<IndexedFilter> parts) implements IndexedFilter {
    public Set<String> matchingIds(CatalogIndex idx) {
        Set<String> result = new HashSet<>();
        parts.forEach(f -> result.addAll(f.matchingIds(idx)));
        return result;
    }
}

The Composite structure from earlier is unchanged. Only the leaf filters now use indexes instead of predicates. Filters that can't be indexed (a complex custom rule) can still run as predicates after the indexed filters have shrunk the candidate set.

Facet counts

Search pages show counts next to each filter option ("Brand: Acme (42), Zenith (17)"). Compute them over the current result set:

Map<String, Long> brandFacets(Set<String> resultIds, CatalogIndex idx) {
    return resultIds.stream().map(idx::get)
            .collect(Collectors.groupingBy(p -> p.brand, TreeMap::new, Collectors.counting()));
}

A subtle UX rule: counts for a facet group are usually computed with that group's own selection removed. If a user selected "Acme", the other brands should still show how many results they'd give, so the user can switch or add a brand. Otherwise every other brand would show zero.

Pagination and stable ordering

Sort the filtered results with the chosen SortStrategy, then return one page. Add a tie-breaker (product ID) to every comparator, so that products with equal prices don't reshuffle between page loads, which would make items appear twice or never across pages:

Comparator<Product> cmp = sort.comparator().thenComparing(p -> p.id);
List<Product> page = results.stream().map(idx::get).sorted(cmp).skip((long) pageNo * size).limit(size).toList();

For large result sets, a partial sort (a bounded heap of the top (pageNo + 1) × size items) avoids sorting everything to show page 1. This is exactly what dedicated search engines (Elasticsearch/OpenSearch) do internally, along with text relevance scoring, which is why they take over at scale.

Follow-up questions this topic invites — and their answers

Q: How would you add OR semantics (price range OR category X) to this Composite design? A: A second composite implementation, e.g. OrCompositeFilter, using anyMatch instead of allMatch — both implement the same FilterCriteria interface, and complex boolean expressions (mixing AND and OR) can be built by nesting composites of composites, exactly the recursive structure Composite pattern is named for.

Q: Does adding a new filter type (e.g. a 'brand' filter) require changing CompositeFilter? A: No — this is the direct Open/Closed payoff: CompositeFilter only depends on the FilterCriteria interface, never on any specific implementation, so a new filter type is a new class implementing that interface, with zero changes needed to CompositeFilter or any existing filter.

Q: How would you handle a filter that's expensive to evaluate (e.g. checking real-time stock from an external inventory service)? A: Order matters for performance — evaluating cheap, in-memory filters (price, category) FIRST and short-circuiting before reaching expensive filters (an external stock check) avoids unnecessary expensive calls for products that would've been filtered out anyway; allMatch's short-circuit behavior naturally supports this if filters are ordered cheap-to-expensive in the composite's list.

Q: Should sorting happen before or after filtering? A: Filtering first, then sorting — sorting the full unfiltered catalog before applying filters wastes work sorting products that filtering will discard anyway; filter down to the relevant subset first, then sort only that smaller result set.

Q: Why intersect ID sets starting from the smallest? A: Intersection cost is driven by the smaller set, since you check each of its elements against the others. Starting small, and stopping early when the result becomes empty, turns expensive broad filters into cheap lookups.

Q: How should facet counts behave when a filter in the same group is already selected? A: Compute each facet group's counts against results filtered by all the other groups, excluding that group's own selection. That shows users what they'd get by switching or adding an option within the group, instead of zeroing every alternative.

Q: Why add a tie-breaker to sort comparators? A: Items with equal sort keys can come back in a different order on each query, so offset-based pages overlap or skip items. A unique tie-breaker such as the product ID makes the order deterministic.