Skip to content

ARCH.md

Latest commit

 

History

History
139 lines (98 loc) · 10.1 KB

ARCH.md

File metadata and controls

139 lines (98 loc) · 10.1 KB
Raw

Architecture

HypGrep is a serverless grep over Parquet files in S3. A client (browser, Node, etc.) reads a small precomputed index over HTTP range requests, then reads only the source byte ranges that could plausibly match. The dominant cost being optimized is per-query transfer bytes — every byte the client pulls is wall-clock latency and dollar cost. File size on disk is a secondary metric.

Index format

A HypGrep index is itself a Parquet file with two columns:

column type encoding meaning
ngram STRING DELTA_BYTE_ARRAY a lowercase n-character substring
blockId INT32 DELTA_BINARY_PACKED logical block this n-gram appears in

Rows are sorted by (ngram, blockId). The set of blockIds for a given n-gram is its posting list. The source file is divided into logical blocks of block_size consecutive rows (independent of Parquet row groups). The index records, for each block, the set of distinct n-grams present across every indexed string column.

Key-value metadata on the index file:

hypgrep.version          # format version
hypgrep.block_size       # rows per block
hypgrep.ngram_length     # n-gram size (default 5)
hypgrep.text_columns     # which columns were indexed
hypgrep.source_rows      # total rows in source
hypgrep.source_bytelength # source file size (lets the client pre-size buffers)

Storing source size in the metadata lets the client construct an AsyncBuffer for the source without a separate HEAD request.

Query path

For a query string Q:

  1. Derive n-grams from the query.
    • String query: lowercase; split on /[^a-z0-9]+/; emit every n-character window of each alphanumeric run. This is a superset filter; the row matcher applies the final search semantics.
    • RegExp query: walk the regex source to extract mandatory literal substrings (handling escapes, character classes, groups, quantifiers, and top-level alternation safely), then run the string n-gram extractor over each literal.
    • No extractable n-grams (very short string, or regex like /./ or /foo|bar/): skip pruning and return all blocks. The substring/regex filter still runs per row — correct grep semantics, just no index acceleration.
  2. Push-down filter on the index with { ngram: { $in: queryNgrams } }. Hyparquet only reads the row-group(s) covering those n-grams.
  3. Intersect. Group returned rows by blockId; keep blocks that hit every query n-gram.
  4. For each candidate block, in order, read the row range from the source with parquetReadObjects({ rowStart, rowEnd }) and useOffsetIndex: true. Both files are wrapped in cachedAsyncBuffer for the duration of the query so adjacent blocks within a Parquet row group don't re-fetch its pages.
  5. Per-row match. parquetFind verifies the full string query as a contiguous case-insensitive substring; parquetSearch requires every whitespace-separated query word and scores by occurrence count. For RegExp queries, the regex runs across indexed columns.
  6. limit short-circuits as soon as enough matches have been yielded — subsequent blocks are never read.

Key tuning decisions

Why n = 5

Shorter n-grams fail to prune prose at any reasonable block size — every block of natural-language text contains every common 3- or 4-character window, so trigram intersection returns every block as a candidate and we end up scanning the whole source. n = 5 has a large enough universe (~285K alnum 5-grams vs ~47K trigrams) that distinguishing windows like rverl (serverless) or ichor (petrichor) prune effectively. Per-query source transfer on a 420 MB Wikipedia dump:

query n=3 n=4 n=5
eigenvalue (67 hits) 839 MB 205 MB 189 MB
petrichor (0) 839 MB 839 MB 316 MB
serverless (0) 839 MB 839 MB 29 MB

Tradeoff: index size grows with n. n=3 → 1.2 MB, n=5 → 15 MB on Wikipedia. The goal weighs query bytes far more than index size, so the larger index pays for itself many times over after the first few queries.

Why blockSize = 100

Smaller blocks improve pruning — when a candidate block is selected, fewer "wasted" non-matching rows ride along. Going from 500 to 100 cuts source transfer roughly in half on absent/rare-string queries:

query b=500 b=100
petrichor 301 MB 157 MB
serverless 28 MB 0 MB

Tradeoff: smaller blocks mean more (ngram, blockId) postings. Index grows 15 → 25 MB. Again favorable under the goal.

Per-block reads + cachedAsyncBuffer

Both source and index files are wrapped with cachedAsyncBuffer for the duration of a query. Parquet readers commonly re-fetch the same byte range across calls (page footer + page data, or overlapping row-group pages when adjacent blocks fall in the same row group). The cache memoizes slices by (start, end), so duplicate fetches are free.

An earlier version coalesced contiguous candidate blocks into single parquetReadObjects calls to avoid the re-fetch. That worked for transfer bytes but defeated limit: a limit: 10 query against a string that matched every block still pulled the entire coalesced run. Switching back to per-block reads (relying on the cache to dedupe pages) costs identical bytes on full scans while letting limit short-circuit on the next block boundary. Measured impact:

query without cache with cache
eigenvalue 195 MB 150 MB
petrichor 106 MB 59 MB
quantum entanglement 159 MB 107 MB

End-to-end bytes on Wikipedia (420 MB source, 24 MB index)

No limit (every match):

query matches total index source
eigenvalue 67 150.4 MB 724 KB 150 MB
petrichor 0 59.6 MB 646 KB 59 MB
serverless 0 0.7 MB 689 KB 0 MB
quantum entanglement 12 107.7 MB 870 KB 107 MB
wikipedia 156289 401.3 MB 708 KB 401 MB

limit: 10 (typical client usage):

query matches total index source
eigenvalue 10 42.5 MB 724 KB 42 MB
petrichor 0 59.6 MB 646 KB 59 MB
serverless 0 0.7 MB 689 KB 0 MB
quantum entanglement 10 76.3 MB 870 KB 75 MB
wikipedia 10 14.1 MB 708 KB 13 MB

Per-query index transfer is bounded at ~700 KB regardless of selectivity — that's the property that makes the design serverless-friendly. The source transfer scales with how many blocks legitimately match, and limit lets selective UIs (first 10 hits) clip it further.

API surface

  • createIndex({ sourceFile, indexFile, blockSize?, ngramLength?, ... }) — build the index Parquet. blockSize, indexRowGroupSize, and ngramLength must be positive safe integers.
  • queryIndex({ query, indexFile, indexMetadata? }) — return candidate blocks, or undefined for an empty query. query accepts a string or RegExp.
  • parquetFind({ query, url, limit?, rowFilter?, ... }) — async generator of matching rows in natural order. query accepts a string or RegExp. rowFilter overrides the default row predicate.
  • parquetSearch({ query, url, limit?, ... }) — async generator of matching rows ranked by occurrence count.

All reader functions accept either a url (with optional asyncBufferFactory) or pre-loaded sourceFile / indexFile AsyncBuffers.

CLI

hypgrep <file.parquet> [<file.index.parquet>]      build an index
hypgrep search <file.parquet> <pattern> [options]   grep the file

Search options: --limit N, --index <path>, -c/--count, -i/--ignore-case. Patterns wrapped as /regex/flags are treated as regex; otherwise literal.

Known limitations and where to push next

  1. Queries shorter than ngramLength (default 5) chars fall back to a full scan of every block. Correct, just unaccelerated.

  2. Common-everywhere words (e.g. wikipedia in a Wikipedia dump) match every block; the source transfer is unavoidable because every row really does match. No n-gram strategy fixes this.

  3. Per-row precision is missing. A candidate block is scanned in full even if only one row matches. Storing per-(ngram, block) row bitmaps would let queries narrow the source read to specific rows, at the cost of a ~3× larger index. Probably the highest-value next step for sparse queries that match a small number of rows spread across many blocks.

  4. No-limit queries on dense matches do more work than they need to. When every block matches (e.g. wikipedia against a Wikipedia dump), exhausting all matches takes ~24 s of CPU because we process blocks one at a time. The bytes are minimal; the time is CPU/parsing overhead. Real clients should pass a limit.

  5. Regex literal extractor caps DNF expansion at 32 branches. Groups with alternation are recursed into and cross-producted, so /abc(foo|bar)def/ yields the tight {abcfoodef} ∨ {abcbardef}. Two flavors of fold keep adjacent literals contiguous so the n-gram extractor can prune them:

    • Char class fold: small literal-only classes (no negation, no ranges, no \w/\d, single occurrence) concat into the run — /serv[ei]rless/ becomes {serverless} ∨ {servirless} (333 MB → 0 MB on Wikipedia).
    • Group fold: when every inner branch is a single contiguous literal, the group also concats — /(eigen|petri)(value|chor)/ becomes {eigenvalue} ∨ {eigenchor} ∨ {petrivalue} ∨ {petrichor} (615 MB full scan → 51 MB).

    Negated classes, ranges, \d/\w, multi-char quantifiers like [ab]{3} (which could match aab), and groups whose inner branches contain wildcards or multiple literals fall back to wildcard or independent-literal treatment to stay correct. Deeply nested expansions that would exceed 32 branches drop the offending construct conservatively.

  6. Index files are not back-compatible. hypgrep.version exists but we don't ship a multi-version reader. Reasonable for a 0.x package.

Dependencies

  • hyparquet — Parquet reader with push-down filtering, offset index, and cachedAsyncBuffer.
  • hyparquet-writer — Parquet writer with DELTA_BYTE_ARRAY / DELTA_BINARY_PACKED encodings that keep the index small.
  • hyparquet-compressors — compression codecs.