1

I have a table where the rows have a particular order. Users can insert new rows at any place in the ordering.

Our current strategy is:

  • Use column called "order_index" with Integer type
  • Have rows with their "order_index" separated by 10000
  • When new row is inserted, assign integer halfway in between its neighbors
  • If rows become too tightly packed (have separation of one), then lock and re-assign "order_index" to all rows, incrementing by 10000

This is obviously somewhat complex and the re-assigning is not optimal since it takes longer than we'd like. Any better approach to this?

Garrett
  • 4,007
  • 2
  • 41
  • 59
  • 1
    Are there any indexing/retrieval requirements? My mind initially went to a linked-list for this kind of problem, such as something like [this](https://stackoverflow.com/questions/65205/linked-list-in-sql#answer-65295). Insert times would be very quick, but retrieval times might be pretty slow. – Jon Warren Oct 21 '20 at 20:27
  • @Garrett A little bit more context is necessary here for providing a solution. Could you explain how do you decide a new row should lie between start and end range. For example, a new row should be between 10000 and 20000 – SUMIT PATRO Oct 21 '20 at 20:36
  • 1
    You have not indicated how the user indicates where in the sequence the row is to follow, but for order_index use numeric rather an integer. The initial 2 rows can be set to any desired value. Then when inserting just average the order_index previous and next rows to get the order_index of the current row. ( Note: a [numeric](https://www.postgresql.org/docs/12/datatype-numeric.html) column provides up to 16383 digits after the decimal point so plenty of room). For new first or last order_index add or subtract any value. The exact process works is user can reorder the order_index. – Belayer Oct 21 '20 at 22:11
  • @JonWarren a linked list would solve the problem, although we tried that first and the data never stayed pristine (it ended with some messiness like cycles). – Garrett Oct 22 '20 at 02:28
  • @SUMITPATRO we know the row that the new row should come after. – Garrett Oct 22 '20 at 02:28
  • @Belayer, thanks! Good point, the 16,383 digits of `numeric` would buy us ~54K binary splits (assuming we take strategy of averaging neighbors when inserting) before needing to reindex (or ~450K splits using the digits before decimal too). The only downside being a slight loss in readability and DB size (will have to look into that). – Garrett Oct 22 '20 at 02:33
  • Does this answer your question? [What's the best way to store sort order in SQL?](https://stackoverflow.com/questions/2826829/whats-the-best-way-to-store-sort-order-in-sql) – Dai Aug 17 '22 at 08:30
  • @Dai, thanks, but no, it appears [the top answer](https://stackoverflow.com/a/39871377/2223706) that contains a solution just says to do it the way in my question, I was hoping there was a better way. – Garrett Aug 22 '22 at 22:55

1 Answers1

0

If you use a floating point index, there is always a number halfway in between.

Curt Evans
  • 346
  • 2
  • 4
  • Was thinking that too at first, but realized floating point data type actually can have 2 numbers that are maximally close to each other and there's no option in between them (given they have finite precision). – Garrett Aug 22 '22 at 22:44