Highly Composite SQL

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.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s