In our application we have a grid where users can page over a large number of records (10-20 million). The grid supports sorting in ascending and descending order in a number of columns (20+). Many of the values are also not unique and so the application also sorts by id as a tie-breaker to make sure that rows always appear on the same page. As an example, should the user want to sort by widget size (starting with the largest), the application generates a query that looks a bit like this:
SELECT TOP 30
* -- (Pretend that there is a list of columns here)
FROM Test
-- WHERE widgetSize > 100
ORDER BY
widgetSize DESC,
id ASC
This query takes ~15s to run (with cached data), the major of the cost appears to be sorting ~1.3m rows by widgetSize. In an attempt to tune this query I discovered that if I add in a WHERE
clause restricted to just the largest widgetSizes(commented out in the above query) the query takes just ~800ms (all of the top 50,000 results have a widget size > 100).
Why is the query without the WHERE
clause so much slower? I've checked the statistics on the widgetSize column and they show that the top 739 rows have a WidgetSize > 506. As only 30 rows are required can SQL server not use this information to deduce that it only needs to sort rows with a widget size which is large?
I know that I can make this specific query perform quicker by adding in an index on widgetSize
and id
, however this index is only useful in this specific scenario, and becomes worthless if (for example) the user reverses the sort direction. This table contains many additional columns and each index is large (~200mb) so I can't really afford to add an index for every possible sort order.
Is there some way I can get these queries query to perform without adding an index for every possible sort order? (the user can sort by any one of 20+ columns)
The following script creates the above table and populates it with some representative data. The table is far narrower than the actual table, however still demonstrates the performance that I am seeing. On my PC the query with the where clause takes ~200ms while the query without the where caluse takes ~800ms.
Warning: The resulting database after running this script is ~2Gb in size.
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
Best Answer
There is no magic solution to this type of problem. To avoid a potentially expensive sort, there has to be an index that can provide the requested order (and the optimizer must choose to use that index). Without a supporting index, the best SQL Server can do natively is to restrict the qualifying rows (based on the
WHERE
clause) before sorting the resulting set. Without aWHERE
clause, this means sorting all the rows in the table.The 'top 739' rows in that statement presumably refers to the first entries in the statistics histogram, ordered by
RANGE_HI_KEY
. The histogram is built on an ordered stream (using a sort). No information is kept about where those rows are in the table. Even if those rows are encountered first in the table scan, the engine has no option but to fully complete the scan to ensure it doesn't encounter values that sort higher.To find the 30 largest rows, SQL Server has to check every single row (that qualifies the
WHERE
clause). There is no way for SQL Server to pick an arbitrary 'minimum value' that qualifies as 'large enough', and even if it did, it couldn't locate those rows without the appropriate index.In fact, Top N Sort where N <= 100 does use a replacement strategy where only incoming values that are larger than the current minimum are placed in the sort buffer, but this is a minor optimization compared to the cost of reading rows from the table and passing them to the sort.
In principle, the engine could push a dynamic filter (on the current minimum value present in the sort buffer) down into the table scan, to restrict rows as early as possible, but this is not implemented. To work around this, a similar idea involves creating an indexed view over the distinct values of
widgetSize
with the number of rows matching each value:This indexed view will be much smaller than an equivalent nonclustered index on
widgetSize
if there are relatively few distinct values (as is the case with the sample data). This information can then be used to assess which minimumwidgetSize
to filter on, while still guaranteeing there will be at least 30 rows found.First page
For the first page of 30 rows, the implementation looks like this:
Execution plans:
This improves execution time markedly, with most of the remaining cost associated with the table scan and pushed-down filter. Performance can be improved further by creating a nonclustered column-store index (SQL Server 2012 onward):
On my laptop, performing the scan and filter in batch mode on the column-store index reduced execution time from around 300ms to just 20ms:
Next page
The last row returned by the first-page query has
widgetSize = 2903
andid = 327
:Finding the next 30 rows (page 2) requires only simple modifications to the previous query:
This produces the same results as the obvious extension of the original query:
The query using the indexed view and nonclustered column-store index completes in 25ms, compared with over 2000ms for the original.
Traditional index solution
Alternatively, if you were to create (minimal, non-covering) nonclustered indexes to support the most common ordering requests, the chances are quite good that the query optimizer will use them to satisfy the
TOP (30)
query. Index compression could be used to minimize the size of these additional indexes.