Estructura de datos para almacenar un campo de clasificación para permitir modificaciones de manera eficiente

Question

Estoy usando Django y PostgreSQL, pero no estoy absolutamente vinculado al ORM de Django si hay una forma mejor de hacerlo con SQL puro o operaciones específicas de la base de datos.

Tengo un modelo que necesita un orden secuencial. Las operaciones de búsqueda generalmente recuperarán la lista completa en orden. La operación más común en estos datos es mover una fila a la parte inferior de la lista, con un subconjunto de los elementos que intervienen burbujeando para reemplazar el artículo anterior de esta manera:

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

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

Notice how D does not move. 

En general, el subconjunto de artículos no será más de aproximadamente 50 elementos, pero la lista base puede crecer a decenas de miles de entradas.

La forma más obvia de implementar esto es con un campo de orden entero simple. Esto parece poco óptimo. Requiere el compromiso de hacer que la columna de ordenamiento de posición no sea única, donde la no exclusividad solo se requiere para la duración de una operación de modificación. Para ver esto, imagina la operación mínima, con un subconjunto de B:

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

A pesar de que ha almacenado la posición, en la segunda línea que ha violado la restricción de unicidad. Además, este método hace que la atomicidad sea problemática: su operación de lectura tiene que ocurrir antes de la escritura, y durante ese tiempo sus registros podrían cambiar. La documentación de manejo de transacciones predeterminada de Django no soluciona esto, aunque sé que debería ser posible en el SQL usando el nivel de bloqueo de transacción "REPEATABLE READ".

Estoy buscando estructuras de datos alternativas que se ajusten más a este patrón de uso. He buscado this question para obtener ideas.

Una propuesta no es la solución estilo decimal Dewey, lo que hace que las operaciones de inserción se producen numéricamente entre los valores existentes, por lo que la inserción de una entre B y C resultados en:

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

Esto resuelve la columna singularidad problema, pero introduce el problema de que la columna debe ser un flotante de un número específico de decimales. O sobreestimo y almaceno más datos de los que necesito, o el sistema queda limitado por la longitud decimal arbitraria que impongo. Además, no espero que el uso sea uniforme en la base de datos: algunas claves se moverán con mucha más frecuencia que otras, lo que hará que esta solución llegue al límite antes. Podría resolver este problema periódicamente volviendo a numerar la base de datos, pero parece que una buena estructura de datos debería evitar necesitar esto.

Otra estructura que he considerado es la lista vinculada (y variantes). Esto tiene la ventaja de hacer que la modificación sea sencilla, pero no estoy seguro de sus propiedades con respecto a SQL: ordenar una lista de este tipo en la consulta SQL parece ser dolorosa, y extraer un subconjunto no secuencial de la lista es terrible. propiedades de recuperación.

Más allá de esto, hay B-Trees, varios árboles binarios, y así sucesivamente. ¿Qué recomiendas para esta estructura de datos? ¿Hay una estructura de datos estándar para esta solución en SQL? ¿La idea inicial de ir con enteros secuenciales realmente va a tener problemas de escalado, o estoy viendo problemas donde no los hay?

Answer 1

soluciones preferente:

Un linked list serían la forma habitual para lograrlo. Una consulta para devolver los elementos en orden es trivial in Oracle, pero no estoy seguro de cómo lo haría en PostreSQL.

Otra opción sería implementar esto usando el ltree module for postgresql.

Menos gracia (y escribir-pesado) solución: transacción Inicio. "seleccionar para la actualización" dentro del alcance de los bloqueos de nivel de fila. Mueva el registro de destino a la posición 0, actualice los registros de éxito futuros de los objetivos a +1 donde su posición sea más alta que la posición original de los objetivos (o viceversa) y luego actualice el destino a la nueva posición: una sola escritura adicional necesaria sin una restricción única.Comprometerse: D

(y aún así escribir-pesado) Una solución simple si puede esperar para PostgreSQL 8.5 (Alpha está disponible) :)

envolverlo en una transacción, seleccione Actualizar en su alcance, y el uso una restricción diferida (postgresql 8.5 has support for deferred unique constraints como Oracle).

Answer 2

Me parece que su problema real es la necesidad de bloquear una mesa durante la transacción. No veo de inmediato una buena manera de resolver este problema en una sola operación, de ahí la necesidad de bloqueo.

Por lo tanto, la pregunta es si puede hacer esto de una manera "Django" en lugar de usar SQL directo.Al buscar "tabla de bloqueo django" aparecieron algunos enlaces interesantes, incluido this snippet, hay muchos otros que implementan un comportamiento similar.

En este documento stack overflow post se puede encontrar una solución de estilo de lista enlazada SQL, me pareció lógico y sucinto, pero una vez más son dos operaciones.

Tengo mucha curiosidad por saber cómo resulta esto y cuál es su solución final, ¡asegúrese de mantenernos actualizados!

Answer 3

Puede resolver el problema de renumeración haciendo la columna de orden como un entero que siempre es un número par. Cuando se desplaza los datos, cambia el campo para el nuevo valor de ordenación + 1 y luego hacer una actualización rápida para convertir todos los campos de orden impar a par:

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

De este modo se puede mantener la singularidad de sort_order como una restricción

EDITAR: Bien, volviendo a ver la pregunta, comencé una nueva respuesta.

Answer 4

¿Por qué no hacer un campo de caracteres simples de alguna longitud como un máximo de 16 (o 255) inicialmente?

Comience inicialmente con el etiquetado de las cosas aaa a zzz (que deberían ser 17576 entradas). (También podría agregar 0-9, y las letras y símbolos en mayúsculas para una optimización.)

A medida que se agregan los elementos, pueden llegar al final hasta el máximo que permita los "tiempos de finalización" adicionales (zzza, zzzaa, zzzaaa, zzzaab, zzzaac, zzzaad, etc.)

Esto debería ser razonablemente simple de programar, y es muy similar al sistema Dewey Decimal.

Sí, tendrá que reequilibrarlo de vez en cuando, pero debería ser una operación simple. El enfoque más simple es dos pasos, el pase 1 sería establecer la nueva etiqueta de pedido en '0' (o cualquier carácter anterior al primer carácter) seguido de la nueva etiqueta de la longitud adecuada, y el paso 2 sería eliminar el ' 0 desde el frente.

Obviamente, podría hacer lo mismo con flotadores, y reequilibrarlo regularmente, esto es solo una variación de eso. La única ventaja es que la mayoría de las bases de datos le permitirán establecer un tamaño máximo ridículamente grande para el campo de caracteres, lo suficientemente grande para que sea muy, muy poco probable que se quede sin dígitos para hacer el pedido y también lo haga poco probable. que alguna vez tendrías que modificar el esquema, sin perder mucho espacio.

Answer 5

Una tabla temporal y una transacción deben mantener la atomicidad y la restricción única en el orden de clasificación. Reiterando el problema, quiere ir a partir de:

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

donde puede haber cualquier número de elementos en el medio de cada fila. Entonces, primero lea en los registros y cree una lista [['A',10],['B',25],['C',26],['E',34]]. A través de un poco de magia Pythonic usted cambia los identificadores alrededor e insertarlas en una tabla temporal:

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

Ahora la actualización:

pgsql

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

sólo estoy suponiendo que puede manejar esa consulta. Si puede, será atómico.

Opcionalmente, cree el REORDENADOR de tabla como una tabla permanente y la transacción asegurará que se serializarán los intentos de reordenar el mismo registro dos veces.

---

EDITAR: Hay algunos problemas de transacción. Es posible que necesites implementar mis dos ideas. Si dos procesos desean actualizar el elemento B (por ejemplo), puede haber problemas. Por lo tanto, asumir todos los valores del orden son aún:

1. iniciar la transacción
2. incrementa todas las órdenes siendo utilizado por 1. Esto pone bloqueos de escritura de nivel de fila en todas las filas que se van a actualizar.
3. Seleccione los datos que acaba de actualizar, si alguno de los campos sort_order es incluso algún otro proceso ha agregado un registro que coincida con sus criterios. Puede cancelar la transacción y reiniciar o simplemente puede soltar el registro y finalizar la operación usando solo los registros que se actualizaron en el paso 2. Lo "correcto" depende de lo que necesite este código para lograr.
4. Llene su tabla de reordenación temporal como se indicó anteriormente utilizando los ordenados ordenados correctos.
5. Actualice la tabla principal como se indica anteriormente.
6. Suelta la tabla temporal.
7. confirmar la transacción

Paso 2 asegura que si dos listas se superponen, sólo el primero de ellos tendrá acceso a la fila en cuestión hasta que la transacción se complete:

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 

Alternativamente, se puede agregue un campo de control a la tabla para obtener el mismo efecto y luego no necesita jugar con el campo sort_order. La ventaja de usar el campo sort_order es indizar por un campo BIT o un campo LOCK_BY_USERID cuando el campo es generalmente nulo tiende a tener un rendimiento deficiente ya que el índice el 99% del tiempo no tiene sentido. A los motores SQL no les gustan los índices que pasan la mayor parte del tiempo vacíos.