Quando e perché i join di database sono costosi?

StackOverflow https://stackoverflow.com/questions/173726

Domanda

Sto facendo delle ricerche sui database e sto esaminando alcune limitazioni dei DB relazionali.

Sto ottenendo che i join di tabelle di grandi dimensioni sono molto costosi, ma non sono completamente sicuro del perché. Cosa deve fare il DBMS per eseguire un'operazione di join, dov'è il collo di bottiglia?
In che modo la denormalizzazione può aiutare a superare questa spesa? In che modo aiutano altre tecniche di ottimizzazione (ad esempio l'indicizzazione)?

Le esperienze personali sono benvenute! Se hai intenzione di pubblicare collegamenti a risorse, evita Wikipedia. So già dove trovarlo.

In relazione a questo, mi chiedo quali siano gli approcci denormalizzati utilizzati dai database dei servizi cloud come BigTable e SimpleDB. Vedi questa domanda .

È stato utile?

Soluzione

Denormalizzare per migliorare le prestazioni? Sembra convincente, ma non trattiene l'acqua.

Chris Date, che in collaborazione con il dottor Ted Codd era il proponente originale del modello di dati relazionali, ha esaurito la pazienza con argomenti male informati contro la normalizzazione e li ha demoliti sistematicamente usando il metodo scientifico: ha ottenuto grandi database e testato queste affermazioni.

Penso che l'abbia scritto in Relational Database Writings 1988-1991 ma questo libro è stato successivamente inserito nell'edizione sei di Introduzione ai sistemi di database , che è il testo definitivo sulla teoria e la progettazione dei database, nella sua ottava edizione mentre scrivo e probabilmente rimarrà stampato per i decenni a venire. Chris Date era un esperto in questo campo quando la maggior parte di noi correva ancora scalza.

Ha scoperto che:

  • Alcuni di essi valgono per casi speciali
  • Tutti non riescono a pagare per uso generale
  • Tutti sono significativamente peggiori per altri casi speciali

Tutto torna a mitigare le dimensioni del set di lavoro. I join che coinvolgono chiavi correttamente selezionate con indici impostati correttamente sono economici, non costosi, poiché consentono una potatura significativa del risultato prima che le righe vengono materializzate.

La materializzazione del risultato comporta letture di dischi di massa che sono l'aspetto più costoso dell'esercizio per ordine di grandezza. Al contrario, l'esecuzione di un join richiede logicamente il recupero delle sole chiavi . In pratica, nemmeno i valori chiave vengono recuperati: i valori hash chiave vengono utilizzati per i confronti dei join, mitigando il costo dei join a più colonne e riducendo radicalmente il costo dei join che comportano confronti tra stringhe. Non solo si adatta molto di più alla cache, c'è molto meno lettura del disco da fare.

Inoltre, un buon ottimizzatore sceglierà la condizione più restrittiva e la applicherà prima di eseguire un join, sfruttando in modo molto efficace l'elevata selettività dei join su indici con elevata cardinalità.

È vero che questo tipo di ottimizzazione può essere applicato anche a database denormalizzati, ma il tipo di persone che vogliono in genere denormalizzare uno schema in genere non pensa alla cardinalità quando (se) impostano gli indici.

È importante capire che le scansioni delle tabelle (esame di ogni riga in una tabella nel corso della produzione di un join) sono rare nella pratica. Un Query Optimizer sceglierà una scansione della tabella solo quando uno o più dei seguenti elementi sono validi.

  • Ci sono meno di 200 righe nella relazione (in questo caso una scansione sarà più economica)
  • Non ci sono indici adatti sulle colonne di join (se è significativo unirsi su queste colonne, allora perché non sono indicizzate? correggilo)
  • È necessaria una coercizione di tipo prima di poter confrontare le colonne (WTF ?! risolverlo o tornare a casa) VEDI NOTE DI FINE PER IL PROBLEMA DI ADO.NET
  • Uno degli argomenti del confronto è un'espressione (nessun indice)

L'esecuzione di un'operazione è più costosa di non eseguirla. Tuttavia, eseguire l'operazione errata , essere forzato in I / O su disco inutili e quindi scartare le scorie prima di eseguire il join di cui si ha realmente bisogno, è molto più costoso. Anche quando "errato" l'operazione è pre-calcolata e gli indici sono stati applicati in modo ragionevole, rimane una penalità significativa. La denormalizzazione per precompilare un join - nonostante le anomalie di aggiornamento comportate - è un impegno per un join specifico. Se hai bisogno di un diverso , quell'impegno ti costerà grande .

Se qualcuno vuole ricordarmi che è un mondo che cambia, penso che scoprirai che set di dati più grandi su hardware più grande esagerano la diffusione dei risultati di Date.

Per tutti voi che lavorate su sistemi di fatturazione o generatori di posta indesiderata (vergognatevi) e state indignando la mano sulla tastiera per dirmi che sapete per certo che la denormalizzazione è più veloce, scusate ma vivete in una dei casi speciali, in particolare il caso in cui si elaborano tutti i dati, in ordine. Non è un caso generale e tu sei giustificato nella tua strategia.

Sei non giustificato nel generalizzare erroneamente. Vedi la fine della sezione note per ulteriori informazioni sull'uso appropriato della denormalizzazione negli scenari di data warehousing.

Vorrei anche rispondere a

  

I join sono solo prodotti cartesiani con alcuni lipgloss

Che carico di bollock. Le restrizioni vengono applicate il più presto possibile, prima le più restrittive. Hai letto la teoria, ma non l'hai capito. I join vengono trattati come prodotti cartesiani ai quali si applicano i predicati " solo da Query Optimizer. Questa è una rappresentazione simbolica (una normalizzazione, in effetti) per facilitare la decomposizione simbolica in modo che l'ottimizzatore possa produrre tutte le trasformazioni equivalenti e classificarle in base al costo e alla selettività in modo da poter selezionare il miglior piano di query.

L'unico modo in cui otterrai l'ottimizzatore per produrre un prodotto cartesiano è non riuscire a fornire un predicato: SELEZIONA * DA A, B

Note

David Aldridge fornisce alcune importanti informazioni aggiuntive.

Esistono in effetti una varietà di altre strategie oltre agli indici e alle scansioni delle tabelle, e un moderno ottimizzatore le costerà tutte prima di produrre un piano di esecuzione.

Un consiglio pratico: se può essere usato come chiave esterna, indicizzalo, in modo che una strategia di indice sia disponibile all'ottimizzatore.

Ero più intelligente dell'ottimizzatore MSSQL. Ciò è cambiato due versioni fa. Ora in genere insegna me . È, in un senso molto reale, un sistema esperto, che codifica tutta la saggezza di molte persone molto intelligenti in un dominio sufficientemente chiuso da rendere efficace un sistema basato su regole.

" Bollocks " potrebbe essere stato senza tatto. Mi viene chiesto di essere meno altero e mi viene in mente che la matematica non mente. Questo è vero, ma non tutte le implicazioni dei modelli matematici dovrebbero necessariamente essere prese alla lettera. Radici quadrate di numeri negativi sono molto utili se eviti attentamente di esaminarne l'assurdità (gioco di parole lì) e assicurati dannatamente di annullarle tutte prima di provare a interpretare la tua equazione.

Il motivo per cui ho risposto così selvaggiamente è stato che l'affermazione formulata dice che

  

I join sono prodotti cartesiani ...

Questo potrebbe non essere quello che intendevi, ma è ciò che è stato scritto ed è categoricamente falso. Un prodotto cartesiano è una relazione. Un join è una funzione. Più specificamente, un join è una funzione valutata in base alla relazione. Con un predicato vuoto produrrà un prodotto cartesiano e verificare che ciò avvenga è un controllo di correttezza per un motore di query del database, ma nessuno scrive join non vincolati in pratica perché non hanno alcun valore pratico al di fuori di una classe.

L'ho chiamato perché non voglio che i lettori cadano nell'antica trappola di confondere il modello con la cosa modellata. Un modello è un'approssimazione, deliberatamente semplificata per una comoda manipolazione.

Il limite per la selezione di una strategia di join per la scansione della tabella può variare tra i motori di database. È influenzato da una serie di decisioni di implementazione come il fattore di riempimento del nodo dell'albero, la dimensione del valore-chiave e le sottigliezze dell'algoritmo, ma in generale l'indicizzazione ad alte prestazioni ha un tempo di esecuzione di k log n + c . Il termine C è un overhead fisso costituito principalmente da tempo di configurazione e la forma della curva indica che non si ottiene un payoff (rispetto a una ricerca lineare) fino a quando n è tra le centinaia.

A volte la denormalizzazione è una buona idea

La denormalizzazione è un impegno per una particolare strategia di join. Come accennato in precedenza, ciò interferisce con le altre strategie di partecipazione. Ma se si dispone di secchi di spazio su disco, modelli prevedibili di accesso e una tendenza a elaborarli in gran parte o tutti, quindi precompilare un join può essere molto utile.

È inoltre possibile capire i percorsi di accesso utilizzati in genere dall'operazione e precompilare tutti i join per tali percorsi di accesso. Questa è la premessa alla base dei data warehouse, o almeno lo è quando sono costruiti da persone che sanno perché stanno facendo quello che stanno facendo, e non solo per motivi di conformità delle parole d'ordine.

Un data warehouse progettato correttamente viene prodotto periodicamente da una trasformazione in blocco da un sistema di elaborazione delle transazioni normalizzato. Questa separazione delle banche dati sulle operazioni e sui rapporti ha l'effetto molto desiderabile di eliminare lo scontro tra OLTP e OLAP (elaborazione delle transazioni online, ovvero immissione dei dati, e elaborazione analitica online, ovvero rapporti).

Un punto importante qui è che, a parte gli aggiornamenti periodici, il data warehouse è di sola lettura . Questo rende discutibile la questione delle anomalie di aggiornamento.

Non commettere l'errore di denormalizzare il database OLTP (il database su cui avviene l'immissione dei dati). Potrebbe essere più veloce per le esecuzioni di fatturazione, ma se lo fai otterrai anomalie di aggiornamento. Hai mai provato a convincere Reader's Digest a smettere di inviarti roba?

Lo spazio su disco è poco costoso in questi giorni, quindi buttati fuori. Ma la denormalizzazione è solo una parte della storia dei data warehouse. Guadagni prestazionali molto più grandi derivano da valori cumulativi precalcolati: totali mensili, quel genere di cose. Si tratta di sempre sulla riduzione del working set.

Problema ADO.NET con mancate corrispondenze di tipo

Supponiamo di avere una tabella di SQL Server contenente una colonna indicizzata di tipo varchar e di utilizzare AddWithValue per passare un parametro che vincola una query su questa colonna. Le stringhe C # sono Unicode, quindi il tipo di parametro dedotto sarà NVARCHAR, che non corrisponde a VARCHAR.

VARCHAR in NVARCHAR è una conversione in espansione, quindi accade implicitamente, ma saluta l'indicizzazione e buona fortuna per capire perché.

" Conta gli hit del disco " (Rick James)

Se tutto è memorizzato nella cache nella RAM, JOINs è piuttosto economico. Cioè, la normalizzazione non ha molta penalità di prestazione .

Se un " normalizzato " lo schema fa sì che JOINs colpisca molto il disco, ma l'equivalente "denormalizzato" lo schema non dovrebbe colpire il disco, quindi la denormalizzazione vince un concorso di prestazioni.

  

Commento dell'autore originale: i moderni motori di database sono molto bravi nell'organizzazione del sequenziamento degli accessi per ridurre al minimo le mancate cache durante le operazioni di join. Quanto sopra, sebbene vero, potrebbe essere errato nel senso che implica che i join sono necessariamente problematicamente costosi su dati di grandi dimensioni. Ciò porterebbe a un cattivo processo decisionale da parte di sviluppatori inesperti.

Altri suggerimenti

Ciò che la maggior parte dei commentatori non nota è l'ampia gamma di metodologie di join disponibili in un RDBMS complesso, e i denormalizzatori invariabilmente sorvolano il costo più elevato del mantenimento dei dati denormalizzati. Non tutti i join si basano su indici e i database hanno molti algoritmi e metodologie di join ottimizzati volti a ridurre i costi dei join.

In ogni caso, il costo di un join dipende dal suo tipo e da alcuni altri fattori. Non deve essere affatto costoso - alcuni esempi.

  • Un hash join, in cui i dati in blocco sono allineati, è davvero molto economico e il costo diventa significativo solo se la tabella hash non può essere memorizzata nella cache. Nessun indice richiesto. Il partizionamento equo tra i set di dati uniti può essere di grande aiuto.
  • Il costo di un'unione di tipo-merge è determinato dal costo dell'ordinamento piuttosto che dall'unione: un metodo di accesso basato su indice può praticamente eliminare il costo dell'ordinamento.
  • Il costo di un join ad anello nidificato su un indice è determinato dall'altezza dell'indice b-tree e dall'accesso del blocco tabella stesso. È veloce, ma non adatto a join di massa.
  • Un join ad anello nidificato basato su un cluster è molto più economico, con un numero minore di I / O logici richiesti per riga di join: se le tabelle unite sono entrambe nello stesso cluster, il join diventa molto economico attraverso la colocazione delle righe unite.

I database sono progettati per unirsi e sono molto flessibili nel modo in cui lo fanno e generalmente molto performanti a meno che non sbagliano il meccanismo di join.

Penso che l'intera domanda sia basata su una premessa errata. I join su tavoli di grandi dimensioni sono non necessariamente costosi. In effetti, fare join in modo efficiente è uno dei motivi principali per cui esistono database relazionali . I join su set di grandi dimensioni sono spesso costosi, ma molto raramente si desidera unire l'intero contenuto della tabella grande A con l'intero contenuto della tabella grande B. Invece, si scrive la query in modo tale che vengono utilizzate solo le righe importanti di ciascuna tabella e l'insieme effettivo mantenuto dall'unione rimane più piccolo.

Inoltre, hai le efficienze menzionate da Peter Wone, in modo tale che solo le parti importanti di ogni record devono essere in memoria fino a quando il set di risultati finale non si materializza. Inoltre, nelle query di grandi dimensioni con molti join in genere si desidera iniziare con i set di tabelle più piccoli e passare a quelli di grandi dimensioni, in modo che il set tenuto in memoria rimanga il più piccolo possibile il più a lungo possibile.

Se eseguiti correttamente, i join sono generalmente il modo migliore per confrontare, combinare o filtrare grandi quantità di dati.

Il collo di bottiglia è praticamente sempre I / O su disco, e ancora più specificamente - I / O su disco casuale (in confronto, le letture sequenziali sono abbastanza veloci e possono essere memorizzate nella cache con strategie di lettura anticipata).

Unire può aumentare le ricerche casuali - se stai saltando in giro leggendo piccole parti di un grande tavolo. Ma gli ottimizzatori di query lo cercano e lo trasformeranno in una scansione sequenziale della tabella (scartando le righe non necessarie) se ritiene che sarebbe meglio.

Una singola tabella denormalizzata presenta un problema simile: le righe sono grandi e quindi meno adatte a una singola pagina di dati. Se hai bisogno di righe che si trovano lontano da un'altra (e le grandi dimensioni delle righe le rendono più distanti), avrai I / O più casuali. Ancora una volta, una scansione della tabella può essere forzata per evitarlo. Ma, questa volta, la scansione della tabella deve leggere più dati a causa delle grandi dimensioni della riga. Aggiungete a ciò il fatto che state copiando i dati da una singola posizione a più posizioni e RDBMS ha molto di più da leggere (e memorizzare nella cache).

Con 2 tabelle, ottieni anche 2 indici cluster - e in genere puoi indicizzare di più (a causa di un sovraccarico di inserimento / aggiornamento inferiore) che può farti aumentare drasticamente le prestazioni (principalmente, ancora una volta, perché gli indici sono (relativamente) piccoli, rapidi a leggere il disco (o economico da memorizzare nella cache) e ridurre la quantità di righe della tabella che è necessario leggere dal disco).

L'unico overhead con un join proviene dal capire le righe corrispondenti. Sql Server utilizza 3 diversi tipi di join, principalmente in base alle dimensioni del set di dati, per trovare le righe corrispondenti. Se l'ottimizzatore sceglie il tipo di join errato (a causa di statistiche imprecise, indici inadeguati o solo un bug dell'ottimizzatore o un caso limite) può influire drasticamente sui tempi di query.

  • Un loop loop è decisamente economico per (almeno 1) set di dati di piccole dimensioni.
  • Un join unione richiede prima una sorta di entrambi i set di dati. Se ti unisci su una colonna indicizzata, tuttavia, l'indice è già ordinato e non è necessario eseguire ulteriori lavori. Altrimenti, nell'ordinamento sono presenti un certo sovraccarico di CPU e memoria.
  • L'hash join richiede sia memoria (per memorizzare l'hashtable) sia CPU (per creare l'hash). Ancora una volta, questo è abbastanza veloce in relazione all'I / O del disco. Tuttavia , se non c'è abbastanza RAM per archiviare l'hashtable, Sql Server utilizzerà tempdb per memorizzare parti dell'hashtable e delle righe trovate, quindi elaborerà solo parti dell'hashtable alla volta. Come per tutte le cose su disco, questo è abbastanza lento.

Nel caso ottimale, questi non causano I / O del disco - e quindi sono trascurabili dal punto di vista delle prestazioni.

Tutto sommato, nel peggiore dei casi - dovrebbe effettivamente essere più veloce leggere la stessa quantità di logici dati da x tabelle unite, poiché proviene da una singola tabella denormalizzata a causa delle letture del disco più piccole. Per leggere la stessa quantità di dati fisici , potrebbe esserci un leggero sovraccarico.

Poiché il tempo di interrogazione è generalmente dominato dai costi di I / O e la dimensione dei dati non cambia (meno un sovraccarico di righe molto minuscolo) con la denormalizzazione, non c'è un enorme beneficio da unire semplicemente le tabelle . Il tipo di denormalizzazione che tende ad aumentare le prestazioni, IME, memorizza nella cache i valori calcolati anziché leggere le 10.000 righe richieste per calcolarli.

L'ordine in cui ti unisci ai tavoli è estremamente importante. Se disponi di due set di dati, prova a creare la query in modo tale da utilizzare prima il più piccolo per ridurre la quantità di dati su cui la query deve funzionare.

Per alcuni database non ha importanza, ad esempio MS SQL conosce il corretto ordine di join per la maggior parte del tempo. Per alcuni (come IBM Informix) l'ordine fa la differenza.

Decidere se denormalizzare o normalizzare è un processo abbastanza semplice se si considera la classe di complessità del join. Ad esempio, tendo a progettare i miei database con normalizzazione quando le query sono O (k log n) dove k è relativo alla grandezza di output desiderata.

Un modo semplice per denormalizzare e ottimizzare le prestazioni è pensare a come le modifiche alla struttura di normalizzazione influenzano la struttura denormalizzata. Può essere problematico, tuttavia, poiché potrebbe richiedere la logica transazionale per funzionare su una struttura denormalizzata.

Il dibattito sulla normalizzazione e sulla denormalizzazione non finirà poiché i problemi sono enormi. Ci sono molti problemi in cui la soluzione naturale richiede entrambi gli approcci.

Come regola generale, ho sempre archiviato una struttura normalizzata e cache denormalizzate che possono essere ricostruite. Alla fine, queste cache mi salvano il culo per risolvere i futuri problemi di normalizzazione.

Elaborando ciò che gli altri hanno detto,

I join sono solo prodotti cartesiani con alcuni lucidalabbra. {1,2,3,4} X {1,2,3} ci darebbe 12 combinazioni (nXn = n ^ 2). Questo set calcolato funge da riferimento su quali condizioni vengono applicate. Il DBMS applica le condizioni (come dove sia sinistra che destra sono 2 o 3) per darci le condizioni corrispondenti. In realtà è più ottimizzato ma il problema è lo stesso. Le modifiche alle dimensioni degli insiemi aumenterebbero esponenzialmente le dimensioni del risultato. La quantità di cicli di memoria e CPU consumati viene effettuata in termini esponenziali.

Quando denormalizziamo, evitiamo del tutto questo calcolo, pensiamo di avere un adesivo colorato, attaccato ad ogni pagina del tuo libro. È possibile inferire le informazioni senza utilizzare un riferimento. La penalità che paghiamo è che stiamo compromettendo l'essenza del DBMS (organizzazione ottimale dei dati)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top