Mysql: Optimizing Finding Super Node in Nested Set Tree

Mysql: Optimizing finding super node in nested set tree

To optimize nested set queries in MySQL, you should create a SPATIAL (R-Tree) index on the set boxes:

ALTER TABLE projects ADD sets LINESTRING;

UPDATE  projects
SET     sets = LineString(Point(-1, lft), Point(1, rgt));

ALTER TABLE projects MODIFY sets LINESTRING NOT NULL;

CREATE SPATIAL INDEX sx_projects_sets ON projects (sets);

SELECT  hp.*
FROM    projects hp
WHERE   MBRWithin(Point(0, 4), hp.sets)
ORDER BY
        lft;

See this article in my blog for more detail:

• Adjacency list vs. nested sets: MySQL

Nested sets how to determine the left and right nodes

I think you really need to work on understanding how the nested set works.

I would read this for the diagram of the model and how new nodes are inserted (the rest is good info, too).
http://falsinsoft.blogspot.com/2013/01/tree-in-sql-database-nested-set-model.html

Note that all leaves are _rgt = _lft + 1. The _lft of the left most leaf is min(select _lft .... where _rgt = _lft + 1).

Combine this knowledge with the path to a node query on that same page and I think you'll have what you need.

An additional resource is the wikipedia page:

http://en.wikipedia.org/wiki/Nested_set_model

How to get sons without grandsons of a node design in nested set model?

select *
from table as t_children
where t_children.parent_id in (
    select *
    from table as t_parent
    where t_parent.parent_id is null
)

Finding breadcrumbs for nested sets

What I ended up doing is making a large join that simply ties this table to itself, over and over for every level.

First I populate a table @topLevelGroups with just the 1st level groups (if you only have one root you can skip this step), and then @userGroups with the groups that user can see.

SELECT groupid,
   (level1 
    + CASE WHEN level2 IS NOT NULL THEN ' > ' + level2 ELSE '' END
    + CASE WHEN level3 IS NOT NULL THEN ' > ' + level3 ELSE '' END
   )as [breadcrumb]
FROM (
  SELECT g3.*
    ,g1.name as level1
    ,g2.name as level2
    ,g3.name as level3
  FROM @topLevelGroups g1
  INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid
  INNER JOIN @userGroups g3 ON g3.parentid = g2.groupid 

  UNION

  SELECT g2.*
    ,g1.name as level1
    ,g2.name as level2
    ,NULL as level3
  FROM @topLevelGroups g1 
  INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid

  UNION

  SELECT g1.*
    ,g1.name as level1
    ,NULL as level2
    ,NULL as level3 
  FROM @topLevelGroups g1

) a
ORDER BY [breadcrumb]

This is a pretty big hack, and is obviously limited to a certain number of levels (for my app, there is a reasonable limit I can pick), with the problem that the more levels are supported, it increases the number of joins exponentially, and thus is much slower.

Doing it in code is most certainly easier, but for me that is simply not always an option - there are times when I need this available directly from a SQL query.

---

I'm accepting this as the answer, since it's what I ended up doing and it may work for other people -- however, if someone can come up with a more efficient method I'll change it to them.

Slow location based search result query

You can use the mysql spatial extension and save the latitude and longitude as a point datatype and make it a spatial index. That way you can reorder the coordinates along a curve and reduce the dimension and preserve spatial information. You can use the spatial index as a bounding box to filter the query and then use the harvesine formula to pick the optimal result. Your bounding box should be bigger then the radius of the great circle. Mysql uses a rtree with some spatial index and my example was about a z curve or a hilbert curve: https://softwareengineering.stackexchange.com/questions/113256/what-is-the-difference-between-btree-and-rtree-indexing.
Then you can insert a geocoordinate directly into a point column: http://dev.mysql.com/doc/refman/5.0/en/creating-spatial-values.html. Or you can use a geometry datatype: http://markmaunder.com/2009/10/10/mysql-gis-extensions-quick-start/. Then you can use MBRcontains function like so: http://dev.mysql.com/doc/refman/4.1/en/relations-on-geometry-mbr.html or any other functions: http://dev.mysql.com/doc/refman/5.5/en/functions-for-testing-spatial-relations-between-geometric-objects.html. Hence you need a bounding box.
Here are some examples:

• Storing Lat Lng values in MySQL using Spatial Point Type
• https://gis.stackexchange.com/questions/28333/how-to-speed-up-this-simple-mysql-points-in-the-box-query

Here is a simple example with point datatype:

    CREATE SPATIAL INDEX sx_place_location ON place (location)

    SELECT  * FROM    mytable
    WHERE   MBRContains
           (
           LineString
                   (
                   Point($x - $radius, $y - $radius),
                   Point($x + $radius, $y + $radius)
                   )
           location
           )
    AND Distance(Point($x, $y), location) <= $radius

• MySQL latitude and Longitude table setup.

I'm not sure if it works because it's uses a radius variable with a bounding-box function. It's seems to me MBRwithin is a bit simpler, because it doesn't need any argument: Mysql: Optimizing finding super node in nested set tree.

---

Related Topics