SQLを見直す以外にも、一時的にインデックスをはずすとかそういうのでもずいぶん変わったりするもんだけど
規模がどれほどのものか分からないけどそんなに時間がかかるのはなんか不思議に思うよ