Urgent stock options/org chart query

[Dan Tan]

Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com

[Sumit]

I think a good way to do this would be through a recursive Stored Procedure.

------------
Dan Tan at 1/9/01 2:51:51 AM


Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com

[Tom Christopher]

Sql Server magazine has exactly this problem solved in User defined functions, which if you don't have SQL 2000 can be done thru similar recursive stored procedures. see : http://www.sqlmag.com/


------------
Dan Tan at 1/9/01 2:51:51 AM


Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com

[Xiao Tan]

say, here is your organization tree:

A
B C
D E F G

(B is boss of D and E, C is boss of F and G, A is boss of B and C)

my approach to solve this problem would be trying to avoid to
re-calculate the department-option again and again. If you just
use some simple recursive function to cal this, to cal A, you need
to cal the options of its children and grandchild (B, C, D, E, F, G).
At the time, you need the option of B, you have to cal options for
D and E AGAIN! To avoid this, I will modify the table structure,
hold department option number and level number

create table new_table (SID, EID, Option, Dep_Option, Level)

In this case, you need to run some initialization process to cal
all Dep_option number, you can try to cal from the root, because
you don't need to recursive all the way up, then one level at a time
back up to the top.

There is of course a trade off in this approach.
Your insertion time will be longer, and will be a little
more complicated. Because whenever you insert an new employee, or
whenever there is some organization move, you have
to update all the dep-option above him. But in this case
you will have a instant output of all department option numbers.

Hope this helps.


------------
Dan Tan at 1/9/01 2:51:51 AM


Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com

[Jun]

Hi Dan,

Hope you got some solutions for your Stock Options calculation.

Here is my idea: If your have a table (Employ_Options)with the following structure:

em_id, report_to_id, Option_amount, group_option, Total_option
1
2 1
3 2
5 1


You can create a stored procedure like the following
(just a suggestion, you may need to modify according your specific situation)


/************************************************** ***/
CREATE PROC Stockoption_Calculation

AS

-- Assign basic amount for all (assuming all non-manager employee gets same amount basic options)
UPDATE Employ_Options
SET option_amount = 5000
WHERE em_id not IN ( SELECT REPORT_TO_ID FROM Employ_Options )

-- Use a loop to calculate the stock option amount one management level at a time
-- ( assume the managers get the basic amount plus all sum of his subordinates )
WHILE (SELECT COUNT (EM_ID) FROM Employ_Options WHERE OPTION_AMOUNT IS NULL) > 0
BEGIN
UPDATE Employ_Options
SET OPtion_amount = ISNULL (option_amount, 0) +
( SELECT SUM (OPTION_AMOUNT)
FROM EMPLOY_OPTIONS t1
WHERE T1.REPORT_TO_ID = EMPLOY_Options.EM_ID
GROUP BY REPORT_TO_ID )
WHERE Option_amount is NULL


IF NOT EXISTS ( SELECT em_id FROM Employ_Options WHERE OPTION_AMOUNT IS NULL )
BREAK
ELSE
CONTINUE

END
/************************************************** ***************/

Hope this helps!

Jun



------------
Dan Tan at 1/9/01 2:51:51 AM


Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com

[Jim W]

Alternatively, if you need something really quick and dirty, and there is a limit to the number of supervisor levels, you could do something like this:

select s1.options, s2.options, s3.options, s4.options, s5.options, s6.options
from stock s1
left join stock s2 on s2.empid = s1.supid
left join stock s3 on s3.empid = s2.supid
left join stock s4 on s4.empid = s3.supid
left join stock s5 on s5.empid = s4.supid
left join stock s6 on s6.empid = s5.supid
where s1.empid = 1

There is a limit to the number of levels due to the limit of joins you can do.
Also, a problem with this is that you can't do a straight s1.options+s2.options+ etc because adding a null to an integer results in a null.

------------
Jun at 1/11/01 11:12:27 AM



Hi Dan,

Hope you got some solutions for your Stock Options calculation.

Here is my idea: If your have a table (Employ_Options)with the following structure:

em_id, report_to_id, Option_amount, group_option, Total_option
1
2 1
3 2
5 1


You can create a stored procedure like the following
(just a suggestion, you may need to modify according your specific situation)


/************************************************** ***/
CREATE PROC Stockoption_Calculation

AS

-- Assign basic amount for all (assuming all non-manager employee gets same amount basic options)
UPDATE Employ_Options
SET option_amount = 5000
WHERE em_id not IN ( SELECT REPORT_TO_ID FROM Employ_Options )

-- Use a loop to calculate the stock option amount one management level at a time
-- ( assume the managers get the basic amount plus all sum of his subordinates )
WHILE (SELECT COUNT (EM_ID) FROM Employ_Options WHERE OPTION_AMOUNT IS NULL) > 0
BEGIN
UPDATE Employ_Options
SET OPtion_amount = ISNULL (option_amount, 0) +
( SELECT SUM (OPTION_AMOUNT)
FROM EMPLOY_OPTIONS t1
WHERE T1.REPORT_TO_ID = EMPLOY_Options.EM_ID
GROUP BY REPORT_TO_ID )
WHERE Option_amount is NULL


IF NOT EXISTS ( SELECT em_id FROM Employ_Options WHERE OPTION_AMOUNT IS NULL )
BREAK
ELSE
CONTINUE

END
/************************************************** ***************/

Hope this helps!

Jun



------------
Dan Tan at 1/9/01 2:51:51 AM


Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com

[Jim W]

This should do the trick. It's fast (imo), accurate, and works with any number of levels of supervision:

set nocount on
create table #stockoptions (supid int, levelid int, options int)

declare @levelid int

insert into #stockoptions (supid, levelid, options)
select empid, 0, options from stock
where empid = 1

set @levelid = 0

while exists
(select * from stock emp
join #stockoptions sup on sup.supid = emp.supid and levelid = @levelid)
begin
insert #stockoptions (supid, levelid, options)
select emp.empid, @levelid+1, emp.options from stock emp
join #stockoptions sup on sup.supid = emp.supid and levelid = @levelid

set @levelid = @levelid + 1
end

select sum(options) as optioncount from #stockoptions

set nocount on

drop table #stockoptions


------------
Dan Tan at 1/9/01 2:51:51 AM


Okay, here's an algorithm question for you TSQL gurus out there...

Due to circumstances beyond our control, our group has been tasked with a massive project and a very short timeline. And of course, timely completion is needed because our STOCK OPTIONS grants depend on this! And of course board meetings are always scheduled sooner than you expect.

Here's one of the killer questions we're trying to solve...

Given a table of employee ID's, associated supervisor ID's, and the amount of stock options given, how would you write a stored procedure to return, for any branch of the organizational tree, the sum of all the stock options in a particular branch?

Example:

EMPID SUPERVISORID STOCKOPTIONS
1 2 100
2 30 500
3 2 150
30 50 1000
50 60 5000

What we need is something like : "sp_StockOptionsPerDepartment @SUPERVISORID=30"
with a result : "1750".

Basically we're building an organizational chart of our company from this table, on the fly, and also counting up for certain branches of the org chart, the total stock options.

If a manager has two managers under him, and each sub-manager has three employees, then we want to know the total stock options that all 3+3+2+1 = 9 people possess. Basically it's the total pool of stock options for a department, or work group, or division, etc.

Got this to work for a small set of employees, but when we begin to scale up to entire departments, the query times out because it takes tooooo long...

Any ideas? ANY ideas at ALL would be helpful...

Comments
(1) This is basically a tree-traversal algorithm, but conversion into SQL is not always so straightforward. Starting from an arbitrary root node, we must visit every child node underneath, walking all the way down to the leaves.

(2) We tried a brute force algorithm which is fast for smaller sets, but impossibly long for sets where we're dealing with hundreds of employees. Any cheats? Caching results as we go? Any ideas out there?

Thanks,
Dan
dantan@pobox.com