This is a classic problem and the classic solution, which runs on all versions of SQL Server, turns out to be quite fast.

--===== Create the test data.

-- This is NOT a part of the solution.

-- We're just building the test data table

-- to look as expected.

SELECT ID = Number

INTO #YourTable

FROM master.dbo.spt_values

WHERE Type = 'P'

AND Number %100 = 0

;

--===== Add the expected clustered index.

-- This is also NOT a part of the solution.

-- We're just building the test data table

-- to look as expected.

ALTER TABLE #YourTable

ADD PRIMARY KEY CLUSTERED (ID)

;

--===== This is the classic solution that will work on all versions of

-- SQL Server and is very fast in the presence of the correct index.

SELECT ID, MID = (SELECT TOP 1 ID FROM #YourTable t2 WHERE t2.ID < t1.ID ORDER BY t1.ID DESC)

FROM #YourTable t1

;

{EDIT} If you compare the code above to Sean's good code, it also demonstrates that APPLY isn't much more than a sophisticated correlated sub-query.