SQLug.se Challenge 2011

By | October 8, 2014

In 2011 I arranged the second round of the national Swedish SQL Server developer championship. Again the competition was run entirely in Swedish, but I think our competition problem could be interesting also outside of Sweden. It’s a very good example of “relational division” (a common database task).

SQLug.se Challenge Award

Competition problem 2011

Let’s assume you are running a dating website where members have entered personal information. Your task in this competition is to write an efficient search match-making function.

A search could for example look like this.

WantedSetID AttributeName AttributeValue
1 Gender F
1 Age B
1 Driver’s license B
2 Gender F
2 Age B
3 Gender M
3 Age C

Each WantedSetID represents a collection of search criteria. WantedSetID 1 has three criteria: gender must be F, age must be B and driver’s license must be B. Only people that fulfill all these critera should be returned as search results for WantedSetID 1.

The database contains the following tables.

  • People, a list of members of the dating site
  • PeopleAttribute, contains all the attribute values for all members
  • Attribute, a list of searchable attributes
  • WantedAttribute, that contains the search criteria (see example table above).

Task

Create a search function that finds all people that match the search criteria in WantedAttribute and return as a table.

PeopleID WantedSetID
1 2
2 1
2 2
3 2

Your task is to make the search function as fast as possible.

Other restrictions in the competition:

  • The solutions had to run on a SQL Server 2008 R2
  • T-SQL or SQLCLR is allowed
  • You are not allowed to make any changes to the MeterReadings table except creating non clustered indexes
  • Indexed views are not allowed

Author

This competition problem was authored by Peter Larsson and based on a real world scenario.

SQL Script & Test data

SQL setup script
Testdata

Winning solution

-- Göran Rönnbäck, SQL Service

CREATE NONCLUSTERED INDEX [IX_PeopleAttribute_ID_Value] ON [dbo].[PeopleAttribute]
(
[AttributeID] ASC,
[AttributeValue] ASC
)
INCLUDE ( [PeopleID]) WITH (PAD_INDEX = ON, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 100) ON [PRIMARY]

GO

CREATE NONCLUSTERED INDEX [IX_WantedAttribute_ID_Value] ON [dbo].[WantedAttribute]
(
[AttributeID] ASC,
[AttributeValue] ASC
)
INCLUDE ( [WantedSetID]) WITH (PAD_INDEX = ON, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, FILLFACTOR = 100) ON [PRIMARY]

GO

CREATE VIEW [dbo].[qryWantedPeople15]
WITH SCHEMABINDING
AS
SELECT w.WantedSetID, p.PeopleID, COUNT(*) AS qryWantedPeople_Count
FROM dbo.WantedAttribute w
CROSS APPLY (
SELECT PeopleID
FROM dbo.PeopleAttribute
WHERE w.AttributeID = AttributeID
AND w.AttributeValue = AttributeValue
-- AND ASCII(w.AttributeValue) = ASCII(AttributeValue)
) AS p
GROUP BY w.WantedSetID, p.PeopleID

GO

CREATE PROCEDURE [dbo].[SQLUG_GetRows_GR15]
AS

/*
DBCC DROPCLEANBUFFERS
DBCC FREEPROCCACHE
EXEC [dbo].[SQLUG_GetRows_GR15]
*/

SET NOCOUNT ON

SELECT People.PeopleID, People.WantedSetID
FROM qryWantedPeople15 People
WHERE People.qryWantedPeople_Count =

(
SELECT COUNT(*) AS Count_WantedSetID
FROM [dbo].[WantedAttribute] Wanted
WHERE Wanted.WantedSetID = People.WantedSetID
GROUP BY [WantedSetID]
)
OPTION (LOOP JOIN, MAXDOP 0);

GO

-- 2. Exekveringsdel

EXEC [dbo].[SQLUG_GetRows_GR15]

-- 3. Cleanup

IF EXISTS (SELECT * FROM sys.indexes WHERE object_id = OBJECT_ID(N'[dbo].[PeopleAttribute]') AND name = N'IX_PeopleAttribute_ID_Value')
DROP INDEX [IX_PeopleAttribute_ID_Value] ON [dbo].[PeopleAttribute] WITH ( ONLINE = OFF )

GO

IF EXISTS (SELECT * FROM sys.indexes WHERE object_id = OBJECT_ID(N'[dbo].[WantedAttribute]') AND name = N'IX_WantedAttribute_ID_Value')
DROP INDEX [IX_WantedAttribute_ID_Value] ON [dbo].[WantedAttribute] WITH ( ONLINE = OFF )

GO

IF EXISTS (SELECT * FROM sys.views WHERE object_id = OBJECT_ID(N'[dbo].[qryWantedPeople15]'))
DROP VIEW [dbo].[qryWantedPeople15]

GO

IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[SQLUG_GetRows_GR15]') AND type in (N'P', N'PC'))
DROP PROCEDURE [dbo].[SQLUG_GetRows_GR15]

GO