No sane person would even consider using SQL Server to construct a list of prime numbers. So just to prove that I’m not sane (as if there could be any doubt!), this post will be about finding prime numbers.
First a bit of history. Ward Pond wrote about efficient ways to populate a table with one million GUIDs. I posted a comment with a slightly more efficient algorithm. And that was quickly followed by a new post from Ward, tweaking my syntax even further. And that’s when Denis the SQL Menace lived true to his name by posting this comment:
“How about the next challenge is to return all 78498 prime numbers between 1 and 1000000?”
Now of course, this is a silly challenge. Not because prime numbers are silly, mind you. They are very useful to mathematicians, and many encryption algorithms wouldn’t even be possible without (large) prime numbers. The silly part is using SQL Server, a data manipulation tool, to calculate prime numbers. If you really need them, code a quick algorithm in a C++ program. Or buy a ready-made list with the first million or so prime numbers. So I attempted to resist the challenge.
Alas – the flesh is weak. So when I saw Ward’s reply to Denis’ challenge, I was no longer able to resist temptation. After all, Ward’s attempt is not only interesting – it is also very long, and apparently (with an estimated completion time of 1 to 2 days!!) not very efficient. I decided that I should be able to outperform that.
My assumptions are that a table of numbers is already available, and that this table holds at least all numbers from 1 to 1,000,000. (Mine holds numbers from 1 to 5,764,801), and that the challenge is to create and populate a table with the prime numbers from 1 to 1,000,000, in as little speed as possible. Displaying the prime numbers is not part of the challenge. For testing purposes, I replaced the upper limit of 1,000,000 with a variable @Limit, and I set this to a mere 10,000. That saves me a lot of idle waiting time!
As a first attempt, I decided to play dumb. Just use one single set-based query that holds the definition of prime number. Here’s the SQL:
DROP TABLE dbo.Primes
go
CREATE TABLE dbo.Primes
(Prime int NOT NULL PRIMARY KEY)
go
DECLARE @Start datetime, @End datetime
SET @Start = CURRENT_TIMESTAMP
DECLARE @Limit int
SET @Limit = 10000
INSERT INTO dbo.Primes (Prime)
SELECT n1.Number
FROM dbo.Numbers AS n1
WHERE n1.Number > 1
AND n1.Number < @Limit
AND NOT EXISTS
(SELECT *
FROM dbo.Numbers AS n2
WHERE n2.Number > 1
AND n2.Number < n1.Number
AND n1.Number % n2.Number = 0)
SET @End = CURRENT_TIMESTAMP
SELECT @Start AS Start_time, @End AS End_time,
DATEDIFF(ms, @Start, @End) AS Duration,
COUNT(*) AS Primes_found, @Limit AS Limit
FROM dbo.Primes
go
--select * from dbo.Primes
go
This ran in 1,530 ms on my test system. (And in case you ask – I also tested the equivalent query with LEFT JOIN; that took 11,466 ms, so I quickly discarded it). With @Limit set to 20,000 and 40,000, execution times were 5,263 and 18,703 ms – so each time we double @Limit, execution time grows with a factor 3.5. Using this factor, I can estimate an execution time of one to two hours.
That’s a lot better than the one to two days Ward estimates for his version – but not quite fast enough for me. So I decided to try to convert the Sieve of Eratosthenes to T-SQL. This algorithm is known to be both simple and fast for getting a list of prime numbers. Here’s my first attempt:
DROP TABLE dbo.Primes
go
CREATE TABLE dbo.Primes
(Prime int NOT NULL PRIMARY KEY)
go
DECLARE @Start datetime, @End datetime
SET @Start = CURRENT_TIMESTAMP
DECLARE @Limit int
SET @Limit = 10000
-- Initial fill of sieve;
-- filter out the even numbers right from the start.
INSERT INTO dbo.Primes (Prime)
SELECT Number
FROM dbo.Numbers
WHERE (Number % 2 <> 0 OR Number = 2)
AND Number <> 1
AND Number <= @Limit
-- Set @Current to 2, since multiples of 2 have already been processed
DECLARE @Current int
SET @Current = 2
WHILE @Current < SQRT(@Limit)
BEGIN
-- Find next prime to process
SET @Current =
(SELECT TOP (1) Prime
FROM dbo.Primes
WHERE Prime > @Current
ORDER BY Prime)
DELETE FROM dbo.Primes
WHERE Prime IN (SELECT n.Number * @Current
FROM dbo.Numbers AS n
WHERE n.Number >= @Current
AND n.Number <= @Limit / @Current)
END
SET @End = CURRENT_TIMESTAMP
SELECT @Start AS Start_time, @End AS End_time,
DATEDIFF(ms, @Start, @End) AS Duration,
COUNT(*) AS Primes_found, @Limit AS Limit
FROM dbo.Primes
go
--select * from dbo.Primes
The time that Eratosthenes takes to find the prime numbers up to 10,000 is 7,750 ms – much longer than the previous version. My only hope was that the execution time would not increase with a factor of 3.5 when doubling @Limit – and indeed, it didn’t. With @Limit set to 20,000 and 40,000, execution times were 31,126 and 124,923 ms, so the factor has gone up to 4. With @Limit set to 1,000,000, I expect an execution time of 15 to 20 hours.
Time to ditch the sieve? No, not at all. Time to make use of the fact that SQL Server prefers to process whole sets at a time. Let’s look at the algorithm in more detail – after the initial INSERT that fills the sieve and removes the multiples of 2, it finds 3 as the next prime number and removes multiples of 3. It starts removing at 9 (3 squared) – so we can be pretty sure that numbers below 9 that have not yet been removed will never be removed anymore. Why process them one at a time? Why not process them all at once? That’s what the algorithm below does – on the first pass of the WHILE loop, it takes the last processed number (2), finds the first prime after that (3), then uses the square of that number (9) to define the range of numbers in the sieve that are now guaranteed to be primes. It then removes multiples of all primes in that range. And after that, it repeats the operation, this time removing multiples in the range between 11 (first prime after 9) and 121 (11 square). Let’s see how this affects performance.
DROP TABLE dbo.Primes
go
CREATE TABLE dbo.Primes
(Prime int NOT NULL PRIMARY KEY)
go
DECLARE @Start datetime, @End datetime
SET @Start = CURRENT_TIMESTAMP
DECLARE @Limit int
SET @Limit = 10000
-- Initial fill of sieve;
-- filter out the even numbers right from the start.
INSERT INTO dbo.Primes (Prime)
SELECT Number
FROM dbo.Numbers
WHERE (Number % 2 <> 0 OR Number = 2)
AND Number <> 1
AND Number <= @Limit
-- Set @Last to 2, since multiples of 2 have already been processed
DECLARE @First int, @Last int
SET @Last = 2
WHILE @Last < SQRT(@Limit)
BEGIN
-- Find next prime as start of next range
SET @First =
(SELECT TOP (1) Prime
FROM dbo.Primes
WHERE Prime > @Last
ORDER BY Prime)
-- Range to process ends at square of starting point
SET @Last = @First * @First
DELETE FROM dbo.Primes
WHERE Prime IN (SELECT n.Number * p.Prime
FROM dbo.Primes AS p
INNER JOIN dbo.Numbers AS n
ON n.Number >= p.Prime
AND n.Number <= @Limit / p.Prime
WHERE p.Prime >= @First
AND p.Prime < @Last)
END
SET @End = CURRENT_TIMESTAMP
SELECT @Start AS Start_time, @End AS End_time,
DATEDIFF(ms, @Start, @End) AS Duration,
COUNT(*) AS Primes_found, @Limit AS Limit
FROM dbo.Primes
go
--select * from dbo.Primes
The time taken for the 1,229 primes between 1 and 10,000? A mere 266 ms!! With execution times like that, I saw no need to rely on extrapolation – I set @Limit to 1,000,000, hit the Execute button, sat back – and get the following result after 19 seconds:
Start_time End_time Duration Primes_found Limit
----------------------- ----------------------- ----------- ------------ -----------
2006-09-24 00:42:22.780 2006-09-24 00:42:41.750 18970 78498 1000000
From 1-2 days to just under 20 seconds – and this time, I didn’t even have to add an index!
Finally, to top things off, I tried one more thing. I have often read that SQL Server won’t optimize an IN clause as well as an EXISTS clause, especially if the subquery after IN returns a lot of rows – which is definitely the case here. So I rewrote the DELETE statement in the heart of the WHILE loop to read like this:
DELETE FROM dbo.Primes
WHERE EXISTS
(SELECT *
FROM dbo.Primes AS p
INNER JOIN dbo.Numbers AS n
ON n.Number >= p.Prime
AND n.Number <= @Limit / p.Prime
WHERE p.Prime >= @First
AND p.Prime < @Last
AND Primes.Prime = n.Number * p.Prime)
And here are the results:
Start_time End_time Duration Primes_found Limit
----------------------- ----------------------- ----------- ------------ -----------
2006-09-24 00:47:42.797 2006-09-24 00:48:01.903 19106 78498 1000000
Which just goes to prove that you shouldn’t believe everything you read, I guess.
No comments:
Post a Comment