Recently, I had to solve that same problem in PostgreSQL. I use a multicolumn index with the soundex of first name, soundex of last name, and birthdate. This yi

Recently, I had to solve that same problem in PostgreSQL. I use a multicolumn index with the soundex of first name, soundex of last name, and birthdate. This yields a set of preliminary candidates to match. On a second step, we prune according to a hand-crafted distance measure, which relies on levenshtein and a bunch of simple calculations on the whole record. Finally, we order the candidates by distance and take as match that record with minimal distance under a threshold.