Sieve of Eratosthenes in PL/SQL

Yesterday I posted an Oracle SQL query that would produce primes, but it wasn't an implementation of the Sieve of Eratosthenes. Here for your viewing pleasure discomfort is a version in Oracle PL/SQL.

create or replace package josh.sieve as
   type prime_numbers is table of number;
   function calculate ( the_end number ) return prime_numbers pipelined;
end;
/


create or replace package body josh.sieve as
   function calculate ( the_end number ) return prime_numbers pipelined is
      type bitbucket is table of boolean index by binary_integer;
      primes bitbucket;
      max_sqrt number :=floor(sqrt(the_end));
      i number:=3;
      j number:=1;
    begin
        pipe row(2);

        for i IN 1 .. the_end loop
          primes(i) := true;
        end loop;

        while i <= the_end loop
          if primes(i) then
            if(i<=max_sqrt) then
              j:=i*i;
              while j<=the_end loop
                primes(j):=false;
                j:=j+2*i;
              end loop;
            end if;

            pipe row(i);
          end if;

          i:=i+2;
        end loop;
    end;
end;
/

This is the ugliest one so far. It really burns my eyes!

What I liked
I was kind of pleased to see the pipe row(foo); functionality. This is very similar to yield in c# where I can just lazily return numbers as they are found instead of building up the whole list table in advance.

What I hated
There's a bunch here. First off, I tried to write this with a for loop, but there is no way to define the step value. I had to resort to using a while loop with an external counter variable. It also sucks that I have to define a custom type which is just a table of numbers. Finally, I didn't see a clean way to initialize a table with a size and default value.

Why it burns my eyes
I'm not digging that assignments have to have a colon-equal "foo := 42" operator. To the same tune as basic, I hate that blocks end with an end keyword. This is an especially big WTF when you consider that lines are terminated with semi-colons. The end result is a bunch of colon-ish punctuation littered with end keywords.

Regardless, I was pleased with the performance. Running a query like select count(1) from table(josh.sieve.calculate(1000000)); runs in about 600 milliseconds on our db machine. Not too shabby...

No comments yet. Be the first.

Leave a reply