I’m just learning about SQL. I have this query:
SELECT div.number FROM divisors div WHERE 0 = (SELECT COUNT(*) FROM divisors t , numdivisors(div.number) djn WHERE t.number < div.number AND numdivisors(t.number) >= djn) GROUP BY div.number
Where numdivisors is defined as:
CREATE FUNCTION numdivisors(integer) RETURNS bigint AS $$ SELECT COUNT(*) FROM divisors WHERE number = $1 $$ LANGUAGE SQL;
And divisors is just a table which relates number, divisor, multiplicity in the obvious way. It stores numbers from 2 to 100 (so it has about 382 rows).
The problem is that this query takes about two seconds to run (on postgres). I don’t understand why. The equivalent Haskell (for lenient definitions of “equivalent”):
divisors :: Integer -> [(Integer, Int)] divisors n = divisors' d mul where divisors' d mul | d <= n = if n `mod` d^(mul+1) == 0 then divisors' d (n+1) else (if mul > 0 then [(d,mul)] else ) ++ divisors' (d+1) 0 | otherwise =  numDivisors :: Integer -> Int numDivisors = length . divisors filter (\div -> let nd = numDivisors div in null $ filter (\t -> numDivisors t >= nd) [2..div-1]) [2..100]
Is almost instantaneous. And if I had to make a bet, I’d say that the Haskell version is doing more work because it’s computing the divisors on the fly, too, whereas my SQL table already held them. But then it’s always hard to tell how much work Haskell is actually doing because of its laziness and my lack of understanding thereof.
How do I speed up that SQL?…
Oh, I should probably say, this query is computing the Highly Composite Numbers.