Думаю начать надо с выделения сущностей и нормализации. Исходя из запросов (хорошенько проексплейнив) следует расставить индексы. Если и этого не хватит — задуматься над денормализацией.

Свежий порт google-diff-match-patch на PHP.