Cutting Rule Matching Latency: From Exponential to Linear with Inverted Index & Bitmaps

Background

Promise's time‑control system is a critical node in the order‑placement chain, selecting the optimal rule from a rule base of hundreds of thousands to return timing control results to the client. During peak traffic (e.g., Double‑11), the system handles millions of TPS with an SLA of under 5 ms, making fast and accurate rule matching a major technical challenge.

Naïve Solution

The simple approach caches the rule base line‑by‑line in Redis (key = rule condition, value = rule result). For each request, all possible parameter combinations are generated and used as keys to look up matching rules, then the best rule is selected. This leads to a time complexity of 2ⁿ (n≈12), requiring up to 4096 calculations and reads per request, which is unacceptable at scale.

New Solution

The improved design flips the perspective from rows to columns, using column‑wise inverted indexes and bitmap bitwise operations. Each column’s values are mapped to a posting list (row IDs). Bitmaps are generated from these posting lists, allowing fast logical OR (||) within a column and AND (&&) across columns to obtain a candidate rule set.

Algorithm Details

4.1 Pre‑compute Column Inverted Indexes and Bitmaps

For each column value, a posting list is created (e.g., A=301 → {1}, A=201 → {2,3,4,5}). Empty values are also indexed (nil → {7}).

4.2 Convert Inverted Indexes to Bitmaps

The posting lists are transformed into bitmaps where each row ID corresponds to a bit position, enabling efficient bitmap calculations.

4.3 Query Processing

Request parameters are used as keys to retrieve matching bitmaps. Within each column, bitmap OR operations handle normal and empty values; across columns, bitmap AND operations produce the candidate rule set.

4.4 Selecting the Optimal Rule

Candidate rules are sorted by business priority. Bitwise AND is applied iteratively; the last non‑zero result yields the optimal rule. If a column’s bitmap is missing, an empty bitmap (e.g., B_nil) participates in the AND.

Complexity Analysis

Time complexity drops to O(n): one OR pass and one AND pass for candidate generation, plus one AND pass for optimal rule selection, yielding roughly 3n ≈ n operations.

Space complexity increases because each column stores posting lists, but bitmap compression (e.g., RoaringBitmap) dramatically reduces actual memory usage.

Engineering Issue – Bitmap Compression

Sparse bitmaps can waste space. For a rule hitting the 10 millionth bit, a plain BitSet would consume ~1.2 MB, whereas RoaringBitmap compresses it to ~144 bytes. In a 10 million‑bit space with 10 000 values, RoaringBitmap uses ~31 KB versus ~2 MB, a ~100× reduction.

RoaringBitmap splits large bitmaps into containers that are allocated only when needed, enabling both storage compression and faster set operations.

Applicability

The approach works well when posting lists are simple row IDs and queries are equality‑based. It is unsuitable for complex objects or range/LIKE queries because the method relies on a finite, enumerable key space.

Other Optimizations

Beyond bitmap bitwise operations, ordered posting lists can be accelerated with skip‑lists or hash tables. For example, Elasticsearch uses skip‑lists to intersect posting lists in O(log n) time.

Reference: “How the industry leverages skip‑lists, hash tables, and bitmaps for inverted index acceleration?” https://time.geekbang.org/column/article/221292