Could someone explain to me how this SQL query works exactly?
WITH recursive n(n) AS (
SELECT 2 n
UNION ALL
SELECT n+1 FROM n WHERE n<1000
)
SELECT a.n
FROM n a
LEFT JOIN n b
ON b.n < sqrt(a.n)
GROUP BY a.n
HAVING a.n=2 OR MIN(a.n % b.n) > 0;
This will generate the following in PostgresQL:
n
====
251
887
601
647
577
...
9
(177 rows)
My understanding of the line-by-line breakdown:
SELECT 2 n -- select the number 2 as n [the anchor member of CTE]
UNION ALL -- combine with recursive component n+1 from n<1000, so display all numbers from 2 to 1000
SELECT a.n FROM n a -- run the above query [the recursive member of CTE]
LEFT JOIN n b -- left join the numbers 2-1000 with a second set of numbers
ON b.n < sqrt(a.n) -- where the second set of numbers is less than the square root of the first column of numbers?
GROUP BY a.n -- only display the first column of numbers
HAVING a.n=2 OR MIN(a.n. % b.n) > 0 -- ...where A=2 or the minimum of A modulo B is greater than 0?
It's a stupid query but any help in deciphering it would be appreciated.
Your query, when properly fixed, generates a list of primes below 1000:
WITH recursive n(n) AS (
SELECT 2 n
UNION ALL
SELECT n+1 FROM n WHERE n<1000
)
SELECT a.n
FROM n a
LEFT JOIN n b
ON b.n <= sqrt(a.n) -- Fix #1
GROUP BY a.n
HAVING a.n=2 OR a.n=3 OR MIN(a.n % b.n) > 0 -- Fix #2
ORDER BY a.n ASC
The explanation is rather straightforward: the recursive part of your query is simply a way to give you a list of numbers from 2, inclusive, to 1000, exclusive. You could replace the recursive clause with an actual table populated with consecutive integer numbers.
These numbers are then fed into the non-CTE part of your query, and joined to themselves on the condition b.n < sqrt(a.n). The a side represents candidate primes; the b side represents candidate divisors.
Here is the first error in your query: < must be changed to <=, otherwise square roots of prime squares would be included into the output.
The GROUP BY groups potential primes with its candidate divisors into a single group. HAVING clause drops everything with one or more candidate divisors dividing the candidate prime evenly, i.e. where MIN(a.n % b.n) is zero.
This is where you need a second fix, because the square root of 3, a prime number, is less than 2, the smallest candidate divisor on the list. Hence, 3 ends up with no candidate divisors at all, and get thrown out by HAVING clause; you need to add OR a.n=3 to preserve it.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments