Re-ordering a list - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

Transact-SQL (2000)

Re-ordering a list

Author

Topic

jshepler
Yak Posting Veteran

60 Posts

Posted - 2005-12-31 : 13:44:15

We built a custom ticket system that lets us manage what is tracked on various types of tickets. On the admin page, these items are shown with arrow buttons to move the up and down the list. Some lists are getting rather large and when an admin adds a new item that needs moved up the list, clicking the arrow button 20 times becomes a chore. So, instead of the arrow buttons, I'm now showing a text box with the position number and the admin can just change the position number of an item (or items) and click an update button.

I'm having problems coming up with an efficient way of taking a list of moves and re-ordering the list.

[CODE]
CREATE TABLE #Q (id int, position int, item varchar(255))
INSERT INTO #Q
SELECT 23, 1, 'aaa' UNION ALL
SELECT 5, 2, 'bbb' UNION ALL
SELECT 164, 3, 'ccc' UNION ALL
SELECT 65, 4, 'ddd' UNION ALL
SELECT 258, 5, 'eee' UNION ALL
SELECT 2, 6, 'fff' UNION ALL
SELECT 74, 7, 'ggg' UNION ALL
SELECT 16, 8, 'hhh' UNION ALL
SELECT 99, 9, 'iii' UNION ALL
SELECT 38, 10, 'jjj'
[/CODE]

would give:
[CODE]
id position item
23 1 aaa
5 2 bbb
164 3 ccc
65 4 ddd
258 5 eee
2 6 fff
74 7 ggg
16 8 hhh
99 9 iii
38 10 jjj
[/CODE]

Let's say we want to move item 'fff' from position 6 to position 2 and item 'iii' from position 9 to position 3. The result would be:
[CODE]
id position item
23 1 aaa
2 2 fff
99 3 iii
5 4 bbb
164 5 ccc
65 6 ddd
258 7 eee
74 8 ggg
16 9 hhh
38 10 jjj
[/CODE]

or if we move pos 3 to pos 9, pos 6 to pos 1, and pos 5 to pos 3; we would get:
[CODE]
id position item
2 1 fff
23 2 aaa
258 3 eee
5 4 bbb
65 5 ddd
74 6 ggg
16 7 hhh
99 8 iii
164 9 ccc
38 10 jjj
[/CODE]

Rolling ideas around my head for a couple of days and I think I might be onto something. I was thinking that if I could determine the number "rows" to move an item, I could do the re-order as a simple update. Using the last example, the old #1 would move down 1 row, the old #2 would move down 2 rows, the old #4 would move down 1 row (#3 was skipped in this because it was part of a move command - the new position is specified, not calculated):
[CODE]
id item old new change
23 aaa 1 2 +1
5 bbb 2 4 +2
164 ccc 3 9 -- (specifed)
65 ddd 4 5 +1
258 eee 5 3 -- (specifed)
2 fff 6 1 -- (specifed)
74 ggg 7 6 -1
16 hhh 8 7 -1
99 iii 9 8 -1
38 jjj 10 10 0
[/CODE]

So, the trick seems to be figuring out the change. If we can calculate change, we could do a simple update like:
[CODE]
CREATE TABLE #Moves (old int, new int)
INSERT INTO #Moves
SELECT 3, 9 UNION ALL
SELECT 6, 1 UNION ALL
SELECT 5, 3

UPDATE #Q
SET Position = ISNULL(m.new, q.Position + CHANGE)
FROM #Q q
LEFT JOIN #Moves m ON q.Position = m.old
[/CODE]

Any ideas on figuring out CHANGE?

Or any other ideas on doing the re-ordering?

/jeff

rrb
SQLTeam Poet Laureate

1479 Posts

Posted - 2006-01-02 : 19:00:50

hi jeff

you may well be on to something, but its too clever for me by a long way - try this

--create a stored procedure
create proc dbo.MoveTo 
	@id int, 
	@moveTo int
as
	declare @moveFrom int
	select @moveFrom = position from #Q where id = @id
	
        --key concept - only update in between rows
	update #Q
	set position = case when id = @id then @moveTo else position + 1 end
	where position between @moveTo and @moveFrom
go

then test it as follows

CREATE TABLE #Q (id int, position int, item varchar(255))
INSERT INTO #Q
SELECT 23, 1, 'aaa' UNION ALL
SELECT 5, 2, 'bbb' UNION ALL
SELECT 164, 3, 'ccc' UNION ALL
SELECT 65, 4, 'ddd' UNION ALL
SELECT 258, 5, 'eee' UNION ALL
SELECT 2, 6, 'fff' UNION ALL
SELECT 74, 7, 'ggg' UNION ALL
SELECT 16, 8, 'hhh' UNION ALL
SELECT 99, 9, 'iii' UNION ALL
SELECT 38, 10, 'jjj'
go

--do the moves 
Exec dbo.MoveTo 2,2
Exec dbo.MoveTo 99,3

--show the result
select * from #Q order by position

drop table #q
drop procedure dbo.MoveTo
go

which produces

23	1	aaa
2	2	fff
99	3	iii
5	4	bbb
164	5	ccc
65	6	ddd
258	7	eee
74	8	ggg
16	9	hhh
38	10	jjj

Simple, straight forward and makes sense to me...the key concept is that you only need to update the rows in between where you're moving from and to

--
I hope that when I die someone will say of me "That guy sure owed me a lot of money"

khtan
In (Som, Ni, Yak)

17689 Posts

Posted - 2006-01-03 : 04:34:38

Modified from rrb's code to make it able to move up or down

create proc dbo.MoveTo 
	@id	int,
	@moveTo	int
as
begin

declare
	@moveFr	int

select	@moveFr	= position from #Q where id = @id

update 	#Q
	set	position	= case 	when 	position < @moveFr then
						position + 1
					when	position > @moveFr then
						position - 1
					else
						@moveTo
					end
	where	(@moveTo < @moveFr and position between @moveTo and @moveFr)
	or	(@moveTo > @moveFr and position between @moveFr and @moveTo)
end

Try this :
exec dbo.MoveTo 2,2 -- move Up
exec dbo.MoveTo 99,3 -- move Up
exec dbo.MoveTo 2,8 -- move Down

-----------------
[KH]
2006 a new beginning

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2006-01-03 : 07:38:59

I'm all in favour of a SQL solution, but why not make the 'user control' easier to work with....maybe use a 'dragable slider' instead of a 'clickable arrow'...a small drag would move an item 1 spot and a larger drag would move an item up several places?

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-03 : 09:24:14

AndrewMurphy:
The user control is just a mechanism to determine what row needs to be moved where - it doesn't help with the actual moving part.

rrb/hktan:
Your solution is fine in the scope of a single move. Even in a list of moves, your solution is only scoped to a single move - without regard to the other moves. For example, if an item was moved to #3 and afterwards another item was moved to #2, the item moved to #3 would get bumped down to #4. To fix that, you would need to order the list of moves by new position number so that one move would not affect another move. We have 2 choices of where to order the list of moves: 1) in sql server, but would require a cursor (which I don't want) or 2) in code, that would loop through the list of moves and making a database hit for each iteration (which I don't want - doesn't scale at all).

I need a set-based solution.

/jeff

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-03 : 10:24:14

I've been working on this when I can and I've gotten closer.

Let's start with a simple move - #5 to #2 would result in:
[CODE]
id item old new change
23 aaa 1 1 0
5 bbb 2 3 +1
164 ccc 3 4 +1
65 ddd 4 5 +1
258 eee 5 2 --
2 fff 6 6 0
74 ggg 7 7 0
16 hhh 8 8 0
99 iii 9 9 0
38 jjj 10 10 0
[/CODE]
Since only 1 item is being moved that would affect items #2 through #5, we can do this update with:

[CODE]
UPDATE #Q
SET Position = ISNULL(m.New
, Position + (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN new AND old)
)
FROM #Q q
LEFT JOIN #M m ON q.Position = m.old
[/CODE]
(old > new, so have to reverse old and new for the BETWEEN)

This works for all single moves going up. For moves going down (#5 to #8):
[CODE]
id item old new change
23 aaa 1 1 0
5 bbb 2 2 0
164 ccc 3 3 0
65 ddd 4 4 0
258 eee 5 8 --
2 fff 6 5 -1
74 ggg 7 6 -1
16 hhh 8 7 -1
99 iii 9 9 0
38 jjj 10 10 0
[/CODE]
We'd have:
[CODE]
UPDATE #Q
SET Position = ISNULL(m.New
, Position - (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN old AND new)
)
FROM #Q q
LEFT JOIN #M m ON q.Position = m.old
[/CODE]
Just like other moves that take direction into account, this time we have to subtract from the position.

It'd be nice if we could have one calculation that would be negative when needed. We can by using a trick with BETWEEN. If X > Y, then BETWEEN X AND Y would always be false for any value. Take this query:
[CODE]
SELECT ID
, Item
, Position
, Old_LT_New = (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN old AND new)
, Old_GT_New = (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN new AND old)
, Diff = (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN new AND old)
- (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN old AND new)
FROM #Q q
LEFT JOIN #M m ON q.Position = m.old
ORDER BY q.Position
[/CODE]
For the first example (#5 to #2), you'd get:
[CODE]
ID Item Position Old_LT_New Old_GT_New
23 aaa 1 0 0
5 bbb 2 0 1
164 ccc 3 0 1
65 ddd 4 0 1
258 eee 5 0 1
2 fff 6 0 0
74 ggg 7 0 0
16 hhh 8 0 0
99 iii 9 0 0
38 jjj 10 0 0
[/CODE]
Since old > new, the old < new column will always have a 0. In the 2nd example (#5 to #8), we'd have:
[CODE]
ID Item Position Old_LT_New Old_GT_New
23 aaa 1 0 0
5 bbb 2 0 0
164 ccc 3 0 0
65 ddd 4 0 0
258 eee 5 1 0
2 fff 6 1 0
74 ggg 7 1 0
16 hhh 8 1 0
99 iii 9 0 0
38 jjj 10 0 0
[/CODE]
Since old < new, the old > new column will always have a 0. If we subtract Old_GT_New from Old_LT_New, we would have our positive number for items being moved up, and negative numbers for items being moved down. Let's change our query to show this difference as well as the resulting new. To keep the results from being confusin, let's show NULL for moves' rows (#5 should not show any calculations because it's being moved):
[CODE]
SELECT ID
, Item
, Position
, Old_LT_New = CASE
WHEN m.new IS NOT NULL THEN NULL
ELSE (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN old AND new)
END
, Old_GT_New = CASE
WHEN m.new IS NOT NULL THEN NULL
ELSE (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN new AND old)
END
, Diff = CASE
WHEN m.new IS NOT NULL THEN NULL
ELSE(SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN new AND old)
- (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN old AND new)
END
, New = ISNULL(m.new, Position
+ (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN new AND old)
- (SELECT COUNT(*) FROM #M WHERE q.Position BETWEEN old AND new)
)
FROM #Q q
LEFT JOIN #M m ON q.Position = m.old
ORDER BY q.Position
[/CODE]
and combine the two examples by moving #6 to #9 and #5 to #2, we'd have:
[CODE]
ID Item Position Old_LT_New Old_GT_New Diff New
23 aaa 1 0 0 0 1
5 bbb 2 0 1 1 3
164 ccc 3 0 1 1 4
65 ddd 4 0 1 1 5
258 eee 5 NULL NULL NULL 2
2 fff 6 NULL NULL NULL 9
74 ggg 7 1 0 -1 6
16 hhh 8 1 0 -1 7
99 iii 9 1 0 -1 8
38 jjj 10 0 0 0 10
[/CODE]

Seems like that's it, doesn't it? Well, it's not. Let's use one of the first examples (#3 to #9, #6 to #1, and #5 to #3), the result would be:
[CODE]
ID Item Position Old_LT_New Old_GT_New Diff New
23 aaa 1 0 1 1 2
5 bbb 2 0 1 1 3 <--
164 ccc 3 NULL NULL NULL 9
65 ddd 4 1 2 1 5
258 eee 5 NULL NULL NULL 3 <--
2 fff 6 NULL NULL NULL 1
74 ggg 7 1 0 -1 6
16 hhh 8 1 0 -1 7
99 iii 9 1 0 -1 8
38 jjj 10 0 0 0 10
[/CODE]
Notice we have duplicate new #3s. Old #2 should become New #4 because moving item #6 to #1 would have bumped it down to #3 and then moving #5 to #3 should have moved it down to #4.

So, it's not quite right yet.

Any ideas?

/jeff

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-03 : 10:26:53

Sorry, forgot to re-post the code for #M
[CODE]
CREATE TABLE #M (old int, new int)
INSERT INTO #M
SELECT 3, 9 UNION ALL
SELECT 6, 1 UNION ALL
SELECT 5, 3
[/CODE]

/jeff

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2006-01-03 : 10:48:59

"AndrewMurphy: The user control is just a mechanism to determine what row needs to be moved where - it doesn't help with the actual moving part"

...I know

...but your original problem as worded seemed to suggest a core problem of too many-user-clicks to move an item up/down, and not specifically to do with a data updating issue...I was focusssing on that side of things.

How often does this activity have to be done? Does it have to be done in the most efficient basis or just faster than currently "not-accepted"? Would that circumvent the search for the most-efficient solution?

Off the wall here...what about looking into some ^2 maths, where your position can be represented by a score to the power of 2 and then you may be able to do some bitwise-style comparisons/updates? I seem to remember others advocating the value of bitwise operations but I haven't executed any myself.

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2006-01-03 : 11:17:30

I had provided a solution to a similar problem. You might see if any of this is helpfull:
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=59128

the 3 parameters in this case where @fileid int, @caseid, @direction.
@caseid was redundant in this case but @fileid and @directionid was used like:

@fileid = 12, @direction = -8
(move fileid 12 up 8 positions)

@fileid = 12, @direction = 4
(move fileid 12 down 4 positions)

EDIT:
he was using this for moving 1 position at a time but his parameters allowed for multiple moves so I coded it that way. However some of the errror messages would need to be reworded like when the user tries to move to an invalid position.

Be One with the Optimizer
TG

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-03 : 11:22:13

"...but your original problem as worded seemed to suggest a core problem of too many-user-clicks to move an item up/down, and not specifically to do with a data updating issue...I was focusssing on that side of things."

You are correct that this revision came up because users complained about having to click too many times. You are correct in that a new user control needs to be created to make doing the updates easier for the user. However, the user control is not the problem. I also stated "So, instead of the arrow buttons, I'm now showing a text box with the position number and the admin can just change the position number of an item (or items) and click an update button." While this might not be the most "user-friendly" control, for a web page w/o doing some fancy javascriping, this is what I'm going to use.

"How often does this activity have to be done? Does it have to be done in the most efficient basis or just faster than currently "not-accepted"? Would that circumvent the search for the most-efficient solution?"

Not very often and you are correct - I'm looking for the most efficient method. Yes, I could just use a cursor to do what I want and it'll work just fine. Since the project is a low-priority change, I'm taking the time to use this as an exercise in set-based logic.

"Off the wall here...what about looking into some ^2 maths, where your position can be represented by a score to the power of 2 and then you may be able to do some bitwise-style comparisons/updates? I seem to remember others advocating the value of bitwise operations but I haven't executed any myself."

That's almost the same as using a linked-list to do the re-ordering. However, that would still be an iteration-based move instead of a set-based move. You would have to do 1 move at a time, shifting the appropriate bits the appropiate direction the appropriate number of places. While this would get rid of looping through all the "rows" that need to be shifted for a move, you would still have to loop through the list of moves.

Again, I'm after a set-based solution.

Thanks for the reply! Even though I shot down the bitwise operations, I hadn't thought about it and it is a good suggestion. It made me re-evaluate some other projects that I'm working on. :)

/jeff

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-03 : 11:36:58

quote:
Originally posted by TG

I had provided a solution to a similar problem. You might see if any of this is helpfull:
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=59128

Thanks TG, but this is still an iteration-based solution in the sense that you would have to iterate over a list of moves and call your proc for each move. Each move is ignorant of the other moves. This can cause problems: #6 moves to #3, #8 moves to #2, the new item at #3 would then (incorrectly) get shifted down to #4.

/jeff

rrb
SQLTeam Poet Laureate

1479 Posts

Posted - 2006-01-03 : 17:28:16

jeff

i'm not really clever (and am often wrong), but I suspect that conceptually what you want is by definition an iterative solution. this is because, the user performs the moves in order (ie iteratively) to get the final result, and if the moves are not performed in order you end up with a different result. at the end of all of the user's moves, you may end up with a list of moves (from the UI), but these must be done in order again (in the database), and therefore iteratively (unless I'm misunderstanding something about the nature of the problem)

as an example, consider the list
a 1
b 2
c 3
d 4

the user may move b to 1, c to 2 and d to 3.

what is the result? well either:
b 1
c 2
d 3
a 4 (moves done in order)

OR

b 1
a 2
c 3
d 4 (moves done in reverse order)

so if we apply those moves in a "set based" fashion - ie irrespective of order - we get (potentially) different results. there's probably some really neat mathematical way of expressing what i'm trying to say, but i'm not a mathematician - just a very naughty boy.

[thought bubble]OK - more thinking - i think my issue is that when you move d from 4 to 2, you are also moving b from 2 to 3 and c from 3 to 4. your solution must take into account these "implied" moves also...[/thought bubble]

my gut tells me that attempting to get a "set based solution" as you call it, is in fact not really possible, by definition. however, this doesn't preclude you doing some very clever maths to optimise the list of moves once they have been recorded in the UI.

for example, a move of d to position 3 and a move of d to 4 may be able to be summed as no move at all, but probably only if they were consecutive moves, because the state of the ordered list is potentially changed by each move.

i think it's like rubiks' cube - you have to do it iteratively. unless of course you pull it apart, or simply move the stickers...

but hey, I could be wrong

--
I hope that when I die someone will say of me "That guy sure owed me a lot of money"

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-03 : 17:58:25

quote:
Originally posted by rrb

jeff

i'm not really clever (and am often wrong), but I suspect that conceptually what you want is by definition an iterative solution. this is because, the user performs the moves in order (ie iteratively) to get the final result,
...

I present the list of items with a textbox next to each one populated with the item's position number. The user could change the positions of multiple items and then click the submit button.

I'm trying to do the moves so the result would be what the user expects. Using your example, I would expect the result to be your first set (forward order) as the 2nd set (reverse order) has the wrong result (c is not 2 and d is not 3). However, the order is not the order of moves entered, but the order of destination numbers. So, yes, we can set up an iteration to apply the moves and get the result expected.

I was really hoping that I would not have to do the iteration (either sql cursor or client-code loop). Thus began my search for more of a set-based solution. I don't believe any fancy math is needed either.

/jeff

rrb
SQLTeam Poet Laureate

1479 Posts

Posted - 2006-01-03 : 18:09:02

oh, ok

so the "new positions" are end positions and not interim states? in this case, you may be able to do a set based solution, but i think you'd still have to consider the "implied moves" and include them in your set of transitions

i'll be very interested to see if you can

--
I hope that when I die someone will say of me "That guy sure owed me a lot of money"

TG
Master Smack Fu Yak Hacker

6065 Posts

Posted - 2006-01-03 : 18:37:57

>>i think it's like rubiks' cube - you have to do it iteratively. unless of course you pull it apart, or simply move the stickers
That analogy might not be a bad idea. If the user can basically "rebuild" the order, maybe it's simpler just to delete and re-insert in whatever order the user ended up with.

Have you decided how/what you're going to pass to the SP?

Be One with the Optimizer
TG

DustinMichaels
Constraint Violating Yak Guru

464 Posts

Posted - 2006-01-03 : 18:48:17

We had something similar to this in our CMS when users were able to order the child pages of an item.

What we did was take the list of textboxes and did a single update query to update the order column of all the child pages. It was pretty easy.

jshepler
Yak Posting Veteran

60 Posts

Posted - 2006-01-04 : 10:09:24

rrb:
Me too. :)

TG:
I build a string like "3=8,6=2,9=1" and the proc pares it into a temp table of moves (the #M in my examples).

/jeff

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources