Multi Column Sort

• SwePeso

  SSC-Dedicated

  Points: 39757

  More actions

  April 9, 2009 at 11:59 pm

  #975579

  john.arnott (4/9/2009)

  ---

  Peso,

  I'm not sure that I'm following your toll-booth analogy properly. I don't see how it fits with the data you posted as coming from the OP:

  SELECT 1, 2.35, 3.01, 3.49, 4.25, 4.79, 5.36, 5.82, 6.31

  UNION SELECT 2, null, 3.59, 4.32, null, 5.21, null, null, 7.12

  UNION SELECT 3, NULL, null, null, 5.23, 5.41, 6.33, 6.89, 7.99

  UNION SELECT 4, null, 5.46, 5.31, 5.92, null, 6.87, 7.34, null

  UNION SELECT 5, 5.12, 5.66, 6.31, 6.92, null, 7.87, 8.34, null

  In the example above you start with record 1 which has 8 toll-booths open. So you need to get next record which has the minimum difference in fees. As you can see, that is record 2 which as a minimum difference of 0.42 over toll-booth (passage) 5.

  Then you find next record which is #3 which has a minimum difference of 0.2 over toll-booth 5 (again).

  Then you find next record which is #4 which has a minimum difference of 0.45 over toll-booth 7.

  Then you find next record which is #5 which has a minimum difference of 0.2 over toll-booth 2

  And as you can imagine, the solution has to be a hideous RBAR-solution, with 0.5 * n^2 iterations.

  ---

  N 56°04'39.16"
  E 12°55'05.25"

• RBarryYoung

  SSC Guru

  Points: 143329

  More actions

  April 10, 2009 at 5:31 am

  #975662

  Nice explanation, Peso.

  Of course, in this example you are assuming that the first record is easy to identify, but even that is not necessarily so.

  [font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
  Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]

• SwePeso

  SSC-Dedicated

  Points: 39757

  More actions

  April 10, 2009 at 5:46 am

  #975674

  It doesn't matter where you start.

  You can, as you drive "downwards" the records, also drive "upwards" the records.

  I am thinking of an algorithm that picks an arbitrary record in the middle somewhere of totalt records, sorted by minimum value across all columns. That should give a good starting point.

  Then you find the nearest "downwards" record AND the nearest "upwards" record in same SELECT with MIN(ABS()) functions.

  Then you iterate, for the nearest "upwards" record that record's nearest upwards record, and the nearest "downwards" record for the recently picked nearest "downwards" record.

  And so on, until there are no more records to pick in either direction...

  Or, just pick an arbitrary record in the sample data and work your way upwards until no more records can be found.

  Then you start working your way downwards from the original picked record, until there are no more records to pick.

  ---

  N 56°04'39.16"
  E 12°55'05.25"

• ChrisM@Work

  SSC Guru

  Points: 186127

  More actions

  April 10, 2009 at 6:24 am

  #975702

  RBarryYoung (4/10/2009)

  ---

  Nice explanation, Peso.

  Of course, in this example you are assuming that the first record is easy to identify, but even that is not necessarily so.

  It sounds very promising, Peso...bear in mind that, near the end of the sample data as ordered by CorrectSequence, the difference in fees between two rows of col1 is much less than 1: the difference in fees for col8 is several orders of magnitude higher. col1 and col2 on the same row remain within an order of magnitude of each other, col7 and col8 require scientific notation to display.

  If you try to identify the first record by the most obvious method, matching on min of each column

  i.e. MIN(col1) = col1 OR MIN(col2) = col2

  you get something like 7 rows returned!

  ^{“Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail Shaw}

  For fast, accurate and documented assistance in answering your questions, please read this article.
  Understanding and using APPLY, (I) and (II) Paul White
  Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff Moden

• jsanborn

  Old Hand

  Points: 348

  More actions

  April 10, 2009 at 8:16 am

  #975774

  Maybe this example will be clearer. Suppose you are doing an experiment with rats and mazes. You have a maze that a rat can find a single direct route through. You place fifteen buttons throughout just off the direct path so the rat has to remember where they are and deviate from the path a little to punch the button to get a reward, then continue through the maze without getting lost while making all the detours for snacks. So you put a rat into the start of the maze and mark the time when each button is pushed. Every minute you start a new rat off into the maze. (The rats have a letter assigned but it's not really relevant to the problem.) For each rat going in you record a new trip through the maze and you record the time and number of each button when pushed. Some rats will randomly miss a button here and there. In this case we'll assume it takes a rat 30 to 54 seconds between button locations. We also assume none of the rats catch up and pass the rat in front of it before completing the maze. So if each row in the table represents a trip through the maze, the ordered rows will increment from left to right and columns will increment from top to bottom and there will be random nulls.

  You could also think of a train schedule as a good example. You have several trains running a route with 15 stops along the way. One train after another and they don't pass each other. Because of varying passenger load throughout the day, all of the trains don't always stop at every station. If you are looking at a table of the train schedule, you would have times that always increment from left to right and increment top to bottom with empty spots where the trains don't stop.

  I've included a script to build a table for the rats. Two tables record each trip for a rat and the time and button number for each button pushed. Then the two tables are used to construct a schedule showing all the data. For simplicity, the times are stored as integer values representing seconds from midnight. As you can see, if by chance all the rats always missed one of the buttons (it was too hard to find) then that column would not be represented in the final output. So you wouldn't have a complete column of nulls. We can also assume in our rat experiment that one researcher with a clipboard is marking time for each rat in the maze. When their rat is done, they grab another rat and start it into the maze and follow it through. If there are several rats in the maze at a time and each researcher, one at a time, then records the data they collected, the data wouldn't be entered in the correct order. So I also rigged the script so the table doesn't output data already in the correct sorted order. And again, while the rat letter may prove useful in ordering the table, the goal is to find a way to sort the data based only on the columns of numbers. It's also very simple to increase the size of the sample dataset as much as you want.

  So again (and I'm sure someone will say I'm completely changing the requirements), the data should be sorted using only the values in the 'b' columns without relying on the letters or id field. The values increment left to right in each row (which they will always do anyway) and should increment from top to bottom in each column. Nulls are not considered in the sorting but simply fall where they may.

  CREATE TABLE #trips (TripID INT, Rat CHAR(1))

  CREATE TABLE #buttons (TripID INT, ButtonNumber INT, PunchTime INT)

  CREATE TABLE #results(TripID INT, Rat CHAR(1))

  DECLARE @i INT, @j-2 INT, @char INT, @start INT,

  @time INT, @tripID INT, @sql NVARCHAR(500)

  SET @i = 0

  SET @tripID = 0

  SET @start = 28800

  WHILE @i < 20

  BEGIN

  SET @char = 65

  WHILE @char < 73

  BEGIN

  SET @tripID = @tripID + 1

  INSERT INTO #trips VALUES(@tripID, CHAR(@char))

  SET @time = @start

  SET @char = @char + 1

  SET @j-2 = 0

  WHILE @j-2 < 15

  BEGIN

  SET @j-2 = @j-2 + 1

  SET @time = @time + CAST(((RAND() * 100) / 4) + 30 AS INT)

  IF(CAST(RAND() * 10 + 1 AS INT) <> 5)

  INSERT INTO #buttons VALUES(@tripID, @j-2, @time)

  END

  SET @start = @start + 60

  END

  SET @i = @i + 1

  END

  INSERT INTO #results

  SELECT TripID, Rat FROM #trips

  DECLARE buttons CURSOR FOR

  SELECT DISTINCT ButtonNumber

  FROM #buttons ORDER BY ButtonNumber

  OPEN buttons

  FETCH NEXT FROM buttons INTO @i

  WHILE (@@FETCH_STATUS <> -1)

  BEGIN

  SET @sql = N'ALTER TABLE #results ADD b' + CONVERT(NVARCHAR(2), @i) + ' INT'

  EXEC sp_executesql @sql

  SET @sql = N'UPDATE #results SET b' + CONVERT(NVARCHAR(2), @i) +

  ' = b.PunchTime FROM #results r INNER JOIN #buttons b

  ON r.TripID = b.TripID AND b.ButtonNumber = ' + CONVERT(NVARCHAR(2), @i)

  EXEC sp_executesql @sql

  FETCH NEXT FROM buttons INTO @i

  END

  CLOSE buttons

  DEALLOCATE buttons;

  -- Comment out this section to see the table in correct order --

  WITH b AS (

  SELECT ROW_NUMBER() OVER(ORDER BY Rat, b1) AS RowNum, TripID

  FROM #results )

  UPDATE #results SET TripID = b.RowNum

  FROM #results a INNER JOIN b

  ON a.TripID = b.TripID

  -- ********************************************************** --

  SELECT * FROM #results ORDER BY TripID

  DROP TABLE #trips

  DROP TABLE #buttons

  DROP TABLE #results

• RBarryYoung

  SSC Guru

  Points: 143329

  More actions

  April 10, 2009 at 8:56 am

  #975816

  jsanborn (4/10/2009)

  ---

  Maybe this example will be clearer. Suppose you are doing an experiment with rats and mazes. You have a maze that a rat can find a single direct route through. You place fifteen buttons throughout just off the direct path so the rat has to remember where they are and deviate from the path a little to punch the button to get a reward, then continue through the maze without getting lost while making all the detours for snacks. So you put a rat into the start of the maze and mark the time when each button is pushed. Every minute you start a new rat off into the maze. (The rats have a letter assigned but it's not really relevant to the problem.) For each rat going in you record a new trip through the maze and you record the time and number of each button when pushed. Some rats will randomly miss a button here and there. In this case we'll assume it takes a rat 30 to 54 seconds between button locations. We also assume none of the rats catch up and pass the rat in front of it before completing the maze.

  The data generator that I provided also works in this model.

  Except that my rats are all so drunk or high that they can only find one or two of the buttons at best (though they can always find at least one of the buttons that the rat in front of them found). Plus there are some serious relativistic time dilation effects in my maze. :-D.

  [font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
  Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]

• SwePeso

  SSC-Dedicated

  Points: 39757

  More actions

  April 10, 2009 at 1:44 pm

  #975949

  Attached is a zip-file with working solutions for original problem.

  Both files contains same algorithm.

  One file is based on Barry's test data and one file is based on jsanborn's latest sample data.

  For Barry's sample data, 500 records takes about 2 seconds, 1000 records about 6 seconds and 1500 records takes about 15 seconds.

  ---

  N 56°04'39.16"
  E 12°55'05.25"

• mister.magoo

  SSC-Forever

  Points: 47174

  More actions

  April 10, 2009 at 4:18 pm

  #975984

  jsanborn (4/10/2009)

  ---

  Maybe this example will be clearer. ...

  I've included a script to build a table for the rats. ...

  So again (and I'm sure someone will say I'm completely changing the requirements), the data should be sorted using only the values in the 'b' columns without relying on the letters or id field. The values increment left to right in each row (which they will always do anyway) and should increment from top to bottom in each column. Nulls are not considered in the sorting but simply fall where they may.

  Unfortunately, the data generated by this is flawed - it breaks the rules of the challenge...

  See this sample :

  TripID Rat b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15

  62 F 32514 32554 32608 32659 32698 32749 32780 32833 32880 32915 32947 32990 33032 33080 33126

  63 G 32550 32597 32630 32666 32706 32739 32785 32830 32864 32915 32948 NULL 33036 NULL 33107

  Columns b6, b8,b9 and b15 are all breaking the rules (or at least it is impossible to order these rows correctly)

  MM

  MM
  

  ---

  
  select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);

• Forum Etiquette: How to post Reporting Services problems
[/url]
• Forum Etiquette: How to post data/code on a forum to get the best help - by Jeff Moden
[/url]
• How to Post Performance Problems - by Gail Shaw
[/url]