SQL 中的用户定义顺序

最近在做需求的时候，遇到这么一个场景，维护报表的菜单列表，需要支持用户定义的项目顺序。其中挑战在于顺序是任意的，并且用户可以重新进行排列。

上面的问题看起似乎很简单，给每个报表一个int类型的sort字段编号即可，但如果在这个过程中，思考空间和时间效率，稳健性等呢？

空间和时间效率。存储行顺序应在磁盘上紧凑，并且重新排序项目应使用最少的 CPU 和 I/O 资源。
稳健性。对于重新排列的次数应该没有实际限制。
优雅。解决方案不需要复杂的 PL/pgSQL 函数或解析字符串中的数字列表。

下面给出在解决这个需求的过程中的一些思考方案。

方法 1：整数位置列

如上面所讲，很容易想到的尝试是添加一个自动递增的整数列来跟踪每个报表的位置：

sql

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

  unique (pos)
);

这种方案就和数组类似，很容易在末尾写入和查询，但是对于中间的写入和重新排列报表顺序。假设我们想在第 2 项和第 3 项之间插入一个新的“YYY”报表。这需要将第 3 项及以后的报表向后移动一个位置，并将当前报表插入到位置 3。但即使是第一步也会遇到问题：

sql

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

唯一性约束使更新对每个表行的处理时间敏感。在我们的例子中，它尝试将报表 3 移动到位置 4，而不先将报表 4 移动到位置 5。

我们可以通过推迟事务内部的唯一性约束来实现更灵活的行为。

sql

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;

现在已经可以实现我们的需求了，但是考虑我们最开始提出的问题？

高效吗？不高效。它需要更新一堆行才能在其他行之间插入一行。
稳健吗？是的。它支持在任何其他项之间可靠地插入/移动项。此外，即使在“读取已提交”隔离级别，并发项插入也不会导致不一致。
优雅吗？不优雅。该技术需要一系列精细的步骤，包括推迟约束和调整序列。

那留出空间呢？

与其使用连续整数，不如在它们之间留出空格？就像在 BASIC 编程语言中跳过行号一样，我们可以跳过表中的位置值并在它们之间留出空间，即用空间换取时间，例如：

sql

create sequence todos_gapped_seq
  increment by 65536;

-- the todos table is declared same as before

要在两个报表之间插入一个报表，只需使用周围项目的平均位置即可。但是，由于我们选择在每个报表之间留出 2^16 个空格，因此我们最多只能支持在第一个报表和下一个报表之间连续插入 16 个报表。达到此限制后，我们将恢复到以前将报表向前移动的方法。

这与顺序整数方法相比如何？

效率高吗？平均而言效率较高，但有时必须承受换挡的压力。
稳健吗？是的，与之前的方法一样有效。
优雅吗？不，由于逻辑混乱，它甚至比之前的方法更糟糕。

方法 2：小数位置

前面用的整数位下标来标记报表的顺序位置，同时进一步在整数位之间插空来避免调整带来的顺序移动，但显然都有着各自的问题。因此，现在我们再仔细想想，貌似float浮点数是一个不错的选择。这将允许将新元素挤在其他元素之间，而不是将报表移动以腾出空间。

sql

create sequence todos_seq;

create table todos (
  task text,
  pos float not null
    default nextval('todos_seq'),

  unique (pos)
);

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

现在在第 2 行和第 3 行之间插入一个报表很容易：

sql

insert into todos (pos, task) values
  ((2.0+3)/2, 'edit article');

这似乎是一个完美的解决方案！但是浮点数的精度有限。例如，如果我们反复插入 1000 到 1001 之间的数字，每次都减半，那么到第 38 次迭代时，它将截断为 1000：

sql

┌────┬──────────────────┐
│ i  │       val        │
├────┼──────────────────┤
│ 25 │  1000.0000000298 │
│ 26 │  1000.0000000149 │
│ 27 │ 1000.00000000745 │
│ 28 │ 1000.00000000373 │
│ 29 │ 1000.00000000186 │
│ 30 │ 1000.00000000093 │
│ 31 │ 1000.00000000047 │
│ 32 │ 1000.00000000023 │
│ 33 │ 1000.00000000012 │
│ 34 │ 1000.00000000006 │
│ 35 │ 1000.00000000003 │
│ 36 │ 1000.00000000001 │
│ 37 │ 1000.00000000001 │
│ 38 │             1000 │
│ 39 │             1000 │
│ 40 │             1000 │
└────┴──────────────────┘

高效吗？是的。一个简单的 64 位列和一些算法就可以非常快速地将新元素插入列表。
强大吗？它看上去有效，但最终失败了。
优雅吗？是的。找到中点很容易。

任意精度

既然精度导致了后续的问题，那我们就解决精度问题。使用sql中的decimal类型。它有一个可变的大小，可以根据需要增长以存储精确的数字。它会变得多大？让我们问数据库：

sql

select
  (1 / power(2, i))::numeric as val,
  pg_column_size(1 / power(2, i)::numeric) as sz
from generate_series(1, 21) as i;

/*
┌─────────────────────────┬────┐
│           val           │ sz │
├─────────────────────────┼────┤
│                     0.5 │  8 │
│                    0.25 │  8 │
│                   0.125 │  8 │
│                  0.0625 │  8 │
│                 0.03125 │ 10 │
│                0.015625 │ 10 │
│               0.0078125 │ 10 │
│              0.00390625 │ 10 │
│             0.001953125 │ 12 │
│            0.0009765625 │ 12 │
│           0.00048828125 │ 12 │
│          0.000244140625 │ 12 │
│         0.0001220703125 │ 14 │
│        0.00006103515625 │ 12 │
│       0.000030517578125 │ 12 │
│      0.0000152587890625 │ 12 │
│     0.00000762939453125 │ 14 │
│    0.000003814697265625 │ 14 │
│   0.0000019073486328125 │ 14 │
│  0.00000095367431640625 │ 14 │
│ 0.000000476837158203125 │ 16 │
└─────────────────────────┴────┘
*/

它很快就达到 12 个字节，而实际上像这样在 0 和 1 之间切割是最好的情况。随着整数部分的增长，numeric需要更多的字节。但是，除了磁盘使用量之外，这是迄今为止最好的方法。

高效吗？是的，大部分情况下如此。如果列表重新排列不多，类型超过 128 位的情况并不常见，并且对列的大多数操作都是索引比较，而不是算术。
numeric稳健吗？是的。随着列表不断重新排列，这些值可能会在很长一段时间内继续占用更多空间，但出于所有实际目的，您可以永远重新排列列表。
优雅？是的，就像float。

方法 3：真分数

前面不管是整数还是浮点数还是内置的decimal类型的数来作为报表的sort依据其实思路都是一样的，需要两个报表之间存在可填充的空，以至于重排序或者新插入新的报表的时候存在足够的空间，但在最终的实现的时候，都因为各种限制，导致情况并不理想，很快就会消耗殆尽中间的空（往糟糕的情况想）。

因此我们可不可以尽可能的进行切割两个数的找到中间态呢？没错，整数、浮点数、decimal这些都不行，那我们组合一下呢？是的，分数，分数完全符合我们的需求，如下图所示，非负分数实际上形成一个二叉树，每个分数（最低项）都出现在一个唯一的节点上。通过类似下面图所示的拆分和组合，我们可以实现我们的需求。

高效吗？是的。每个有理数使用 64 位。
健壮吗？是的。通过反复重新排序列表，几乎永远都用不完空间。
优雅吗？是的。

小结

上面简单探讨了一个很常见的排序问题，简单点你可以将其看做一个数组写入和排序问题，不同的是我们加了一点点条件，SQL中，不使用外在的语言来协调。这确实也是我们项目中的一个实际场景，因为报表的开发和业务代码等是分离的，无关的。只需要上传报表到Tomcat服务器，然后在对应表中新增报表的位置即可，报表数量少还可以手动操作移动，但当报表数量成百上千，再手动去移动显然不科学。因此总结了上面的方法。帮助不移动且高效插入排序。当然，退一步，如果不局限于SQL，其实可以通过链表等数据结构来迎合当前的业务场景肯定更合适。毕竟相对于中间写入，链表更合适。

SQL 中的用户定义顺序 ​

方法 1：整数位置列 ​

那留出空间呢？ ​

方法 2：小数位置 ​

任意精度 ​

方法 3：真分数 ​

小结 ​