Ordenar arbitrariamente registros en una tabla

Una necesidad común cuando se usa una base de datos es acceder a los registros en orden. Por ejemplo, si tengo un blog, quiero poder reordenar mis publicaciones en un orden arbitrario. Estas entradas a menudo tienen muchas relaciones, por lo que una base de datos relacional parece tener sentido.

La solución común que he visto es agregar una columna entera order:

CREATE TABLE AS your_table (id, title, sort_order)
AS VALUES
  (0, 'Lorem ipsum',   3),
  (1, 'Dolor sit',     2),
  (2, 'Amet, consect', 0),
  (3, 'Elit fusce',    1);

Luego, podemos ordenar las filas orderpara obtenerlas en el orden correcto.

Sin embargo, esto parece torpe:

• Si quiero mover el registro 0 al inicio, tengo que reordenar cada registro
• Si quiero insertar un nuevo registro en el medio, tengo que reordenar cada registro después
• Si quiero eliminar un registro, tengo que reordenar cada registro después de él

Es fácil imaginar situaciones como:

• Dos registros tienen lo mismo order
• Hay lagunas en los orderregistros entre

Esto podría suceder con bastante facilidad por varias razones.

Este es el enfoque que adoptan aplicaciones como Joomla:

Se podría argumentar que la interfaz aquí es mala, y que en lugar de que los humanos editen números directamente, deberían usar flechas o arrastrar y soltar, y probablemente tenga razón. Pero detrás de escena, está sucediendo lo mismo.

Algunas personas han propuesto usar un decimal para almacenar el orden, de modo que pueda usar "2.5" para insertar un registro entre los registros en el orden 2 y 3. Y aunque eso ayuda un poco, podría decirse que es aún más complicado porque puede terminar con decimales extraños (¿dónde se detiene? 2.75? 2.875? 2.8125?)

¿Hay una mejor manera de almacenar el pedido en una mesa?

Si quiero mover el registro 0 al inicio, tengo que reordenar cada registro

No, hay una manera más simple.

update your_table
set order = -1 
where id = 0;

Si quiero insertar un nuevo registro en el medio, tengo que reordenar cada registro después

Eso es cierto, a menos que use un tipo de datos que admita valores "entre". Los tipos flotante y numérico le permiten actualizar un valor a, digamos, 2.5. Pero varchar (n) también funciona. (Piense 'a', 'b', 'c'; luego piense 'ba', 'bb', 'bc'.)

Si quiero eliminar un registro, tengo que reordenar cada registro después de él

No, hay una manera más simple. Solo borra la fila. Las filas restantes aún se ordenarán correctamente.

Es fácil imaginar situaciones como:

Dos registros tienen el mismo orden.

Una restricción única puede evitar eso.

Hay espacios en el orden entre registros

Las brechas no tienen efecto sobre cómo un dbms ordena los valores en una columna.

Algunas personas han propuesto usar un decimal para almacenar el orden, de modo que pueda usar "2.5" para insertar un registro entre los registros en el orden 2 y 3. Y aunque eso ayuda un poco, podría decirse que es aún más complicado porque puede terminar con decimales extraños (¿dónde se detiene? 2.75? 2.875? 2.8125?)

No te detienes hasta que tienes que hacerlo. El dbms no tiene problemas para ordenar valores que tienen 2, 7 o 15 lugares después del punto decimal.

Creo que su verdadero problema es que le gustaría ver los valores en orden ordenado como enteros. Usted puede hacer eso.

create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);

insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will "transform" the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table

Es muy simple. Debe tener una estructura de "agujero de cardinalidad":

Necesitas tener 2 columnas:

1. pk = 32bit integer
2. orden = 64 bits bigint( no double )

Insertar / actualizar

1. Al insertar el primer registro nuevo, establezca order = round(max_bigint / 2).
2. Al insertar al principio de la tabla, establezca order = round("order of first record" / 2)
3. Al insertar al final de la tabla, configure order = round("max_bigint - order of last record" / 2) 4) Al insertar en el medio, configureorder = round("order of record before - order of record after" / 2)

Este método tiene una cardinalidad muy grande. Si tiene un error de restricción o si cree que tiene una pequeña cardinalidad, puede reconstruir la columna de orden (normalizar).

En una situación máxima con normalización (con esta estructura) puede tener un "agujero de cardinalidad" en 32 bits.

Recuerde no utilizar tipos de punto flotante: ¡el orden debe ser un valor preciso!

En general, el pedido se realiza de acuerdo con cierta información en los registros, el título, la identificación o lo que sea apropiado para esa situación en particular.

Si necesita un pedido especial, usar una columna entera no es tan malo como parece. Por ejemplo, para dejar espacio para que un registro ingrese al 5to lugar, podría hacer algo como:

update table_1 set place = place + 1 where place > 5.

Con suerte, puede declarar que la columna es uniquey tal vez tener un procedimiento para hacer reordenamientos "atómicos". Los detalles dependen del sistema, pero esa es la idea general.

... podría decirse que es aún más desordenado porque puede terminar con decimales extraños (¿dónde se detiene? 2.75? 2.875? 2.8125?)

¿A quien le importa? Estos números solo están ahí para que la computadora los maneje, por lo que no importa cuántos dígitos fraccionales tengan o cuán feos nos parezcan.

El uso de valores decimales significa que para mover el elemento F entre los elementos J y K, todo lo que necesita hacer es seleccionar los valores de orden para J y K, luego promediarlos y luego actualizar F. Dos declaraciones SELECT y una declaración UPDATE (probablemente hechas usando aislamiento serializable para evitar puntos muertos).

Si desea ver enteros en lugar de fracciones en la salida, calcule enteros en la aplicación cliente o use las funciones ROW_NUMBER () o RANK () (si su RDBMS los incluye).

En mi propio proyecto, planeo probar una solución similar a la solución de números decimales, pero en su lugar utilizo matrices de bytes:

def pad(x, x_len, length):
    if x_len >= length:
        return x
    else:
        for _ in range(length - x_len):
            x += b"\x00"
        return x

def order_index(_from, _to, count, length=None):
    assert _from != _to
    assert _from < _to

    if not length:
        from_len = len(_from)
        to_len = len(_to)
        length = max(from_len, to_len)

        _from = pad(_from, from_len, length)
        _to = pad(_to, to_len, length)

    from_int = int.from_bytes(_from, "big")
    to_int = int.from_bytes(_to, "big")
    inc = (to_int - from_int)//(count + 1)
    if not inc:
        length += 1
        _from += b"\x00"
        _to += b"\x00"
        return order_index(_from, _to, count, length)

    return (int.to_bytes(from_int + ((x+1)*inc), length, "big") for x in range(count))

>>> index = order_index(b"A", b"Z", 24)
>>> [x for x in index]
[b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y']
>>> 
>>> index = order_index(b"A", b"Z", 25)
>>> [x for x in index]
[b'A\xf6', b'B\xec', b'C\xe2', b'D\xd8', b'E\xce', b'F\xc4', b'G\xba', b'H\xb0', b'I\xa6', b'J\x9c', b'K\x92', b'L\x88', b'M~', b'Nt', b'Oj', b'P`', b'QV', b'RL', b'SB', b'T8', b'U.', b'V$', b'W\x1a', b'X\x10', b'Y\x06']

La idea es que nunca puede quedarse sin posibles valores intermedios porque y simplemente agrega un b"\x00"a los registros involucrados si necesita más valores. ( intno está limitado en Python 3, de lo contrario, tendría que elegir una porción de los bytes al final para comparar, suponiendo que, entre dos valores adyacentes, las diferencias se agruparían hacia el final).

Por ejemplo, digamos que tiene dos registros, b"\x00"y b"\x01"desea un registro entre ellos. No hay valores disponibles entre 0x00y 0x01, por lo que agrega b"\x00"a ambos, y ahora tiene un montón de valores entre ellos que puede usar para insertar nuevos valores.

>>> records = [b"\x00", b"\x01", b"\x02"]
>>> values = [x for x in order_index(records[0], records[1], 3)]
>>> records = records + values
>>> records.sort()
>>> records
[b'\x00', b'\x00@', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

La base de datos puede ordenarlo fácilmente porque todo termina en orden lexicográfico. Si elimina un registro, todavía está en orden. Sin embargo, en mi proyecto, hice b"\x00"y b"\xff"como FIRSTy LASTregistros, para usarlos como valores virtuales "de" y "a" para anteponer / agregar nuevos registros:

>>> records = []
>>> value = next(order_index(FIRST, LAST, 1))
>>> value
b'\x7f'
>>> records.append(value)
>>> value = next(order_index(records[0], LAST, 1))
>>> value
b'\xbf'
>>> records.append(value)
>>> records.sort()
>>> records
[b'\x7f', b'\xbf']
>>> value = next(order_index(FIRST, records[0], 1))
>>> value
b'?'
>>> records.append(value)
>>> records.sort()
>>> records
[b'?', b'\x7f', b'\xbf']

Encontré esta respuesta mucho mejor. Citando completamente:

Las bases de datos están optimizadas para ciertas cosas. Actualizar muchas filas rápidamente es una de ellas. Esto se vuelve especialmente cierto cuando dejas que la base de datos haga su trabajo.

Considerar:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

Y si desea avanzar Beat Ithasta el final, tendría dos consultas:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

Y eso es. Esto aumenta muy bien con números muy grandes. Intente poner unos pocos miles de canciones en una hipotética lista de reproducción en su base de datos y vea cuánto tiempo lleva mover una canción de un lugar a otro. Como estos tienen formas muy estandarizadas:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Tiene dos declaraciones preparadas que puede reutilizar de manera muy eficiente.

Esto proporciona algunas ventajas significativas: el orden de la tabla es algo sobre lo que puede razonar. La tercera canción tiene un orderde 3, siempre. La única forma de garantizar esto es usar enteros consecutivos como orden. El uso de listas seudoenlazadas o números decimales o enteros con espacios no le permitirá garantizar esta propiedad; en estos casos, la única forma de obtener la enésima canción es ordenar toda la tabla y obtener el enésimo registro.

Y realmente, esto es mucho más fácil de lo que piensas. Es simple descubrir lo que quiere hacer, generar las dos declaraciones de actualización y que otras personas vean esas dos declaraciones de actualización y se den cuenta de lo que se está haciendo.