title: modified preorder tree: selecting top elements of specific type
body: <p>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:</p>
  
  <pre><code>+-------+---------------+-----+-----+------+
  | 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  |
   ....
  +-------+---------------+-----+-----+------+
  </code></pre>
  
  <p><code>TYPE</code> 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., <code>Vamos</code> and <code>Rethymno</code>) as its children.</p>
  
  <p>I'm required to perform two types of queries:</p>
  
  <p>1) Fetch all locations of specific type under specific parent.</p>
  
  <p>2) Fetch all top locations of specific type under specific parent: for provided example of locations only <code>Crete Isl.</code> should be returned when querying for cities inside Greece, because <code>Crete Isl.</code> doesn't have parents of type city, while cities <code>Vamos</code> and <code>Rethymno</code> have parent of type city - <code>Crete Isl.</code></p>
  
  <p>What are the fastest queries to perform in each case?</p>
  
  <p>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?</p>
  
  <p>For the second case I don't have any suitable idea currently. I tried simple sub-select:</p>
  
  <pre><code>select loc.* from LOC_TABLE loc 
  where 4 not in 
  (select TYPE from LOC_TABLE p 
      where p.lft &lt; loc.lft AND p.rgt &gt; loc.rgt) 
  AND loc.LFT &gt; 100 AND loc.RGT &lt; 200;
  </code></pre>
  
  <p>But it's too long.</p>
  
  <p>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.</p>
  
  <p>Thanks.</p>