PySpark 대규모 퍼지 매칭 — Cross Join 없이 수억 건 레코드 링크

"같은 사람인데 이름이 조금씩 다른" 레코드를 합치는 일 — 고객 마스터 통합, 중복 거래처 정리, 부정거래 탐지 — 은 데이터 엔지니어링의 단골 난제입니다. 정확히 일치하면 조인하면 그만이지만, "김철수" 와 "김 철수", "Seoul" 과 "서울특별시" 처럼 유사하지만 다른 값을 매칭해야 합니다.

문제는 규모입니다. 100만 건끼리 모든 쌍을 비교하면 5천억 번의 비교가 필요합니다(O(n²)). 수억 건이면 cross join 으로는 우주가 끝나도 안 끝납니다. 이 글은 이 벽을 넘는 두 가지 핵심 기법 — 블로킹(Blocking) 과 LSH(Locality Sensitive Hashing) — 를 PySpark 로 구현하는 법을 정리합니다.

1. 문제의 본질 — O(n²) 의 벽

100만 × 100만 = 1조 쌍 → 각 쌍마다 유사도 계산 → 현실적으로 불가능

퍼지 매칭의 모든 기법은 결국 하나의 목표를 향합니다 — "비교할 필요 없는 쌍을 비교 후보에서 빼는 것". 전부 비교(cross join)하지 않고, 닮았을 가능성이 있는 쌍만 추려서 그 안에서만 정밀 비교합니다.

2. 1단계 — 블로킹(Blocking)

가장 단순하고 강력한 기법. "같은 블록 키를 가진 것끼리만 비교" 합니다. 예를 들어 "성씨 + 생년" 이 같은 사람끼리만 비교하면, 비교 대상이 극적으로 줄어듭니다.

from pyspark.sql import functions as F
 
# 블로킹 키 생성: 성씨 첫 글자 + 생년 + 우편번호 앞 3자리
df = df.withColumn("block_key",
    F.concat_ws("|",
        F.substring("name", 1, 1),
        F.year("birth"),
        F.substring("zipcode", 1, 3)))
 
# 같은 블록 안에서만 self-join (cross join 회피)
a = df.alias("a")
b = df.alias("b")
candidates = (a.join(b, "block_key")
    .where("a.id < b.id"))      # 중복 쌍·자기자신 제거

핵심 트레이드오프: 블록 키가 느슨하면 블록이 커져 비교가 많아지고, 빡빡하면 진짜 매칭을 놓칩니다. 보통 여러 블로킹 키를 만들어 union(multi-pass blocking)해서 recall 을 높입니다.

블록 스큐 주의

흔한 성씨(김)는 거대 블록을 만들어 그 안에서 다시 O(n²) 가 됩니다. 블록 크기를 모니터링하고, 큰 블록은 키를 더 세분화하세요. (스큐 일반론은 별도 글 "PySpark 데이터 스큐 완전 정복" 참고.)

3. 2단계 — MinHash LSH 로 유사 후보 추리기

블로킹은 "정확히 같은 키"가 전제입니다. 오타·표기 변형까지 잡으려면 LSH 가 필요합니다. LSH 의 아이디어: 유사한 항목이 높은 확률로 같은 해시 버킷에 떨어지게 하는 해시 함수를 써서, 같은 버킷 안에서만 비교합니다.

문자열 유사도(자카드)에는 MinHash LSH 를 씁니다. Spark MLlib 에 내장되어 있습니다.

단계 ① 텍스트 → 특징 벡터 (n-gram)

from pyspark.ml.feature import RegexTokenizer, NGram, HashingTF
 
# 문자 단위 정규화
df = df.withColumn("clean", F.lower(F.regexp_replace("name", "\\s+", "")))
 
# 문자 3-gram 생성 (예: "김철수" → ["김철수"] 등 — 한글은 자소/문자 단위 선택)
df = df.withColumn("chars", F.split("clean", ""))
ngram = NGram(n=3, inputCol="chars", outputCol="ngrams")
df = ngram.transform(df)
 
# n-gram → 희소 벡터
tf = HashingTF(inputCol="ngrams", outputCol="features", numFeatures=1 << 18)
df = tf.transform(df)

단계 ② MinHashLSH 학습·적용

from pyspark.ml.feature import MinHashLSH
 
mh = MinHashLSH(inputCol="features", outputCol="hashes", numHashTables=5)
model = mh.fit(df)
 
# 자기 자신 데이터셋 내 근사 유사 쌍 찾기 (자카드 거리 임계값 0.3 이하 = 유사도 0.7 이상)
pairs = model.approxSimilarityJoin(df, df, threshold=0.3, distCol="jaccard_dist")
 
candidates = (pairs
    .where("datasetA.id < datasetB.id")   # 중복·자기자신 제거
    .select(
        F.col("datasetA.id").alias("id_a"),
        F.col("datasetB.id").alias("id_b"),
        F.col("jaccard_dist")))

approxSimilarityJoin 은 cross join 없이, LSH 버킷이 겹치는 쌍만 후보로 내놓습니다. numHashTables 를 늘리면 recall(놓침 감소)이 올라가지만 비용도 늘어납니다.

4. 3단계 — 후보 정밀 비교(스코어링)

블로킹/LSH 로 추린 소수의 후보 쌍에 대해서만 비싼 정밀 유사도를 계산합니다. 이제 쌍이 적으므로 UDF/Pandas UDF 를 써도 됩니다.

# 여러 필드의 가중 유사도 (Levenshtein 등 내장 + 커스텀)
scored = candidates.join(df.alias("ra"), F.col("id_a") == F.col("ra.id")) \
                   .join(df.alias("rb"), F.col("id_b") == F.col("rb.id")) \
    .withColumn("name_sim",
        1 - F.levenshtein("ra.name", "rb.name") /
            F.greatest(F.length("ra.name"), F.length("rb.name")))
 
matches = scored.withColumn("score",
    0.6 * F.col("name_sim") + 0.4 * (1 - F.col("jaccard_dist"))
).where("score >= 0.85")

정밀 비교에 복잡한 로직이 필요하면 벡터화된 pandas_udf 가 적합합니다(별도 글 "PySpark UDF가 느린 이유와 Pandas UDF" 참고). 핵심은 이 단계에 들어오는 쌍이 이미 충분히 적다는 것입니다.

5. 전체 파이프라인

[원본 수억 건]
     │  ① 정규화 (소문자·공백·특수문자 제거)
     ▼
[블로킹 또는 LSH] ── cross join 회피, 유사 후보만 ──> [후보 쌍 (수백만)]
     │  ③ 정밀 스코어링 (Levenshtein·가중합)
     ▼
[매칭 쌍 (score ≥ 임계값)]
     │  ④ 군집화 (연결된 매칭을 한 엔티티로)
     ▼
[통합 엔티티]

마지막 ④단계 — "A=B, B=C 면 A=C" 로 매칭을 군집(연결 요소)으로 묶는 것 — 은 그래프 문제입니다. GraphFrames 의 Connected Components 로 푸는 법은 별도 글 "PySpark GraphFrames 엔티티 해소"에서 다룹니다.

6. 정밀도 vs 재현율 튜닝

퍼지 매칭은 놓침(recall) 과 오매칭(precision) 의 줄다리기입니다.

실무 권장: 블로킹으로 1차 후보를 좁히고, LSH 로 변형까지 커버하고, 정밀 스코어로 마무리하는 3단 구성이 비용·품질 균형이 가장 좋습니다. 한 기법만으로 다 하려 하지 마세요.

7. 흔한 함정

8. 정리

대규모 퍼지 매칭의 핵심은 단 하나 — "모든 쌍을 비교하지 않는 것" 입니다. 블로킹으로 명확한 후보를, LSH 로 변형까지 포함한 후보를 추린 뒤, 그 소수에만 비싼 정밀 비교를 적용합니다. O(n²) 를 정면 돌파하려 들면 어떤 클러스터로도 못 풀지만, 후보를 영리하게 줄이면 수억 건도 현실적인 시간에 매칭할 수 있습니다.

이 글은 Spark 3.5 + MLlib 기준으로 작성되었습니다. 대규모 고객 마스터 통합·레코드 링크·중복 정리 파이프라인이 필요하시면 언제든 문의해 주세요.

— Data Dynamics 엔지니어링 팀