Quando e por que as associações ao banco de dados são caras?

Estou pesquisando bancos de dados e analisando algumas limitações dos bancos de dados relacionais.

Estou percebendo que unir mesas grandes é muito caro, mas não sei ao certo por quê. O que o DBMS precisa fazer para executar uma operação de junção, onde está o gargalo?
Como a desnormalização ajuda a superar essa despesa? Como outras técnicas de otimização (indexação, por exemplo) ajudam?

Experiências pessoais são bem-vindas! Se você quiser publicar links para recursos, evite a Wikipedia. Eu já sei onde encontrar isso.

Em relação a isso, estou me perguntando sobre as abordagens desnormalizadas usadas pelos bancos de dados de serviço em nuvem, como BigTable e SimpleDB. Veja esta pergunta .

Desnormalização para melhorar o desempenho? Parece convincente, mas não retém água.

Chris Date, que na companhia do Dr. Ted Codd era o proponente original do modelo de dados relacionais, ficou sem paciência com argumentos desinformados contra a normalização e os demoliu sistematicamente usando o método científico: ele obteve grandes bancos de dados e testou essas afirmações.

Acho que ele o escreveu em Relational Database Writings 1988-1991, mas este livro foi posteriormente lançado na edição seis da Introdução aos Sistemas de Banco de Dados , que é o texto definitivo sobre teoria e design de banco de dados, em sua oitava edição enquanto escrevo e provavelmente continuarei impressa nas próximas décadas. Chris Date era um especialista nesse campo quando a maioria de nós ainda andava descalça.

Ele descobriu que:

• Alguns deles são válidos para casos especiais
• Todos eles não pagam para uso geral
• Todos eles são significativamente piores para outros casos especiais

Tudo volta a atenuar o tamanho do conjunto de trabalho. As junções que envolvem chaves selecionadas corretamente com índices configurados corretamente são baratas, não caras, porque permitem a remoção significativa do resultado antes que as linhas sejam materializadas.

A materialização do resultado envolve leituras em disco em massa, que são o aspecto mais caro do exercício por uma ordem de magnitude. A execução de uma junção, por outro lado, exige logicamente a recuperação apenas das chaves . Na prática, nem mesmo os valores-chave são buscados: os valores-chave de hash são usados ​​para comparações de junções, mitigando o custo de junções de várias colunas e reduzindo radicalmente o custo de junções envolvendo comparações de strings. Além de se encaixar muito mais no cache, há muito menos leitura de disco a ser feita.

Além disso, um bom otimizador escolhe a condição mais restritiva e a aplica antes de executar uma junção, aproveitando de maneira muito eficaz a alta seletividade de junções em índices com alta cardinalidade.

É certo que esse tipo de otimização também pode ser aplicado a bancos de dados desnormalizados, mas o tipo de pessoa que deseja desnormalizar um esquema normalmente não pensa em cardinalidade quando (se) configura índices.

É importante entender que as varreduras de tabela (exame de todas as linhas de uma tabela durante a produção de uma junção) são raras na prática. Um otimizador de consulta escolherá uma varredura de tabela apenas quando um ou mais dos seguintes itens forem mantidos.

• Há menos de 200 linhas na relação (nesse caso, uma verificação será mais barata)
• Não há índices adequados nas colunas de junção (se é significativo ingressar nessas colunas, por que eles não são indexados? Corrija-o)
• É necessária uma coerção de tipo antes que as colunas possam ser comparadas (WTF ?! corrija-a ou vá para casa) VEJA AS NOTAS FINAIS DO PROBLEMA DO ADO.NET
• Um dos argumentos da comparação é uma expressão (sem índice)

Realizar uma operação é mais caro do que não realizá-la. No entanto, executar a operação errada , ser forçado a E / S de disco inútil e depois descartar a escória antes de realizar a junção de que você realmente precisa é muito mais caro. Mesmo quando a operação "incorreta" é pré-computada e os índices foram aplicados de maneira sensata, permanece uma penalidade significativa. A desnormalização para pré-calcular uma associação - apesar das anomalias de atualização associadas - é um compromisso com uma associação específica. Se você precisar de uma associação diferente , esse compromisso custará muito .

Se alguém quiser me lembrar que é um mundo em mudança, acho que você descobrirá que conjuntos de dados maiores em hardware mais pesado exageram a disseminação das descobertas de Date.

Para todos vocês que trabalham em sistemas de cobrança ou geradores de lixo eletrônico (que vergonha) e estão indignadamente colocando a mão no teclado para me dizer que sabem que a desnormalização é mais rápida, desculpe, mas você está vivendo em um dos lugares especiais casos - especificamente, o caso em que você processa todos os dados, em ordem. Não é um caso geral, e você está justificado em sua estratégia.

Você não está justificado em generalizar falsamente. Consulte o final da seção de notas para obter mais informações sobre o uso apropriado da desnormalização em cenários de data warehousing.

Eu também gostaria de responder a

As junções são apenas produtos cartesianos com algum brilho labial

Que carga de besteiras. As restrições são aplicadas o mais cedo possível, mais restritivas primeiro. Você leu a teoria, mas não a entendeu. As junções são tratadas como "produtos cartesianos aos quais os predicados se aplicam" apenas pelo otimizador de consultas. Essa é uma representação simbólica (uma normalização, de fato) para facilitar a decomposição simbólica, para que o otimizador possa produzir todas as transformações equivalentes e classificá-las por custo e seletividade, para que possa selecionar o melhor plano de consulta.

A única maneira de obter o otimizador para produzir um produto cartesiano é deixar de fornecer um predicado: SELECT * FROM A,B

Notas

David Aldridge fornece algumas informações adicionais importantes.

De fato, há uma variedade de outras estratégias além de índices e varreduras de tabelas, e um otimizador moderno custará todas elas antes de produzir um plano de execução.

Um conselho prático: se puder ser usado como chave estrangeira, indexe-a, para que uma estratégia de indexação esteja disponível para o otimizador.

Eu costumava ser mais esperto que o otimizador MSSQL. Isso mudou duas versões atrás. Agora isso geralmente me ensina . É, em um sentido muito real, um sistema especialista, codificando toda a sabedoria de muitas pessoas muito inteligentes em um domínio suficientemente fechado para que um sistema baseado em regras seja eficaz.

"Bollocks" pode ter sido sem tato. Me pedem para ser menos arrogante e lembrei que a matemática não mente. Isso é verdade, mas nem todas as implicações dos modelos matemáticos devem necessariamente ser tomadas literalmente. As raízes quadradas dos números negativos são muito úteis se você evitar cuidadosamente examinar o absurdo (trocadilho ali) e se certificar de cancelá-las antes de tentar interpretar sua equação.

A razão pela qual eu respondi de forma tão violenta foi que a declaração redigida diz que

As junções são produtos cartesianos ...

Pode não ser o que quis dizer, mas é o que foi escrito e é categoricamente falso. Um produto cartesiano é uma relação. Uma junção é uma função. Mais especificamente, uma junção é uma função com valor de relação. Com um predicado vazio, ele produzirá um produto cartesiano, e verificar se o faz é uma verificação de correção de um mecanismo de consulta de banco de dados, mas ninguém na prática cria uniões irrestritas porque não tem valor prático fora da sala de aula.

Eu falei isso porque não quero que os leitores caiam na armadilha antiga de confundir o modelo com o que foi modelado. Um modelo é uma aproximação, deliberadamente simplificada para manipulação conveniente.

O ponto de corte para a seleção de uma estratégia de junção de varredura de tabela pode variar entre os mecanismos de banco de dados. Ele é afetado por várias decisões de implementação, como fator de preenchimento do nó da árvore, tamanho do valor-chave e sutilezas do algoritmo, mas, em termos gerais, a indexação de alto desempenho tem um tempo de execução de k log n + c . O termo C é uma sobrecarga fixa composta principalmente de tempo de configuração, e o formato da curva significa que você não recebe um pagamento (comparado a uma pesquisa linear) até que n esteja na casa das centenas.

Às vezes, a desnormalização é uma boa ideia

A desnormalização é um compromisso com uma estratégia de junção específica. Como mencionado anteriormente, isso interfere com outras estratégias de junção. Mas se você tiver intervalos de espaço em disco, padrões previsíveis de acesso e uma tendência a processar grande parte ou a totalidade dele, a pré-computação de uma junção pode valer muito a pena.

Você também pode descobrir os caminhos de acesso que sua operação normalmente usa e pré-calcular todas as junções para esses caminhos de acesso. Essa é a premissa por trás dos data warehouses, ou pelo menos é quando eles são criados por pessoas que sabem por que estão fazendo o que estão fazendo, e não apenas por uma questão de conformidade com os chavões.

Um data warehouse adequadamente projetado é produzido periodicamente por uma transformação em massa de um sistema de processamento de transações normalizado. Essa separação dos bancos de dados de operações e relatórios tem o efeito muito desejável de eliminar o conflito entre OLTP e OLAP (processamento de transações online, por exemplo, entrada de dados e processamento analítico online, por exemplo, relatório).

Um ponto importante aqui é que, além das atualizações periódicas, o armazém de dados é somente leitura . Isso torna discutível a questão das anomalias de atualização.

Não cometa o erro de desnormalizar seu banco de dados OLTP (o banco de dados no qual a entrada de dados ocorre). Pode ser mais rápido para execuções de cobrança, mas se você fizer isso, receberá anomalias de atualização. Já tentou fazer com que o Reader's Digest parasse de lhe enviar coisas?

Hoje em dia, o espaço em disco é barato, portanto, se nocauteie. Mas a desnormalização é apenas parte da história dos data warehouses. Ganhos de desempenho muito maiores são derivados de valores acumulados pré-computados: totais mensais, esse tipo de coisa. É sempre uma questão de reduzir o conjunto de trabalho.

Problema no ADO.NET com incompatibilidades de tipo

Suponha que você tenha uma tabela do SQL Server contendo uma coluna indexada do tipo varchar e use AddWithValue para passar um parâmetro que restringe uma consulta nessa coluna. As seqüências de caracteres C # são Unicode, portanto, o tipo de parâmetro inferido será NVARCHAR, que não corresponde a VARCHAR.

O VARCHAR para o NVARCHAR é uma conversão cada vez maior, por isso ocorre implicitamente - mas diga adeus à indexação e boa sorte para descobrir o porquê.

"Conte os hits do disco" (Rick James)

Se tudo estiver armazenado em cache na RAM, JOINsserá bastante barato. Ou seja, a normalização não possui muita penalidade de desempenho .

Se um esquema "normalizado" causar muito JOINsimpacto no disco, mas o esquema "desnormalizado" equivalente não precisar atingir o disco, a desnormalização vence uma competição de desempenho.

Comentário do autor original: Os modernos mecanismos de banco de dados são muito bons em organizar o seqüenciamento de acesso para minimizar as falhas de cache durante as operações de junção. O exposto acima, embora verdadeiro, pode ser mal interpretado, pois implica que as junções são necessariamente problemáticas em grandes volumes de dados. Isso levaria a uma tomada de decisão ruim por parte de desenvolvedores inexperientes.

O que a maioria dos comentaristas deixa de notar é a grande variedade de metodologias de junção disponíveis em um RDBMS complexo, e os desnormalizadores invariavelmente encobrem o custo mais alto da manutenção de dados desnormalizados. Nem toda junção é baseada em índices, e os bancos de dados têm muitos algoritmos e metodologias otimizados para junção, com o objetivo de reduzir os custos da junção.

De qualquer forma, o custo de uma associação depende do seu tipo e de alguns outros fatores. Não precisa ser caro - alguns exemplos.

• Uma junção de hash, na qual os dados em massa são equivalentes, é muito barata e o custo só se torna significativo se a tabela de hash não puder ser armazenada em cache na memória. Nenhum índice é necessário. O particionamento equitativo entre os conjuntos de dados unidos pode ser uma grande ajuda.
• O custo de uma junção de mesclagem de classificação é determinado pelo custo da classificação, e não pela mesclagem - um método de acesso baseado em índice pode praticamente eliminar o custo da classificação.
• O custo de uma junção de loop aninhado em um índice é determinado pela altura do índice da árvore b e pelo acesso do próprio bloco de tabelas. É rápido, mas não é adequado para junções em massa.
• Uma junção de loop aninhada com base em um cluster é muito mais barata, com menos IOs lógicas necessárias por linha de junção - se as tabelas unidas estiverem no mesmo cluster, a junção se tornará muito barata por meio da colocação de linhas unidas.

Os bancos de dados são projetados para ingressar e são muito flexíveis na maneira de fazê-lo e, geralmente, têm um desempenho excelente, a menos que eles entendam errado o mecanismo de ingresso.

Eu acho que toda a questão é baseada em uma premissa falsa. Associações em mesas grandes não são necessariamente caras. De fato, fazer junções com eficiência é uma das principais razões pelas quais os bancos de dados relacionais existem . Associações em conjuntos grandes geralmente são caras, mas muito raramente você deseja unir todo o conteúdo da tabela grande A com todo o conteúdo da tabela grande B. Em vez disso, escreva a consulta de modo que apenas as linhas importantes de cada tabela sejam usadas e o conjunto real mantido pela junção permanece menor.

Além disso, você possui as eficiências mencionadas por Peter Wone, de modo que apenas as partes importantes de cada registro precisam estar na memória até que o conjunto de resultados finais seja materializado. Além disso, em consultas grandes com muitas junções, você normalmente deseja começar com conjuntos de tabelas menores e trabalhar até os grandes, para que o conjunto mantido na memória permaneça o menor possível, pelo maior tempo possível.

Quando feitas corretamente, as junções geralmente são a melhor maneira de comparar, combinar ou filtrar grandes quantidades de dados.

O gargalo é quase sempre a E / S do disco e, mais especificamente, a E / S aleatória do disco (por comparação, as leituras sequenciais são bastante rápidas e podem ser armazenadas em cache com estratégias de leitura antecipada).

As junções podem aumentar as buscas aleatórias - se você estiver pulando lendo pequenas partes de uma mesa grande. Porém, os otimizadores de consulta procuram por isso e o transformam em uma varredura seqüencial de tabela (descartando as linhas desnecessárias) se achar que seria melhor.

Uma única tabela desnormalizada tem um problema semelhante - as linhas são grandes e, portanto, menos cabem em uma única página de dados. Se você precisar de linhas localizadas distantes de outras (e o tamanho grande da linha as separar), terá E / S mais aleatória. Novamente, uma varredura de tabela pode ser forçada para evitar isso. Mas, desta vez, sua verificação de tabela precisa ler mais dados devido ao grande tamanho da linha. Acrescente a isso o fato de que você está copiando dados de um único local para vários locais, e o RDBMS tem muito mais para ler (e armazenar em cache).

Com 2 tabelas, você também recebe 2 índices agrupados - e geralmente pode indexar mais (por causa de menos sobrecarga de inserção / atualização), o que pode aumentar drasticamente o desempenho (principalmente, novamente, porque os índices são (relativamente) pequenos, de leitura rápida do disco (ou barato para armazenar em cache) e diminua a quantidade de linhas da tabela que você precisa ler do disco).

A única sobrecarga com uma junção vem da descoberta das linhas correspondentes. O Sql Server usa 3 tipos diferentes de junções, principalmente com base nos tamanhos dos conjuntos de dados, para encontrar linhas correspondentes. Se o otimizador escolher o tipo de junção errado (devido a estatísticas imprecisas, índices inadequados ou apenas um bug do otimizador ou um caso extremo), poderá afetar drasticamente os tempos de consulta.

• Uma junção de loop é muito barata para (pelo menos 1) conjunto de dados pequeno.
• Uma junção de mesclagem requer um tipo de ambos os conjuntos de dados primeiro. Se você ingressar em uma coluna indexada, no entanto, o índice já está classificado e nenhum trabalho adicional precisa ser feito. Caso contrário, há alguma sobrecarga de CPU e memória na classificação.
• A junção de hash requer memória (para armazenar a hashtable) e CPU (para criar o hash). Novamente, isso é bastante rápido em relação à E / S do disco. No entanto , se não houver RAM suficiente para armazenar a hashtable, o Sql Server usará o tempdb para armazenar partes da hashtable e das linhas encontradas e, em seguida, processará apenas partes da hashtable por vez. Como em todas as coisas do disco, isso é bastante lento.

No caso ideal, elas não causam E / S de disco - e, portanto, são desprezíveis da perspectiva do desempenho.

Em suma, na pior das hipóteses - deve ser realmente mais rápido ler a mesma quantidade de dados lógicos de x tabelas unidas, pois é de uma única tabela desnormalizada por causa das leituras menores do disco. Para ler a mesma quantidade de dados físicos , pode haver uma pequena sobrecarga.

Como o tempo de consulta geralmente é dominado pelos custos de E / S, e o tamanho dos seus dados não muda (menos uma sobrecarga de linha muito minúscula) com a desnormalização, não há uma quantidade enorme de benefícios a serem obtidos ao mesclar tabelas. O tipo de desnormalização que tende a aumentar o desempenho, IME, está armazenando em cache os valores calculados em vez de ler as 10.000 linhas necessárias para calculá-los.

A ordem em que você está entrando nas mesas é extremamente importante. Se você tiver dois conjuntos de dados, tente criar a consulta de maneira que o menor seja usado primeiro para reduzir a quantidade de dados na qual a consulta precisa trabalhar.

Para alguns bancos de dados, isso não importa, por exemplo, o MS SQL sabe a ordem de junção correta na maioria das vezes. Para alguns (como o IBM Informix), o pedido faz toda a diferença.

Decidir se desnormalizar ou normalizar é um processo bastante simples quando você considera a classe de complexidade da junção. Por exemplo, eu tendem a projetar meus bancos de dados com normalização quando as consultas são O (k log n) em que k é relativo à magnitude de saída desejada.

Uma maneira fácil de desnormalizar e otimizar o desempenho é pensar em como as alterações em sua estrutura normalizada afetam sua estrutura desnormalizada. No entanto, pode ser problemático, pois pode exigir lógica transacional para trabalhar em uma estrutura desnormalizada.

O debate sobre normalização e desnormalização não vai acabar, já que os problemas são vastos. Existem muitos problemas em que a solução natural requer as duas abordagens.

Como regra geral, eu sempre armazenei uma estrutura normalizada e caches desnormalizados que podem ser reconstruídos. Eventualmente, esses caches salvam minha bunda para resolver os futuros problemas de normalização.

Elaborando o que os outros disseram,

As junções são apenas produtos cartesianos com algum brilho labial. {1,2,3,4} X {1,2,3} nos daria 12 combinações (nXn = n ^ 2). Este conjunto calculado atua como uma referência sobre quais condições são aplicadas. O DBMS aplica as condições (como onde esquerda e direita são 2 ou 3) para nos fornecer as condições correspondentes. Na verdade, é mais otimizado, mas o problema é o mesmo. As alterações no tamanho dos conjuntos aumentariam exponencialmente o tamanho do resultado. A quantidade de memória e os ciclos da CPU consumidos são efetuados em termos exponenciais.

Quando desnormalizamos, evitamos esse cálculo completamente, pense em ter um adesivo colorido, anexado a todas as páginas do seu livro. Você pode inferir as informações sem usar uma referência. A penalidade que pagamos é que estamos comprometendo a essência do DBMS (organização ideal de dados)