1. Как советовали выше, добавляем колонку (у меня называется priority - дело вкуса).
2. Определяем ее, например, как decimal(6,3) - то есть число с тремя знаками после запятой.
3. Для новых объектов заполняем ее значением max(priority)+1 - вставка в конец.
4. Когда пользователь решает перетащить объект на другую позицию, получаем значения предыдущего и следующего элементов. Если нет предыдущего, считаем его за 0, если нет следующего - за предыдущий+1. Записываем для сортируемого объекта priority = (prev + next) / 2.
5. Если очень много раз таскать туда-сюда, можем получить ситуацию, когда соседние priority отличаются на 0.001 - обрабатываем этот случай в коде, пересчитывая приоритеты так, чтобы увеличить интервал. Или просто переиндексируем все целиком в фоне с какой-то разумной регулярностью.
Таким образом для сортировки нам нужно выбрать только два объекта одним запросом и изменить только одну строку.
Вместо дробных значений можно тупо добавлять новые с большим шагом - max(priority)+1000.