10

In got a programming task in the area of T-SQL.

Task:

  1. People want to get inside an elevator every person has a certain weight.
  2. The order of the people waiting in line is determined by the column turn.
  3. The elevator has a max capacity of <= 1000 lbs.
  4. Return the last person's name that is able to enter the elevator before it gets too heavy!
  5. Return type should be table

enter image description here

Question: What is the most efficient way to solve this problem? If looping is correct is there any room for improvement?

I used a loop and # temp tables, here my solution:

set rowcount 0
-- THE SOURCE TABLE "LINE" HAS THE SAME SCHEMA AS #RESULT AND #TEMP
use Northwind
go

declare @sum int
declare @curr int
set @sum = 0
declare @id int

IF OBJECT_ID('tempdb..#temp','u') IS NOT NULL
    DROP TABLE #temp

IF OBJECT_ID('tempdb..#result','u') IS NOT NULL
    DROP TABLE #result

create table #result( 
    id int not null,
    [name] varchar(255) not null,
    weight int not null,
    turn int not null
)

create table #temp( 
    id int not null,
    [name] varchar(255) not null,
    weight int not null,
    turn int not null
)

INSERT into #temp SELECT * FROM line order by turn

 WHILE EXISTS (SELECT 1 FROM #temp)
  BEGIN
   -- Get the top record
   SELECT TOP 1 @curr =  r.weight  FROM  #temp r order by turn  
   SELECT TOP 1 @id =  r.id  FROM  #temp r order by turn

    --print @curr
    print @sum

    IF(@sum + @curr <= 1000)
    BEGIN
    print 'entering........ again'
    --print @curr
      set @sum = @sum + @curr
      --print @sum
      INSERT INTO #result SELECT * FROM  #temp where [id] = @id  --id, [name], turn
      DELETE FROM #temp WHERE id = @id
    END
     ELSE
    BEGIN    
    print 'breaaaking.-----'
      BREAK
    END 
  END

   SELECT TOP 1 [name] FROM #result r order by r.turn desc 

Here the Create script for the table I used Northwind for testing:

USE [Northwind]
GO

/****** Object:  Table [dbo].[line]    Script Date: 28.05.2018 21:56:18 ******/
SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[line](
    [id] [int] NOT NULL,
    [name] [varchar](255) NOT NULL,
    [weight] [int] NOT NULL,
    [turn] [int] NOT NULL,
PRIMARY KEY CLUSTERED 
(
    [id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY],
UNIQUE NONCLUSTERED 
(
    [turn] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[line]  WITH CHECK ADD CHECK  (([weight]>(0)))
GO

INSERT INTO [dbo].[line]
    ([id], [name], [weight], [turn])
VALUES
    (5, 'gary', 800, 1),
    (3, 'jo', 350, 2),
    (6, 'thomas', 400, 3),
    (2, 'will', 200, 4),
    (4, 'mark', 175, 5),
    (1, 'james', 100, 6)
;
0
16

You should try to avoid loops generally. They are normally less efficient than set based solutions as well as less readable.

The below should be pretty efficient.

Even more so if the name and weight columns could be INCLUDE-d in the index to avoid the key lookups.

It can scan the unique index in order of turn and calculate the running total of the Weight column - then use LEAD with the same ordering criteria to see what the running total in the next row will be.

As soon as it finds the first row where this exceeds 1000 or is NULL (indicating there is no next row) then it can stop the scan.

WITH T1
     AS (SELECT *,
                SUM(Weight) OVER (ORDER BY turn ROWS UNBOUNDED PRECEDING) AS cume_weight
         FROM   [dbo].[line]),
     T2
     AS (SELECT LEAD(cume_weight) OVER (ORDER BY turn) AS next_cume_weight,
                *
         FROM   T1)
SELECT TOP 1 name
FROM   T2
WHERE  next_cume_weight > 1000
        OR next_cume_weight IS NULL
ORDER  BY turn 

Execution Plan

enter image description here

In practice it seems to read a few rows ahead of where is strictly necessary - it looks like each window spool/stream aggregate pair causes two additional rows to be read.

For the sample data in the question ideally it would only need to read two rows from the index scan but in reality it reads 6 but this is not a significant efficiency issue and it does not degrade as more rows are added to the table (as in this demo)

For those interested in this issue an image with the rows output by each operator (as shown by the query_trace_column_values extended event) is below, the rows are output in row_id order (starting at 47 for the first row read by the index scan and finishing at 113 for the TOP)

Click the image below to make it larger or alternatively see the animated version to make the flow easier to follow.

Pausing the animation at the point where the Right hand stream aggregate has emitted its first row (for gary - turn = 1). It seems apparent that it was waiting to receive its first row with a different WindowCount (for Jo - turn = 2). And the window spool doesn't release the first "Jo" row until it has read the next row with a different turn (for thomas - turn = 3)

So the window spool and stream aggregate both cause an additional row to be read and there are four of these in the plan - hence 4 additional rows.

enter image description here

An explanation of the columns shown in the above follows (based on info here)

  • NodeName: Index Scan, NodeId: 15, ColumnName: id base table column covered by index
  • NodeName: Index Scan, NodeId: 15, ColumnName: turn base table column covered by index
  • NodeName: Clustered Index Seek, NodeId: 17, ColumnName: weight base table column retrieved from lookup
  • NodeName: Clustered Index Seek, NodeId: 17, ColumnName: name base table column retrieved from lookup
  • NodeName: Segment, NodeId: 13, ColumnName: Segment1010 Returns 1 at start of new group or null otherwise. As no Partition By in the SUM only the first row gets 1
  • NodeName: Sequence Project, NodeId: 12, ColumnName: RowNumber1009 row_number() within group indicated by Segment1010 flag. As all rows are in the same group this is ascending integers from 1 to 6. Would be used for filtering right frame rows in cases like rows between 5 preceding and 2 following. (or as for LEAD later)
  • NodeName: Segment, NodeId: 11, ColumnName: Segment1011 Returns 1 at start of new group or null otherwise. As no Partition By in the SUM only the first row gets 1 (Same as Segment1010)
  • NodeName: Window Spool, NodeId: 10, ColumnName: WindowCount1012 Attribute that groups together rows belonging to a window frame. This window spool is using the "fast track" case for UNBOUNDED PRECEDING. Where it emits two rows per source row. One with the cumulative values and one with the detail values. Though there is no visible difference in the rows exposed by query_trace_column_values I assume that cumulative columns are there in reality.
  • NodeName: Stream Aggregate, NodeId: 9, ColumnName: Expr1004 Count(*) grouped by WindowCount1012 according to plan but actually a running count
  • NodeName: Stream Aggregate, NodeId: 9, ColumnName: Expr1005 SUM(weight) grouped by WindowCount1012 according to plan but actually the running sum of weight (i.e. cume_weight)
  • NodeName: Segment, NodeId: 7, ColumnName: Expr1002 CASE WHEN [Expr1004]=(0) THEN NULL ELSE [Expr1005] END - Don't see how COUNT(*) can be 0 so will always be running sum (cume_weight)
  • NodeName: Segment, NodeId: 7, ColumnName: Segment1013 No partition by on the LEAD so first row gets 1. All remaining get null
  • NodeName: Sequence Project, NodeId: 6, ColumnName: RowNumber1006 row_number() within group indicated by Segment1013 flag. As all rows are in the same group this is ascending integers from 1 to 4
  • NodeName: Segment, NodeId: 4, ColumnName: BottomRowNumber1008 RowNumber1006 + 1 as the LEAD requires the single next row
  • NodeName: Segment, NodeId: 4, ColumnName: TopRowNumber1007 RowNumber1006 + 1 as the LEAD requires the single next row
  • NodeName: Segment, NodeId: 4, ColumnName: Segment1014 No partition by on the LEAD so first row gets 1. All remaining get null
  • NodeName: Window Spool, NodeId: 3, ColumnName: WindowCount1015 Attribute that groups together rows belonging to a window frame using the previous row numbers. The window frame for LEAD has max 2 rows (the current one and the next one)
  • NodeName: Stream Aggregate, NodeId: 2, ColumnName: Expr1003 LAST_VALUE([Expr1002]) for the LEAD(cume_weight)
0
6

Just as a curiosity (since the question states T-SQL) it is also possible to solve this problem efficiently using SQLCLR.

The idea is to read rows one at a time in turn order until the weight exceeds 1000 (or we run out of rows), then to return the last name read.

The source code is:

using Microsoft.SqlServer.Server;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;

public partial class UserDefinedFunctions
{
    [SqlFunction(DataAccess = DataAccessKind.Read,
        SystemDataAccess = SystemDataAccessKind.None,
        IsDeterministic = true, IsPrecise = true)]
    [return: SqlFacet(IsFixedLength = false, IsNullable = true, MaxSize = 255)]
    public static SqlString Elevator()
    {
        const string query =
            @"SELECT L.[name], L.[weight]
            FROM dbo.line AS L
            ORDER BY L.turn;";

        using (var con = new SqlConnection("context connection = true"))
        {
            con.Open();
            using (var cmd = new SqlCommand(query, con))
            {
                var rdr = cmd.ExecuteReader(CommandBehavior.SingleResult);
                var name = SqlString.Null;
                var total = 0;

                while (rdr.Read() && (total += rdr.GetInt32(1)) <= 1000)
                {
                    name = rdr.GetSqlString(0);
                }
                return name;
            }
        }
    }
}

The compiled assembly and T-SQL function:

CREATE ASSEMBLY Elevator AUTHORIZATION [dbo]
FROM 0x4D5A90000300000004000000FFFF0000B800000000000000400000000000000000000000000000000000000000000000000000000000000000000000800000000E1FBA0E00B409CD21B8014CCD21546869732070726F6772616D2063616E6E6F742062652072756E20696E20444F53206D6F64652E0D0D0A2400000000000000504500004C010300606C0E5B0000000000000000E00022200B013000000C000000060000000000004A2A0000002000000040000000000010002000000002000004000000000000000600000000000000008000000002000000000000030060850000100000100000000010000010000000000000100000000000000000000000F82900004F00000000400000A802000000000000000000000000000000000000006000000C000000C02800001C0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000080000000000000000000000082000004800000000000000000000002E74657874000000500A000000200000000C000000020000000000000000000000000000200000602E72737263000000A80200000040000000040000000E0000000000000000000000000000400000402E72656C6F6300000C00000000600000000200000012000000000000000000000000000040000042000000000000000000000000000000002C2A0000000000004800000002000500F0200000D007000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001B30030070000000010000117201000070730600000A0A066F0700000A723500007006730800000A0B07176F0900000A0C7E0A00000A0D1613042B0808166F0B00000A0D086F0C00000A2C14110408176F0D00000A5825130420E803000031DC091305DE14072C06076F0E00000ADC062C06066F0E00000ADC11052A011C000002001D003C59000A0000000002000B005863000A000000001E02280F00000A2A42534A4201000100000000000C00000076342E302E33303331390000000005006C000000AC010000237E0000180200002002000023537472696E677300000000380400008801000023555300C0050000100000002347554944000000D00500000002000023426C6F620000000000000002000001471502000900000000FA01330016000001000000110000000200000002000000010000000F000000050000000200000001000000020000000000E70001000000000006008A00A9010600BC00A9010600610096010F00C901000006000202F9000A0075005C010A003E005C010A0038005C010A00AA005C010A00DD00D8010A00120109020A002D0009020A00400109020A00050120010A00770113000A003301200106004D00F900000000000A00000000000100010001001000ED0100001500010001005020000000009600870150000100E820000000008618900106000200000000000000090090010100110090010600190090010A00310090010600490090010600590090011E0071000001060061009001230061004E012A005100F40031006900DA003500810028003B00810001003F0089005900060029009001060020002300860024002B00CE012E000B0055002E0013005E002E001B007D00100044000480000000000000000000000000000000008701000004000000000000000000000047001F000000000004000000000000000000000047001300000000000000000000476574496E743332003C4D6F64756C653E0053797374656D2E44617461006D73636F726C696200526561640053716C436F6D6D616E640053797374656D446174614163636573734B696E640049446973706F7361626C6500446973706F73650044656275676761626C654174747269627574650053716C46756E6374696F6E41747472696275746500436F6D70696C6174696F6E52656C61786174696F6E734174747269627574650053716C46616365744174747269627574650052756E74696D65436F6D7061746962696C6974794174747269627574650047657453716C537472696E6700456C657661746F722E646C6C004E756C6C0053797374656D004F70656E004462436F6E6E656374696F6E0053716C436F6E6E656374696F6E0053797374656D2E446174612E436F6D6D6F6E004462446174615265616465720053716C446174615265616465720045786563757465526561646572004D6963726F736F66742E53716C5365727665722E53657276657200436F6D6D616E644265686176696F7200456C657661746F72002E63746F720053797374656D2E446961676E6F73746963730053797374656D2E52756E74696D652E436F6D70696C6572536572766963657300446562756767696E674D6F6465730053797374656D2E446174612E53716C54797065730055736572446566696E656446756E6374696F6E73004F626A6563740053797374656D2E446174612E53716C436C69656E740000003363006F006E007400650078007400200063006F006E006E0065006300740069006F006E0020003D00200074007200750065000081510D000A00200020002000200020002000200020002000200020002000530045004C004500430054000D000A0020002000200020002000200020002000200020002000200020002000200020004C002E005B006E0061006D0065005D002C000D000A0020002000200020002000200020002000200020002000200020002000200020004C002E005B007700650069006700680074005D000D000A00200020002000200020002000200020002000200020002000460052004F004D002000640062006F002E006C0069006E00650020004100530020004C000D000A002000200020002000200020002000200020002000200020004F0052004400450052002000420059000D000A0020002000200020002000200020002000200020002000200020002000200020004C002E007400750072006E003B000D000A00200020002000200020002000200020002000200020002000006C68AC85076C6945BCECB2CE73B9787F000420010108032000010520010111110D0706122D123112351129081129042001010E062002010E122D0620011235113D0306112905200111290803200002042001080802060E08B77A5C561934E08904000011290801000800000000001E01000100540216577261704E6F6E457863657074696F6E5468726F7773010801000200000000008146010004005455794D6963726F736F66742E53716C5365727665722E5365727665722E446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D342E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038390A446174614163636573730100000054557F4D6963726F736F66742E53716C5365727665722E5365727665722E53797374656D446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D342E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038391053797374656D446174614163636573730000000054020F497344657465726D696E69737469630154020949735072656369736501310100030054020D497346697865644C656E6774680054020A49734E756C6C61626C65015408074D617853697A65FF00000000000000606C0E5B00000000020000001C010000DC280000DC0A000052534453F8D0A90B6069F74DB5FBFABECC9D213901000000633A5C75736572735C7061756C775C736F757263655C7265706F735C4461746162617365325C4461746162617365325C6F626A5C52656C656173655C456C657661746F722E7064620000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000202A000000000000000000003A2A00000020000000000000000000000000000000000000000000002C2A0000000000000000000000005F436F72446C6C4D61696E006D73636F7265652E646C6C0000000000FF2500200010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000000018000080000000000000000000000000000001000100000030000080000000000000000000000000000001000000000048000000584000004C02000000000000000000004C0234000000560053005F00560045005200530049004F004E005F0049004E0046004F0000000000BD04EFFE00000100000000000000000000000000000000003F000000000000000400000002000000000000000000000000000000440000000100560061007200460069006C00650049006E0066006F00000000002400040000005400720061006E0073006C006100740069006F006E00000000000000B004AC010000010053007400720069006E006700460069006C00650049006E0066006F0000008801000001003000300030003000300034006200300000002C0002000100460069006C0065004400650073006300720069007000740069006F006E000000000020000000300008000100460069006C006500560065007200730069006F006E000000000030002E0030002E0030002E00300000003A000D00010049006E007400650072006E0061006C004E0061006D006500000045006C0065007600610074006F0072002E0064006C006C00000000002800020001004C006500670061006C0043006F00700079007200690067006800740000002000000042000D0001004F0072006900670069006E0061006C00460069006C0065006E0061006D006500000045006C0065007600610074006F0072002E0064006C006C0000000000340008000100500072006F006400750063007400560065007200730069006F006E00000030002E0030002E0030002E003000000038000800010041007300730065006D0062006C0079002000560065007200730069006F006E00000030002E0030002E0030002E0030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000C0000004C3A00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
WITH PERMISSION_SET = SAFE;
GO
CREATE FUNCTION dbo.Elevator ()
RETURNS nvarchar(255)
AS EXTERNAL NAME Elevator.UserDefinedFunctions.Elevator;

Getting the result:

SELECT dbo.Elevator();
1

Slight variation from Martin Smith's solution

SELECT top 1 name
FROM (
    SELECT id, name, weight, turn
         , SUM(weight) OVER (ORDER BY turn) AS cumulative_weight
    FROM line                               
) as T
WHERE cumulative_weight <= 1000
ORDER BY turn DESC 

RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW is the default window frame so I did not declare that.

A predicate for current cumulative weight is used instead of next cumulative weight.

I haven't checked any plan so I can't tell if there is a difference in that regard.

5
  • I see, I am surrounded by DB geeks :-). I have to checkout the all the keywords you guys mention to grasp what they do. I've only taken a look at Client statistics --> Total Execution Time, not the Actual execution plan which is probably the most interesting here. As of Client Statistics your solution is a tiny bit slower then Martin's. Thanks for the additional info. Which method can be used to measure performance differences between different approaches? – Legends May 30 '18 at 4:39
  • 1
    I'm afraid my knowledge of SQL-server is very limited so I don't have much insight when it comes to what metrics to use. Martin has a db<>fiddle link in his answer, perhaps you can look at the plans there. – Lennart May 30 '18 at 5:21
  • 1
    i haven't checked the plans either but would imagine that this probably will compute the running total over the whole table and then sort the resulting rows matching the WHERE. I doubt that it will use the check constraint to know that the running total is strictly ascending and can stop early. Also in SQL Server except where the batch mode window aggregate is used specifying ROWS rather than RANGE is preferable even where there are no duplicates as the window spool is in memory not disc – Martin Smith May 30 '18 at 5:56
  • @MartinSmith, interesting. In your solution LEAD makes it possible to push the next_cume_weight < 10000 predicate inside T1 and bail out early from the index scan? I checked the plan for my query and ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW introduces a Sequence Project (Compute Scalar), operator. Needless to say I have no idea what this means:-) – Lennart May 30 '18 at 6:21
  • 1
    The index delivers the rows in the order needed by the sum, lead and top. As soon as top receives its first row it can stop requesting any more rows and the execution can stop. – Martin Smith May 30 '18 at 7:04
0

You can do a join against itself:

select 
    a.id, a.turn, a.game, 
    coalesce(sum(b.weight), 0) as cumulative_weight
from
    table a
left join 
    table b
on
    a.turn > b.turn
group by
    a.id, a.turn, a.game ;

This kind of thing is not very efficient as it causes a select per row. But at least it's expressed as a single statement.

If you don't have to do it entirely in SQL then you can simply select all the rows and loop through them, adding up as you go.

You could do the same in a stored procedure without the temp table as well. Just hold the sum and last row name in a variable.

5
  • Sorry, I don't know how to make it work with a self-join, if you could make a little reproducible example, I have added the table definition to my question. My sql is bad.... I need the name of the person closest to <=1000 lbs. – Legends May 28 '18 at 20:24
  • looks like your update works ok, you'll need to fiddle with it a bit if you want it to produce just the exact output. But like I say, its not super efficent – Ewan May 28 '18 at 20:26
  • Ok? I get null for Person with id 5... – Legends May 28 '18 at 20:27
  • that is odd, I would expect sum() to return 0 for a sum over 0 rows – Ewan May 28 '18 at 20:29
  • SUM over 0 rows is not 0 (unfortunately). You need to use COALESCE() or ISNULL() function or a CASE expression to make it 0. – ypercubeᵀᴹ May 30 '18 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.