Help with SP on a large number of rows 2

[etoucan]

Intro: I am writing an application that will help in the choice of players in a fantasy football league [those who hate footie, please keep reading 8¬) ].

Background: I have a db containing 3 tables - tblClubs with fldClubID & fldClubName (22 rows), tblPositions with fldPositionID & fldPosition (5 rows - Manager, Goalkeeper, Defender, Midfield & Forward) and tblPlayers with fldName, fldCost, fldPoints, fldClubID (FK to tblClubs) & fldPositionID (FK to tblPositions) (450 rows).

Problem: I want to write a stored procedure that will return all possible combinations of players to make teams of 12, based on a team comprising 1 manager, 1 goalkeeper, 4 defenders, 3 midfield & 3 forwards (from tblPositions). Basically, I want to know which combination of 12 players scored the most points.

Constraint 1: The total cost of each team must be <= 55.
Constraint 2: No more than 3 players from the same club per team.
Constraint 3: There needs to be user input for a threshold number of points a team has in total for it to be included in output results, eg 1000 (this should reduce the number of rows).
Constraint 4:Because this is such a large query, need to show returned rows on-screen as they are calculated and not wait until the query completes.

I have a working VB solution using 12 loops and various tests, but I've calculated that the routine will take several billion years to complete. Hmmm. So that's where I thought SQLServer might help. So, I wrote the following...

IF EXISTS (SELECT ROUTINE_NAME
	FROM INFORMATION_SCHEMA.ROUTINES 
	WHERE ROUTINE_TYPE = 'PROCEDURE' AND ROUTINE_NAME = 'GenerateTeams')
	DROP PROCEDURE GenerateTeams
GO

USE Football
GO

CREATE PROC GenerateTeams
AS
SELECT	dbo.qryManagers01.fldLastName AS Mgr, 
	dbo.qryGoalkeepers01.fldLastName AS G, 
	dbo.qryDefenders01.fldLastName AS D1, 
	dbo.qryDefenders02.fldLastName AS D2, 
	dbo.qryDefenders03.fldLastName AS D3, 
	dbo.qryDefenders04.fldLastName AS D4, 
	dbo.qryMidfield01.fldLastName AS M1, 
	dbo.qryMidfield02.fldLastName AS M2, 
	dbo.qryMidfield03.fldLastName AS M3, 
	dbo.qryForwards01.fldLastName AS F1, 
	dbo.qryForwards02.fldLastName AS F2, 
	dbo.qryForwards03.fldLastName AS F3, 
	
	dbo.qryManagers01.fldCost+ 
	dbo.qryGoalkeepers01.fldCost+ 
	dbo.qryDefenders01.fldCost+ 
	dbo.qryDefenders02.fldCost+ 
	dbo.qryDefenders03.fldCost+ 
	dbo.qryDefenders04.fldCost+ 
	dbo.qryMidfield01.fldCost+ 
	dbo.qryMidfield02.fldCost+ 
	dbo.qryMidfield03.fldCost+ 
	dbo.qryForwards01.fldCost+ 
	dbo.qryForwards02.fldCost+ 	dbo.qryForwards03.fldCost AS [Total cost], 
      	
	dbo.qryManagers01.fldPoints + 
	dbo.qryGoalkeepers01.fldPoints + 
	dbo.qryDefenders01.fldPoints + 
	dbo.qryDefenders02.fldPoints + 
	dbo.qryDefenders03.fldPoints + 
	dbo.qryDefenders04.fldPoints + 
	dbo.qryMidfield01.fldPoints + 
	dbo.qryMidfield02.fldPoints + 
	dbo.qryMidfield03.fldPoints + 
	dbo.qryForwards01.fldPoints + 
	dbo.qryForwards02.fldPoints + 
	dbo.qryForwards03.fldPoints AS [Total points]

FROM    dbo.qryManagers01 CROSS JOIN
        dbo.qryGoalkeepers01 CROSS JOIN
        dbo.qryDefenders01 CROSS JOIN
        dbo.qryDefenders02 CROSS JOIN
        dbo.qryDefenders03 CROSS JOIN
        dbo.qryDefenders04 CROSS JOIN
        dbo.qryMidfield01 CROSS JOIN
        dbo.qryMidfield02 CROSS JOIN
        dbo.qryMidfield03 CROSS JOIN
        dbo.qryForwards01 CROSS JOIN
        dbo.qryForwards02 CROSS JOIN
        dbo.qryForwards03

WHERE	(dbo.qryManagers01.fldCost+ 
	dbo.qryGoalkeepers01.fldCost+ 
	dbo.qryDefenders01.fldCost+ 
	dbo.qryDefenders02.fldCost+ 
	dbo.qryDefenders03.fldCost+ 
	dbo.qryDefenders04.fldCost+ 
	dbo.qryMidfield01.fldCost+ 
	dbo.qryMidfield02.fldCost+ 
	dbo.qryMidfield03.fldCost+ 
	dbo.qryForwards01.fldCost+ 
	dbo.qryForwards02.fldCost+ 
	dbo.qryForwards03.fldCost <= 55) 
AND 
	(dbo.qryManagers01.fldPoints + 
	dbo.qryGoalkeepers01.fldPoints + 
	dbo.qryDefenders01.fldPoints + 
	dbo.qryDefenders02.fldPoints + 
	dbo.qryDefenders03.fldPoints + 
	dbo.qryDefenders04.fldPoints + 
	dbo.qryMidfield01.fldPoints + 
	dbo.qryMidfield02.fldPoints + 
	dbo.qryMidfield03.fldPoints + 
	dbo.qryForwards01.fldPoints + 
	dbo.qryForwards02.fldPoints + 
	dbo.qryForwards03.fldPoints >= 1000)
GO

EXECUTE GenerateTeams
GO

The dbo.queries are pre-built views which filter for position, but I've read somewhere that using views in SP's might not be a good idea. This seems to work but takes for ever (maybe < N billion years, though). It also does not take constraint 2 into account, which I have zero ideas about. Am I on the right track? Are there other ways to reduce the overhead? I'm pretty new to SQL and I don't know the language very well, so there are bound to be things I'm missing. Any ideas? Thanks for reading this long question.

 

[donutman]

First of all the query won't work. The cross joins do not eliminate already selected players. If you give me the individual counts of managers, goalkeepers, defenders, etc. that you have and ignoring the 3 members per club and cost <55, then I can calculate the number of possible teams that you have. This will tell you if it's worth going any further with a solution.
-Karl

[red] Cursors, triggers, user-defined functions and dynamic SQL are an axis of evil![/red]
[green]Life's uncertain...eat dessert first...www.deerfieldbakery.com[/green]

 

[etoucan]

The query does work to a point because the included views filter for position and same name in a position. Here are the numbers: Managers 22, Goalkeepers 45, Defenders 148, Midfield 158, Forwards 102. I guess the possible number of teams is 22 x 45 x 148 x 147 x 146 x 145 x 158 x 157 x 156 x 102 x 101 x 100, which is immense and why I had to give up the VB loop method. The real problem is that even with a solid procedure that handles the 3 per team and cost<55 criteria I don't know how long SQLServer will take to process the possiblities or hoe large the output might be. Another option might be to exclude players with lower points, perhaps all those below the average.

 

[donutman]

...possible number of teams is 22 x 45 x 148 x 147 x 146 x 145 x 158 x 157 x 156 x 102 x 101 x 100, which is immense

What makes you think SQL Server can do it? It can't handle 1.8177660419575802E+24 rows.
-Karl

[red] Cursors, triggers, user-defined functions and dynamic SQL are an axis of evil![/red]
[green]Life's uncertain...eat dessert first...www.deerfieldbakery.com[/green]

 

[etoucan]

I don't yet know that SQLServer can't handle it by eliminating a large number of unrequired rows using the criteria I stipulated earlier. Do you know the maximum number of rows it can output?

 

[donutman]

Divide the number of bytes of free space you have by that immense number and get (a) real.
-Karl

[red] Cursors, triggers, user-defined functions and dynamic SQL are an axis of evil![/red]
[green]Life's uncertain...eat dessert first...www.deerfieldbakery.com[/green]

 

[vongrunt]

With such broad constraints, entire approach tends to be... bogus. Something like sorting numbers by shuffling them until they get sorted (aka: bogo-sort). Or using squad of monkeys for writing Shakespeare's stuff.

Idea: split team selection into few steps. Let user choose defenders first, then forwards etc... while controlling global constraints (like #1). Finally, someone may prefer defensive-oriented teams (for example) and dedicate more points there.

------
Math problems? Call 0800-[(10x)(13i)^2]-[sin(xy)/2.362x]

 

[donutman]

That's a brilliant idea. Perform random reads of the PlayerTable and check constraints as you go along within the VB program. You display each acceptable team as you get them, per the original post. You allow the person to terminate the process at any time. The SP for the defenders is something like this.

Select Top 4 PlayerID from PlayerTable 
   where PlayerType='Defender' order by NEWID()
[

You could even add a loop that does the constraint checking and returns only valid groups by adding a Cost parameter, but you would have to worry about getting into a situation where total cost gets too high. You could check for that by sorting cost desc, so that you know a solution can or can't be found at onset. This approach needs work, but it's doable.
-Karl

[red] Cursors, triggers, user-defined functions and dynamic SQL are an axis of evil![/red]
[green]Life's uncertain...eat dessert first...www.deerfieldbakery.com[/green]

 

[etoucan]

Thanks, this looks useful. Let me clarify further. The prime objective here is for a user to be able to select the best team at the start of a season based on last season's form. That's why I originally thought that the easy way to go was simply to find the best theoretical teams and let the user select from them. However, now I would agree that this approach is somewhat 'bogus' in terms of the potential magnitude of results returned.

Are you saying in this new approach that it's a sort of 'suck it and see' method depending on the user's preferences? Like, give him the options of the best players in any given position and then 'drill down' with othre options until he finds the best fit?

Could you please expand on the thought process? Anybody else's contributions/thhoughts are very welcome.