Во-первых, попробуйте проанализировать характер рабочей нагрузки и ваши приоритеты.И станет понятнее, в каком направлении искать решение.
Например, если вы можете предположить, что обновления будут происходить гораздо реже, чем удаления и добавления, и у вас есть ограниченное время - внедрите просто простое удаление, вставьтезапускает и обрабатывает обновление как повторную вставку в обе таблицы.