Структура данных для хранения поля сортировки для эффективного разрешения изменений

Question

Я использую Django и PostgreSQL, но я не совсем привязан к Django ORM, если есть лучший способ сделать это с необработанными операциями SQL или базой данных.

У меня есть модель, которая требует последовательного заказа. Операции поиска обычно извлекают весь список по порядку. Самая распространенная операция с этими данными - переместить строку в конец списка, с подмножеством промежуточных элементов, всплывающих вверх, чтобы заменить предыдущий элемент следующим образом:

(operation on A, with subset B, C, E)

A -> B
B -> C
C -> E
D -> D
E -> A

Notice how D does not move.

Как правило, подмножество элементов будет содержать не более 50 элементов, но базовый список может увеличиться до десятков тысяч записей.

Наиболее очевидный способ реализовать это с помощью простого целочисленного поля порядка. Это кажется неоптимальным. Это требует компромисса, заключающегося в том, чтобы сделать столбец упорядочения позиций неуникальным, тогда как неуникальность требуется только на время операции модификации. Чтобы увидеть это, представьте минимальную операцию с использованием A с подмножеством B:

oldpos = B.pos
B.pos = A.pos
A.pos = oldpos

Даже если вы сохранили позицию, во второй строке вы нарушили ограничение уникальности. Кроме того, этот метод делает атомарность проблематичной - ваша операция чтения должна выполняться до записи, в течение которой ваши записи могут измениться. Документация по обработке транзакций по умолчанию в Django не решает эту проблему, хотя я знаю, что это должно быть возможно в SQL с использованием уровня блокировки транзакций «REPEATABLE READ».

Я ищу альтернативные структуры данных, которые более соответствуют этому шаблону использования. Я посмотрел на этот вопрос для идей.

В одном предложении предлагается решение в стиле десятичной дроби Дьюи, в котором операции вставки выполняются численно между существующими значениями, поэтому вставка A между B и C приводит к:

A=1   ->   B=2
B=2   ->   A=2.5
C=3   ->   C=3

Это решает проблему уникальности столбца, но создает проблему, состоящую в том, что столбец должен быть числом с плавающей запятой указанного числа десятичных знаков. Либо я переоцениваю и сохраняю гораздо больше данных, чем мне нужно, или система становится ограниченной любой произвольной десятичной длиной, которую я навязываю. Более того, я не ожидаю, что использование будет даже над базой данных - некоторые ключи будут перемещаться гораздо чаще, чем другие, что делает это решение быстрее. Я мог бы решить эту проблему путем периодической нумерации базы данных, но, похоже, хорошей структуре данных следует избегать этого.

Другая структура, которую я рассмотрел, это связанный список (и варианты). Это имеет преимущество, заключающееся в упрощении модификации, но я не уверен в ее свойствах в отношении SQL - упорядочивание такого списка в запросе SQL кажется болезненным, а извлечение непоследовательного подмножества списка - ужасно поисковые свойства.

Помимо этого, есть B-деревья, различные двоичные деревья и так далее. Что вы рекомендуете для этой структуры данных? Существует ли стандартная структура данных для этого решения в SQL? У первоначальной идеи перехода с последовательными целыми числами действительно будут проблемы с масштабированием, или я вижу проблемы там, где их нет?

Answer 1

Предпочтительные решения:

A связанный список будет обычным способом добиться этого. Запрос на возврат элементов в порядке тривиален в Oracle , но я не уверен, как бы вы сделали это в PostreSQL.

Другой вариант - реализовать это с помощью модуля ltree для postgresql.

Менее изящное (и трудоемкое) решение: Начать транзакцию. «выбрать для обновления» в области видимости для блокировки уровня строки. Переместите целевую запись в положение 0, обновите будущие последующие записи цели до +1, где их позиция выше, чем исходная позиция цели (или наоборот), а затем обновите цель до новой позиции - единственная дополнительная запись, которая необходима без уникальное ограничение. Совершить: D

Простое (но все еще трудоемкое для записи) решение, если вы можете подождать Postgresql 8.5 (доступна альфа):)

Оберните его в транзакцию, выберите для обновления в области и используйте отложенное ограничение ( postgresql 8.5 поддерживает отложенные уникальные ограничения , как Oracle).

Answer 2

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

A  10   to  B  10
B  25       C  25
C  26       E  26
E  34       A  34

Где может быть любое количество предметов между каждой строкой. Итак, сначала вы читаете в записях и создаете список [['A',10],['B',25],['C',26],['E',34]]. С помощью некоторой питонической магии вы перемещаете идентификаторы и вставляете их во временную таблицу:

create temporary table reorder (
    id varchar(20), -- whatever
    sort_order number,
    primary key (id));

Теперь для обновления:

update table XYZ
set sort_order = (select sort_order from reorder where xyz.id = reorder.id)
where id in (select id from reorder)

Я только предполагаю, что pgsql может обработать этот запрос. Если это возможно, он будет атомным.

При необходимости создайте таблицу REORDER как постоянную таблицу, и транзакция обеспечит сериализацию попыток переупорядочить одну и ту же запись дважды.

---

РЕДАКТИРОВАТЬ: Есть некоторые проблемы с транзакциями. Возможно, вам придется реализовать обе мои идеи. Если два процесса хотят обновить элемент B (например), могут возникнуть проблемы. Итак, предположим, что все значения заказа четные:

1. Начать транзакцию
2. Увеличивает все используемые ордера на 1. Это устанавливает блокировки записи на уровне строк для всех строк, которые вы собираетесь обновить.
3. Выберите данные, которые вы только что обновили, если в каких-либо полях sort_order есть какой-то другой процесс, добавили запись, соответствующую вашим критериям. Вы можете либо прервать транзакцию и перезапустить ее, либо просто удалить запись и завершить операцию, используя только записи, которые были обновлены на шаге 2. «Правильные» действия зависят от того, для чего нужен этот код.
4. Заполните таблицу временного переупорядочения, как указано выше, используя правильные четные сортировки.
5. Обновите основную таблицу, как указано выше.
6. Удалите временную таблицу.
7. Совершить транзакцию

Шаг 2 гарантирует, что если два списка перекрываются, только первый будет иметь доступ к строке до завершения транзакции:

update XYZ set sort_order = sort_order + 1
where -- whatever your select criteria are

select * from XYZ
where -- same select criteria
order by sort_order

Кроме того, вы можете добавить поле управления к столу, чтобы получить тот же эффект, и тогда вам не нужно играть с полем sort_order. Преимущество использования поля sort_order заключается в индексации с помощью поля BIT или поля LOCK_BY_USERID, когда поле обычно имеет значение null, как правило, имеет низкую производительность, поскольку индекс 99% времени не имеет смысла. Механизмам SQL не нравятся индексы, которые проводят большую часть своего времени пустыми.

Answer 3

Вы можете решить проблему перенумерации, указав в столбце заказа целое число, которое всегда является четным числом. При перемещении данных вы изменяете поле заказа на новое значение сортировки + 1, а затем выполняете быстрое обновление, чтобы преобразовать все поля нечетного порядка в четные:

update table set sort_order = bitand(sort_order, '0xFFFFFFFE')
where sort_order <> bitand(sort_order, '0xFFFFFFFE')

Таким образом, вы можете сохранить уникальность sort_order в качестве ограничения

РЕДАКТИРОВАТЬ: Хорошо, снова глядя на вопрос, я начал новый ответ.

Answer 4

Почему бы не создать простое поле символов некоторой длины, например, максимум 16 (или 255).

Начните с маркировки вещей от aaa до zzz (это должно быть 17576 записей). (Вы также можете добавить 0-9, а также заглавные буквы и символы для оптимизации.)

Когда элементы добавляются, они могут доходить до конца, до тех пор, пока вы не дадите максимальное время окончания (zzza, zzzaa, zzzaaa, zzzaab, zzzaac, zzzaad и т. Д.)

Это должно быть достаточно просто для программирования, и оно очень похоже на десятичную систему Дьюи.

Да, вам нужно будет периодически перебалансировать его, но это должна быть простая операция. Самый простой подход - два прохода, проход 1 будет состоять в том, чтобы установить новый тег упорядочения на «0» (или любой символ, предшествующий первому символу), за которым следует новый тег соответствующей длины, а на шаге 2 будет удалено « 0 спереди.

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

Answer 5

Мне кажется, что вашей настоящей проблемой является необходимость блокировки таблицы на время транзакции. Я не сразу вижу хороший способ решить эту проблему за одну операцию, отсюда и необходимость блокировки.

Таким образом, вопрос заключается в том, можете ли вы сделать это «способом Джанго», а не использовать прямой SQL. Поиск по «таблице блокировки django» обнаружил несколько интересных ссылок, в том числе этот фрагмент , и многие другие, которые реализуют подобное поведение.

Простое решение в стиле связанного списка SQL можно найти в этом сообщении о переполнении стека , оно показалось мне логичным и лаконичным, но опять же это две операции.

Мне очень любопытно услышать, как это получается и каково ваше окончательное решение, будьте уверены, что мы будем в курсе!