T-SQL - What's the most efficient way to loop through a table until a condition is met
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
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.
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 theSUM
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 likerows between 5 preceding and 2 following
. (or as forLEAD
later) - NodeName: Segment, NodeId: 11, ColumnName: Segment1011 Returns 1 at start of new group or null otherwise. As no
Partition By
in theSUM
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 byquery_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 howCOUNT(*)
can be 0 so will always be running sum (cume_weight
) - NodeName: Segment, NodeId: 7, ColumnName: Segment1013 No
partition by
on theLEAD
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 theLEAD
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 theLEAD(cume_weight)
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();