分页性能，可自定义排序数百万行
Jus*_*tin 19 sql-server t-sql sorting paging
在我们的应用程序中，我们有一个网格，用户可以在其中翻阅大量记录（10-2000 万）。网格支持在多列 (20+) 中按升序和降序排序。许多值也不是唯一的，因此应用程序还按 id 排序作为决胜局，以确保行始终出现在同一页面上。例如，如果用户想要按小部件大小（从最大的开始）排序，应用程序会生成一个看起来像这样的查询：
SELECT TOP 30
* -- (Pretend that there is a list of columns here)
FROM Test
-- WHERE widgetSize > 100
ORDER BY
widgetSize DESC,
id ASC
此查询需要大约 15 秒才能运行（使用缓存数据），主要成本似乎是按小部件大小对大约 130 万行进行排序。在尝试调整此查询时，我发现如果我添加一个WHERE仅限于最大 widgetSizes的子句（在上面的查询中注释掉），则查询只需要约 800 毫秒（所有前 50,000 个结果的小部件大小都大于 100） .
为什么没有WHERE子句的查询速度会如此之慢？我检查了 widgetSize 列的统计数据，它们显示前 739 行的 WidgetSize > 506。由于只需要 30 行，SQL Server 可以不使用此信息来推断它只需要对具有小部件大小的行进行排序哪个大？
我知道我可以通过在和上添加索引来使这个特定查询更快地执行，但是这个索引只在这个特定场景中有用，并且如果（例如）用户反转排序方向就变得毫无价值。该表包含许多附加列，并且每个索引都很大（~200mb），因此我无法为每个可能的排序顺序添加索引。widgetSizeid
有什么方法可以让这些查询查询执行而不为每个可能的排序顺序添加索引？（用户可以按 20 多列中的任何一列进行排序）
以下脚本创建上表并用一些代表性数据填充它。该表比实际表窄得多，但仍然展示了我所看到的性能。在我的 PC 上，带有 where 子句的查询需要约 200 毫秒，而没有 where caluse 的查询需要约 800 毫秒。
警告：运行此脚本后生成的数据库大小约为 2Gb。
CREATE TABLE Test
(
id INT NOT NULL IDENTITY(1,1) PRIMARY KEY,
widgetSize INT NOT NULL
)
CREATE TABLE #Data
(
widgetSize INT NOT NULL,
recordCount INT NOT NULL
)
INSERT INTO #Data (widgetSize, recordCount)
VALUES
(40826,1),
(30317,1),
(28513,1),
(24255,1),
(20247,1),
(20245,1),
(16445,1),
(15719,1),
(8489,1),
(8486,1),
(4753,1),
(4424,1),
(4409,1),
(3738,1),
(3732,1),
(3725,4),
(3691,1),
(3678,1),
(3655,1),
(3653,3),
(3575,1),
(3572,1),
(3569,1),
(2919,1),
(2903,1),
(2804,1),
(2795,1),
(2765,1),
(2732,1),
(2731,1),
(2677,1),
(2631,1),
(2624,1),
(2548,1),
(2544,1),
(2531,2),
(2516,3),
(2512,1),
(2503,1),
(2502,1),
(2472,1),
(2467,2),
(2460,1),
(2452,1),
(2442,2),
(2439,1),
(2412,1),
(2411,1),
(2405,1),
(2382,1),
(2375,1),
(2348,1),
(2341,1),
(2322,1),
(2321,1),
(2316,1),
(2314,1),
(2291,1),
(2284,1),
(2258,1),
(2251,1),
(2232,1),
(2229,7),
(2222,1),
(2204,1),
(2186,1),
(2173,1),
(2145,2),
(2143,1),
(2113,2),
(2110,1),
(2089,1),
(2082,1),
(2080,1),
(2056,1),
(2054,1),
(2052,1),
(2019,1),
(1991,2),
(1900,1),
(1870,1),
(1869,1),
(1856,1),
(1826,1),
(1802,1),
(1792,1),
(1786,1),
(1784,1),
(1781,1),
(1780,1),
(1771,1),
(1758,1),
(1756,1),
(1749,2),
(1742,1),
(1740,2),
(1729,1),
(1728,1),
(1726,1),
(1718,1),
(1717,1),
(1707,1),
(1701,2),
(1696,1),
(1694,1),
(1688,1),
(1679,1),
(1649,2),
(1632,1),
(1621,1),
(1616,1),
(1588,2),
(1584,1),
(1554,2),
(1539,1),
(1525,1),
(1516,1),
(1515,1),
(1476,1),
(1467,1),
(1463,2),
(1406,1),
(1390,1),
(1370,1),
(1350,1),
(1338,1),
(1335,2),
(1326,1),
(1325,1),
(1316,2),
(1315,1),
(1311,3),
(1308,1),
(1305,1),
(1302,1),
(1299,1),
(1298,1),
(1285,1),
(1283,1),
(1282,1),
(1270,1),
(1261,1),
(1255,1),
(1251,1),
(1250,1),
(1242,1),
(1220,1),
(1219,1),
(1217,1),
(1216,1),
(1193,1),
(1190,1),
(1164,2),
(1147,1),
(1137,3),
(1134,2),
(1133,1),
(1128,2),
(1120,1),
(1113,1),
(1105,1),
(1099,6),
(1098,1),
(1096,2),
(1095,2),
(1092,3),
(1082,1),
(1061,2),
(1050,1),
(1040,1),
(1007,1),
(987,1),
(966,1),
(960,1),
(954,1),
(952,1),
(951,1),
(950,1),
(924,1),
(923,2),
(917,1),
(916,2),
(907,2),
(902,1),
(900,1),
(896,1),
(892,1),
(889,1),
(879,2),
(876,1),
(874,3),
(868,2),
(861,8),
(860,2),
(854,4),
(853,1),
(852,1),
(851,6),
(847,1),
(846,1),
(843,13),
(839,3),
(838,1),
(837,3),
(825,3),
(824,1),
(820,1),
(819,1),
(818,5),
(817,9),
(814,2),
(811,13),
(809,1),
(807,1),
(804,4),
(798,4),
(795,1),
(794,7),
(791,2),
(789,2),
(788,2),
(782,7),
(778,1),
(770,1),
(769,3),
(768,1),
(763,2),
(760,1),
(756,6),
(755,5),
(753,5),
(751,1),
(748,1),
(747,3),
(746,2),
(745,1),
(744,2),
(743,3),
(742,2),
(741,3),
(737,3),
(735,1),
(734,1),
(733,2),
(731,2),
(730,1),
(728,1),
(727,2),
(726,1),
(724,1),
(721,1),
(718,2),
(714,3),
(710,1),
(707,8),
(706,2),
(703,1),
(697,3),
(696,2),
(692,2),
(686,1),
(684,1),
(683,1),
(680,2),
(678,2),
(674,2),
(672,2),
(671,1),
(669,1),
(668,2),
(667,2),
(666,1),
(665,1),
(663,3),
(662,1),
(661,2),
(658,1),
(657,2),
(656,1),
(655,1),
(654,2),
(652,2),
(651,1),
(650,3),
(649,4),
(644,3),
(643,1),
(642,1),
(641,1),
(637,2),
(636,1),
(632,1),
(631,1),
(630,1),
(629,3),
(627,1),
(625,2),
(624,2),
(623,1),
(620,1),
(618,5),
(617,3),
(616,1),
(615,2),
(614,2),
(612,7),
(605,2),
(603,5),
(601,3),
(595,1),
(594,1),
(593,1),
(590,1),
(588,6),
(587,3),
(586,3),
(583,1),
(582,1),
(580,3),
(578,1),
(577,2),
(576,1),
(575,2),
(574,2),
(573,1),
(572,2),
(571,3),
(570,1),
(569,1),
(568,2),
(567,4),
(566,4),
(565,2),
(564,2),
(563,2),
(562,1),
(560,1),
(559,2),
(558,1),
(557,3),
(556,3),
(555,2),
(554,3),
(553,1),
(552,4),
(551,4),
(550,1),
(549,3),
(548,2),
(547,2),
(546,8),
(544,1),
(543,3),
(542,8),
(541,1),
(538,8),
(536,1),
(534,1),
(533,2),
(532,1),
(531,1),
(530,1),
(529,11),
(528,1),
(527,3),
(526,1),
(525,2),
(524,5),
(523,3),
(522,1),
(521,2),
(520,5),
(518,12),
(517,5),
(515,5),
(514,3),
(513,1),
(511,16),
(510,6),
(509,1),
(508,2),
(507,1),
(506,41),
(505,2),
(504,7),
(503,7),
(502,3),
(501,3),
(500,8),
(499,1),
(498,4),
(497,6),
(496,10),
(495,8),
(494,4),
(493,5),
(492,3),
(491,3),
(490,6),
(489,6),
(488,2),
(487,3),
(486,4),
(485,6),
(484,2),
(483,5),
(482,12),
(481,3),
(480,9),
(479,10),
(478,6),
(477,5),
(476,19),
(475,5),
(474,4),
(473,3),
(472,3),
(471,8),
(470,5),
(469,11),
(468,2),
(467,1),
(466,5),
(465,9),
(464,13),
(463,10),
(462,5),
(461,12),
(460,1),
(459,5),
(458,3),
(457,1),
(456,13),
(455,3),
(454,11),
(453,5),
(452,6),
(451,20),
(450,51),
(449,12),
(448,8),
(447,6),
(446,6),
(445,6),
(444,16),
(443,80),
(442,5),
(441,10),
(440,5),
(439,12),
(438,14),
(437,58),
(436,2),
(435,13),
(434,7),
(433,5),
(432,16),
(431,7),
(430,30),
(429,21),
(428,6),
(427,18),
(426,2),
(425,7),
(424,21),
(423,11),
(422,4),
(421,8),
(420,8),
(419,7),
(418,15),
(417,9),
(416,22),
(415,6),
(414,22),
(413,10),
(412,15),
(411,9),
(410,68),
(409,62),
(408,5),
(407,7),
(406,12),
(405,12),
(404,8),
(403,8),
(402,31),
(401,24),
(400,11),
(399,3),
(398,16),
(397,19),
(396,6),
(395,18),
(394,3),
(393,2),
(392,18),
(391,20),
(390,14),
(389,12),
(388,26),
(387,14),
(386,27),
(385,23),
(384,25),
(383,25),
(382,21),
(381,69),
(380,14),
(379,34),
(378,41),
(377,24),
(376,27),
(375,13),
(374,35),
(373,32),
(372,43),
(371,28),
(370,30),
(369,27),
(368,21),
(367,23),
(366,36),
(365,45),
(364,42),
(363,82),
(362,16),
(361,33),
(360,29),
(359,15),
(358,19),
(357,17),
(356,29),
(355,11),
(354,18),
(353,29),
(352,5),
(351,6),
(350,9),
(349,17),
(348,11),
(347,17),
(346,16),
(345,20),
(344,15),
(343,14),
(342,19),
(341,7),
(340,13),
(339,13),
(338,23),
(337,13),
(336,15),
(335,9),
(334,6),
(333,10),
(332,30),
(331,22),
(330,21),
(329,13),
(328,8),
(327,10),
(326,50),
(325,16),
(324,18),
(323,17),
(322,26),
(321,18),
(320,24),
(319,18),
(318,20),
(317,6),
(316,19),
(315,17),
(314,14),
(313,39),
(312,29),
(311,23),
(310,21),
(309,27),
(308,27),
(307,14),
(306,19),
(305,27),
(304,42),
(303,29),
(302,38),
(301,47),
(300,19),
(299,9),
(298,14),
(297,46),
(296,11),
(295,20),
(294,20),
(293,16),
(292,23),
(291,27),
(290,35),
(289,20),
(288,15),
(287,21),
(286,22),
(285,33),
(284,24),
(283,11),
(282,25),
(281,17),
(280,47),
(279,22),
(278,15),
(277,26),
(276,18),
(275,20),
(274,29),
(273,53),
(272,28),
(271,17),
(270,20),
(269,30),
(268,15),
(267,40),
(266,143),
(265,35),
(264,11),
(263,30),
(262,32),
(261,39),
(260,52),
(259,96),
(258,31),
(257,18),
(256,35),
(255,52),
(254,24),
(253,35),
(252,64),
(251,34),
(250,21),
(249,45),
(248,52),
(247,64),
(246,131),
(245,108),
(244,36),
(243,34),
(242,45),
(241,50),
(240,38),
(239,57),
(238,55),
(237,62),
(236,31),
(235,82),
(234,43),
(233,40),
(232,43),
(231,58),
(230,38),
(229,38),
(228,38),
(227,69),
(226,23),
(225,54),
(224,90),
(223,91),
(222,60),
(221,277),
(220,70),
(219,33),
(218,42),
(217,100),
(216,185),
(215,98),
(214,108),
(213,57),
(212,54),
(211,77),
(210,150),
(209,175),
(208,46),
(207,199),
(206,158),
(205,68),
(204,85),
(203,129),
(202,75),
(201,59),
(200,73),
(199,123),
(198,72),
(197,155),
(196,193),
(195,66),
(194,119),
(193,119),
(192,80),
(191,80),
(190,96),
(189,284),
(188,108),
(187,79),
(186,118),
(185,93),
(184,92),
(183,194),
(182,152),
(181,96),
(180,134),
(179,108),
(178,121),
(177,91),
(176,140),
(175,262),
(174,159),
(173,121),
(172,134),
(171,118),
(170,116),
(169,168),
(168,297),
(167,171),
(166,214),
(165,474),
(164,176),
(163,131),
(162,215),
(161,310),
(160,175),
(159,183),
(158,208),
(157,377),
(156,248),
(155,804),
(154,452),
(153,133),
(152,224),
(151,826),
(150,299),
(149,367),
(148,427),
(147,413),
(146,1190),
(145,796),
(144,450),
(143,334),
(142,308),
(141,707),
(140,580),
(139,601),
(138,403),
(137,351),
(136,411),
(135,547),
(134,528),
(133,506),
(132,306),
(131,485),
(130,419),
(129,832),
(128,1034),
(127,894),
(126,1168),
(125,313),
(124,787),
(123,1079),
(122,984),
(121,1086),
(120,1525),
(119,1007),
(118,539),
(117,1596),
(116,1307),
(115,2081),
(114,1256),
(113,2200),
(112,1184),
(111,535),
(110,1404),
(109,1219),
(108,1675),
(107,1765),
(106,1784),
(105,890),
(104,931),
(103,1769),
(102,1720),
(101,1528),
(100,1639),
(99,1955),
(98,1434),
(97,979),
(96,2295),
(95,2516),
(94,3043),
(93,2972),
(92,3493),
(91,1873),
(90,1047),
(89,2228),
(88,2328),
(87,1804),
(86,5243),
(85,2256),
(84,1602),
(83,898),
(82,2025),
(81,2207),
(80,2559),
(79,2720),
(78,3302),
(77,5410),
(76,994),
(75,2767),
(74,3343),
(73,3951),
(72,4116),
(71,6164),
(70,2992),
(69,2066),
(68,18269),
(67,13159),
(66,13142),
(65,7387),
(64,8759),
(63,4887),
(62,1847),
(61,10239),
(60,6990),
(59,8785),
(58,8161),
(57,10081),
(56,4899),
(55,1744),
(54,9916),
(53,8713),
(52,9529),
(51,8827),
(50,10255),
(49,6392),
(48,2253),
(47,9939),
(46,12083),
(45,12103),
(44,12667),
(43,19758),
(42,9699),
(41,5450),
(40,26566),
(39,41836),
(38,48441),
(37,49562),
(36,71987),
(35,32390),
(34,7159),
(33,179598),
(32,158675),
(31,132676),
(30,151839),
(29,139014),
(28,632065),
(27,7800),
(26,259440),
(25,215240),
(24,170986),
(23,157141),
(22,167304),
(21,20408),
(20,11949),
(19,267541),
(18,208096),
(17,174708),
(16,156445),
(15,153569),
(14,73937),
(13,73821),
(12,310246),
(11,231829),
(10,179047),
(9,145506),
(8,133433),
(7,108736),
(6,73381),
(5,84825),
(4,86641),
(3,86172),
(2,87690),
(1,148110),
(0,7960761),
(-1,861),
(-2,365),
(-3,356),
(-4,578),
(-5,293),
(-6,310),
(-7,414),
(-8,748),
(-9,113),
(-10,782),
(-11,705),
(-12,711),
(-13,915),
(-14,539),
(-15,70),
(-16,21),
(-17,40),
(-18,56),
(-19,52),
(-20,34),
(-21,46),
(-22,20),
(-23,10),
(-24,24),
(-25,44),
(-26,18),
(-27,13),
(-28,4),
(-29,3),
(-30,6),
(-31,2),
(-58,1),
(-59,13),
(-60,2),
(-61,2),
(-64,1),
(-70,1),
(-97,1),
(-145,1),
(-234,1),
(-239,2),
(-240,2),
(-272,2),
(-273,1),
(-274,1),
(-276,4),
(-1094,1),
(-1096,1),
(-1337,1),
(-1341,1),
(-3545,1),
(-3547,1),
(-10962,1),
(-10964,1),
(-255449,1),
(-255470,1),
(-365104,1),
(-365105,1)
DECLARE c CURSOR FOR
SELECT widgetSize, recordCount FROM #Data
OPEN c
DECLARE @widgetSize INT
DECLARE @rowCount INT
FETCH NEXT FROM c INTO @widgetSize, @rowCount
WHILE @@FETCH_STATUS = 0
BEGIN
;WITH cte AS
(
SELECT rowNumber = 1
UNION ALL
SELECT rowNumber + 1
FROM cte
WHERE rowNumber < @rowCount
)
INSERT INTO Test
(
widgetSize
)
SELECT
@widgetSize
FROM cte
OPTION (MAXRECURSION 0)
FETCH NEXT FROM c INTO @widgetSize, @rowCount
END
CLOSE c
DEALLOCATE c
DROP TABLE #Data
CREATE STATISTICS WidgetSize
ON Test (WidgetSize) WITH FULLSCAN
Pau*_*ite 15
此类问题没有神奇的解决方案。为了避免潜在的昂贵排序，必须有一个索引可以提供请求的顺序（并且优化器必须选择使用该索引）。在没有支持索引的情况下，SQL Server 本身可以做的最好的事情是WHERE在对结果集进行排序之前限制符合条件的行（基于子句）。如果没有WHERE子句，这意味着对表中的所有行进行排序。
我检查了 widgetSize 列的统计数据，它们显示前 739 行的 WidgetSize > 506
该语句中的“前 739”行大概是指统计直方图中的第一个条目，按 排序RANGE_HI_KEY。直方图建立在有序流上（使用排序）。不会保留有关这些行在表中的位置的信息。即使在表扫描中首先遇到这些行，引擎也别无选择，只能完全完成扫描以确保它不会遇到排序更高的值。
由于只需要 30 行，SQL Server 是否可以不使用此信息来推断它只需要对小部件大小较大的行进行排序？
要找到最大的 30 行，SQL Server 必须检查每一行（限定WHERE子句）。SQL Server 无法选择符合“足够大”条件的任意“最小值”，即使选择了，它也无法在没有适当索引的情况下定位这些行。
事实上，Top N Sort where N <= 100 确实使用了一种替换策略，其中只有大于当前最小值的传入值才会放置在排序缓冲区中，但与从表中读取行的成本相比，这是一个次要的优化并将它们传递给排序。
原则上，引擎可以将动态过滤器（基于排序缓冲区中的当前最小值）下推到表扫描中，以尽早限制行，但这并未实现。为了解决这个问题，一个类似的想法包括在不同的值上创建一个索引视图，widgetSize其中的行数与每个值匹配：
CREATE VIEW dbo.WidgetSizes
WITH SCHEMABINDING
AS
SELECT
T.widgetSize,
NumRows = COUNT_BIG(*)
FROM dbo.Test AS T
GROUP BY
T.widgetSize;
GO
CREATE UNIQUE CLUSTERED INDEX CUQ_WidgetSizes_widgetSize
ON dbo.WidgetSizes (widgetSize);
widgetSize如果不同值相对较少（示例数据就是这种情况），则此索引视图将比等效的非聚集索引小得多。然后可以使用此信息来评估widgetSize要过滤的最小值，同时仍保证至少会找到 30 行。
第一页
对于 30 行的第一页，实现如下所示：
DECLARE
@TopRows bigint = 30,
@Minimum integer;
SELECT TOP (1)
@Minimum = Filtered.widgetSize
FROM
(
SELECT * FROM
(
SELECT
WS.widgetSize,
WS.NumRows,
-- SQL Server 2012 or later
SumNumRows = SUM(WS.NumRows) OVER (
ORDER BY WS.widgetSize DESC)
FROM dbo.WidgetSizes AS WS WITH (NOEXPAND)
) AS RunningTotal
WHERE
RunningTotal.SumNumRows >= @TopRows
) AS Filtered
ORDER BY
Filtered.SumNumRows ASC;
SELECT TOP (@TopRows)
T.id,
T.widgetSize
FROM dbo.Test AS T
WHERE T.widgetSize >= @Minimum
ORDER BY
T.widgetSize DESC,
T.id ASC;
执行计划：
这显着缩短了执行时间，大部分剩余成本与表扫描和下推过滤器相关。通过创建非聚集列存储索引（SQL Server 2012 以后）可以进一步提高性能：
CREATE NONCLUSTERED COLUMNSTORE INDEX
NCCI_Test_id_widgetSize
ON dbo.Test (id, widgetSize);
在我的笔记本电脑上，在列存储索引上以批处理模式执行扫描和过滤将执行时间从大约 300 毫秒减少到仅 20毫秒：
下一页
第一页查询返回的最后一行有widgetSize = 2903和id = 327：
查找接下来的 30 行（第 2 页）只需要对之前的查询进行简单的修改：
DECLARE
@TopRows bigint = 30,
@Minimum integer;
SELECT TOP (1)
@Minimum = Filtered.widgetSize
FROM
(
SELECT * FROM
(
SELECT
WS.widgetSize,
WS.NumRows,
SumNumRows = SUM(WS.NumRows) OVER (
ORDER BY WS.widgetSize DESC)
FROM dbo.WidgetSizes AS WS WITH (NOEXPAND)
WHERE
-- Added
WS.widgetSize < 2903
) AS RunningTotal
WHERE
RunningTotal.SumNumRows >= @TopRows
) AS Filtered
ORDER BY
Filtered.SumNumRows ASC;
SELECT TOP (@TopRows)
T.id,
T.widgetSize
FROM dbo.Test AS T
WHERE
T.widgetSize >= @Minimum
AND
(
-- Added
T.widgetSize < 2903
OR (widgetSize = 2903 AND id > 327)
)
ORDER BY
T.widgetSize DESC,
T.id ASC;
这产生与原始查询的明显扩展相同的结果：
SELECT TOP 30
* -- (Pretend that there is a list of columns here)
FROM Test
WHERE widgetSize < 2903
OR (widgetSize = 2903 AND id > 327)
ORDER BY
widgetSize DESC,
id ASC;
利用在索引视图和非聚集列存储索引完成查询为25ms，与原来的2000毫秒以上比较。
传统索引解决方案
或者，如果您要创建（最小的、非覆盖的）非聚集索引来支持最常见的排序请求，那么查询优化器很可能会使用它们来满足TOP (30)查询。索引压缩可用于最小化这些附加索引的大小。
代替您，我会退后一步并质疑要求。您的方钉只会略微适合圆形整体。
考虑过滤和搜索，而不是排序和分页。对于后端更好，并为更好的为用户。没有人是真正经柱美孚排序并导航到312页的搜索广告的强与10万行的交互是一个如此好得多UX比喻。
您可以询问如何根据数据库（列存储）中的任意条件构建高效的搜索和过滤，但大多数情况下，实现只是从数据库外部（Lucene、Sphinx 等）进行搜索。