0

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
  • 3,043
  • 2
  • 34
  • 46
  • 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

1 Answers1

0

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

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