How to maintain a query that runs forever?

Question

I would like to run a query that finds prime numbers, and I would like to run it forever.

@Solomon Rutzky on this page Prime numbers in a given range , give us a good example of the Sieve of Eratosthenes.

DECLARE  @RangeStart INT = 1,
         @RangeEnd INT = 100000;
DECLARE  @HowMany INT = CEILING((@RangeEnd - @RangeStart + 1) / 2.0);

;WITH frst AS
(
    SELECT  tmp.thing1
    FROM        (VALUES (0), (0), (0), (0), (0), (0), (0), (0), (0), (0)) tmp(thing1)
), scnd AS
(
    SELECT  0 AS [thing2]
    FROM        frst t1
    CROSS JOIN frst t2
    CROSS JOIN frst t3
), base AS
(
    SELECT  TOP( CONVERT( INT, CEILING(SQRT(@RangeEnd)) ) )
            ROW_NUMBER() OVER (ORDER BY (SELECT 1)) AS [num]
    FROM        scnd s1
    CROSS JOIN  scnd s2
), nums AS
(
    SELECT  TOP (@HowMany)
            (ROW_NUMBER() OVER (ORDER BY (SELECT 1)) * 2) + 
                (@RangeStart - 1 - (@RangeStart%2)) AS [num]
    FROM        base b1
    CROSS JOIN  base b2
), divs AS
(
    SELECT  [num]
    FROM        base b3
    WHERE   b3.[num] > 4
    AND     b3.[num] % 2 <> 0
    AND     b3.[num] % 3 <> 0
)
SELECT  given.[num] AS [Prime]
FROM        (VALUES (2), (3)) given(num)
WHERE   given.[num] >= @RangeStart
UNION ALL
SELECT  n.[num] AS [Prime]
FROM        nums n
WHERE   n.[num] BETWEEN 5 AND @RangeEnd
AND     n.[num] % 3 <> 0
AND     NOT EXISTS (SELECT *
                    FROM divs d
                    WHERE d.[num] <> n.[num]
                    AND n.[num] % d.[num] = 0
                    );

So we can easily generate a list of all prime numbers from 0 to 100.

But let's say I want the query to run for the next 20 years, so I set as limit a very large number:

DECLARE  @RangeStart INT = 1,
         @RangeEnd INT = 100000000000000000000000000000000000000000000000000;

And here is where the problem comes: how can I maintain this query for the next 20 years?

Because the Sieve of Eratosthenes has a peculiarity:

If it gets interrupted you have to restart from the beginning.

So my questions start here:

• How can I manage to change the CPU, upgrade RAM, change Hard Drive, etc...
• How can I manage a failover disaster scenario in order to avoid that script to stop?
• Will the failover guarantee that the query won't stop?
• Cloud redundancy and failover to different providers (Azure / AWS / GCE) will this assure that the script won't stop?
• What if the failover is from Azure to AWS in 2 different parts of the globe? Will this failover keep the stored procedure running?

And now the Disaster Recovery part:

• Can I take a backup, let's say every month, of the status of that stored procedure, and eventually resume from that image?
• If I run the stored procedure on a virtual machine and I take snapshots, can I resume the stored procedure?

I know for sure that someone is doing this: this online database of factorized prime numbers http://factordb.com/status.php has managed to increase from 200MB (in 2014) to nearly 800MB today (2019).

Answer 1

1st thought

You have an XY Problem. You need to use an algorithm that allows you to restart from a specific point.

Code Review

• Dividend.num <=@endnum exists in two places.
  • Get rid of the 2nd one
• Divisor.num between 2 and sqrt(dividend.num) is more restrictive than Divisor.num <= @endnum`.
  • get rid of the less restrictive one.
• Since the NOT EXISTS uses the appropriate range of rows for all Dividend rows...
  • You can safely change Dividend.num <= @endnum to Dividend.num between @startnum and @endnum
• Generate T16M once will allow you to reuse the results
  • That is: make is a regular table

Algortihm Notes

Now that the SQL statement defines a RANGE...you can run for 20 years

For all numbers between A and B:

1. Chunk them up into smaller, manageable ranges.
2. Run n Chunks in parallel

Unlike the Segmented Sieve method, you are using all values for each chunk, not just known Primes.

Segmented Sieve

Required changes to implement Segmented Sieve

• the key is to use the values in the table T16M, not a CTE.
• Modify the code to DELETE the non-prime numbers in T16M. (eg DELETE FROM T16M WHERE num in ( .... ) )
• Serially run each chunk in lowest to highest order.

Notes

The lifespan of the universe (and the required amount of disk space) will probably limit you to how big of a number you can find.

Original Questions Concerns

1. Long Running System

At 40 years and still going, one of the longest running computer programs is that of Voyager 1/Voyager 2.

https://www.space.com/26041-nasa-voyager-probes-solar-system-legacy.html

Voyager employs three dual-redundant computer systems per spacecraft. https://history.nasa.gov/computers/Ch6-2.html

2. adding CPU/RAM/Disks

Adding/replacing Disks can be done via SAN system.

Hot adding physical CPU/RAM may require non-Intel equipment.

CPU and memory resources can be non-disruptively added to the system.... https://en.wikipedia.org/wiki/IBM_Z

Chunking

Oracle users can use DMBS_PARALLEL_EXECUTE to create Chunks and run them. Other RDBMS will need to implement their own API that does that.

Answer 2

It would be easier to mod the script so that it writes out either the last value, or a value every n times so that you can restart the script with the last known value in case of failure. Linux hardware is pretty reliable, I've had servers that have had over 4 year uptime but of course nothing is guaranteed.

Answer 3

Preliminary remark: There were some (now deleted) comments around the feasibility of changing to an approach, which allows to restart the on the Sieve of Eratosthenes based search for primes…

Something along the following should work:

Setting the Stage/Seed:

CREATE TABLE Prime (
    id INT NOT NULL IDENTITY PRIMARY KEY,
    prime INT NOT NULL UNIQUE
);
CREATE TABLE LastOne (
    id INT NOT NULL PRIMARY KEY
);
BEGIN TRANSACTION;
  INSERT INTO Prime (prime) VALUES (2);
  INSERT INTO LastOne VALUES (2);
COMMIT;

Be Ready To Do the Job Whenever Possible:

CREATE PROC dbo.SieveOfEratosthenes AS
DECLARE
    @nextPrimeCandidate INT = NULL
BEGIN
  SET @nextPrimeCandidate = (
    SELECT id + 1
    FROM LastOne AS Dividend
    WHERE
      (Dividend.id + 1) % 2 = 1
      AND
      NOT EXISTS (
        SELECT 1
        FROM Prime
        WHERE
          prime BETWEEN 2 AND SQRT(Dividend.id + 1)
          AND
          (Dividend.id + 1) % prime = 0
    )
  )
  ;
  BEGIN TRANSACTION
    IF (@nextPrimeCandidate IS NOT NULL)
    INSERT INTO Prime (prime) VALUES (@nextPrimeCandidate);
    UPDATE LastOne SET id = id + 1;
  COMMIT;
END;

See it in action: db<>fiddle.

N.B.: Just the idea - T-SQL is not really my cup of tea…

Please comment, if and as this requires adjustment / further detail.