-2

I have an interesting question and I cannot find a reply.

I would like to create a database of prime numbers. On this page Prime numbers in a given range , I can find various examples of SQL code that can help me out reach the goal thanks to the Sieve of Eratosthenes.

So if I run this code:

CREATE PROC dbo.PrintPrimeNumbers
    @startnum int,
    @endnum int
AS 
WITH 
     t4 AS (SELECT n FROM (VALUES(0),(0),(0),(0)) t(n))
    ,t256 AS (SELECT 0 AS n FROM t4 AS a CROSS JOIN t4 AS b CROSS JOIN t4 AS c CROSS JOIN t4 AS d)
    ,t16M AS (SELECT ROW_NUMBER() OVER (ORDER BY (a.n)) AS num FROM t256 AS a CROSS JOIN t256 AS b CROSS JOIN t256 AS c)
SELECT num
FROM t16M AS Dividend
WHERE
    Dividend.num <= @endnum
    AND NOT EXISTS(
        SELECT 1
        FROM t16M AS Divisor
        WHERE
            Divisor.num <= @endnum
            AND Divisor.num BETWEEN 2 AND SQRT(Dividend.num)
            AND Dividend.num % Divisor.num = 0
            AND Dividend.num <= @endnum
    );
GO
EXEC dbo.PrintPrimeNumbers 1, 100;
GO

I 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:

EXEC dbo.PrintPrimeNumbers 1, 1000000000000000000000000000000000000000000000000000000000...;

The query will start and will run... let's say for the next 20 years.

But 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 stored procedure 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?
  • 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).

enter image description here

  • 3
    Why would you do this in a database rather than a more appropriate solution like C++? I suspect this is likely a hypothetical example to the general question How to maintain a Database with stored procedure that runs forever? the answer of which is, you're doing it wrong as long running transactions are detrimental in nature in regards to RDBMS platforms. – John Eisbrener Dec 3 '19 at 19:22
  • @JohnEisbrener, of course, C++, Python, Java, whatever... is a valid option for me. But still the question remain: can we pause that process and restart it? How can we maintain a server that needs to be always ON and cannot be turned OFF not even for milliseconds? We cannot resume the Sieve not even if it's written in C++ as far as I know – Francesco Mantovani Dec 4 '19 at 9:56
4
+50

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 thanDivisor.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

Thanks to LowlyDBA for URL.

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

  1. 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.

| improve this answer | |
  • where is LowlyDBA's URL? I never heard about the Segmented Sieve, you teach me something, thank you. I wasn't expecting that editing code would have been an option (stackoverflow.com/questions/10249378/…). I will investigate and let you know – Francesco Mantovani Dec 4 '19 at 9:52
  • your reply added a new option for me. IBM Z is definitely the reply and just for that you deserve the 50 points. BTW, from your experience, do you think a simple snapshot of a VM would not interrupt the process? I'm buying some hardware and I will test myself but have you ever had experience around this? What if I commit an update that modify the DB and I take a snapshot during the commitment? Will the backup be corrupted? Thank you – Francesco Mantovani Dec 4 '19 at 10:11
4

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.

| improve this answer | |
  • thank you but the Sieve of Eratosthenes needs to restart from 0. math.stackexchange.com/questions/2257023/… you cannot say "please restart from here". But nice idea, thank you! – Francesco Mantovani Nov 29 '19 at 14:18
  • 1
    @FrancescoMantovani maybe you should ask a different question about how to modify the code. – James Jenkins Dec 3 '19 at 19:21
  • Sorry @JamesJenkins, apparently we can modify the code as Michael is saying. But if we have to focus on my main question: is virtualisation a valid options? I'm buying hardware and I will create a lab at home to see if VM are an option for a process that n ever stop. Then I will also take Michael solution as an option. – Francesco Mantovani Dec 4 '19 at 9:58
0

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.