Implementing Re-Ordering at the Database Level: Our Experience
March 9, 2023
How to store ordering at the database level isn’t talked about enough on the internet, so this article briefly describes the solution we took for saving a user-defined order for entities in our Postgres database.
We recently implemented a long-requested feature in Basedash: the ability to re-order pages in the sidebar. The biggest challenge was figuring out how to save the order in our database and how we were going to update that order value when a user re-orders the page in the sidebar.
We had two requirements for re-ordering pages in the sidebar:
- Reorder pages within a section
- Allow a page to be dragged to a new section
In the sidebar, pages are grouped by Team and then can be further classified in sections. This image shows 3 sections (Apps, Docks, and Users) within the Everyone team.
We tried out two different implementations for how we manage the order of pages.
Initially, we opted to go with the most obvious approach which was to add an
order column to our
Page table that would contain the index of the page within a section.
Here’s a look at how the page order value would look like for sidebar items:
This implementation proved to be difficult to work with because when you re-order a page, you cannot simply change the
order value for a single page in the database, but rather you must update the order of multiple pages so that there are no gaps between numbers.
You can imagine that if I were to move a page with an
0 to an
2, I would need to write a database query that looks like the following:
The SQL is slightly different if having to move a page from
order 2 to
The above is only if you consider a page moving to a different order within the same section. Things get more complicated when you consider that pages could be moved to a different section because then you would need to update all the pages in two different sections.
These update statements are also not performant—every reorder causes multiple records to be updated, sometimes requiring every page in a section to be updated. Even worse, we have an index on the
order column, which means that updates are even slower.
We had also added a database level constraints to make sure there can only be a unique combination of
order to make sure there cannot be the same order for a page in a given section, but ran into many edge cases where we were trying to set the same order for a given section. We also found out that
null values in postgres are treated as unique, which means that if one row has a
null and and
1 and another row has the same value for
1, the unique constraint between
order will pass because one
null value compared to another
null is seen as different.
💡 Postgres 15 introduces a
NULLS NOT DISTINCToption that will fix the problem of having
nullvalues being seen as different (source). We would have to upgrade our Postgres database in order to use this option, which is not necessarily trivial, and we would also need to instruct our self-hosted Basedash clients to upgrade, which is not feasible.
So as you can see, this approach was complicated and it proved hard to get to work properly.
The implementation we decided to ultimately use implements floating point numbers for the order in the database.
Using floating point values for the
order in the database allows us to move a page between two other pages and determine the new
order value by averaging the
order values for the surrounding pages. This means that we only need to update a single record: the one being moved.
As an example, if we were to insert a page between one that has an order of
2, then the inserted page would have an order of
One thing to be aware with this approach is that because floating point numbers have limited precision, we will eventually hit a floating point rounding situation, which will give us an incorrect value for the order. As an example, if we had a page with
1000 and another page with order of
1001 and repeatedly kept moving pages to the position right after the page with
1000, we would run into issues on the 38th iteration due to floating point rounding.
Number of iterations before floating point rounding occurs when starting with an order of 1000 and 1001 (source: https://begriffs.com/posts/2018-03-20-user-defined-order.html).
38 iterations is still a lot and it seems unlikely in Basedash’s case that someone will repeatedly try to move a pages in such a way that this threshold will be reached, so we aren’t too concerned with the approach. If we wanted to resolve this, we could occasionally “re-balance” the order values, aligning them along a single order of magnitude.
To walk through the flow from front-end to back-end, it looks like this:
- User moves a page with order
4to the position between pages
- The client-side state is updated for the page being moved to have a new value for
- An API call is made to the server that indicates that the page should have an
- A database query is made to update the page with the new
This is a nice and straightforward approach that doesn’t involve having to update the order of many pages when moving a single page (like the initial implementation required).
Possible improvements to ordering at the database level
According to this article, an even more robust approach than the floating point method described above is to store “true fractions” in your database. Read the article if you’d like to find out how to do it. It requires installing a Postgres extension to get a new column type, but it seems like you can go have many more orders of magnitudes of list re-order operations before you run into any sort of rounding issues.
How the drag and drop re-ordering was implemented on the client
We used the dnd-kit library to handle the drag and drop re-ordering. Native drag & drop APIs are a nightmare to work with, so using a library like dnd-kit is almost necessary in my opinion. I’m not going to get into the nitty gritty of how we put together the parts of dnd-kit to form the drag & drop behavior since the code is fairly complex. The code complexity is because there is a lot going on with drag & drop re-ordering, such as:
- Highlighting the section for which the page is being dragged in
- Re-ordering items “on the fly” as you drag
- Showing a preview of where the element will be “dropped” using a <DragOverlay>
- Update both the local state of draggable items as well as the
pageentity in the global store with an updated
- Figure out what new
ordervalue should be used and all the possible edge cases (e.g. what if moving a page to the end/beginning of a list?)
I have a much greater appreciation for the effort it takes to incorporate ordering capabilities into an app now. If anyone knows of a simpler way that this could have been implemented, I’d be curious to hear. You can contact me on Twitter @RobertCooper_RC.