Detta är en del av en SQL Server Internals Problematic Operators-serie. För att läsa det första inlägget, klicka här.
SQL Server har funnits i över 30 år, och jag har arbetat med SQL Server nästan lika länge. Jag har sett många förändringar under åren (och decennier!) och versioner av denna otroliga produkt. I dessa inlägg kommer jag att dela med mig av hur jag ser på några av funktionerna eller aspekterna av SQL Server, ibland tillsammans med lite historiskt perspektiv.
Förra gången pratade jag om en skanningsoperation i en SQL Server-frågeplan som en potentiellt problematisk operatör i SQL Server-diagnostik. Även om skanningar ofta används bara för att det inte finns något användbart index, finns det tillfällen då skanningen faktiskt är ett bättre val än en indexsökningsoperation.
I den här artikeln kommer jag att berätta om en annan familj av operatörer som ibland ses som problematisk:hashing. Hashing är en mycket välkänd databehandlingsalgoritm som har funnits i många decennier. Jag studerade det i mina datastrukturklasser långt tillbaka när jag först studerade datavetenskap på universitetet. Om du vill ha bakgrundsinformation om hash- och hashfunktioner kan du kolla in den här artikeln på Wikipedia. SQL Server lade dock inte till hashing till sin repertoar av frågebearbetningsalternativ förrän SQL Server 7. (Som ett undantag ska jag nämna att SQL Server använde hash i några av sina egna interna sökalgoritmer. Som Wikipedia-artikeln nämner , använder hashing en speciell funktion för att mappa data av godtycklig storlek till data av en fast storlek. SQL använde hashing som en sökteknik för att mappa varje sida från en databas av godtycklig storlek till en buffert i minnet, vilket är en fast storlek. Faktum är att , brukade det finnas ett alternativ för sp_configure kallade "hash-buckets", som gjorde det möjligt för dig att kontrollera antalet hinkar som används för hashning av databassidor till minnesbuffertar.)
Vad är hashing?
Hashing är en sökteknik som inte kräver att data beställs. SQL Server kan använda den för JOIN-operationer, aggregeringsoperationer (DISTINCT eller GROUP BY) eller UNION-operationer. Vad dessa tre operationer har gemensamt är att sökmotorn letar efter matchande värden under exekvering. I en JOIN vill vi hitta rader i en tabell (eller raduppsättning) som har matchande värden med rader i en annan. (Och ja, jag är medveten om kopplingar som inte jämför rader baserade på jämlikhet, men de icke likvärdiga kopplingarna är irrelevanta för den här diskussionen.) För GROUP BY hittar vi matchande värden som ska inkluderas i samma grupp, och för UNION och DISTINCT letar vi efter matchande värden för att utesluta dem. (Ja, jag vet att UNION ALL är ett undantag.)
Före SQL Server 7 var det enda sättet som dessa operationer lätt kunde hitta matchande värden om data sorterades. Så om det inte fanns något befintligt index som upprätthöll data i sorterad ordning, skulle frågeplanen lägga till en SORT-operation till planen. Hashing organiserar din data för effektiv sökning genom att lägga alla rader som har samma resultat från den interna hashfunktionen i samma "hash-bucket".
För en mer detaljerad förklaring av SQL Servers hash JOIN-operation, inklusive diagram, ta en titt på det här blogginlägget från SQL Shack.
När hash blev ett alternativ, ignorerade SQL Server inte helt möjligheten att sortera data före sammanfogning eller aggregering, men det blev bara en möjlighet för optimeraren att överväga. I allmänhet, men om du försöker gå med, aggregera eller utföra UNION på osorterade data, kommer optimeraren vanligtvis att välja en hashoperation. Så många människor antar att en HASH JOIN (eller annan HASH-operation) i en plan betyder att du inte har lämpliga index och att du bör bygga lämpliga index för att undvika hash-operationen.
Låt oss titta på ett exempel. Jag skapar först två oindexerade tabeller.
USE AdventureWorks2016 GO DROP TABLE IF EXISTS Details;
GO
SELECT * INTO Details FROM Sales.SalesOrderDetail;
GO
DROP TABLE IF EXISTS Headers;
GO
SELECT * INTO Headers FROM Sales.SalesOrderHeader;
GO
Now, I’ll join these two tables together and filter the rows in the Details table:
SELECT *
FROM Details d JOIN Headers h
ON d.SalesOrderID = h.SalesOrderID
WHERE SalesOrderDetailID < 100;
Quest Spotlight Tuning Pack verkar inte indikera att hash-anslutningen är ett problem. Den markerar bara de två tabellskanningarna.
Förslagen rekommenderar att man bygger ett index på varje tabell som inkluderar varje enskild icke-nyckelkolumn som en INKLUDERAD kolumn. Jag tar sällan de rekommendationerna (som jag nämnde i mitt tidigare inlägg). Jag bygger bara indexet på Detaljer tabell, i sammanfogningskolumnen och inte ha några inkluderade kolumner.
CREATE INDEX Header_index on Headers(SalesOrderID);
När det indexet är byggt försvinner HASH JOIN. Indexet sorterar data i Rubrikerna tabell och tillåter SQL Server att hitta de matchande raderna i den inre tabellen med hjälp av indexets sorteringssekvens. Nu är den dyraste delen av planen skanningen på det yttre bordet (Detaljer ) som kan minskas genom att bygga ett index på SalesOrderID kolumnen i den tabellen. Jag lämnar det som en övning för läsaren.
En plan med en HASH JOIN är dock inte alltid en dålig sak. Den alternativa operatören (förutom i speciella fall) är en NESTED LOOPS JOIN, och det är vanligtvis valet när bra index finns. En NESTED loops-operation kräver dock flera sökningar i den inre tabellen. Följande pseudokod visar de kapslade loops join-algoritmen:
for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
Som namnet indikerar utförs en NESTED LOOP JOIN som en kapslad loop. Sökningen av den inre tabellen kommer vanligtvis att utföras flera gånger, en gång för varje kvalificerande rad i den yttre tabellen. Även om det bara är några få procent av raderna som kvalificerar sig, om tabellen är väldigt stor (kanske i hundratals miljoner, eller miljarder eller rader) kommer det att bli många rader att läsa. I ett system som är I/O-bundet kan dessa miljoner eller miljarder avläsningar vara en riktig flaskhals.
En HASH JOIN, å andra sidan, gör inte flera läsningar av någon av tabellen. Den läser den yttre tabellen en gång för att skapa hash-hinkarna, och sedan läser den den inre tabellen en gång och kontrollerar hash-hinkarna för att se om det finns en matchande rad. Vi har en övre gräns på ett enda pass genom varje bord. Ja, det finns CPU-resurser som behövs för att beräkna hashfunktionen och hantera innehållet i hinkarna. Det finns minnesresurser som behövs för att lagra hashad information. Men om du har ett I/O-bundet system kan du ha minne och CPU-resurser över. HASH JOIN kan vara ett rimligt val för optimeraren i dessa situationer där dina I/O-resurser är begränsade och du går med i mycket stora tabeller.
Här är pseudokoden för hash join-algoritmen:
for each row R1 in the build table
begin
calculate hash value on R1 join key(s)
insert R1 into the appropriate hash bucket
end
for each row R2 in the probe table
begin
calculate hash value on R2 join key(s)
for each row R1 in the corresponding hash bucket
if R1 joins with R2
output (R1, R2)
end
Som nämnts tidigare kan hashning också användas för aggregeringsoperationer (liksom UNION). Återigen, om det finns ett användbart index som redan har data sorterad, kan gruppering av data göras mycket effektivt. Men det finns också många situationer där hashing inte alls är en dålig operatör. Överväg en fråga som följande, som grupperar data i Detaljer tabell (skapad ovan) av Produkt-ID kolumn. Det finns 121 317 rader i tabellen och bara 266 olika Produkt-ID värden.
SELECT ProductID, count(*)
FROM Details
GROUP BY ProductID;
GO
Använda hashoperationer
För att använda hashing behöver SQL Server bara skapa och underhålla 266 hinkar, vilket inte är mycket. Faktum är att Quest Spotlight Tuning Pack inte indikerar att det är några problem med den här frågan. 
Ja, det måste göra en tabellskanning, men det beror på att vi måste undersöka varje rad i tabellen, och vi vet att skanningar inte alltid är en dålig sak. Ett index skulle bara hjälpa till med försorteringen av data, men att använda hash-aggregering för ett så litet antal grupper ger vanligtvis rimliga prestanda även utan något användbart index tillgängligt.
Liksom tabellskanningar ses hashoperationer ofta som en "dålig" operatör att ha i en plan. Det finns fall där du kan förbättra prestandan avsevärt genom att lägga till användbara index för att ta bort hashoperationerna, men det är inte alltid sant. Och om du försöker begränsa antalet index på tabeller som är kraftigt uppdaterade, bör du vara medveten om att hashoperationer inte alltid är något som måste "fixas", så att lämna frågan för att använda en hash kan vara en rimlig sak att göra. Dessutom, för vissa frågor på stora tabeller som körs på I/O-bundna system, kan hash faktiskt ge bättre prestanda än alternativa algoritmer på grund av det begränsade antalet läsningar som behöver utföras. Det enda sättet att veta säkert är att testa olika möjligheter på ditt system, med dina frågor och dina data.
I följande inlägg i den här serien kommer jag att berätta om andra problematiska operatörer som kan dyka upp i dina frågeplaner, så kom tillbaka snart!