Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: SQL competition: the shortest interval coalesce/pack query
"Lennart Jonsson" <lennart_at_kommunicera.umea.se> wrote in message
news:6dae7e65.0412040742.572da937_at_posting.google.com...
> "John Gilson" <jag_at_acm.org> wrote in message news:<ujesd.60193$Vk6.30697_at_twister.nyc.rr.com>...
> > [...] > >
> >
> >
> >
> > Hi John. Very interesting and I will have a look at it later. > > In fact I hadnt started worrying about the correctness of my attempt, > but merely the performance. Because of the nature of the problem the > cover set grows very fast. I took the liberty to take you code for a > run > > select * from intervals > > X Y > ----------- ----------- > 1 3 > 2 5 > 4 11 > 10 12 > 20 21 > 4 16 > 5 17 > 6 18 > > WITH Cover (x,y,n) > AS (SELECT x,y, > (SELECT COUNT(*) FROM Intervals) > FROM Intervals > UNION ALL > SELECT CASE WHEN C.x <= I.x THEN C.x ELSE I.x END, > CASE WHEN C.y >= I.y THEN C.y ELSE I.y END, > C.n - 1 > FROM Intervals AS I, Cover AS C > WHERE I.x <= C.y AND > I.y >= C.x AND > (I.x <> C.x OR I.y <> C.y) AND > C.n > 1) > SELECT count(C1.x) > FROM Cover AS C1; > > 1 > ----------- > SQL0347W The recursive common table expression "LELLE.COVER" may > contain an > infinite loop. SQLSTATE=01605 > > 2379720 > > > But your query terminates very quickly so perhaps the optimizer is > smart enough to push the predicates inside the cover clause? > > > /Lennart
Hi Lennart, I'm glad you did bother to take the code out for a spin. Though the query returns the correct result with the data you provided, the row count in the unrestricted Cover table is several orders of magnitude greater than expected! On further inspection, one can be more discriminating in defining both the base and recursive cases for Cover:
CREATE TABLE Intervals
(
x INT NOT NULL,
y INT NOT NULL,
CHECK (y > x),
PRIMARY KEY (x,y)
);
INSERT INTO Intervals (x, y)
VALUES (1,3),(2,5),(4,11),(10,12),(20,21),(4,16),(5,17),(6,18);
WITH IntervalTally (n) AS (SELECT COUNT(*) FROM Intervals),
Cover (x,y,n) AS (SELECT I1.x,I1.y, T.n FROM Intervals AS I1, IntervalTally AS T WHERE NOT EXISTS (SELECT * FROM Intervals AS I2 WHERE I2.x <= I1.x AND I2.y >= I1.y AND (I2.x <> I1.x OR I2.y <> I1.y)) UNION ALL SELECT CASE WHEN C.x <= I.x THEN C.x ELSE I.x END, CASE WHEN C.y >= I.y THEN C.y ELSE I.y END, C.n - 1 FROM Intervals AS I, Cover AS C WHERE I.x <= C.y AND I.y >= C.x AND (I.x < C.x OR I.y > C.y) AND C.n > 1)
FROM Cover AS C2 WHERE C2.x <= C1.x AND C2.y >= C1.y AND (C1.x <> C2.x OR C1.y <> C2.y))ORDER BY C1.x;
1 18
20 21
Now let's take a look at the row tally in Cover:
WITH IntervalTally (n) AS (SELECT COUNT(*) FROM Intervals),
Cover (x,y,n) AS (SELECT I1.x,I1.y, T.n FROM Intervals AS I1, IntervalTally AS T WHERE NOT EXISTS (SELECT * FROM Intervals AS I2 WHERE I2.x <= I1.x AND I2.y >= I1.y AND (I2.x <> I1.x OR I2.y <> I1.y)) UNION ALL SELECT CASE WHEN C.x <= I.x THEN C.x ELSE I.x END, CASE WHEN C.y >= I.y THEN C.y ELSE I.y END, C.n - 1 FROM Intervals AS I, Cover AS C WHERE I.x <= C.y AND I.y >= C.x AND (I.x < C.x OR I.y > C.y) AND C.n > 1)
204
Now that seems more reasonable.
-- JAGReceived on Mon Dec 06 2004 - 00:33:34 CST