大規模帳單明細驗重監控優化

1. 業務背景

這是一個每天排程執行的監控腳本，用來對帳單明細背後的計費設定做「驗重」：檢查是否存在彼此衝突、可能造成重複計費或計費錯誤的設定。發現衝突時，所有衝突的 record pair (A, B) 都必須完整記錄輸出供人工檢查，不能只保留 count 或前 N 筆。

隨著資料量成長到 100K+ 筆帳單明細，這個監控腳本開始常態性地：

• 跑超過執行時間限制，被系統強制中斷、exit 1
• 或把記憶體吃到 OOM，被系統 kill、exit 1

兩種情況都會讓每日監控直接失敗、觸發告警，且完全跑不出驗重結果。這份文件記錄怎麼優化這個腳本的邏輯，讓它能在時間與記憶體限制內每天穩定跑完。

2. 原始邏輯與瓶頸

單筆帳單明細（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 判定規則：

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、region 有 all wildcard 語意（all 可以 match 任何值）
• campaign_id、field_A~D 等欄位沒有 wildcard 語意，只能 exact match

原始實作是最直接的 brute-force：把全部 record 抓進記憶體，兩兩互相比較：

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

瓶頸：

兩者是獨立問題：Time bottleneck 來自「沒有先篩選就硬比對」；Space bottleneck 來自「業務要求完整輸出」這個無法妥協的限制。無論哪一種，監控腳本都會在跑出驗重結果之前就失敗，所以優化拆成 Time 與 Space 兩條路線分別處理。

3. Time 優化

3.1 第一層：Multi-dimensional Safe Partition

核心想法： campaign_id、field_A~D 這些沒有 wildcard 語意的欄位可以安全地拿來做 equality partition —— 只要其中一個不同，兩筆 record 就絕對不可能衝突（不會因為 app/region = all 而復活）。app、region 因為有 wildcard 語意，不能拿來 partition。

做法：用這些欄位組成 composite key 分組，pairwise 比較只在同個 group 內進行，取代原本的 global 比較：

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

這會在 pairwise comparison 前先消除大量不可能 conflict 的 pairs。

效果： 設 partition 後切成 G 個大小接近的 group，複雜度從 O(n²) 降為 O(n²/G)。舉例來說，n = 10 不做 partition 時 n² = 100；平均切成 2 個大小為 5 的 group，變成 5² + 5² = 50，光是這樣就直接砍半，還沒動到真正的 conflict 判斷邏輯。實際上有 4~5 個可用維度組成 composite key，G 會被撐得很大，n²/G 遠小於 n²。

3.2 第二層：group 內用 Priority Queue 卡 end_time

partition 完之後，單個 group 裡仍可能有大量 record（設 group size = m），如果 group 內直接兩兩比較，還是 O(m²)。可以再用一層 sweep line 進一步縮小實際比較量。

做法：把 group 內的 record 依 start_time 排序，用一個以 end_time 排序的 min-heap（priority queue）維護「目前仍可能重疊的 active interval」。依序處理每筆 record 時：

1. 把 heap 裡 end_time < current.start_time 的 interval 全部移除——它們已經結束，不可能再跟這筆或之後任何 record 重疊
2. current 只需要跟 heap 裡剩下的 active interval 比較
3. 把 current 推入 heap，繼續處理下一筆

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

處理 A → heap: A(10)
處理 B → A.end(10) ≥ B.start(3)，A 仍 active → 比較 A/B → heap: B(5), A(10)
處理 C → B.end(5) < C.start(6)，移除 B；A.end(10) ≥ 6 → 只比較 A/C
處理 D → C.end、A.end 都 < D.start(11)，全部移除 → heap 為空 → D 不用跟任何 record 比較

不重疊的 interval，在真正比較之前就被排除掉了。

效果： 排序 O(m log m)；heap push/pop 各 O(log m)，維護成本合計也是 O(m log m)。設 K 為 group 內「時間區間互相重疊」的 pair 數量——也就是 heap 篩選後，真正需要被比較的那些 pair（app/region 的 wildcard 判斷還要再花 O(1) 個 pair 一次，但那不影響 K 本身；K 純粹是時間重疊的數量，不是最終判定為 conflict 的數量）。總體為 O(m log m + K)。最壞情況所有 interval 兩兩重疊，K = O(m²)，跟原本一樣；但當 group 內大量 interval 在時間上不重疊時，K << m²，單個 group 的實際比較量可以大幅下降。

4. Database-side Group Discovery

如果先把全部 records 抓進 application 再做 partition：

MySQL → 100K+ rows → Application → Partition

比較量雖然降低了，但 application 仍然要先扛住整份 dataset，Space 瓶頸並沒有真的解決。

因此改成先讓 MySQL 算出 partition metadata，而不是直接抓資料：

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;

這個 query 的目的不是做 validation，而是先取得「每個 partition key 對應多少筆資料」：

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

Application 因此可以在真正 fetch record 之前，就先知道每個 group 有多大——這份 group size 資訊正是下一節 batch planner 用來決定怎麼打包 batch 的依據。

5. Space 優化

5.1 Bounded Complete-Group Batching（限制輸入端記憶體）

拿到每個 partition 的 group size 後，依記憶體上限（例如 10K rows）把完整的 group 打包成 batch，逐 batch fetch → validate → 釋放：

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

這也順便解決了 DB round-trip 的取捨：batch 太小 → round trip 變多；batch 太大 → 記憶體變大。以完整 group 打包到接近上限，兩者取得平衡。

Application 記憶體因此不再是 O(n) 同時載入全部資料，而是 O(B)（B 為單個 batch 大小）。

5.2 Incremental Conflict Logging（限制輸出端記憶體）

即使輸入被 batch 限制住，conflict log 仍可能持續累積到爆記憶體。改成固定大小的 buffer（大小為 L），滿了就 flush 到暫存檔：

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

最終輸出也不整份讀回記憶體，而是用 stream 逐 chunk 讀暫存檔輸出。完整 log 大小依然可能是業務要求下無法避免的 O(n²)，但這個 O(n²) 落在 disk，不是 application RAM。

6. 最終架構

把上述所有步驟串起來：

                         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. 前後對比

優化後 application 記憶體 O(G + B + L) 由三部分組成：G 為 partition group 數量（group metadata 大小）、B 為單個 batch 的最大 record 數、L 為固定大小的 log buffer 容量。

B、L 是人為設定的上限值（batch size cap、buffer size），不會隨 n 成長，可視為 O(1)；只有 G 會隨資料量與 partition 維度變化。因此 O(G + B + L) 可以進一步簡化成 O(G)。

8. 結論

Time optimization 分兩層：先用 safe equality dimensions 縮小跨 group 的 candidate 比較範圍，再用 end_time 的 sweep line 在 group 內部把不重疊的 interval 排除在比較之前。Space optimization 靠 complete-group batching 限制輸入端 working set，再靠 incremental buffer + streaming 把業務要求下無法避免的大量 conflict result 從 RAM 移到 disk。兩者都不改變原本的 wildcard 語意與「完整輸出所有 conflict」的業務要求，讓 brute-force validation 變成可處理 100K+ records 的 bounded pipeline。