писать подзапрос при вставке в таблицу для принудительного задания id:
SELECT MAX(id) + 1 FROM some_table 1 FROM some_table
после удаления записи обновлять автоинкримент: ALTER TABLE some_table AUTO_INCREMENT = del_id
В обоих вариантах это надо делать в транзакции. Во втором варианте ещё следить, чтобы не было удалений из середины таблицы или выполнять запрос только при удалении последнего (а это тоже отдельный запрос в транзакции)
Возможно, дело в том, что phpmyadmin выполняя запросы добавляет в них LIMIT. Сколько всего строк в результате? INNER JOIN даёт произведение множеств и при отсутствии лимита msql вынужден проверять все комбинации, что много даже при наличии индексов.