User-defined Order in SQL
Joe Nelson (via Hacker News):
The most natural first attempt is to add an auto-incrementing integer column to track each item’s position[…] It requires updating a bunch of rows to insert one between others.
[…]
What if we store the position of each row using
floatornumericvalues rather thanintorbigint? This would allow squeezing new elements between others, rather than shifting items forward to make room. […] However floating point numbers have limited precision.[…]
Non-negative fractions actually form a binary tree, with every fraction (in lowest terms) appearing at a unique node. […] The terms of these fractions are expressed in lowest terms and grow slowly at each insertion. For instance you can see from the tree diagram earlier that inserting between 1 and 0 toward 0 generates 1/2, 1/3, 1/4 … which can go a very long time because numerators and denominators in pg_rational each get 32 bits of storage.
Other approaches:
- Using a string column lets you always add rows in between other rows without ever having to renumber the world because the strings can be arbitrarily long.
- A linked list is efficient for updating the rows but doesn’t work well with partial fetching.
Ordered relationships in Core Data seem to use the basic integer approach. I’ve not used this feature much because it’s always seemed risky to rely on it. For many years it was buggy, NSOrderedSet still isn’t available in Swift, and CloudKit doesn’t support ordered relationships.
Previously:
1 Comment RSS · Twitter
The author forgot to investigate pg_renum, akin to BASIC's RENUM statement 😎.
