Large-Scale Billing Statement Duplicate-Check Monitor Optimization

1. Business Background

This is a monitoring script that runs on a daily schedule, used to "de-duplicate" the billing rules behind billing statements: checking whether there are conflicting rules that could cause duplicate or incorrect billing. When a conflict is found, every conflicting record pair (A, B) must be fully logged and output for manual review — keeping only a count or the first N results is not acceptable.

As data volume grew to 100K+ billing statement records, this monitoring script started to regularly:

• Exceed the execution time limit and get forcibly terminated — exit 1
• Or run out of memory (OOM) and get killed — exit 1

Either case causes the daily monitor to fail outright, triggering an alert, without ever producing a de-duplication result. This document records how the script's logic was optimized so it can run reliably every day within the time and memory limits.

2. Original Logic and Bottlenecks

The simplified structure of a single billing statement record:

{
  app: string | 'all',
  region: string | 'all',
  campaign_id: string,
  field_A: string,
  field_B: string,
  field_C: string,
  field_D: string,
  start_time: number,
  end_time: number,
  // ~100 other fields
}

Conflict rule:

Conflict(A, B) = MatchingDimensions(A, B) AND OverlappingTime(A, B)

MatchingDimensions(A, B) = app matching AND region matching
                           AND field_A/B/C/D matching AND ...

• app and region have all wildcard semantics (all matches any value)
• campaign_id, field_A~D, and similar fields do not have wildcard semantics — only exact match applies

The original implementation was the most straightforward brute-force approach: load all records into memory and compare every pair:

for (const a of records) {
  for (const b of records) {
    if (isConflict(a, b)) logs.push([a, b]);
  }
}

Bottlenecks:

These are two independent problems: the time bottleneck comes from "comparing brute-force without filtering first"; the space bottleneck comes from the non-negotiable requirement of "fully outputting every conflict." Either way, the monitor script fails before it ever produces a result — so the optimization is split into two separate tracks: Time and Space.

3. Time Optimization

3.1 Layer 1 — Multi-dimensional Safe Partition

Core idea: Fields without wildcard semantics — campaign_id, field_A~D — can safely be used as equality partition keys. If even one of them differs, two records can never conflict (they can't be "revived" by app/region being all). app and region, because they carry wildcard semantics, cannot be used for partitioning.

Approach: build a composite key from these fields to group records, and only run pairwise comparisons within the same group — replacing the original global comparison:

All records
     ↓
Multi-dimensional partition
     ↓
┌────────┬────────┬────────┬──────┐
│ Group A│ Group B│ Group C│ ...  │
└────────┴────────┴────────┴──────┘
     ↓
Compare within each group

This eliminates a large number of pairs that could never conflict, before any pairwise comparison happens.

Effect: If partitioning splits the data into G roughly equal-sized groups, complexity drops from O(n²) to O(n²/G). For example, with n = 10 and no partitioning, n² = 100. Splitting evenly into 2 groups of 5 gives 5² + 5² = 50 — already half the comparisons, without touching any of the actual conflict-detection logic. In practice there are 4–5 usable dimensions to build the composite key from, so G can be pushed quite large, making n²/G far smaller than n².

3.2 Layer 2 — Priority Queue on end_time (within a group)

Even after partitioning, a single group can still hold a large number of records (say group size m), and naively comparing every pair within that group is still O(m²). A sweep-line pass over the time dimension can cut this down further.

Approach: sort the records in the group by start_time, and maintain a min-heap (priority queue) ordered by end_time, holding only the intervals that could still overlap the record being processed. For each record, in start_time order:

1. Pop every interval whose end_time < current.start_time off the heap — those intervals have already ended and can't overlap this or any later record.
2. Compare current only against whatever intervals remain in the heap.
3. Push current onto the heap and move to the next record.

A [1, 10]   B [3, 5]   C [6, 8]   D [11, 15]

Process A → heap: A(10)
Process B → A.end(10) ≥ B.start(3), A still active → compare A/B → heap: B(5), A(10)
Process C → B.end(5) < C.start(6), pop B; A.end(10) ≥ 6 → only compare A/C
Process D → both C.end and A.end < D.start(11), pop everything → heap empty → D needs no comparisons

Non-overlapping intervals get excluded before any comparison actually happens.

Effect: Sorting is O(m log m); each heap push/pop is O(log m), so heap maintenance is also O(m log m). Let K be the number of pairs within the group whose time intervals actually overlap — that's exactly the set of pairs the heap forces us to compare (app/region still need a final O(1) wildcard check per pair, but K itself is just the overlap count, not the final conflict count). The total becomes O(m log m + K). Worst case K = O(m²) (every interval overlaps every other), same as before; but when most intervals don't overlap in time, K << m², and the real comparison workload inside a group drops substantially.

4. Database-side Group Discovery

If all records are fetched into the application first and then partitioned:

MySQL → 100K+ rows → Application → Partition

The comparison workload goes down, but the application still has to hold the entire dataset first — the space bottleneck isn't actually solved.

So instead, let MySQL compute the partition metadata first, rather than fetching the data directly:

SELECT campaign_id, field_A, field_B, field_C, field_D, COUNT(*) AS cnt
FROM statement
GROUP BY campaign_id, field_A, field_B, field_C, field_D;

The purpose of this query isn't validation — it's to get "how many rows correspond to each partition key":

(A, X, P, M, 1) → 2K
(A, X, P, M, 2) → 3K
(B, Y, Q, N, 1) → 4K
...

This lets the application know how big each group is before it actually fetches any records — and this group-size information is exactly what the batch planner in the next section uses to decide how to pack batches.

5. Space Optimization

5.1 Bounded Complete-Group Batching (bounding input-side memory)

Once the group sizes for each partition are known, the application packs complete groups into batches under a memory cap (e.g. 10K rows), fetching, validating, and releasing one batch at a time:

MySQL group metadata → batch planner → Batch 1 (complete groups) → fetch → validate → release
                                     → Batch 2 → ...

This also resolves the DB round-trip trade-off: batches too small → more round trips; batches too large → more memory. Packing complete groups up to near the cap balances both.

Application memory therefore is no longer O(n) for loading everything at once — it's O(B), where B is the maximum batch size.

5.2 Incremental Conflict Logging (bounding output-side memory)

Even with input bounded by batching, the conflict log can still keep growing until memory runs out. Instead, use a fixed-size buffer (size L); once it's full, flush it to a temp file:

const buffer = [];
for (const conflict of conflicts) {
  buffer.push(conflict);
  if (buffer.length >= BUFFER_SIZE) {
    flushToFile(buffer);
    buffer.length = 0;
  }
}

The final output is also never read back into memory as a whole — it's streamed out chunk by chunk from the temp file. The total log size can still be the business-mandated, unavoidable O(n²), but that O(n²) now lives on disk, not in application RAM.

6. Final Architecture

Putting all the steps together:

                         MySQL
                           │
                           ▼
              GROUP BY safe equality fields
                           │
                           ▼
                  Partition metadata
                  (key + row count)
                           │
                           ▼
                  Application planner
                           │
                           ▼
              Complete-group batch planning
                           │
              ┌────────────┴────────────┐
              ▼                         ▼
           Batch 1                   Batch 2
              │                         │
              ▼                         ▼
       Fetch complete              Fetch complete
          groups                      groups
              │                         │
              ▼                         ▼
       Pairwise validation         Pairwise validation
       within each group           within each group
              │                         │
              └────────────┬────────────┘
                           ▼
                  Fixed-size log buffer
                           │
                      buffer full
                           ▼
                    Temporary file
                           │
                           ▼
                   Streaming output

7. Before / After Comparison

The optimized application memory O(G + B + L) has three parts: G is the number of partition groups (group metadata size), B is the maximum record count per batch, and L is the fixed log buffer capacity.

B and L are manually configured caps (batch size cap, buffer size) that don't grow with n, so they're O(1); only G varies with data volume and partition dimensionality. So O(G + B + L) simplifies further to O(G).

8. Conclusion

Time optimization works in two layers: safe equality dimensions first shrink the candidate comparison space across groups, then a sweep line over end_time within each group filters out non-overlapping intervals before they're ever compared. Space optimization relies on complete-group batching to bound the input-side working set, plus incremental buffering and streaming to move the unavoidable, business-mandated large volume of conflict results from RAM to disk. None of this changes the original wildcard semantics or the "fully output every conflict" business requirement — together they turn the brute-force validation into a bounded pipeline that can handle 100K+ records.