I am now within the final stages of improving the hierarchy design inside a major transactional system, and I've been looking for some time only at that 150-line query (which I'll spare all of you the tedium of reading through) and convinced that there has to be an easy method.

A fast review of now you ask , the following:

How does one implement a hierarchical search that suits several search phrases at different levels within the hierarchy, enhanced for quickest search time?


I discovered a somewhat related question, but it is really no more than 20% from the answer I really need. This is actually the full scenario/specs:

  • The finish goal is to locate one or more arbitrary products at arbitrary positions within the hierarchy.
  • The entire hierarchy is all about 80,000 nodes, forecasted to develop as much as 1M inside a couple of years.
  • The entire text of the entire path lower the hierarchy is exclusive and descriptive however, the written text of the individual node might not be. This can be a business reality, and never a choice which was made gently.
  • Example: a node may have a title like "Door", that is meaningless alone, however the full context, "Aaron > House > Family Room > Liquor Cabinet > Door", has obvious meaning, it describes a particular door inside a specific location. (Observe that this really is just a good example, the actual design is way less trivial)
  • To be able to find this unique door, a person might type "aaron liquor door", which may likely arrive just one result. The totally converted like a sequence: A product that contains the written text "door", under a product that contains the written text "liquor", under another item that contains the written text "aaron."
  • Or, a person could type "house liquor" to list out all of the liquor cabinets in individuals houses (that would be nice). I mention this situation clearly to point the search do not need to match any particular root or leaf level. This user knows which door he's searching for, but can't remember offhand who is the owner of it, and would remember when the title put their hands up before him.
  • All terms should be matched up within the specified sequence, but because the above good examples suggest, levels within the hierarchy could be "missed." The word "aaron booze cabinet" would not match this node.
  • The woking platform is SQL Server 2008, however i think that this can be a platform-independent problem and would rather to not restrict solutions to that particular platform.
  • The hierarchy itself is dependant on hierarchyid (materialized path), indexed both breadth-first and depth-first. Each hierarchy node/record includes a Name column which is queried on. Hierarchy queries in line with the node are very fast, so don't be concerned about individuals.
  • There's no strict hierarchy - a root could have no nodes whatsoever or could have 30 subtrees fanning to 10,000 leaf nodes.
  • The utmost nesting is arbitrary, but used it is commonly a maximum of 4-8 levels.
  • The hierarchy can and does change, although rarely. Any node could be moved holiday to a node, using the apparent exceptions (parent can not be moved into its very own child, etc.)
  • Just in case this wasn't already implied: I actually do have total control within the design and may add indexes, fields, tables, whatever may be necessary for the greatest results.

My "dream" would be to provide instant feedback towards the user, as with a progressive search/filter, however i realize that this might be impossible or very difficult. I'd be pleased with any significant improvement within the current method, which often takes between .5s to 1s with respect to the quantity of results.

With regard to completeness, the present query (saved procedure) begins by gathering all leaf nodes that contains the ultimate term, then joins upward and excludes any whose pathways don't complement the sooner terms. If the appears backward to anybody, be assured, it's a lot more efficient than beginning using the roots and fanning out. Which was the "old" way and may easily take several seconds per search.

So my question again: It is possible to better (more effective) method to perform this search?

I am not always searching for code, just approaches. I've considered a couple of options however they all appear to possess some problems:

  • Produce a delimited "path text" column and index it with Full-Text Search. Unfortunately that the explore this column would return all child nodes too "aaron house" also matches "aaron house kitchen" and "aaron house basement".
  • Produced a NamePath column that's really a nested sequence of strings, utilizing a CLR type, much like hierarchyid itself. Issue is, I've no clue how Microsoft has the capacity to "translate" queries about this type to index procedures, and I am not really confident that you can do on the UDT. When the internet result is simply a full index scan, I have acquired nothing with this approach.

It isn't truly the finish around the globe basically can't fare better than I curently have the search is "pretty fast", nobody has were not impressed with it. But I am prepared to wager that a person has handled this issue before and it has ideas. Please share them!