Re: Nested sets in SQL - inventor?

Michael Kamfonas wrote:
> Mikito,
>
> Recursive unions are NOT as efficient as you think, particularly if you
> deal with substantial volumes of data and complex queries. Repetitive
> invocation even at the server is at least half a level of magnitude
> (usually more)worse than an L/R scan.

Michael,

I don't think I follow here. Assuming that in the Edges(tail, head) relation both head and tail columns are indexed, we are able to quickly navigate. Travesing a path with length grater than 2 requires to perform index range scan repeatedly. This is a minimum amount of work that is logically is required to do, and I fail to understand how this could be inefficient. Perhaps an example can help here.

> Aside from this however the real advantage of the L/R enumeration
> (nested set) method is that you can detect ancestor/descendent
> dependency without traversing the path. If you deal with very large
> sets, the recurcive union has to traverse the complete graph to pick the
> ancestor-descendent pairs and then apply other predicates. This means
> that you traverse practically the whole unfiltered graph. In the nested
> set case however, the optimizer could filter the nodes based on other
> productive criteria, leaving a potentially very small set of rows to be
> compared for ancestor/descendent dependency. This has the potential of
> multiple levels of magnitude difference.

Again we aren't on a firm ground without an example here, but "magic" optimization of recursive queries is supposed to push predicates inside recursive query. I don't know if to what extent (if at all) magic optimization is implemented in SQLServer and DB2. Received on Wed Aug 17 2005 - 20:24:45 CEST