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