Random order by performance

What is the best way to get top n rows by random order?

I use the query like:

Select top(10) field1,f开发者_运维技巧ield2 .. fieldn
from Table1
order by checksum(newid())

The problem in the above query is that it will keep getting slower as table size increases. it will always do full clustered index scan to find top(10) rows by random order.

Is there any other better way to do it?

I have tested this and got better performance changing the query.

The DDL for the table I used in my tests.

CREATE TABLE [dbo].[TestTable]
(
    [ID] [int] IDENTITY(1,1) NOT NULL,
    [Col1] [nvarchar](100) NOT NULL,
    [Col2] [nvarchar](38) NOT NULL,
    [Col3] [datetime] NULL,
    [Col4] [nvarchar](50) NULL,
    [Col5] [int] NULL,
 CONSTRAINT [PK_TestTable] PRIMARY KEY CLUSTERED 
 (
    [ID] ASC
 )
)

GO

CREATE NONCLUSTERED INDEX [IX_TestTable_Col5] ON [dbo].[TestTable] 
(
    [Col5] ASC
)

The table has 722888 rows.

First query:

select top 10
  T.ID,
  T.Col1,
  T.Col2,
  T.Col3,
  T.Col5,
  T.Col5
from TestTable as T
order by newid()

Statistics for first query:

SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 13 ms.

(10 row(s) affected)
Table 'TestTable'. Scan count 1, logical reads 12492, physical reads 14, read-ahead reads 6437, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 859 ms,  elapsed time = 1700 ms.

Execution plan first query:

Second query:

select 
  T.ID,
  T.Col1,
  T.Col2,
  T.Col3,
  T.Col5,
  T.Col5
from TestTable as T
  inner join (select top 10 ID
              from TestTable
              order by newid()) as C
    on T.ID = C.ID

Statistics for second query:

SQL Server parse and compile time: 
   CPU time = 125 ms, elapsed time = 183 ms.

(10 row(s) affected)
Table 'TestTable'. Scan count 1, logical reads 1291, physical reads 10, read-ahead reads 399, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 516 ms,  elapsed time = 706 ms.

Execution plan second query:

Summary:

The second query is using the index on Col5 to order the rows by newid() and then it does a Clustered Index Seek 10 times to get the values for the output.

The performance gain is there because the index on Col5 is narrower than the clustered key and that causes fewer reads.

Thanks to Martin Smith for pointing that out.

One way to reduce the size of the scan necessary is by using a combination of TABLESAMPLE with ORDER BY newid in order to select a random number of rows from a selection of pages in the table, rather scanning the entire table.

The idea is to calculate the average number of rows per page, then use tablesample to select 1 random page of data for each row you want to output. Then you will run the ORDER BY newid() query on just that subset of data. This approach will be slightly less random then the original approach, but is much better than just using tablesample and involves reading much less data off the table.

Unfortunately, the TABLESAMPLE clause does not accept a variable so dynamic sql is necessary in order to use a dynamic rows value based on the size of the records of the input table.

declare @factor int
select @factor=8000/avg_record_size_in_bytes from sys.dm_db_index_physical_stats(db_id(), object_id('sample'), null, null, 'detailed') where index_level = 0
declare @numRows int = 10
declare @sampledRows int = @factor * @numRows
declare @stmt nvarchar(max) = N'select top (@numRows) * from sample tablesample (' + convert(varchar(32), @sampledRows) + ' rows) order by checksum(newid())'
exec sp_executesql @stmt, N'@numRows int', @numRows

This question is 7 years old, and had no accepted answer. But it ranked high when I searched for SQL performance on selecting random rows. But none of the current answers seems to give a simple, quick solution in the case of large tables so I want to add my suggestion.

Assumptions:

• The primary key is a numeric data type (typical int / +1 per row)
• The primary key is the clustered index
• The table has many rows, and only a few should be selected

I think this is fairly common, so it would help in a lot of cases.

Given a typical set of data, my suggestion is to

1. Find max and min
2. pick a random number
3. check if the number is a valid id in the table
4. Repeat as needed

These operations should all be very fast as they all are on the clustered index. Only at the end will the rest of the data be read, by selecting a set based on a list of primary keys so we only pull in the data we actually need.

Example (MS SQL):

--
-- First, create a table with some dummy data to select from
-- 

DROP TABLE IF EXISTS MainTable
CREATE TABLE MainTable(
    Id int IDENTITY(1,1) NOT NULL,
    [Name] nvarchar(50) NULL,
    [Content] text NULL
)
GO

DECLARE @I INT = 0
WHILE @I < 40
BEGIN
    INSERT INTO MainTable VALUES('Foo', 'bar')
    SET @I=@I+1
END
UPDATE MainTable SET [Name] = [Name] + CAST(Id as nvarchar(50))

-- Create a gap in IDs at the end
DELETE FROM MainTable
    WHERE ID < 10

-- Create a gap in IDs in the middle
DELETE FROM MainTable
    WHERE ID >= 20 AND ID < 30

-- We now have our "source" data we want to select random rows from



--
-- Then we select random data from our table
-- 

-- Get the interval of values to pick random values from
DECLARE @MaxId int
SELECT @MaxId = MAX(Id) FROM MainTable

DECLARE @MinId int
SELECT @MinId = MIN(Id) FROM MainTable

DECLARE @RandomId int
DECLARE @NumberOfIdsTofind int = 10

-- Make temp table to insert ids from
DROP TABLE IF EXISTS #Ids
CREATE TABLE #Ids (Id int)

WHILE (@NumberOfIdsTofind > 0)
BEGIN
    SET @RandomId = ROUND(((@MaxId - @MinId -1) * RAND() + @MinId), 0)
    -- Verify that the random ID is a real id in the main table
    IF EXISTS (SELECT Id FROM MainTable WHERE Id = @RandomId)
    BEGIN
        -- Verify that the random ID has not already been inserted
        IF NOT EXISTS (SELECT Id FROM #Ids WHERE Id = @RandomId)
        BEGIN
            -- It's a valid, new ID, add it to the list.
            INSERT INTO #Ids VALUES (@RandomId)
            SET @NumberOfIdsTofind = @NumberOfIdsTofind - 1;
        END
    END
END

-- Select the random rows of data by joining the main table with our random Ids   
SELECT MainTable.* FROM MainTable
INNER JOIN #Ids ON #Ids.Id = MainTable.Id

No, there is no way to improve the performance here. Since you want the rows in "random" order, indexes will be useless. You could, however, try ordering by newid() instead of its checksum, but that's just an optimization to the random ordering, not the sorting itself.

The server has no way of knowing that you want a random selection of 10 rows from the table. The query is going to evaluate the order by expression for every row in the table, since it's a computed value that cannot be determined by index values. This is why you're seeing a full clustered index scan.