Problema da Ordem Definida Pelo Usuário

Introdução

Você já se deparou com o seguinte problema?

Você tem uma lista de conteúdos, e o usuário pode alterar a ordem dessa lista à vontade. Além disso, essa ordem precisa ser mantida para o usuário na próxima vez que ele acessar a lista.

Esse problema, que à primeira vista parece simples, esconde uma complexidade considerável. O desafio principal é como realizar essas mudanças de forma eficiente, minimizando o número de alterações no banco de dados.

Neste post quero explorar algumas soluções para esse problema usando SQL e PostgreSQL.

Modelagens

Simples

Uma abordagem inicial seria modelar a lista usando uma coluna inteira chamada position, que determina a posição de cada item na lista.

CREATE TABLE card (
  id SERIAL PRIMARY KEY,
  content TEXT NOT NULL,
  position INTEGER UNIQUE NOT NULL
);

A inserção de elementos nessa estrutura é bastante simples:

INSERT INTO card (content)
    VALUES ('content1'),
           ('content2'),
           ('content3'),
           ('content4');

SELECT * FROM card ORDER BY position ASC;

Isso nos dá uma lista ordenada pelos valores de position.

No entanto, a dificuldade surge quando o usuário decide reordenar os itens. Suponha que o usuário deseje mover o item com position = 3 para a primeira posição. Com essa modelagem, você precisaria:

1. Atualizar o item movido para position = 1
2. Incrementar a posição de todos os outros itens que foram deslocados.

UPDATE card
SET position = position + 1
WHERE position >= 1 AND position < 3;

UPDATE card
SET position = 1
WHERE content = 'content3';

Esse processo envolve múltiplas operações de atualização, o que pode ser ineficiente, especialmente em listas longas.

Posição Decimal

Agora, e se trocássemos o INTEGER por FLOAT para trabalhar com valores decimais? Isso permitiria inserir novos elementos na lista calculando a média entre duas posições (position = (i+j)/2), facilitando a reordenação sem precisar atualizar todas as posições subsequentes.

CREATE TABLE card (
  id SERIAL PRIMARY KEY,
  content TEXT NOT NULL,
  position FLOAT UNIQUE NOT NULL
);

INSERT INTO card (content, position)
    VALUES ('content1', 1.0),
           ('content2', 2.0),
           ('content3', 3.0),
           ('content4', 4.0);

Se for necessário mover o conteúdo 3 para a primeira posição, basta aplicar a média:

UPDATE card
SET position = (0 + 1.0)/2
WHERE content = 'content3';

A princípio, essa parece uma solução eficiente. No entanto, números de ponto flutuante têm uma precisão limitada, o que pode gerar problemas com mudanças sucessivas ao longo do tempo, causando erros de arredondamento e perda de precisão.

Frações Verdadeiras

Tanto a solução usando INTEGER quanto FLOAT têm limitações significativas, especialmente no manejo de posições médias e atualizações consecutivas. Uma abordagem alternativa e mais robusta seria o uso de frações verdadeiras.

Embora o PostgreSQL não ofereça suporte nativo para frações, a extensão pg_rational, criada por begriffs, permite trabalhar com números racionais. Esta extensão converte valores decimais em frações verdadeiras, evitando problemas de precisão. O código pode ser encontrado no GitHub.

A ideia é que as frações não negativas podem ser representadas como uma árvore binária, especificamente a Árvore de Stern–Brocot. Esta árvore permite encontrar frações dentro de limites definidos até atingir o nó desejado, proporcionando uma forma eficiente de reordenar elementos.

Esse método foi um dos melhores que encontrei para manipular a ordem dos itens em listas, mas por não ser uma funcionalidade padrão do PostgreSQL, pode limitar seu uso. No entanto, para quem busca uma solução avançada, vale a pena explorar. Recomendo a leitura da publicação do autor sobre esse método: User-defined Order in SQL.

Árvore Binária

Por fim, uma solução interessante que utiliza uma variação da Árvore de Stern–Brocot, mas implementada de forma nativa no PostgreSQL, é o uso de uma árvore binária de bits. Esta abordagem se baseia em representar posições na lista como sequências binárias, permitindo a inserção de novos elementos entre dois valores adjacentes sem precisar reajustar todas as posições subsequentes.

A estrutura da árvore binária pode ser visualizada da seguinte forma:

                      _____ 1 ____
                ______/            \______
          _ 01 _                          11
        _/      \_                    _/      \_
    001            011            101            111
    /   \          /   \          /   \          /   \
0001   0011    0101   0111    1001   1011    1101    1111

No PostgreSQL, isso pode ser feito utilizando o tipo VARBIT, que permite a representação e manipulação de cadeias binárias variáveis. A ideia é gerar um novo VARBIT entre dois valores adjacentes para criar a nova posição.

CREATE TABLE card (
  id SERIAL PRIMARY KEY,
  content TEXT NOT NULL,
  position VARBIT UNIQUE
);

A função adj é responsável por criar uma nova posição ao ajustar a sequência de bits:

CREATE FUNCTION adj(orig VARBIT, b VARBIT) RETURNS VARBIT LANGUAGE SQL AS $$
  SELECT substring(orig FOR LENGTH(orig)-1)
       ||b
       ||substring(orig FROM LENGTH(orig));
$$;

Já a função f define a lógica para determinar a nova posição entre dois valores adjacentes, considerando os casos em que um dos valores é NULL ou quando as sequências binárias têm comprimentos diferentes:

CREATE FUNCTION f(l VARBIT, h VARBIT) RETURNS VARBIT LANGUAGE plpgsql as $$

BEGIN
  IF l IS NULL AND h IS NULL THEN RETURN B'1'; END IF;
  IF l IS NULL THEN RETURN adj(h,B'0'); END IF;
  IF h IS NULL THEN RETURN adj(l,B'1'); END IF;
  IF LENGTH(l)>LENGTH(h) THEN RETURN adj(l,B'1'); END IF;
  RETURN adj(h,B'0');
END;
$$;

Com isso, dado o meu exemplo anterior.

INSERT INTO card (content, position)
    VALUES ('content1', B'001'),
           ('content2', B'011'),
           ('content3', B'101'),
           ('content4', B'111');

SELECT * FROM card ORDER BY POSITION;

Agora, se eu quero colocar o 3 na primeira posição, basta fazer a troca:

UPDATE card
SET position = f(null, B'001') -- entre null e 1
WHERE content = 'content3';

update card
set position = f(B'101', B'111') --  entre 3 e 4
where content = 'content1';

SELECT * FROM card ORDER BY POSITION;

O pior cenário dessa abordagem ocorre quando a lista é inicialmente carregada com muitas linhas já ordenadas. Isso pode levar a um problema de espaço, já que cada nova inserção exigirá um bit adicional na coluna position para acomodar a posição do novo item. Com o tempo, à medida que a lista cresce e mais posições intermediárias são inseridas, a position pode se tornar significativamente longa, consumindo mais espaço de armazenamento e potencialmente impactando o desempenho.

Conclusão

Neste post, exploramos várias abordagens interessantes para a ordenação de listas definida pelo usuário no banco de dados, começando por soluções simples e avançando para métodos mais sofisticados encontrados na literatura e na prática.

Sinseramente, a escolha da abordagem mais adequada depende das necessidades específicas do seu projeto. No entanto, espero que essa discussão tenha ajudado a esclarecer as diferentes opções disponíveis e como elas podem ser aplicadas para resolver problemas desse tipo de ordenação de forma eficiente.

Referências

• User-defined Order in SQL
• User-Defined ORDERing in SQL