Wrong results if the recursive query contains an embedded GROUP BY clause [CORE3683]

[firebird-automations]

Submitted by: @pavel-zotov

Is duplicated by CORE3698
Is related to QA492

DDL:
-- table of some routes between cities and additional info (names from cenral region of Russia):
recreate table rdeps(parent varchar(32),child varchar(32), parent_type int, child_type int, f01 int);
commit;

insert into rdeps values( 'MOSCOW', 'TULA', 0, 5, 21);
insert into rdeps values( 'MOSCOW', 'TULA', 0, 5, 22);

insert into rdeps values( 'TULA', 'OREL', 5, 5, 51);
insert into rdeps values( 'TULA', 'OREL', 5, 5, 52);

insert into rdeps values( 'TULA', 'LIPETSK', 5, 2, 71);
insert into rdeps values( 'TULA', 'LIPETSK', 5, 2, 72);

insert into rdeps values( 'TULA', 'RYAZAN', 5, 5, 61);
insert into rdeps values( 'TULA', 'RYAZAN', 5, 5, 62);

insert into rdeps values( 'OREL', 'KURSK', 5, 5, 81);
insert into rdeps values( 'OREL', 'KURSK', 5, 5, 82);

insert into rdeps values( 'LIPETSK','VORONEZH', 5, 2, 71);
insert into rdeps values( 'LIPETSK','VORONEZH', 5, 2, 72);

insert into rdeps values( 'RYAZAN','MUROM', 5, 5, 61);
insert into rdeps values( 'RYAZAN','MUROM', 5, 5, 62);

commit;

Task: get all possible routes starting from MOSCOW

Query:
with recursive
rd as(
select
d.parent parent
,d.child
from rdeps d
group by d.parent,d.child -- <<< we need this grouping to eliminate duplicates
)
,cr as(
select 0 step,parent,child,cast(parent as varchar(32000))||'->'||child routes
from rd
where rd.parent='MOSCOW'

UNION ALL

select x.step+1,rd.parent,rd.child,x.routes||'->'||rd.child
from cr x
join rd on x.child=rd.parent
)
select step,routes from cr order by step,routes

Result (WRONG):

STEP ROUTES
0 MOSCOW->TULA
1 MOSCOW->TULA->LIPETSK
1 MOSCOW->TULA->RYAZAN
1 MOSCOW->TULA->RYAZAN
2 MOSCOW->TULA->LIPETSK->VORONEZH
2 MOSCOW->TULA->RYAZAN->MUROM
2 MOSCOW->TULA->RYAZAN->MUROM

(dupliates MOSCOW->TULA->RYAZAN, MOSCOW->TULA->RYAZAN->MUROM; missing MOSCOW->TULA->OREL)

Add [unique] index:

--create unique index rdeps_unq on rdeps(parent, child, f01);
create index rdeps_unq on rdeps(parent, child, f01);
Repeat the query - result will be correct:
STEP ROUTES
0 MOSCOW->TULA
1 MOSCOW->TULA->LIPETSK
1 MOSCOW->TULA->OREL
1 MOSCOW->TULA->RYAZAN
2 MOSCOW->TULA->LIPETSK->VORONEZH
2 MOSCOW->TULA->OREL->KURSK
2 MOSCOW->TULA->RYAZAN->MUROM

PS. The result will be also correct if we replace GROUP BY in root member with DISTINCT - but these operations are not equal.

Commits: fb4e19e f30f9e5 965bf3f 3009484 FirebirdSQL/fbt-repository@72e4e3f

[firebird-automations]

Modified by: @asfernandes

assignee: Adriano dos Santos Fernandes [ asfernandes ]

[firebird-automations]

Modified by: @asfernandes

status: Open [ 1 ] => Resolved [ 5 ]

resolution: Fixed [ 1 ]

Fix Version: 3.0 Alpha 1 [ 10331 ]

[firebird-automations]

Commented by: @pavel-zotov

Adriano, can you also fix this for 2.5.x ?

[firebird-automations]

Commented by: @asfernandes

Would like to Vlad review it first.

[firebird-automations]

Commented by: @hvlad

Adriano,

i reviewed your first commit and it looks OK for me.
But i could miss something as i know opt\rse parts not very well.

[firebird-automations]

Commented by: @asfernandes

The related code is completely different and ugly in 2.5. I'm leaving it.

[firebird-automations]

Modified by: @dyemanov

Version: 2.5.1 [ 10333 ]

Version: 2.1.4 [ 10361 ]

Version: 2.5.0 [ 10221 ]

Version: 3.0 Initial [ 10301 ]

Version: 2.1.3 [ 10302 ]

Version: 2.1.2 [ 10270 ]

Version: 2.1.1 [ 10223 ]

Version: 2.1.0 [ 10041 ]

Component: Engine [ 10000 ]

[firebird-automations]

Modified by: Sean Leyne (seanleyne)

Link: This issue relate to CORE3698 [ CORE3698 ]

[firebird-automations]

Modified by: @dyemanov

Link: This issue relate to CORE3698 [ CORE3698 ] =>

[firebird-automations]

Modified by: @dyemanov

Link: This issue is duplicated by CORE3698 [ CORE3698 ]

[firebird-automations]

Modified by: @dyemanov

summary: recursive query with GROUP BY in root part: wrong results if no index exists for fields that are grouped => Wrong results if the recursive query contains an embedded GROUP BY clause

[firebird-automations]

Commented by: @dyemanov

Backported into v2.5.2.

[firebird-automations]

Modified by: @dyemanov

Fix Version: 2.5.2 [ 10450 ]

[firebird-automations]

Modified by: @pcisar

Link: This issue is related to QA492 [ QA492 ]

[firebird-automations]

Modified by: @pmakowski

status: Resolved [ 5 ] => Closed [ 6 ]

[firebird-automations]

Modified by: @pavel-zotov

status: Closed [ 6 ] => Closed [ 6 ]

QA Status: Done successfully