indexes on mysql self-joined table

I need some help with a complicated sql query that returns children and grandchildren of a dog in a table of 90K dogs.

The query;

SELECT 
             CH.id          AS CH_id
            ,CH.Callname    AS CH_Token
            ,CH.Slem        AS CH_Slem
            ,(SELECT CONCAT(CH.KnownAs,' (',CH.Gender,')'))  AS CH_KnownAs
            ,CH.Paternal    AS CH_Paternal_id
            ,(SELECT Callname from dogs where id = CH.Paternal) AS CH_Paternal_Token
            ,(SELECT Slem from dogs where id = CH.Paternal) AS CH_Paternal_Slem
            ,(SELECT CONCAT(KnownAs,' (',Gender,')')  FROM dogs WHERE id = CH.Paternal) AS CH_Paternal_KnownAs
            ,CH.Maternal    AS CH_Maternal_id
            ,(SELECT Callname from dogs where id = CH.Maternal) AS CH_Maternal_Token
            ,(SELECT Slem from dogs where id = CH.Maternal) AS CH_Maternal_Slem
            ,(SELECT CONCAT(KnownAs,' (',Gender,')')  FROM dogs WHERE id = CH.Maternal) AS CH_Maternal_KnownAs
            ,DATE_FORMAT(CH.DOB,"%d-%m-%Y")         AS CH_DOB
            ,GC.id          AS GC_id
            ,GC.Callname    AS GC_Token
            ,GC.Slem        AS GC_Slem            
            ,(SELECT CONCAT(GC.KnownAs,' (',GC.Gender,')'))  AS GC_KnownAs
            ,DATE_FORMAT(GC.DOB,"%d-%m-%Y")         AS GC_DOB
            ,GC.Paternal    AS GC_Paternal_id
            ,(SELECT Callname from dogs where id = GC.Paternal) AS GC_Paternal_Token
            ,(SELECT Slem from dogs where id = GC.Paternal) AS GC_Paternal_Slem
            ,(SELECT CONCAT(KnownAs,' (',Gender,')')  FROM dogs WHERE id = GC.Paternal) AS GC_Paternal_KnownAs
            ,GC.Maternal    AS GC_Maternal_id
            ,(SELECT Callname from dogs where id = GC.Maternal) AS GC_Maternal_Token
            ,(SELECT Slem from dogs where id = GC.Maternal) AS GC_Maternal_Slem
            ,(SELECT CONCAT(KnownAs,' (',Gender,')') FROM dogs WHERE id = GC.Maternal) AS GC_Maternal_KnownAs
            ,GGC.id         AS GGC_id
            ,GGC.Callname   AS GGC_Token
            ,GGC.Slem       AS GGC_Slem
            ,(SELECT CONCAT(GGC.KnownAs,' (',GGC.Gender,')'))  AS GGC_KnownAs
            ,DATE_FORMAT(GGC.DOB,"%d-%m-%Y")         AS GGC_DOB
            ,GGC.Paternal   AS GGC_Paternal_id
            ,(SELECT Callname from dogs where id = GGC.Paternal) AS GGC_Paternal_Token
            ,(SELECT Slem from dogs where id = GGC.Paternal) AS GGC_Paternal_Slem
            ,(SELECT CONCAT(KnownAs,' (',Gender,')')  FROM dogs WHERE id = GGC.Paternal) AS GGC_Paternal_KnownAs
            ,GGC.Maternal    AS GGC_Maternal_id
            ,(SELECT Callname from dogs where id = GGC.Maternal) AS GGC_Maternal_Token
            ,(SELECT Slem from dogs where id = GGC.Maternal) AS GGC_Maternal_Slem
            ,(SELECT CONCAT(KnownAs,' (',Gender,')') FROM dogs WHERE id = GGC.Maternal) AS GGC_Maternal_KnownAs
             FROM (SELECT id,Gender,KnownAs,Paternal,Maternal,DOB,Callname,Slem FROM dogs WHERE (dogs.Maternal = '77723' OR dogs.Paternal = '77723') AND Deleted
=0) AS CH
             LEFT JOIN dogs AS GC  ON CH.id =  GC.Paternal OR CH.id = GC.Maternal AND GC.Deleted=0
             LEFT JOIN dogs AS GGC ON GC.id = GGC.Paternal OR GC.id = GGC.Maternal AND GGC.Deleted=0
             ORDER BY CH.DOB ASC;

The query returns all dogs that have the subject dog as the mother or father, plus the children of each of those and the children of each of those (the GC and GGC joins)

The query takes 7 seconds (for reference, always relative to the server hardware)

Explain lists;

1	PRIMARY	dogs	NULL	index_merge	parents,Paternal,Maternal	Maternal,parents	5,5	NULL	14	10.00	Using sort_union(Maternal,parents); Using where; Using filesort
1	PRIMARY	GC	NULL	ALL	parents,Paternal,Maternal	NULL	NULL	NULL	86874	100.00	Range checked for each record (index map: 0x38)
1	PRIMARY	GGC	NULL	ALL	parents,Paternal,Maternal	NULL	NULL	NULL	86874	100.00	Range checked for each record (index map: 0x38)
22	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GGC.Maternal	1	100.00	NULL
21	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GGC.Maternal	1	100.00	NULL
20	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GGC.Maternal	1	100.00	NULL
19	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GGC.Paternal	1	100.00	NULL
18	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GGC.Paternal	1	100.00	NULL
17	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GGC.Paternal	1	100.00	NULL
15	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GC.Maternal	1	100.00	NULL
14	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GC.Maternal	1	100.00	NULL
13	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GC.Maternal	1	100.00	NULL
12	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GC.Paternal	1	100.00	NULL
11	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GC.Paternal	1	100.00	NULL
10	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	borderterrier.GC.Paternal	1	100.00	NULL
8	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	func	1	100.00	Using where
7	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	func	1	100.00	Using where
6	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	func	1	100.00	Using where
5	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	func	1	100.00	Using where
4	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	func	1	100.00	Using where
3	DEPENDENT SUBQUERY	dogs	NULL	eq_ref	PRIMARY	PRIMARY	4	func	1	100.00	Using where

I'm expecting the response to be better (query in this case returns 29 rows) and you can see the full scans on the aliased joins (86000 rows range checked).

What am I doing wrong?

note that this is a legacy php application on mysql 5.7