Ordem definida pelo usuário em SQL - Abordagem 1: Coluna de Posição Inteira

[Tiago Neves]

Alguns aplicativos, como listas de tarefas, precisam manter uma ordem de itens definida pelo usuário. O desafio é que a ordem é arbitrária e pode mudar quando o usuário reorganiza os itens:

Alguns aplicativos, como listas de tarefas, precisam manter uma ordem de itens definida pelo usuário. O desafio é que a ordem é arbitrária e pode mudar quando o usuário reorganiza os itens:

• Eficiência no espaço e no tempo. O armazenamento da ordem das linhas deve ser compacto no disco e a reordenação dos itens deve usar recursos mínimos de CPU e E/S.
• Robustez. Não deve haver limite prático para quantas vezes os itens podem ser pedidos novamente.
• Elegância. A solução não deve exigir funções PL/pgSQL complicadas ou análise de listas de números em strings.
   

Abordagem 1: Coluna de Posição Inteira

A primeira tentativa mais natural é adicionar uma coluna inteira com incremento automático para rastrear a posição de cada item:

create table todos (
  task text,
  pos serial, -- <== add this

  unique (pos)
);

Preencher a lista é fácil:
 

insert into todos (task)
    values ('experiment with sql'),
           ('write article'),
           ('relax'),
           ('repeat');

select * from todos order by pos asc;
/*
┌─────────────────────┬─────┐
│        task         │ pos │
├─────────────────────┼─────┤
│ experiment with sql │   1 │
│ write article       │   2 │
│ relax               │   3 │
│ repeat              │   4 │
└─────────────────────┴─────┘
*/

O que é mais difícil é inserir itens na lista ou reordenar os itens existentes. Suponha que queiramos inserir uma nova tarefa de “editar artigo” entre os itens 2 e 3. Isso requer mover os itens 3 e superiores uma posição à frente e inserir o item na posição 3. Mas mesmo a primeira etapa apresenta problemas:

-- shift items 3 and greater one position ahead

update todos set pos = pos+1 where pos >= 3;
/*
ERROR:  23505: duplicate key value violates unique constraint "todos_pos_key"
DETAIL:  Key (pos)=(4) already exists.
*/

A restrição de exclusividade torna a atualização sensível ao momento em que cada linha da tabela é processada. No nosso caso, tentou mover o item 3 para a posição 4 sem primeiro mover o item 4 para o 5.

Podemos permitir um comportamento mais flexível adiando a restrição de exclusividade dentro de uma transação.

create table todos (
  task text,
  pos serial,

  unique (pos)
    deferrable initially deferred
    -- ^^^ add this
);

-- now we can shift the list and insert an item
begin;

update todos set pos = pos+1 where pos >= 3;

insert into todos (pos, task) values
  (3, 'edit article');

-- don't forget to increment the sequence
select nextval('todos_pos_seq');

commit;

Como essa técnica se compara?

• Eficiente? Não. É necessário atualizar várias linhas para inserir uma entre outras.
• Robusto? Sim. Ele suporta a inserção/movimentação confiável de um item entre quaisquer outros. Além disso, mesmo no nível de isolamento “leitura confirmada” , a inserção simultânea de itens não resulta em inconsistências. (Pelo menos em meus testes.)
• Elegante? Não. A técnica requer uma sequência frágil de etapas, incluindo o adiamento de uma restrição e o ajuste de uma sequência.

Agora, em vez de usar números inteiros sequenciais, que tal deixar espaço entre eles? Assim como pular os números de linha na linguagem de programação BASIC, podemos pular os valores das posições na tabela e deixar espaço entre eles. Algo como:

create sequence todos_gapped_seq
  increment by 65536;

-- the todos table is declared same as before

Para inserir um item entre dois outros, basta utilizar a posição que é a média dos itens ao redor. No entanto, com a nossa escolha de 2 ^ 16 espaços em branco entre cada item, não podemos suportar mais do que dezesseis inserções consecutivas entre o primeiro e o próximo item. Depois de atingir este limite, teríamos revertido à abordagem anterior de avançar os itens.

Como isso se compara à abordagem de números inteiros sequenciais?

• Eficiente? Mais eficiente em média, mas ocasionalmente deve suportar o impacto da mudança.
• Robusto? Sim, tão eficaz quanto a abordagem anterior.
• Elegante? Não, é ainda pior do que a abordagem anterior devido à lógica mista.

No próximo post, aprofundaremos a discussão sobre o armazenamento de dados decimais, explorando técnicas de otimização e melhores práticas para diferentes casos de uso.