In an older thread (SQL Puzzle: Prime Numbers - my PL/SQL solution is at Answer 38) we debated whether the proper Sieve algorithm can be implemented in plain SQL. We didn't come up with a satisfactory answer at that time.
I have found a very rudimentary solution, using an idea I had for a quite different problem (Head scratcher (bug?) - seesaw recursive CTE). It is very slow: I can find the prime numbers up to 1,000 in 0.5 seconds. The PL/SQL function finds the primes up to 1,000,000 in the same amount of time.
There are a few possible reasons for the poor performance. One is that the recursive solution generates an insane number of rows (while the PL/SQL function marks numbers as "prime" or "composite" in place). On my machine, using an XE edition, there may be lots of swapping to disk - I didn't monitor this, but it is quite likely. (Not when seeking primes up to 1,000, but almost surely when seeking primes up to 1,000,000 - I can't even find the primes up to 100,000 in any reasonable amount of time). Another is the repeated joins; in the function solution, I mark numbers as composite, one at a time, by taking multiples of the most recently found prime, but in the recursive pure-SQL solution I need to do a very expensive join. Or - DO I REALLY need it? Is there another way to do that? This is my first question in this thread. Third, as in the other problem where I used this "seesaw recurrence" idea, I have to use the CYCLE clause of recursive CTE's to work around an Oracle bug - which, as discussed in the other thread, is not fixed as of Oracle 12.1. I don't know how much overhead that adds, probably not enough to matter, but anyway, it's there.
Here is the code. I am not particularly interested in implementing the Sieve in plain SQL (plain SQL may not be the best tool regardless), but perhaps I can learn a few more things from you, the reader. How can I/we improve this to make it work better?
Also, I am curious (as I was in the older thread) if this "seesaw" recurrence is something well known, or perhaps something that is well known to work poorly. (For one thing, it's the only type of recursive CTE where I ran into the infinite cycle bug.) To expand a little on the "seesaw" concept: in the Sieve algorithm, there are two steps that are repeated recursively, with quite different operations. All numbers between 2 and 1000 (say) are marked as either p(rime), c(omposite) or u(nknown). Initially all are 'u'. One kind of step is - look at all the remaining 'u' numbers; select the MIN, and mark it as 'p'(rime). The other kind of step is - take the most recently market 'p', and mark all its multiples (except itself) as 'c'(omposite). Repeat alternating these steps. In the Sieve algorithm there is also a shortcut at the end, but that is probably not something you would see in many algorithms; my interest is primarily in this recursive alternation of steps.
Anyway, here's the code so far. Thank you!
with
number_list ( x ) as (
select level + 1
from dual
connect by level <= :n_max - 1
),
rec ( x, marker, ptr, flag, ct ) as (
select x, 'u', 1, 1, 1
from number_list
union all
select r.x,
case when r.flag = - 1 and ptr > trunc(power(:n_max, 0.5)) then 'p'
when r.flag = - 1 and r.x = r.ptr then 'p'
when r.flag = - 1 and r.x > r.ptr and n.x is not null then 'c'
else 'u'
end,
case r.flag when 1 then min(r.x) over ()
else r.ptr end,
- r.flag,
ct + 1
from rec r left outer join number_list n on r.x = r.ptr * n.x
where ( r.flag = - 1 or ptr <= trunc(power(:n_max, 0.5)) ) and r.marker = 'u'
)
cycle x, marker, ptr, flag, ct set is_cycle to 'Y' default 'N'
select x
from rec
where marker = 'p'
order by x
;