Dette er en del af en SQL Server Internals Problematic Operators-serie. For at læse det første indlæg, klik her.
SQL Server har eksisteret i over 30 år, og jeg har arbejdet med SQL Server i næsten lige så lang tid. Jeg har set en masse ændringer gennem årene (og årtier!) og versioner af dette utrolige produkt. I disse indlæg vil jeg dele med dig, hvordan jeg ser på nogle af funktionerne eller aspekterne af SQL Server, nogle gange sammen med en smule historisk perspektiv.
Sidste gang talte jeg om en scanningsoperation i en SQL Server-forespørgselsplan som en potentielt problematisk operatør i SQL Server-diagnostik. Selvom scanninger ofte kun bruges, fordi der ikke er noget nyttigt indeks, er der tidspunkter, hvor scanningen faktisk er et bedre valg end en indekssøgningsoperation.
I denne artikel vil jeg fortælle dig om en anden familie af operatører, der lejlighedsvis ses som problematisk:hashing. Hashing er en meget velkendt databehandlingsalgoritme, der har eksisteret i mange årtier. Jeg studerede det i mine datastrukturklasser helt tilbage, da jeg første gang studerede datalogi på universitetet. Hvis du gerne vil have baggrundsinformation om hash- og hashfunktioner, kan du tjekke denne artikel på Wikipedia. SQL Server tilføjede dog ikke hashing til sit repertoire af forespørgselsbehandlingsmuligheder før SQL Server 7. (Som en sidebemærkning vil jeg nævne, at SQL Server brugte hashing i nogle af sine egne interne søgealgoritmer. Som Wikipedia-artiklen nævner , bruger hashing en speciel funktion til at kortlægge data af vilkårlig størrelse til data af en fast størrelse. SQL brugte hashing som en søgeteknik til at kortlægge hver side fra en database af vilkårlig størrelse til en buffer i hukommelsen, som har en fast størrelse. Faktisk , plejede der at være en mulighed for sp_configure kaldet 'hash buckets', som tillod dig at kontrollere antallet af buckets, der blev brugt til hashing af databasesider til hukommelsesbuffere.)
Hvad er hashing?
Hashing er en søgeteknik, der ikke kræver, at dataene skal bestilles. SQL Server kan bruge den til JOIN-operationer, aggregeringsoperationer (DISTINCT eller GROUP BY) eller UNION-operationer. Fælles for disse tre operationer er, at forespørgselsmotoren under udførelsen leder efter matchende værdier. I en JOIN ønsker vi at finde rækker i en tabel (eller rækkesæt), der har matchende værdier med rækker i en anden. (Og ja, jeg er klar over joinforbindelser, der ikke sammenligner rækker baseret på lighed, men disse ikke-equijoins er irrelevante for denne diskussion.) For GROUP BY finder vi matchende værdier, der skal inkluderes i den samme gruppe, og for UNION og DISTINCT søger vi efter matchende værdier for at udelukke dem. (Ja, jeg ved, at UNION ALL er en undtagelse.)
Før SQL Server 7 var den eneste måde, disse operationer nemt kunne finde matchende værdier på, hvis dataene blev sorteret. Så hvis der ikke var noget eksisterende indeks, der vedligeholdt dataene i sorteret rækkefølge, ville forespørgselsplanen tilføje en SORT-operation til planen. Hashing organiserer dine data til effektiv søgning ved at lægge alle de rækker, der har samme resultat fra den interne hash-funktion, i den samme 'hash-bucket'.
For en mere detaljeret forklaring af SQL Servers hash JOIN-operation, inklusive diagrammer, tag et kig på dette blogindlæg fra SQL Shack.
Når først hashing blev en mulighed, ignorerede SQL Server ikke fuldstændigt muligheden for at sortere data før sammenføjning eller aggregering, men det blev bare en mulighed for optimeringsværktøjet at overveje. Generelt, men hvis du forsøger at tilslutte, samle eller udføre UNION på usorterede data, vil optimeringsværktøjet normalt vælge en hash-handling. Så mange mennesker antager, at en HASH JOIN (eller anden HASH-operation) i en plan betyder, at du ikke har passende indekser, og at du bør bygge passende indekser for at undgå hash-operationen.
Lad os se på et eksempel. Jeg vil først oprette to uindekserede 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 lader ikke til at angive hash-tilslutningen som et problem. Det fremhæver kun de to tabelscanninger.
Forslagene anbefaler at bygge et indeks på hver tabel, der inkluderer hver enkelt ikke-nøglekolonne som en INKLUDERT kolonne. Jeg tager sjældent imod disse anbefalinger (som jeg nævnte i mit tidligere indlæg). Jeg bygger kun indekset på Detaljer tabel, på sammenføjningskolonnen og ikke have nogen inkluderede kolonner.
CREATE INDEX Header_index on Headers(SalesOrderID);
Når først det indeks er bygget, forsvinder HASH JOIN. Indekset sorterer dataene i Overskrifterne tabel og tillader SQL Server at finde de matchende rækker i den indre tabel ved hjælp af indeksets sorteringssekvens. Nu er den dyreste del af planen scanningen på det ydre bord (Detaljer ) som kunne reduceres ved at bygge et indeks på SalesOrderID kolonne i denne tabel. Det vil jeg efterlade som en øvelse til læseren.
En plan med et HASH JOIN er dog ikke altid en dårlig ting. Den alternative operatør (undtagen i særlige tilfælde) er en NESTED LOOPS JOIN, og det er normalt valget, når gode indekser er til stede. En NESTED loops-operation kræver dog flere søgninger i den indre tabel. Følgende pseudokode viser den indlejrede sløjfer-sammenføjningsalgoritme:
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 navnet indikerer, udføres en NESTED LOOP JOIN som en indlejret løkke. Søgningen i den indre tabel vil normalt blive udført flere gange, én gang for hver kvalificerende række i den ydre tabel. Selvom der kun er nogle få procent af rækkerne, der kvalificerer sig, hvis tabellen er meget stor (måske i hundredvis af millioner, eller milliarder eller rækker), vil det være mange rækker at læse. I et system, der er I/O-bundet, kan disse millioner eller milliarder af læsninger være en reel flaskehals.
En HASH JOIN udfører på den anden side ikke flere læsninger af nogen af tabellerne. Den læser den ydre tabel én gang for at skabe hash-bøtterne, og derefter læser den den indre tabel én gang og tjekker hash-bøtterne for at se, om der er en matchende række. Vi har en øvre grænse på en enkelt passage gennem hvert bord. Ja, der er behov for CPU-ressourcer til at beregne hash-funktionen og administrere indholdet af buckets. Der er nødvendige hukommelsesressourcer til at gemme den hash-kodede information. Men hvis du har et I/O-bundet system, har du muligvis hukommelse og CPU-ressourcer til overs. HASH JOIN kan være et rimeligt valg for optimizeren i disse situationer, hvor dine I/O-ressourcer er begrænsede, og du deltager i meget store borde.
Her er pseudokode for 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 tidligere nævnt kan hashing også bruges til aggregeringsoperationer (såvel som UNION). Igen, hvis der er et nyttigt indeks, der allerede har dataene sorteret, kan gruppering af data gøres meget effektivt. Der er dog også mange situationer, hvor hashing slet ikke er en dårlig operatør. Overvej en forespørgsel som den følgende, som grupperer dataene i Detaljer tabel (oprettet ovenfor) af ProductID kolonne. Der er 121.317 rækker i tabellen og kun 266 forskellige ProduktID værdier.
SELECT ProductID, count(*)
FROM Details
GROUP BY ProductID;
GO
Brug af hashing-operationer
For at bruge hashing skal SQL Server kun oprette og vedligeholde 266 buckets, hvilket ikke er en hel masse. Faktisk angiver Quest Spotlight Tuning Pack ikke, at der er problemer med denne forespørgsel. 
Ja, den skal lave en tabelscanning, men det er fordi, vi skal undersøge hver række i tabellen, og vi ved, at scanninger ikke altid er en dårlig ting. Et indeks ville kun hjælpe med forudsorteringen af dataene, men brug af hash-aggregering for et så lille antal grupper vil stadig normalt give en rimelig ydeevne, selv uden et nyttigt indeks tilgængeligt.
Ligesom tabelscanninger ses hashing-operationer ofte som en "dårlig" operatør at have i en plan. Der er tilfælde, hvor du i høj grad kan forbedre ydeevnen ved at tilføje nyttige indekser for at fjerne hash-handlingerne, men det er ikke altid sandt. Og hvis du forsøger at begrænse antallet af indekser på tabeller, der er stærkt opdaterede, skal du være opmærksom på, at hash-operationer ikke altid er noget, der skal 'rettes', så det kan være rimeligt at lade forespørgslen bruge en hash at gøre. Derudover, for visse forespørgsler på store tabeller, der kører på I/O-bundne systemer, kan hashing faktisk give bedre ydeevne end alternative algoritmer på grund af det begrænsede antal læsninger, der skal udføres. Den eneste måde at vide det med sikkerhed er at teste forskellige muligheder på dit system med dine forespørgsler og dine data.
I det følgende indlæg i denne serie vil jeg fortælle dig om andre problematiske operatører, der kan dukke op i dine forespørgselsplaner, så tjek snart tilbage!