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

전국의 편의점 목록을 두 DB 에서 받아 통합해야 한다고 상상해 보세요. "GS25 강남점"과 "GS 25 강남점"은 같은 곳이지만, 일반 조인으로는 절대 매칭되지 않습니다. "같은 사람인데 이름이 조금씩 다른" 레코드를 합치는 일 — 고객 마스터 통합, 중복 거래처 정리, 부정거래 탐지 — 은 데이터 엔지니어링의 단골 난제입니다. 정확히 일치하면 조인하면 그만이지만, "김철수" 와 "김 철수", "Seoul" 과 "서울특별시" 처럼 유사하지만 다른 값을 매칭해야 합니다.

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

이 글에서 배우는 것

• 퍼지 매칭이 왜 O(n²) 문제인지, cross join 이 왜 불가능한지
• 블로킹(Blocking)으로 비교 후보를 극적으로 줄이는 원리와 구현
• MinHash LSH 로 오타·표기 변형까지 잡는 근사 유사 조인 구현
• 후보 쌍에만 비싼 Levenshtein 등 정밀 스코어링을 적용하는 3단 파이프라인
• 정밀도(precision)와 재현율(recall) 의 트레이드오프를 튜닝하는 법

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 로 후보를 충분히 줄였다면, 이제 그 소수의 쌍에만 비싼 정밀 유사도를 계산합니다. 쌍이 적으니 Levenshtein 같은 연산도 부담 없습니다.

# 여러 필드의 가중 유사도 (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. 전체 파이프라인

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

6. 정밀도 vs 재현율 튜닝

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

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

7. 흔한 함정

8. 정리

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

마치며 — 핵심 요약

• 수억 건의 퍼지 매칭은 cross join 이 아니라 "후보를 얼마나 영리하게 줄이느냐" 의 싸움입니다.
• 블로킹은 "같은 키끼리만 비교"해 비교 쌍을 급격히 줄이는 1차 필터입니다. 여러 블로킹 키를 union 해 재현율을 높이세요.
• MinHash LSH 는 오타·표기 변형까지 잡는 2차 필터입니다. numHashTables 와 threshold 로 재현율-비용을 조절하세요.
• 정규화(소문자·공백·특수문자 제거)를 충분히 해야 블로킹과 LSH 가 제대로 작동합니다.
• 후보 쌍이 충분히 줄어든 뒤에야 Levenshtein 같은 비싼 정밀 스코어링을 씁니다.
• 마지막 군집화(A=B, B=C → A=C)는 GraphFrames Connected Components 로 해결합니다 — 다음 글을 참고하세요.

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

— Data Dynamics 엔지니어링 팀