CODEWITHSUNDEEP
mysqldatabasepreorder
pavel_kazlou
pavel_kazlou

Reputation: 2046

modified preorder tree: selecting top elements of specific type

I use modified preorder tree to store GEO locations in my application in a single table LOC_TABLE. An example of subtree for e.g. Greece looks something like this:

+-------+---------------+-----+-----+------+
| ID    | NAME          | LFT | RGT | TYPE |
+-------+---------------+-----+-----+------+
|    10 | Greece        | 100 | 200 |   3  |
|    20 | Crete Isl.    | 120 | 140 |   4  |
|    25 | Crete-Vamos   | 121 | 122 |   4  |
|    26 | Crete-Rethymno| 123 | 124 |   4  |
 ....
+-------+---------------+-----+-----+------+

TYPE column is used to store type of location (3 - country, 4 - city). As you can see Crete is stored as city, which contains other cities (e.g., Vamos and Rethymno) as its children.

I'm required to perform two types of queries:

1) Fetch all locations of specific type under specific parent.

2) Fetch all top locations of specific type under specific parent: for provided example of locations only Crete Isl. should be returned when querying for cities inside Greece, because Crete Isl. doesn't have parents of type city, while cities Vamos and Rethymno have parent of type city - Crete Isl.

What are the fastest queries to perform in each case?

For the first case I consider either using two queries (first, get LFT and RGT of Greece, second to fetch all locations of type = 4, which have appropriate LFT and RGT) or using some kind of join to get all locations in one step. Which is the best approach?

For the second case I don't have any suitable idea currently. I tried simple sub-select:

select loc.* from LOC_TABLE loc 
where 4 not in 
(select TYPE from LOC_TABLE p 
    where p.lft < loc.lft AND p.rgt > loc.rgt) 
AND loc.LFT > 100 AND loc.RGT < 200;

But it's too long.

I don't mind adding more columns and populating them with some values which will help to speed up these two types of queries. But I need to fetch the data quickly.

Thanks.

Upvotes: 0

Views: 103

Answers (2)

Kickstart
Kickstart

Reputation: 21533

I would try something like these:-

SELECT b.*
FROM LOC_TABLE a
INNER JOIN LOC_TABLE b
ON a.LFT < b.LFT AND a.RGT > b.RGT
WHERE a.ID = 10
AND b.TYPE = 4

Simple JOIN.

For your second question, maybe something like this. Find the parent, then from that find all the records underneath of the right type. The find any parents of the same type of this child. If one is found then ignore.

SELECT b.*
FROM LOC_TABLE a
INNER JOIN LOC_TABLE b ON a.LFT < b.LFT AND a.RGT > b.RGT
LEFT JOIN LOC_TABLE c ON c.LFT > b.LFT AND c.RGT < b.RGT AND b.TYPE = c.TYPE
WHERE a.ID = 10
AND b.TYPE = 4
AND c.ID IS NULL

Upvotes: 1

Oswald
Oswald

Reputation: 31685

For all records that are cities and descendants of a specific record with an ID given by :id, use

SELECT descendant.ID, descendant.NAME, descendant.TYPE 
FROM LOC_TABLE location
INNER JOIN LOC_TABLE descendant
    ON descendant.LFT > location.LFT AND descendant.RGT < location.RGT
WHERE location.ID = :id AND TYPE = 4

For all records that are cities and child of a record with an ID givien by :id, use

SELECT child.ID, child.NAME, child.TYPE 
FROM LOC_TABLE location
INNER JOIN LOC_TABLE child
    ON child.LFT > location.LFT AND child.RGT < location.RGT
LEFT OUTER JOIN LOC_TABLE intermediate
    ON intermediate.LFT < child.LFT
    AND intermediate.RGT > child.RGT
    AND intermediate.LFT > location.LFT
    AND intermediate.RGT < location.RGT
WHERE location.ID = :id
AND child.TYPE = 4
AND intermediate.ID IS NULL

The LEFT OUTER JOIN along with the condition intermediate.ID IS NULL eliminates those child records, for which there is a decendant of location that is ancestor of child.

Upvotes: 1

Related Questions