views:

473

answers:

7

I'm working on something where users can rearrange items, and at a later time, those items need to be displayed in the order chosen. As a simple example, consider a list of items:

A, B, C, D, E, F, G.
The MySQL table would be something simple: user_id, letter, sortnumber

The user is allowed to change the order in incremental steps. They might move A to after D, G to the beginning, etc. In addition to this, they can add and remove items. So they might delete C, or add X. In each of these steps, I send data to PHP, which will process it, and set the items in MySQL.

There are two ways I see going about this:

  1. Each time they add/remove/reorder something, send the entire list to PHP, delete all the data they previous had in there, and just insert the new list. Problem is, this is a lot of deletions/insertions each time they do anything. They might move A to after B, and then suddenly I delete 7 records, and insert 7 more. On the plus side, it's dead simple.
  2. Each "move" they do (eg: an add, or a remove, or a reorder), send the information for that. EG, they moved A after F, and tell me "move A after F" I now have to check that both A and F exist on the list, then I have to decrement all "sortnumber" between A and F (including F). If they say "delete Z" I have to find it on the list, delete it, and decrement all sortnumbers of records after it.

So I'm just curious... has anybody had to deal with something where order matters, and if so, how did you go about it?

A: 

When the user wants to save the new order of the items, have it compare the new order to the old order and only perform updates on ones who have their sortnumber changed. If they delete an item, you don't need to shift the sortnumbers down. If you sort a list with a number that is missing in the middle, it will still be in the correct order.

ryeguy
+1  A: 

Add a Sequence column to the table - as a floating point number.

When an item is moved between Row-A and Row-B set its sequence number to the Average of those adjacent columns

Index the Sequence column :)

Kristen
That's an interesting idea.
pd
Very novel... would it work? I never thought of indexing a float...
Andrew Vit
You can index any scalar in most RDBMS (just not BLOB/TEXT/array).
Bill Karwin
I thought of this too. The problem is that if a user reorders items many times, eventually the difference in between two elements will be too small to divide any further. This is hard for you to test, and hard to debug when it happens.
Bill Karwin
Yes, needs a Renumber routine. Can either be run as a housekeeping task periodically, or when the difference between two adjacent items is below a threshold. Only need to renumber enough adjacent rows to create a "reasonable" gap again.
Kristen
A: 

The final sequence order is the only one that matters. If you move six items around to get a particular order, you don't really need to care what the sequence of the list is at the points between how it was when you started and what it's like when you're done.

Add and remove items without worrying about the sequence order, and then update the items to set the sequence value when you click a button that says, "Save Sort".

This gives you two advantages:

  • It's much less overhead every time you change an item, which also means it'll be faster.
  • It's dead simple to set the sequence -- all you have to do is send a list of the item IDs in the desired order and then iterate over it, updating the sequence value starting at 0 and going up.
pd
Problem is, it needs to be saved after each action they perform.
Sam
It'll still work, you'll just lose a bit of efficiency. Why does the order need to be set after each operation?
pd
A: 

Have a primary key and a sortnumber for each item. If you have a php array including the primary keys, you can remove items and insert items into the array using array_splice().

// base array
$items = array( 7, 11, 9, 4, 5);
// remove item 11
array_splice($items, array_search(11), 1);
// insert 11 before item 4
array_splice($items, array_search(4), 0, 11);
// input now contains 7, 9, 11, 4, 5

Then loop through the array and update sorting with primary keys

$i = 0;
foreach($items as $item) {
  // UPDATE item_table SET sorting = '$i' WHERE id = '$item';
  i++;
}
vishvananda
A: 

I asked a simular question yesterday: http://stackoverflow.com/questions/547022/how-do-i-store-orders

Thomaschaaf
A: 

Here's the same answer I gave to Thomaschaaf's question:

This is not and easy problem. If you have a low number of sortable elements, I would just reset all of them to their new order.

Otherwise, it seems it would take just as much work or more to "test-and-set" to modify only the records that have changed.

You could delegate this work to the client-side. Have the client maintain old-sort-order and new-sort-order and determine which row[sort-order]'s should be updated - then passes those tuples to the PHP-mySQL interface.

You could enhance this method in the following way (doesn't require floats):

  1. If all sortable elements in a list are initialized to a sort-order according to their position in the list, set the sort-oder of every element to something like row[sort-order] = row[sort-order * K] where K is some number > average number of times you expect the list to be reordered. O(N), N=number of elements, but increases insertion capacity by at least N*K with at least K open slots between each exiting pair of elements.

  2. Then if you want to insert an element between two others its as simple as changing its sort-order to be one that is > the lower element and < the upper. If there is no "room" between the elements you can simply reapply the "spread" algorithm (1) presented in the previous paragraph. The larger K is, the less often it will be applied.

The K algorithm would be selectively applied in the PHP script while the choosing of the new sort-order's would be done by the client (Javascript, perhaps).

Andy
A: 

just add another column...

call it order.

you have the order of rows... and each row has an id or primary key. just go through your rows one at a time, and set the order as you go. so:
UPDATE item_table SET order = 0 WHERE id="fred";
UPDATE item_table SET order = 1 WHERE id="larry";
UPDATE item_table SET order = 2 WHERE id="john";
UPDATE item_table SET order = 3 WHERE id="sydney";

i am sure their are trickery ways of doing this mathematically, but sometimes the simple answers are the best.

then when you make a querry add "SORT BY order"

Bingy