Manso Trick: Updating the order of a row in a table

This time, the article is not about javascript or PHP, but SQL. The idea of this article is to review different methods for updating the order of a row in a table (trying to touch only the row we want to change, keeping intact the rest of rows).

To start with a simple example, let’s say I’m doing a web site related to the motor industry, and as any other good website, I use a database. In that database there are two tables: brand and model. In the table brand there is a row for each car brand (Toyota, Honda, Hyunday, Mercedes, Chrysler, BMW, Audi, Lexus,…), and in the table model there is one row for each car model. For example, some models for Audi will be A6 2.0 TDIe , A5 2.0 TDI, A4, TT …, and the list grows and grows for each brand.

The think is, that in the front-end of my website I want to list the models of a brand in a specific order (the order I defined).

You will think, well, that’s easy, it’s just adding a field called sort_order in the model table, or if you love to have the tables normalized, then you will create an extra table with two foreign keys to model and brand, and then a field called sort_order.

It does not matter which solution you choose, the final concept is that there is a field name sort_order that is set manually on the backend, which defines the order used to list models in the frontend. Let’s see an example of these tables:

Brand
name
description
image
model
name
description
image
sort_order

This was just an informal introduction, let’s get started!

In order to simplify things even more, imagine we are always talking about Audi (just to name one), and imagine we are working only with 4 models in the database: A3, A4, A5 y TT. From now on, we will forget about brands. So at the end, our table model looks like this:

name description sort_order
A3 Audi A3 is cool 1
A4 Audi A4 is cooler 2
A5 Audi A5 is even cooler 3
TT No doubt this is the best 4

Now, when I do a SELECT in my website, and I sort using the sort_order, then the models will be listed this way: A3, A4, A5 and finally Audi TT.

The problem:

¿What do I do if I want Audi TT to be the first in the website?

Please note that I want to move Audi TT to the first position, but I don’t want the A3, A4 and A5 change their respective orders; also note I said the first position, but I could have said I want TT to be placed between A3 and A4.

Solution 1: the easy onel

Well, so the first that comes to mind (at least to me) is basically to increment all rows whose sort_order is greater or equal to the position where I want to place the element I want to move, and then update the element I want to move. Let’s see in SQL:

UPDATE model SET sort_order = sort_order + 1 WHERE sort_order >= 1;
UPDATE model SET sort_order = 1 WHERE name = 'TT';

Above you can see two queries: the first one has a linear complexity because it has to update every single row in the table whose sort order is greater than the position (but all rows should be checked); the other query is just to update the row of the TT.

The problem with this solution is the part where ALL rows should be checked and lots of them updated. Then I though of another solution.

Solution 2: the magic of floats

An idea came to my mind: ¿What if instead of integers I use real numbers?

If the field sort_order was a real number, then maybe I could somehow update just the row I want, and leave the rest untouched. Please keep in mind that I use an interface on the backend as well for listing the products and updating the order, so for all elements I know which is the sort_order for the previous and the next elements, as well as for the element itself.

Now, imagine our initial configuration is (A3, A4, A5, TT), and we want to move the TT between A3 and A4. Then I only have to choose a sort_order value between A3 and A4, and magically the TT will be listed between both values. Let’s see the table after choose the middle value:

name description sort_order
A3 Audi A3 is cool 1
TT No doubt this is the best 1.5
A4 Audi A4 is cooler 2
A5 Audi A5 is even cooler 3

Basically I’ve done (1.0 + 2.0) / 2 to get the intermediate value between A3 and A4.

Notice you can also do this as many times as you want, and not only the order will always be preserved, but you will “never find” two rows having the same sort_order.

Let’s see another example, imagine now we want the A4 to be placed between A3 and TT, then the sort_order for A4 will be (1.0 + 1.5)/2 = 1.25.

name description sort_order
A3 Audi A3 is cool 1
A4 Audi A4 is cooler 1.25
TT No doubt this is the best 1.5
A5 Audi A5 is even cooler 3

It’s easy, ¿isn’t it? And you just have to update a single row.

Now there are lots of questions. This is so easy and cool, but ¿what happens if you want to place an element in the first position? If we asume the sort_order starts at 1 for the first element, then the previous element should be choosen as 0.00 (and the same rules will work).

¿And what happens if you want to insert the A6 model? As there are 4 elements, the sort_order for A6 will be 5.0 (to avoid colision, just use number of rows + 1).

And the very good question is: “floating point numbers had limitations, ¿didn’t they? ¿what happens if there is an overflow?” Yes man! this is the question!

Making sort_order to overflow is as easy as keep moving all elements to the same position, over and over again. For example, if we move the element with sort order 3, between the elements with sort order 1 and 2, then the order will be 1.0, 1.5, 2.0, then if we move the 2.0 between 1 and 1.5, we will have 1.0, 1.25, 1.5, if we do repeat the last operation we will have 1.0, 1.125, 1.25, and if you repeat this several times you will get lots of decimals.

This gets us to the third solution

Solution 3: the workaround
Solution 3.1: the background process

One solution could be to have a process once a day,week or month to sort all elements and update the sort_order by their index once sorted, that will remove all decimals for all rows. But if you are going to do this, better implement the first solution.

Solution 3.2: updating to integer when possible

This solution is the same as the solution 2, but rounding numbers to integers before updating, and checking that the number is between (but not equal) to the previous and the next position where we want to be placed.

Let’s see an example starting with following set of rows:

name description sort_order
A3 Audi A3 is cool 1.125
TT No doubt this is the best 1.0394
A4 Audi A4 is cooler 1.7628
A5 Audi A5 is even cooler 3.78

Then if I move A3, between A4 and A5, using solution two I will do the following: (1.7628 + 3.78)/2 = 2.7714. But, if I round 2.7714 down I get 2, and 2 is still between 1.7628 and 3.78, so instead of updating to 2.7714, it will be updated to 2. This way, if I move TT again between A3 and A5, this time instead of computing (2.7714 + 3.78) / 2, the TT position would be computed as (2 + 3.78) / 2, which contains less decimals.

Just notice that in this solution one only has to check if the number is still between the two numbers around, which are already known, and keeps the performance high. Just an update, as before, and all the computations are made on the client-side

If we assume that the movement of all elements will be almost random, using this way of computing number is less probable (but still possible) that an overflow happens.

By the way, I presented this solution using floating point numbers, but you can use integers (and I don’t mean using 10, 20, 30, and then getting intermediate values).

Conclussion

If you want a robust way, use the first solution; but if you want to update just an element each time, because there will be thousands of elements and thousand of users updating the sort order at the same time, then probably the second solution is better, although there can be problems when dealing with concurrent requests.

Finally although I’ve presented a couple of solutions (with their workarounds), I would be pleased to hear of another solutions or improvements.

Trackback URL

, , , , ,

Comments are closed.