en-USsv-SE

Active Forums

PrevPrev Go to previous topic
NextNext Go to next topic
Last Post 21 Mar 2012 12:18 PM by  HenrikF
SQLug.se challenge 2011
 117 Replies
Sort:
You are not authorized to post a reply.
Page 1 of 612345 > >>
Author Messages
SwePeso
New Member
New Member
Posts: 67


--
12 Mar 2011 12:04 AM

    Nu drar årets svenska mästerskap för SQL Server utvecklare igång, arrangerat av SQLUG. Uppgiften är relativt enkel att komma igång med men svår att lösa optimalt.

    Tävlingen är både individuell och per företag. Som tävlande representerar man både sig själv som individ och det företag man jobbar på.

    Bästa individuella insats vinner ett presentkort på 990 kr hos Liveit, som kan användas till vin- och chokladprovning för två, prova stridsflygsimulator, spabehandling eller vad man nu föredrar.

    De bästa företagen belönas med följande vinster från Red Gate:

    1:a pris - Red Gate SQL Backup Pro, värde $795
    2:a pris - Red Gate SQL Virtual Restore, värde $495
    3:e pris - Red Gate SQL Prompt, värde $195

    Den största vinsten är naturligtvis äran att kunna titulera sig vinnare i SQLug.se challenge 2011!

    Tävlingssponsorer:




    Tävlingsuppgift

    Du driver en dating-site där personer har lagt upp sin personliga information. Uppgiften är nu att skriva en effektiv sökfunktion som söker enligt en uppsättning kriterier.

    Exempelvis kanske du söker efter dessa kriterier

    WantedSetID AttributeName AttributeValue
    1 Kön F
    1 ålder B
    1 Körkort B
    2 Kön F
    2 ålder B
    3 Kön M
    3 ålder C

    Uppgifterna ska tolkas som att i första hand söker du efter "en kvinna i ålder B som har körkort B", i andra hand "en kvinna i ålder B" och i tredje hand "en man i ålder C". Värdet på ett attribut är alltid av typen char(1). Sökningen är case insensitive.

    Sökkriterierna finns i en tabell som heter WantedAttribute. Som du ser är tabellen WantedAttribute flexibel och kan innehålla en eller flera sökset och varje sökset kan innehålla en eller flera matchnings-attribut. Sökfunktionen skall returnera vilka sökset som är uppfyllda och för vilka personer.

    Tävlingsuppgiften är att komma fram till en lösning som fixar uttaget så snabbt som möjligt. Vi vill ha prestanda! I första hand kommer vi att titta på den totala tiden (duration) för lösningen, eftersom det är den tiden slutanvändaren märker av. Skulle två eller flera lösningar vara ungefär lika i tid, kommer antalet processorer som används samt mängden reads att vägas in för att avgöra vilken lösning som är mer effektiv när den är ungefär lika snabb.

    Servern som kommer att användas för testkörningarna har 16 kärnor på 2.5GHz samt 56GB RAM varav 40GB är dedikerat till SQL Server Service. Diskarna finns på ett Hewlett Packard SAN. Första körningen körs med kall cache, övriga körningar med varm cache.

    Tabellerna innehåller följande data

    1) People innehåller namn på alla som anmält sig på siten
    2) Attribute innehåller alla attribut som går att registrera
    3) PeopleAttribute innehåller alla värden för alla attribut som alla People valt att spara
    4) WantedAttribute innehåller de värden som du vill söka på

    Med exempeldatat här kan du se att Carri inte matchar alla sökattribut för set 1 men gör det för set 2.

    Du ser att Robin matchar set 1 och övermatchar set 2. Du ser även att Vera inte matchar alla attribut för set 1 men övermatchar set 2. Ingen matchar set 3.

    Din SQL-kod skall returnera svaret som tabellrader. Sorteringsordning spelar ingen roll. Resultatet för exempeldatat blir

    PeopleID WantedSetID
    1 2
    2 1
    2 2
    3 2

    Material

    Ladda ned dessa script och kör i SQL Server Management Studio (eller annat favoritverktyg).

    Regler

    • Tävlingen är öppen för alla SQLUGs medlemmar.
    • Tävlingsbidrag postas som svar på detta forum. De skall märkas med namn och företag.
    • Vinnare är den/de som har presterat den snabbaste lösningen.
    • Tillåtna metoder är T-SQL och SQL CLR. SQL CLR måste köras i safe läge och källkoden måste bifogas.
    • Inga schemaförändringar på befintliga tabeller är tillåtna förutom att skapa icke-klustrade index.
    • Det är tillåtet att skapa index, vyer, funktioner och procedurer (men ej indexerade vyer). Lösningarna måste städa upp efter sig så att den kan köras om och om igen. Posta din lösning uppdelad på tre script: Setup, Huvudkod, Uppstädning
    • Eventuell vinstskatt betalas av vinnarna.
    • Lösningarna kommer att testköras på en större mängd testdata för att tävlingen skall bli utslagsgivande.
    • Tävlingen avgörs av en jury som består av Johan åhlén, Tibor Karaszi, Tobias Thernström och Peter Larsson.
    • Deadline för att komma med tävlingsbidrag är 26 maj kl 22:00 (svensk tid).

    Vinster

    Individuell tävling: Första pris är ett presentkort på 990 kr från liveit.se
    Företagstävling: De tre bästa lösningarna vinner licenser från Red Gate

    Hur du tävlar

    Posta din lösning på det här forumet. Skriv ditt namn och företagsnamn (om du också representerar ett företag/organisation).

    Frågor

    Frågor angående tävlingen ställs i detta forum.

    Lycka till!

    //Peter Larsson

    HenrikF
    New Member
    New Member
    Posts: 8


    --
    23 Mar 2011 01:19 PM
    Hej

    Intressant uppgift!

    Här kommer ett första försök till lösning:



    -- SETUP

    IF OBJECT_ID('tempdb..#NumberOfSetAttributes') IS NULL
    SELECT
    WantedSetID
    ,count(*) as NumberOfAttributes
    INTO #NumberOfSetAttributes
    FROM WantedAttribute
    GROUP BY WantedSetID



    -- MAIN CODE

    SELECT
    sub.PeopleID
    ,sub.WantedSetID
    FROM (
    SELECT
    PeopleID
    ,WantedSetID
    ,Count(*) as NumberOfMatchingAttributes
    FROM PeopleAttribute
    INNER JOIN WantedAttribute on PeopleAttribute.AttributeID = WantedAttribute.AttributeID AND PeopleAttribute.AttributeValue = WantedAttribute.AttributeValue
    GROUP BY PeopleID,WantedSetID
    ) sub
    INNER JOIN #NumberOfSetAttributes NumberOfSetAttributes on sub.WantedSetID = NumberOfSetAttributes.WantedSetID
    where sub.NumberOfMatchingAttributes = NumberOfSetAttributes.NumberOfAttributes



    -- CLEAN
    IF OBJECT_ID('tempdb..#NumberOfSetAttributes') IS NOT NULL
    DROP TABLE #NumberOfSetAttributes
    JAhlen
    Veteran Member
    Veteran Member
    Posts: 144


    --
    23 Mar 2011 01:24 PM
    HenrikF skrev:
    Hej

    Intressant uppgift!

    Här kommer ett första försök till lösning:


    Det var snabbt jobbat! Tyvärr är inte bidraget tillåtet eftersom det inte är tillåtet att skapa temporärtabeller i setup-scriptet. Om du flyttar skapandet av temporärtabellen till huvudscriptet är det OK!

    MVH
    Johan

    HenrikF
    New Member
    New Member
    Posts: 8


    --
    23 Mar 2011 01:49 PM
    Ok där ser man, men vad får man egentligen göra i Setupdelen? Jag gissar att man rimligen inte får skapa "vanliga" tabeller heller?


    Här kommer hur som helst en redigerad version:




    -- SETUP
    -- Do Nothing


    -- MAIN CODE


    IF OBJECT_ID('tempdb..#NumberOfSetAttributes') IS NULL
    SELECT
    WantedSetID
    ,count(*) as NumberOfAttributes
    INTO #NumberOfSetAttributes
    FROM WantedAttribute
    GROUP BY WantedSetID


    SELECT
    sub.PeopleID
    ,sub.WantedSetID
    FROM (
    SELECT
    PeopleID
    ,WantedSetID
    ,Count(*) as NumberOfMatchingAttributes
    FROM PeopleAttribute
    INNER JOIN WantedAttribute on PeopleAttribute.AttributeID = WantedAttribute.AttributeID AND PeopleAttribute.AttributeValue = WantedAttribute.AttributeValue
    GROUP BY PeopleID,WantedSetID
    ) sub
    INNER JOIN #NumberOfSetAttributes NumberOfSetAttributes on sub.WantedSetID = NumberOfSetAttributes.WantedSetID
    where sub.NumberOfMatchingAttributes = NumberOfSetAttributes.NumberOfAttributes


    IF OBJECT_ID('tempdb..#NumberOfSetAttributes') IS NOT NULL
    DROP TABLE #NumberOfSetAttributes


    -- CLEAN
    -- Do Nothing
    JAhlen
    Veteran Member
    Veteran Member
    Posts: 144


    --
    23 Mar 2011 02:04 PM
    HenrikF skrev:
    Ok där ser man, men vad får man egentligen göra i Setupdelen? Jag gissar att man rimligen inte får skapa "vanliga" tabeller heller?



    Det står i reglerna vad man får göra. Man får skapa icke-klustrade index, vyer, funktioner och procedurer.

    Zhong
    New Member
    New Member
    Posts: 11


    --
    23 Mar 2011 06:47 PM


    -- Lösning 1:

    select t1.PeopleID, t1.WantedSetID
    from (
    select pa.PeopleID, wa.WantedSetID,
    ROW_NUMBER() over (partition by pa.PeopleID, wa.WantedSetID order by PeopleAttributeID) as rownbr
    from PeopleAttribute pa
    join WantedAttribute wa on pa.AttributeID = wa.AttributeID
    and pa.AttributeValue = wa.AttributeValue
    ) t1 join (
    select WantedSetID,
    ROW_NUMBER() over (partition by WantedSetID order by WantedAttributeID) as rownbr
    from WantedAttribute
    ) t2 on t1.WantedSetID = t2.WantedSetID
    group by t1.PeopleID, t1.WantedSetID
    having max(t1.rownbr) = max(t2.rownbr)


    -- Lösning 2:

    select t1.PeopleID, t1.WantedSetID
    from (
    select pa.PeopleID, wa.WantedSetID, COUNT(*) AS cnt
    from PeopleAttribute pa
    join WantedAttribute wa on pa.AttributeID = wa.AttributeID
    and pa.AttributeValue = wa.AttributeValue
    group by pa.PeopleID, wa.WantedSetID
    ) t1 join (
    select WantedSetID, Count(*) as cnt
    from WantedAttribute
    group by WantedSetID
    ) t2 on t1.WantedSetID = t2.WantedSetID and t1.cnt = t2.cnt

    Zhong
    New Member
    New Member
    Posts: 11


    --
    23 Mar 2011 07:37 PM

    Lösning 3:

    select pa.PeopleID, wa.WantedSetID
    from PeopleAttribute pa
    join WantedAttribute wa on pa.AttributeID = wa.AttributeID
    and pa.AttributeValue = wa.AttributeValue
    group by pa.PeopleID, wa.WantedSetID
    having COUNT(*) = (
    select Count(*)
    from WantedAttribute
    where WantedSetID = wa.WantedSetID
    )
    Malin Fröier
    New Member
    New Member
    Posts: 3


    --
    23 Mar 2011 08:30 PM
    /* Malin Davidsson, Affecto*/
    --Här kommer förslag 1:


    --setup
    create function dbo.fn_GetNbr(@WantedSetID as int)
    returns @test table
    ( nbr int)
    as
    begin
    insert into @test (nbr)
    select COUNT(*)
    from dbo.WantedAttribute
    where WantedSetID=@WantedSetID
    return
    END
    GO

    --main
    select pa.PeopleID, wa.WantedSetID
    from WantedAttribute wa
    join PeopleAttribute pa
    on wa.AttributeID=pa.AttributeID and wa.AttributeValue=pa.AttributeValue
    cross apply fn_GetNbr(wa.WantedSetID) as t
    group by pa.PeopleID, wa.WantedSetID, t.nbr
    having t.nbr=COUNT(*)

    --clean
    drop function fn_GetNbr

    Malin Fröier
    New Member
    New Member
    Posts: 3


    --
    23 Mar 2011 09:27 PM
    /* Malin Davidsson, Affecto*/
    --förslag 2:

    select pa.PeopleID,wa.WantedSetID
    from WantedAttribute wa
    join PeopleAttribute pa
    on wa.AttributeID=pa.AttributeID and wa.AttributeValue=pa.AttributeValue
    right join WantedAttribute wa2
    on wa.WantedSetID=wa2.WantedSetID
    group by pa.PeopleID,wa.WantedSetID
    having count(distinct wa.AttributeID)= count(distinct wa2.AttributeID)

    JAhlen
    Veteran Member
    Veteran Member
    Posts: 144


    --
    24 Mar 2011 08:58 AM
    Tack för bidragen Henrik, Zhong och Malin. Vi kommer att testa dem och rapportera hur ni ligger till!

    Vi har beslutat att dölja inskickade bidrag. Detta för att förhindra att man kan kopiera från varandras bidrag. Ni postar som vanligt till forumet, men era bidrag blir inte synliga förrän deadline för tävlingen är över.
    SwePeso
    New Member
    New Member
    Posts: 67


    --
    24 Mar 2011 09:17 AM
    Preliminär ställning

    Placering (efter duration)

    Lösning (efter namn)

    Anteckning

    1 HenrikF 1, Patrik Molin 1, Zhong 2
    4 Zhong 3
    5 MalinD 1
    MalinD 2, Zhong 1 Tar mer än 12 minuter. Testet har avbrutits.
    Zhong 4 Returnerar inte rätt resultat.
















    Zhong
    New Member
    New Member
    Posts: 11


    --
    24 Mar 2011 10:07 AM

    Lösning 4:

    SELECT PeopleID, WantedSetID
    FROM (
    SELECT PeopleID,
    ( SELECT CAST(AttributeID as varchar(3)) + AttributeValue
    FROM PeopleAttribute
    where PeopleID = pa.PeopleID
    ORDER BY PeopleID, AttributeID, AttributeValue
    FOR XML PATH('') ) AS Have
    FROM PeopleAttribute pa
    GROUP BY PeopleID
    ) PA,
    (
    SELECT WantedSetID,
    ( SELECT CAST(AttributeID as varchar(3)) + AttributeValue
    FROM WantedAttribute
    where WantedSetID = wa.WantedSetID
    ORDER BY WantedSetID, AttributeID, AttributeValue
    FOR XML PATH('') ) AS Wanted
    FROM WantedAttribute wa
    GROUP BY WantedSetID
    ) WA
    WHERE LEFT(PA.HAVE, LEN(WA.Wanted)) = WA.Wanted

    HenrikF
    New Member
    New Member
    Posts: 8


    --
    24 Mar 2011 10:36 AM
    Ni har inte lust att bjuda på lite mer testdata?

    Det skulle verkligen underlätta!
    SwePeso
    New Member
    New Member
    Posts: 67


    --
    24 Mar 2011 10:48 AM
    Vi har fått en förfrågan om att publicera mer testdata. Vi tycker inte det behövs från vår sida.



    Ni har alla tabeller och uppgifter. Försök skapa mer testdata och se hur er lösning skalar.

    Den testdata jag använder har jag genererat med hjälp av Data Generator från RedGate.



    Utan att avslöja för mycket så kan jag säga att People har mellan 500 000 och 5 000 000 medlemmar, Attribute har mellan 20 och 200 attribut, PeopleAttribute har mellan 2 000 000 och 20 000 000 rader samt WantedAttribute har mellan 100 och 1 000 rader.

    Detta för att ni ska få en uppfattning om mängden data om era lösningar testas mot.



    Vi har dessutom två uppsättningar av tabeller. En för att enhetstesta lösningarna dvs se att de ger rätt resultat. Dessa tabeller har en mängd edge-conditions och andra kombinationer för att se att lösningen verkligen genererar rätt resultat.



    Den andra uppsättningen av tabeller är den vi mäter tiderna på, som du kan läsa om i stycket ovan.



    Ett snabbt sätt att få fram ett slumptal inom ett givet intervall är SELECT ABS(CHECKSUM(NEWID())) % 100 -- Ger ett positivt slumptal mellan 0 och 99.

    Om ni vill ha en generisk uppsättning av testdata som är hyfsat stort och komplicerat, kör denna kod





    TRUNCATE TABLE dbo.PeopleAttribute



    TRUNCATE TABLE dbo.WantedAttribute



    DELETE FROM dbo.People



    DBCC CHECKIDENT('dbo.People', RESEED, 0)



    DELETE FROM dbo.Attribute



    DBCC CHECKIDENT('dbo.Attribute', RESEED, 0)



    INSERT dbo.People (FirstName, LastName,SSN)

    SELECT Number, Number, Number

    FROM master..spt_values

    WHERE type = 'P' AND number BETWEEN 1 AND 255



    INSERT dbo.Attribute (AttributeName)

    SELECT Number

    FROM master..spt_values

    WHERE type = 'P' AND number BETWEEN 1 AND 255



    INSERT dbo.PeopleAttribute (PeopleID,AttributeID,AttributeValue)

    SELECT p.Number, a.Number, 'x'

    FROM master..spt_values AS p

    INNER JOIN master..spt_values AS a ON a.type = 'P' AND a.number BETWEEN 1 AND p.number

    WHERE p.type = 'P' AND p.number BETWEEN 1 AND 255



    INSERT dbo.WantedAttribute (WantedSetID, AttributeID, AttributeValue)

    SELECT s.Number, a.Number, 'x'

    FROM master..spt_values AS s

    INNER JOIN master..spt_values AS a ON a.type = 'P' AND a.number BETWEEN 1 AND s.number

    WHERE s.type = 'P' AND s.number BETWEEN 1 AND 255

    Patrik Molin
    New Member
    New Member
    Posts: 2


    --
    24 Mar 2011 11:58 AM
    Patrik Molin's första bidrag

    select distinct pa.PeopleID, w.WantedSetID--, COUNT(*) as count
    from PeopleAttribute pa
    inner join WantedAttribute w on pa.AttributeID = w.AttributeID and pa.AttributeValue = w.AttributeValue
    group by pa.PeopleID, WantedSetID
    Having COUNT(*) >= (select COUNT(*) as count
    from WantedAttribute w1
    where w.WantedSetID = w1.WantedSetID
    group by w1.WantedSetID )
    Zhong
    New Member
    New Member
    Posts: 11


    --
    24 Mar 2011 01:59 PM
    Hej,



    Lite överraskad att lösning 4 inte fungerade. Kanske har missat lite i copy-paste. Skicka igen med lite förändring. Resultat är sorterad. Det måste finnas bra lösningar som inte är baserad på att räkna antal av attribute. Lösningen 4 är ett försök.



    Lösning 4:

    -- borttagen av moderator --





    Hej!



    Problemet med din lösning är att HAVE kan t.ex få sekvensen "1A2B3C" medan WANT kan få sekvensen "1A3C".

    Då övermatchar medlemmen det som krävs men din lösning ser inte det.



    //Peter



    Zhong
    New Member
    New Member
    Posts: 11


    --
    25 Mar 2011 11:29 AM
    Här är en ny version:


    SELECT pa.PeopleID, wa.WantedSetID
    FROM (
    SELECT PeopleID, SUBTABLE(AttributeID, AttributeValue) AS Have
    FROM PeopleAttribute pa
    GROUP BY PeopleID
    ) pa JOIN (
    SELECT WantedSetID, SUBTABLE(AttributeID, AttributeValue) AS Wanted
    FROM WantedAttribute wa
    GROUP BY WantedSetID
    ) wa ON pa.Have CONTAINS wa.Wanted


    Självklart det är bara min önsketanke. SQL är inte så SET-orienterad som vi vill men vi får hoppas i framtiden blir det möjligt.

    Istället blir en lösning 4 som kan fungera:



    --setup
    CREATE FUNCTION dbo.IsSubSet
    (
    @Wanted nvarchar(2000),
    @Have nvarchar(2000)
    )
    RETURNS bit
    AS
    BEGIN
    DECLARE
    @wPos int = 1,
    @hPos int = 1,
    @wLen int = LEN(@Wanted),
    @hLen int = LEN(@Have)

    WHILE @wPos <= @wLen
    BEGIN
    IF @hPos > @hLen RETURN 0
    IF SUBSTRING(@Wanted, @wPos, 1) = SUBSTRING(@Have, @hPos, 1)
    SET @wPos += 1
    SET @hPos += 1
    END
    RETURN 1
    END
    GO

    -- main
    SELECT PeopleID, WantedSetID
    FROM (
    SELECT PeopleID, (
    SELECT NCHAR(AttributeID * 255 + ASCII(AttributeValue))
    FROM PeopleAttribute
    WHERE PeopleID = pa.PeopleID
    ORDER BY PeopleID, AttributeID, AttributeValue
    FOR XML PATH('') ) AS Have
    FROM PeopleAttribute pa
    GROUP BY PeopleID
    ) PA JOIN (
    SELECT WantedSetID, (
    SELECT NCHAR(AttributeID * 255 + ASCII(AttributeValue))
    FROM WantedAttribute
    WHERE WantedSetID = wa.WantedSetID
    ORDER BY WantedSetID, AttributeID, AttributeValue
    FOR XML PATH('') ) AS Wanted
    FROM WantedAttribute wa
    GROUP BY WantedSetID
    ) WA ON dbo.IsSubSet(wa.Wanted, pa.Have) = 1


    select pa.PeopleID, wa.WantedSetID
    from PeopleAttribute pa
    join WantedAttribute wa on pa.AttributeID = wa.AttributeID
    and pa.AttributeValue = wa.AttributeValue
    group by pa.PeopleID, wa.WantedSetID
    having COUNT(*) = (
    select Count(*)
    from WantedAttribute
    where WantedSetID = wa.WantedSetID
    )

    -- cleanup
    DROP FUNCTION dbo.IsSubSet
    GO
    JAhlen
    Veteran Member
    Veteran Member
    Posts: 144


    --
    26 Mar 2011 10:31 AM
    Preliminär ställning

    ***************************************************************************
    * Namn * Företag * Tid * Placering *
    ***************************************************************************
    * HenrikF 1 * * XXX XXX * 1 *
    * Patrik Molin 1 * Affecto * XXX XXX * 1 *
    * Zhong 2 * B3IT * XXX XXX * 1 *
    * Zhong 3 * B3IT * XXX XXX * 4 *
    * Per Scheffer 1 * Bizware * XXX XXX * 4 *
    * Malin Davidsson 1 * Affecto * XXX XXX * 6 *
    * Zhong 1 * B3IT * Timeout * 7 *
    * Malin Davidsson 2 * Affecto * Timeout * 7 *
    ***************************************************************************

    Zhong 4 ger inte rätt resultat.

    Vänligen skriv vilket företag ni representerar i inskickade lösningar.

    Don
    New Member
    New Member
    Posts: 1


    --
    26 Mar 2011 10:54 AM
    Ditt förslag på mer testdata Peso skapar ju fler/nya AttributeID. Finns där en gräns för antal AttributeID i testet eller måste lösningen klara oändligt?
    SwePeso
    New Member
    New Member
    Posts: 67


    --
    26 Mar 2011 11:25 AM
    Nej, inte oändligt. Tabellen är definierad med TINYINT som datatyp, så i alla fall 255 stycken olika attribut ska den klara.

    Blir de inskickade lösningarna ungefär lika snabba så kan vi behöva göra om AttributeID till SMALLINT för att det ska bli utslagsgivande för en betydligt större mängd testdata.
    You are not authorized to post a reply.
    Page 1 of 612345 > >>