How to count left side nodes and right side nodes for managing a chain link(binary tree)application

Question

How to count left side nodes and right side nodes for managing a chain link(binary tree)application

Viewing 15 posts - 46 through 60 (of 61 total)

You must be logged in to reply to this topic. Login to reply

Jeff Moden SSC Guru Points: 1004312 More actions · Answer 1

Hey Paul... just so you don't think I'm blowing smoke (I know you don't but it makes me feel better to prove I'm not) or have lost my mind (heh... no help there :-P) by publishing "hear say" about performance problems with the HierarchyID, here's the one post that really got my attention and the reason why I dared say such a thing without first proving it myself...

http://connect.microsoft.com/SQLServer/feedback/details/532403/performance-issue-with-getancestor-hierarchyid-fun-inside-if-statement

Of particular import is where MS came back with the following...

We were able to track down the issue. [font="Arial Black"]The problem is that CLR calls, including hierarchyID's methods, are opaque to the query optimizer. This is by design. However, it means that the cardinality estimate for them can sometimes be quite wrong.[/font]
It happens that your EXISTS queries (the >0 query is transformed into an EXISTS) cause the query optimizer to choose a plan based on such an incorrect cardinality estimate. This causes the poor performance.
For now, the easiest workaround is to use a hint to force the use of the correct index. However, we will look into improving the cardinality estimation for hierarchyID methods to help address this sort of issue in the future.

Of course, the emphasis in the text is all mine. I imagine it's something to watch out for with all SQLCLR. It shouldn't scare anyone off of SQLCLR... they just need to be aware of what can happen.

And, as a sidebar, look what the MS respondent called it... "CLR". 😉

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1004312 More actions · Answer 2

Joe Celko (5/20/2010)
Let's make a simple cycle:
INSERT INTO AdjTree VALUES ('foobar', 1, 1);

Damn. I knew I was forgetting something. Thanks, Joe.

We also need to compel a root with one or more children:
VALUES ('Root', 1, NULL);

Agreed. Then there's the additional problem that there's nothing to prevent the user from shooting himself in the face on a DAG by deleting that row prior to inserting additional rows unless we include a DELETE trigger.

Then, there's always the problem of them adding a new row with a NULL ParentID which is the start of a forest possibly requiring a bit more code in the form of a trigger to prevent such an eventuality.

Heh... as you said, it does get messy.

Of course, you'd have to do some checking with both the Hierarchical Path and Nested Set methods to make sure someone didn't manually enter some bum "coordinates", as well.

Thanks for the feedback, Joe.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Paul White SSC Guru Points: 150467 More actions · Answer 3

Jeff Moden (5/16/2010)
@Paul White,
http://connect.microsoft.com/SQLServer/feedback/details/532403/performance-issue-with-getancestor-hierarchyid-fun-inside-if-statement

Yep. Same issue as for scalar/multi-statement TVFs, many remote operations, table variables, XML methods and so on: no statistics, and Microsoft don't (currently) provide a way for programmers to indicate cardinality effects so the optimiser has to guess.

As they say, this is by design, so I don't see it as unexpected or particularly problematic - that's what hints are for. Using an index hint would be my last choice here, using TOP, FAST n, OPTIMIZE FOR or FORCESEEK for example would be preferable, at least as I see it.

As far as naming is concerned, I'm happy with CLR, SQLCLR, .NET hosting...anything really so long as the meaning is clear. Thanks for the link!

Paul

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Vaghasiya Nilesh SSChasing Mays Points: 633 More actions · Answer 4

Vaghasiya Nilesh

SSChasing Mays

Points: 633

July 16, 2010 at 7:06 am

#1194083

please give this script in sql server 2005

thank you..

Paul White SSC Guru Points: 150467 More actions · Answer 5

Vaghasiya Nilesh (7/16/2010)
please give this script in sql server 2005
thank you..

Which script?

P.S. I never respond to unsolicited emails

Paul White
SQLPerformance.com
SQLkiwi blog
@SQL_Kiwi

Vaghasiya Nilesh SSChasing Mays Points: 633 More actions · Answer 6

How to count left side nodes and right side nodes for managing a chain link(binary tree)application

in already u posted script in sql server 2008 but i want need in sql server 2005 bcz of Hierarcyid datatype is not in sql server 2005

thank u..

Vaghasiya Nilesh SSChasing Mays Points: 633 More actions · Answer 7

USE tempdb;

GO

IF OBJECT_ID(N'dbo.Tree', N'U')

IS NOT NULL

DROP TABLE dbo.Tree;

GO

-- Test table

CREATE TABLE dbo.Tree

(

node_id INTEGER NOT NULL,

name VARCHAR(20) NOT NULL,

hid HIERARCHYID NOT NULL,

parent AS hid.GetAncestor(1) PERSISTED,

level AS hid.GetLevel(),

path AS hid.ToString(),

);

-- Indexes and constraints

CREATE UNIQUE CLUSTERED INDEX [CUQ dbo.Tree depth_first] ON dbo.Tree (hid);

CREATE UNIQUE INDEX [UQ dbo.Tree node_id] ON dbo.Tree (node_id);

CREATE INDEX [IX dbo.Tree parent] ON dbo.Tree (parent);

ALTER TABLE dbo.Tree ADD FOREIGN KEY (parent) REFERENCES dbo.Tree (hid);

-- Nodes

INSERT dbo.Tree(node_id, name, hid) VALUES (1, 'Node 1', hierarchyid::GetRoot());

INSERT dbo.Tree(node_id, name, hid) VALUES (2, 'Node 2', hierarchyid::Parse(N'/1/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (3, 'Node 3', hierarchyid::Parse(N'/2/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (4, 'Node 4', hierarchyid::Parse(N'/1/1/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (5, 'Node 5', hierarchyid::Parse(N'/1/2/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (6, 'Node 6', hierarchyid::Parse(N'/2/1/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (7, 'Node 7', hierarchyid::Parse(N'/2/2/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (8, 'Node 8', hierarchyid::Parse(N'/1/1/1/'));

INSERT dbo.Tree(node_id, name, hid) VALUES (9, 'Node 9', hierarchyid::Parse(N'/1/1/2/'));

Solution:

DECLARE @root HIERARCHYID,

@left HIERARCHYID,

@right HIERARCHYID;

SELECT @root = hid FROM dbo.Tree WHERE node_id = 1;

SELECT @left = (SELECT MIN(hid) FROM dbo.Tree WHERE hid.GetAncestor(1) = @root),

@right = (SELECT MAX(hid) FROM dbo.Tree WHERE hid.GetAncestor(1) = @root);

SELECT left_count =

(

SELECT COUNT_BIG(*)

FROM dbo.Tree T

WHERE T.hid.IsDescendantOf(@left) = 1

),

right_count =

(

SELECT COUNT_BIG(*)

FROM dbo.Tree T

WHERE T.hid.IsDescendantOf(@right) = 1

);

GO

-- Tidy up

DROP TABLE dbo.Tree;

this script is give me in sql server 2005..

thank u..

Vaghasiya Nilesh SSChasing Mays Points: 633 More actions · Answer 8