제가 했던 경험으로는 이렇습니다..
신주소로 변경하면서 엄청 큰 작업과 엄청 큰 데이터를 사용하게 됩니다.
물론 정말 세세하게 완벽한 서치를 하게 만드시려면 정말 소규모의 프로젝트 단위까지 될 수 있습니다.

데이터 양이 너무 많다보니 속도도 안나오는 경우가 많은데요,
여러 가지 방법이 있습니다.

1) 일반적인 방법으로는 우정사업부에서 제공하는 매핑테이블을 이용하는 방법  (예시)
-----------------------------
|          |             |
구    매핑         신

2) 한 테이블에 이용하는 방법 (예시)
구(지역주소) 신(지역주소)구(동주소) 신(동주소)

속도 내는 방법에서는 전 우선 제일 많이 사용하는 컬럼에 인덱스를 걸어주구요,
세세하게 ui단에서 짜를 수 있으면 뎁스 별로 짤라서 검색해주면 평상시보다 훨씬 많은 속도를 내게 됩니다.

저도 처음엔 10초 이상의 쿼리였는데, 1초 대까지 줄일수 있었습니다.