Searching Across Large Datasets

Use Case: Searching Across Large Datasets

The everyday problem: Your app has a search box. Users type "blue wireless headphones" and expect relevant results across millions of products — fast, tolerant of typos, ranked by relevance, maybe filtered by category and price. The naive implementation — WHERE Name LIKE '%' + @term + '%' — works for the first few thousand rows and then collapses: it cannot use an index (the leading wildcard kills it), it scans every row, it has no relevance ranking, no typo tolerance, and no concept of "headphones" matching "headphone". The challenge is delivering fast, relevant, fuzzy search over large datasets without bringing the database to its knees.

Five approaches, escalating from "use the database you already have" to "add a dedicated search engine". Most applications progress up this list as scale and search-quality requirements grow.

---

Way 1: LIKE and Indexed Prefix Search (the baseline)

Best used for: Small to moderate datasets, exact or prefix matching ("starts with"), autocomplete on a single column, or admin lookups where relevance ranking does not matter.

The concept: A leading-wildcard LIKE '%term%' cannot use a B-tree index and always scans. But a trailing-wildcard LIKE 'term%' (prefix search) can use a standard index — the engine seeks to the prefix and reads forward. So the trick is to design searches as prefix matches where possible.

// SLOW — leading wildcard, full table scan, cannot use index
var results = await _db.Products
    .Where(p => EF.Functions.Like(p.Name, $"%{term}%"))   // scans every row
    .Take(20)
    .ToListAsync(ct);

// FAST — prefix search uses a standard index on Name
var results = await _db.Products
    .Where(p => EF.Functions.Like(p.Name, $"{term}%"))    // index seek
    .OrderBy(p => p.Name)
    .Take(20)
    .ToListAsync(ct);

// Index that supports the prefix seek:
// CREATE INDEX IX_Products_Name ON Products (Name);

// Autocomplete pattern — prefix match, capped results, fast
public async Task<List<string>> AutocompleteAsync(string prefix, CancellationToken ct)
    => await _db.Products
        .Where(p => p.Name.StartsWith(prefix))            // translates to Name LIKE 'prefix%'
        .OrderBy(p => p.Name)
        .Select(p => p.Name)
        .Take(10)
        .ToListAsync(ct);

Why it works: Prefix search aligns with how B-tree indexes store data (sorted), so the database seeks directly to matching rows instead of scanning. For "starts with" and autocomplete this is genuinely fast and needs no extra infrastructure.

Benchmark note: On a 5-million-row table, LIKE '%term%' is a full scan — hundreds of milliseconds to seconds, and it gets linearly worse as the table grows. LIKE 'term%' with an index returns in single-digit milliseconds because it touches only matching index entries. The hard limits of this approach: no relevance ranking, no typo tolerance, no multi-word/any-order matching, and the moment you need infix search (%term%) you are back to scanning. This is the floor, not the solution, for real search.

---

Way 2: SQL Server Full-Text Search

Best used for: Natural-language search over text columns in SQL Server — product descriptions, articles, documents — with word stemming, multi-word matching, and relevance ranking, without leaving your existing database.

The concept: SQL Server's Full-Text Search builds a dedicated full-text index that tokenises text into words, applies language-aware stemming ("running" matches "run"), and supports CONTAINS / FREETEXT predicates with relevance ranking via CONTAINSTABLE. It understands words, not just character sequences.

-- Set up a full-text catalog and index (one-time)
CREATE FULLTEXT CATALOG ProductCatalog;
CREATE FULLTEXT INDEX ON Products(Name, Description)
    KEY INDEX PK_Products ON ProductCatalog;

// FREETEXT — natural language, handles word forms and any-order matching
var results = await _db.Products
    .Where(p => EF.Functions.FreeText(p.Description, term))
    .Take(20)
    .ToListAsync(ct);
// "running shoes" matches "shoe for runners" — stemming + word matching

// CONTAINS — more control: AND/OR, prefix, proximity
var results = await _db.Products
    .Where(p => EF.Functions.Contains(p.Name, "\"wireless\" AND \"headphone*\""))
    .Take(20)
    .ToListAsync(ct);

// Relevance ranking requires raw SQL with CONTAINSTABLE:
var ranked = await _db.Products
    .FromSql($@"
        SELECT p.*
        FROM Products p
        INNER JOIN CONTAINSTABLE(Products, (Name, Description), {term}) AS ft
            ON p.Id = ft.[KEY]
        ORDER BY ft.RANK DESC")
    .ToListAsync(ct);

Why it works: The full-text index pre-tokenises and stems text, so a search is a fast lookup against an inverted word index rather than a scan. RANK gives you relevance ordering — more matches and rarer terms score higher.

Benchmark note: Full-text search on millions of rows returns ranked results in tens of milliseconds where LIKE '%...%' would scan for seconds. It is "free" in that it ships with SQL Server. Limitations versus a dedicated engine: index updates are asynchronous (a "population" lag means just-inserted rows may not be searchable for seconds to minutes), typo tolerance is limited, and relevance tuning is coarse compared to Elasticsearch. Good for "decent search inside the database I already run".

---

Way 3: PostgreSQL Full-Text & Trigram (GIN indexes)

Best used for: PostgreSQL shops needing either proper full-text search (tsvector) or fuzzy/typo-tolerant substring matching (pg_trgm trigrams) — often both — without external infrastructure.

The concept: PostgreSQL has two complementary tools. tsvector/tsquery provide stemmed, ranked full-text search backed by a GIN index. The pg_trgm extension breaks text into three-character "trigrams" and indexes them, which makes infix LIKE '%term%' and fuzzy similarity matching fast — solving the leading-wildcard problem that defeats every other index type.

-- Full-text search with a GIN index on a generated tsvector column
ALTER TABLE products ADD COLUMN search_vector tsvector
    GENERATED ALWAYS AS (to_tsvector('english', name || ' ' || description)) STORED;
CREATE INDEX idx_products_search ON products USING GIN (search_vector);

-- Trigram extension for fuzzy / infix / typo-tolerant search
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX idx_products_name_trgm ON products USING GIN (name gin_trgm_ops);

// Full-text ranked search (via raw SQL — EF Core + Npgsql also has NpgsqlTsVector mapping)
var results = await _db.Products
    .FromSql($@"
        SELECT *, ts_rank(search_vector, websearch_to_tsquery('english', {term})) AS rank
        FROM products
        WHERE search_vector @@ websearch_to_tsquery('english', {term})
        ORDER BY rank DESC
        LIMIT 20")
    .ToListAsync(ct);

// Fuzzy / typo-tolerant search using trigram similarity
var fuzzy = await _db.Products
    .FromSql($@"
        SELECT *, similarity(name, {term}) AS sim
        FROM products
        WHERE name % {term}                    -- % = trigram similarity operator
        ORDER BY sim DESC
        LIMIT 20")
    .ToListAsync(ct);
// "hedphones" still matches "headphones" — trigrams tolerate the typo

// Infix LIKE that ACTUALLY uses an index, thanks to the trigram GIN index:
var infix = await _db.Products
    .Where(p => EF.Functions.ILike(p.Name, $"%{term}%"))  // index-backed, not a scan
    .Take(20)
    .ToListAsync(ct);

Why it works: The GIN index on tsvector is an inverted index of stemmed words (fast ranked search). The trigram GIN index makes substring and fuzzy matches indexable — the one thing standard B-tree indexes cannot do — so even %term% and misspellings are fast.

Benchmark note: Trigram-indexed ILIKE '%term%' on a few million rows returns in low tens of milliseconds versus a multi-second sequential scan without the index. Full-text with GIN is comparably fast and adds relevance ranking. The cost: GIN indexes are larger and slower to update than B-tree indexes (heavier write amplification), and the generated tsvector column adds storage. For PostgreSQL users this combination handles a large fraction of search needs without adding Elasticsearch — a genuinely underused capability.

---

Way 4: Dedicated Search Engine (Elasticsearch / OpenSearch)

Best used for: Search-centric products — e-commerce catalogues, log search, large content platforms — needing best-in-class relevance, faceting, typo tolerance, synonyms, aggregations, and horizontal scale beyond what a relational database offers.

The concept: You index your searchable data into a purpose-built engine (Elasticsearch, OpenSearch, or hosted equivalents like Azure AI Search). It maintains inverted indexes optimised purely for search, with rich query DSLs for relevance tuning, fuzzy matching, faceted filtering, and aggregations. Your relational database remains the source of truth; the search engine is a queryable projection of it.

// Querying Elasticsearch via the .NET client
public async Task<List<ProductDoc>> SearchAsync(string term, string? category, CancellationToken ct)
{
    var response = await _elastic.SearchAsync<ProductDoc>(s => s
        .Index("products")
        .Size(20)
        .Query(q => q
            .Bool(b => b
                .Must(m => m
                    .MultiMatch(mm => mm
                        .Query(term)
                        .Fields(new[] { "name^3", "description" }) // name weighted 3x
                        .Fuzziness(new Fuzziness("AUTO"))           // typo tolerance
                    ))
                .Filter(f => category is null
                    ? f.MatchAll()
                    : f.Term(t => t.Field("category").Value(category)))
            )),
        ct);

    return response.Documents.ToList();
}

// Keeping the index in sync — project DB changes into the engine
// (via the outbox pattern, change-data-capture, or a background sync job)
public async Task IndexProductAsync(Product p, CancellationToken ct)
    => await _elastic.IndexAsync(new ProductDoc
    {
        Id = p.Id, Name = p.Name, Description = p.Description,
        Category = p.Category, Price = p.Price
    }, i => i.Index("products"), ct);

Why it works: The engine is built for exactly this — inverted indexes, relevance scoring (BM25), fuzzy matching, and faceted aggregation are first-class and tuned over years. It scales horizontally across nodes, so search performance stays flat as data and query volume grow.

Benchmark note: Sub-50 ms ranked, faceted, typo-tolerant search over tens of millions of documents is routine. The cost is operational: another system to run, secure, monitor, and — critically — keep in sync. The synchronisation problem is the real engineering challenge, not the querying. Stale or missing documents (search shows a product that was deleted, or misses one just added) come from sync lag or failures. Use the outbox pattern or change-data-capture rather than dual-writes (write to DB and ES in the same request), because dual-writes lose data when one side fails. Only adopt this when search quality is a core product requirement — it is significant infrastructure.

---

Way 5: Materialized Views / Denormalized Search Tables

Best used for: Complex search/filter queries that join many tables and aggregate, where the query itself (not just text matching) is the bottleneck — faceted product search, reporting dashboards, "search across everything" features.

The concept: Instead of joining 6 tables and computing aggregates on every search request, you pre-compute a flattened, denormalized table (or materialized view) containing exactly the searchable/filterable fields, refreshed periodically or on change. Searches hit one wide, well-indexed table instead of an expensive multi-join query.

-- PostgreSQL materialized view — pre-joined, pre-aggregated search surface
CREATE MATERIALIZED VIEW product_search AS
SELECT
    p.id, p.name, p.description, p.price,
    c.name        AS category_name,
    b.name        AS brand_name,
    COALESCE(r.avg_rating, 0)  AS avg_rating,
    COALESCE(r.review_count, 0) AS review_count,
    to_tsvector('english', p.name || ' ' || p.description || ' ' || c.name) AS search_vector
FROM products p
JOIN categories c ON c.id = p.category_id
JOIN brands b     ON b.id = p.brand_id
LEFT JOIN (
    SELECT product_id, AVG(rating) avg_rating, COUNT(*) review_count
    FROM reviews GROUP BY product_id
) r ON r.product_id = p.id;

CREATE INDEX idx_psearch_vector ON product_search USING GIN (search_vector);
CREATE INDEX idx_psearch_category ON product_search (category_name);

-- Refresh on a schedule or after bulk changes (CONCURRENTLY avoids locking reads)
REFRESH MATERIALIZED VIEW CONCURRENTLY product_search;

// Search now hits ONE pre-joined table — no runtime joins or aggregation
var results = await _db.Database
    .SqlQuery<ProductSearchResult>($@"
        SELECT * FROM product_search
        WHERE search_vector @@ websearch_to_tsquery('english', {term})
          AND ({category} IS NULL OR category_name = {category})
          AND avg_rating >= {minRating}
        ORDER BY ts_rank(search_vector, websearch_to_tsquery('english', {term})) DESC
        LIMIT 20")
    .ToListAsync(ct);

Why it works: The expensive joins and aggregations happen once at refresh time, not on every query. Searches read from a single denormalized, indexed table — fast and predictable. It is a middle ground: more powerful than raw LIKE, far less infrastructure than Elasticsearch, and it stays inside your database.

Benchmark note: A faceted search that joins 6 tables and aggregates reviews might take 200–500 ms per request live; against a materialized view it is 5–20 ms because the work is pre-done. The trade-off is staleness — results reflect the last refresh, not live data. REFRESH ... CONCURRENTLY avoids locking readers during refresh but requires a unique index and takes longer. Tune refresh frequency to your tolerance for staleness (every few minutes for a catalogue, near-real-time via triggers for critical data). SQL Server's equivalent is an indexed view, with stricter requirements but automatic maintenance.

---

Choosing the right approach

• Autocomplete / "starts with" / small data → Indexed prefix LIKE (Way 1)
• Natural-language search inside SQL Server → SQL Server Full-Text (Way 2)
• Fuzzy / infix / full-text inside PostgreSQL → tsvector + pg_trgm GIN (Way 3)
• Search is a core product feature, large scale → Elasticsearch / OpenSearch (Way 4)
• Expensive multi-join faceted queries → Materialized view / denormalized table (Way 5)

The progression most teams follow: start with indexed LIKE/prefix search (Way 1) — it covers more than people expect. When you need word-aware ranked search, reach for your database's built-in full-text (Way 2 or 3) before adding infrastructure — PostgreSQL's trigram + full-text combination in particular handles a surprising amount. Add a materialized view (Way 5) when the join is the cost, not the text match. Only adopt a dedicated search engine (Way 4) when search quality and scale are genuinely core to the product — and when you do, treat keeping it in sync as the main engineering problem, solved with the outbox pattern, not dual-writes.

Note: this is an informational engineering overview. Benchmark figures are illustrative order-of-magnitude estimates that depend on data size, index design, hardware, and configuration. Always measure against your own workload.