Quando e por que são do banco de dados se junta caro?

https://stackoverflow.com/questions/173726

05-07-2019
|

Pergunta

Estou fazendo algumas pesquisas em bases de dados e eu estou olhando para algumas limitações de bancos de dados relacionais.

Estou recebendo essa junta de grandes tabelas é muito caro, mas eu não estou completamente certo porquê. O que faz os DBMS precisa fazer para executar uma operação de junção, onde está o gargalo?
Como pode Desnormalização ajuda para superar essa despesa? Como outras técnicas de otimização (indexação, por exemplo) ajuda?

As experiências pessoais são bem-vindos! Se você estiver indo para postar links para recursos, evite Wikipedia. Eu sei onde encontrar esse já.

Em relação a isso, eu estou querendo saber sobre as abordagens desnormalizados usados ??por bancos de dados de serviços em nuvem como BigTable e SimpleDB. Consulte esta questão .

Solução

desnormalizar para melhorar o desempenho? Parece convincente, mas não se sustenta.

Chris Data, que em companhia do Dr. Ted Codd foi o proponente original do modelo de dados relacional, perdeu a paciência com argumentos mal informados contra normalização e sistematicamente demolida-los usando o método científico: ele tem grandes bases de dados e testadas essas afirmações.

Eu acho que ele escreveu em Escritos de banco de dados relacional 1988-1991 , mas este livro foi depois enroladas em edição de seis de Introdução ao Banco de Dados de Sistemas , que é o texto definitivo sobre a teoria de banco de dados e design, em sua oitava edição, como eu escrevo e deverá manter-se na cópia para as próximas décadas. Chris Data era um perito neste campo, quando a maioria de nós ainda estavam correndo descalço.

Ele descobriu que:

Alguns deles têm para casos especiais
Todos eles deixam de pagar para uso geral
Todos eles são significativamente pior para outros casos especiais

Tudo volta para mitigar o tamanho do conjunto de trabalho. Junta envolvendo chaves adequadamente selecionados com corretamente configurado índices são baratos, não é caro, porque eles permitem que poda significativa do resultado antes as linhas são materializados.

Materializar o resultado envolve disco grosso lê que são o aspecto mais caro do exercício por uma ordem de magnitude. Realizando uma junção, pelo contrário, logicamente exige a recuperação de apenas os chaves . Na prática, nem mesmo os valores de chave são buscados: os valores de chave de hash são usadas para juntar-se comparações, mitigando o custo de multi-coluna se junta e reduzir radicalmente o custo de junções envolvendo comparações de strings. Não só muito mais caber no cache, há muito menos rígido de leitura para fazer.

Além disso, um bom otimizador escolherá a condição mais restritiva e aplicá-lo antes de executar uma junção, de forma muito eficaz aproveitando a alta seletividade de junta em índices com alta cardinalidade.

É certo que este tipo de otimização também pode ser aplicado a bancos de dados Desnormaliza, mas o tipo de pessoas que deseja para denormalise um esquema normalmente não pensam sobre cardinalidade quando (se) eles montaram índices.

É importante entender que as varreduras de tabela (exame de cada linha em uma tabela no curso de produzir uma junção) são raras na prática. Um otimizador de consulta irá escolher uma tabela digitalizar apenas quando um ou mais dos seguintes detém.

Há menos de 200 linhas na relação (neste caso uma varredura será mais barato)
Não há índices adequados nas colunas união (se é significativo para juntar-se sobre estas colunas, em seguida, porque eles não estão indexados? Corrigi-lo)
Um tipo de coerção é necessária antes que as colunas podem ser comparados (WTF ?! corrigi-lo ou ir para casa) VER FIM NOTAS PARA ADO.NET EDIÇÃO
Um dos argumentos da comparação é uma expressão (sem índice)

Execução de uma operação é mais caro do que não realizá-lo. No entanto, a realização do errado operação, sendo forçado em disco inútil I / O e, em seguida, descartando a prévia escória de realizar o que você entrar realmente necessidade, é muito mais caro. Mesmo quando a operação de "errado" é pré-computados e os índices foram sensivelmente aplicada, continua a haver penalização significativa. Desnormalizar para precompute uma junção - não obstante as anomalias de atualização implicou - é um compromisso para um determinado participar. Se você precisa de um diferente JOIN, que o compromisso vai custar-lhe grande .

Se alguém quiser me lembrar que é um mundo em mudança, eu acho que você verá que os maiores conjuntos de dados sobre hardware gruntier apenas exagera a disseminação das descobertas de data.

Para todos vocês que trabalham em sistemas de faturamento ou geradores de lixo eletrônico (vergonha em você) e está definindo indignado mão ao teclado para me dizer que você sabe para um fato que denormalisation é mais rápido, desculpe, mas você está vivendo em um dos casos especiais - especificamente, o caso onde você processar todas dos dados, na ordem. Não é um caso geral, e você são justificado em sua estratégia.

Você é não justificados em generalizar-lo falsamente. Veja o final da seção de notas para obter mais informações sobre o uso apropriado de desnormalização em Data Warehousing cenários.

Eu também gostaria de responder às

junta são produtos apenas cartesianas com algum gloss

O que uma carga de besteira. Restrições são aplicadas o mais cedo possível, mais restritiva em primeiro lugar. Você já leu a teoria, mas você não entendeu isso. Associações são tratados como "produtos cartesianos ao qual predicados se aplicam" única pelo otimizador de consulta. Esta é uma representação simbólica (uma normalização, de fato) para facilitar a decomposição simbólica para que o otimizador pode produzir todas as transformações equivalentes e classificá-las pelo custo e seletividade para que ele possa escolher o melhor plano de consulta.

A única maneira que você nunca vai conseguir 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.

Há de fato uma variedade de outras estratégias, além de índices e varreduras de tabela, e um otimizador moderna vai custar-lhes tudo antes de produzir um plano de execução.

Uma peça prática de conselho:. Se ele pode ser usado como uma chave estrangeira, em seguida, indexá-lo, de modo que uma estratégia de índice é disponível para o otimizador

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

"Bollocks" pode ter sido falta de tato. Me pedem para ser menos arrogante e lembrou que a matemática não mente. Isto é verdade, mas nem todas as implicações de modelos matemáticos deve necessariamente ser tomado literalmente. raízes quadradas de números negativos são muito útil se você evitar cuidadosamente examinar seu absurdo (trocadilho lá) e fazer maldita certeza você cancelar todas elas antes de tentar interpretar a sua equação.

A razão pela qual eu respondi tão selvagemente era que a declaração tal como formulada, diz que

junta são produtos cartesianos ...

Isto pode não ser o que foi feito, mas é o que foi escrito, e é categoricamente falso. Um produto cartesiano é uma relação. Uma união é uma função. Mais especificamente, uma junção é uma função com valor de relação. Com um predicado vazio que irá produzir um produto cartesiano, e verificar que ele faz isso é uma verificação de correção para um mecanismo de consulta de banco de dados, mas ninguém escreve irrestrita junta-se, na prática, porque eles têm nenhum valor prático fora de uma sala de aula.

Eu chamei isso porque eu não quero que os leitores que caem na antiga armadilha de confundir o modelo com a coisa modelado. Um modelo é uma aproximação, deliberadamente simplificado para a manipulação conveniente.

O ponto de corte para a seleção de uma estratégia table-SCAN se juntar pode variar entre bancos de dados. Ele é afetado por uma série de decisões de implementação, como fator de preenchimento árvore-nó, o 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 é um fixo sobrecarga feito na maior parte do tempo de instalação, e da forma dos meios de curva você não fizer um pagamento (em comparação com uma pesquisa linear) até n é na casa das centenas.

Às vezes desnormalização é uma boa idéia

Desnormalização é um compromisso com um determinado juntar estratégia. Como mencionado anteriormente, isto interfere com other juntar estratégias. Mas se você tem baldes de espaço em disco, padrões previsíveis de acesso, e uma tendência para processar grande parte ou todo ele, então precomputing uma junção pode ser muito útil.

Você também pode descobrir os caminhos de acesso a sua operação normalmente usa e precompute toda a junta para esses caminhos de acesso. Esta é a premissa por trás armazéns de dados, ou pelo menos é quando eles são construídos por pessoas que sabem por que eles estão fazendo o que estão fazendo, e não apenas por uma questão de cumprimento chavão.

Um armazém de dados adequadamente concebido é produzido periodicamente por uma transformação em massa de um sistema de processamento de transacções normalizadas. Esta separação das operações e bancos de dados de relatório tem o efeito muito desejável de eliminar o choque entre OLTP e OLAP (processamento de transações on-line de entrada de dados ie e processamento de informação, ou seja analítico online).

Um ponto importante aqui é que, além das atualizações periódicas, o data warehouse é somente leitura . Isso torna discutível a questão de 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 acontece). Pode ser mais rápido para faturamento pontos, mas se você fizer isso você vai ter anomalias de atualização. Já tentou obter Readers Digest para parar de enviar-lhe coisas?

O espaço em disco é barato hoje em dia, então bater-se. Mas desnormalizar é apenas uma parte da história para data warehouses. Muito maiores ganhos de desempenho são derivados de valores enroladas Precomputed: totais mensais, esse tipo de coisa. É de sempre sobre a redução do conjunto de trabalho.

ADO.NET problema com o tipo incompatibilidades

Suponha que você tenha uma tabela do SQL Server que contém uma coluna indexada do tipo varchar, e você usar AddWithValue para passar um parâmetro restringir uma consulta sobre esta coluna. C # cordas são Unicode, então o tipo de parâmetro inferido será NVARCHAR, o que não corresponde VARCHAR.

VARCHAR para NVARCHAR é uma conversão alargando assim acontece implicitamente -., Mas dizer adeus a indexação, e boa sorte trabalhando para fora porque

"Contar as batidas de disco" (Rick James)

Se tudo estiver em cache na RAM, JOINs são bastante barato. Ou seja, a normalização não tem muita penalidade de desempenho .

Se um "normalizado" causas esquema JOINs para bater o disco muito, mas o equivalente "denormalized" esquema não teria que bater o disco, então desnormalização ganha uma competição desempenho.

Comentário do autor original: motores de banco de dados modernos são muito bons em organizar sequenciamento acesso para minimizar erros de cache durante juntam operações. A descrição acima, embora verdadeira, pode ser miscontrued como implicando que se junta são necessariamente problematicamente caro em dados de grandes dimensões. Isso levaria a causar má-tomada de decisão por parte dos desenvolvedores inexperientes.

Outras dicas

O que a maioria dos comentadores deixar de notar é a ampla gama de juntar-se metodologias disponíveis em um RDBMS complexos, e os denormalisers invariavelmente encobrir o maior custo de manutenção de dados Desnormaliza. Não cada junção é baseado em índices e bases de dados tem um monte de algotithms e metodologias otimizadas para se juntar que se destinam a reduzir a juntar-se os custos.

Em qualquer caso, o custo de uma junção depende do seu tipo e alguns outros fatores. Ele não precisa ser caro a todos -. Alguns exemplos

A junção de hash, em que os dados em massa é equijoined, é muito barato, de fato, eo custo só se tornam significativos se a tabela hash não pode ser armazenado em cache na memória. Nenhum índice necessário. Equi-particionamento entre os conjuntos de dados unidas pode ser uma grande ajuda.
O custo de uma espécie-merge join é impulsionado pelo custo do tipo, em vez da fusão -. Um método de acesso à base de índice pode praticamente eliminar o custo do tipo
O custo de um loop aninhado em um índice é impulsionado pela altura do índice b-tree eo acesso do próprio bloco de tabela. É rápido, mas não é adequado para o volume junta.
Um loop aninhado baseado em um cluster é muito mais barato, com menos lógica IO é exigido por se juntar a linha -. Se as tabelas associadas estão ambos no mesmo cluster, em seguida, a junção se torna muito barato através da colocação de linhas unidas

Os bancos de dados são projetados para se juntar, e eles são muito flexíveis em como fazê-lo e geralmente muito alto desempenho a menos que obtenha o mecanismo errado juntar-se.

Eu acho que toda a questão se baseia em uma premissa falsa. Junta-se em tabelas grandes são não , necessariamente caro. Na verdade, fazer une de forma eficiente é uma das principais razões existem bancos de dados relacionais em tudo. Junta-se em grandes sets , muitas vezes são caros, mas muito raramente você quer se juntar a todo o conteúdo da grande mesa A com todo o conteúdo da grande mesa B. Em vez disso, você escreve a consulta de tal forma que apenas as linhas importantes de cada tabela são usados ??e o conjunto real mantida pelo juntar restos menor.

Além disso, você tem as eficiências mencionados por Peter Wone, de tal forma que apenas as partes importantes de cada registro precisa estar na memória até que o resultado final é materializado. Além disso, em consultas grandes com muitas junções que você normalmente quer começar com os conjuntos de mesa menores e sua maneira de trabalhar para as grandes, para que o conjunto mantido em restos de memória tão pequena quanto possível o maior tempo possível.

Quando feito corretamente, se junta são geralmente o melhor maneira para comparar, combinar, ou filtro de grandes quantidades de dados.

O gargalo é muito bonito sempre disco I / O, e ainda mais especificamente - disco aleatório I / O (por comparação, leituras seqüenciais são bastante rápido e pode ser armazenado em cache com as estratégias de leitura antecipada).

junta pode aumentar aleatório procura - se você está pulando em torno de ler pequenas partes de uma grande mesa. Mas, otimizadores de consulta olhar para isso e vai transformá-lo em uma varredura seqüencial da tabela (descartando as linhas desnecessárias) se ele pensa que seria melhor.

A única tabela desnormalizada tem um problema semelhante - as linhas são grandes, e assim menos aptos em uma página de dados único. Se você precisar de linhas que estão localizados longe da outra (e do grande tamanho da linha torna ainda mais distante), então você terá mais aleatória I / O. Novamente, uma varredura da tabela pode ser forçado a evitar isso. Mas, desta vez, a digitalização tabela tem de ler mais dados por causa do grande tamanho da linha. Acrescente a isso o fato de que você está copiar dados a partir de um único local para vários locais, eo RDBMS tem que muito mais para ler (e cache).

Com 2 tabelas, você também terá 2 índices de cluster - e geralmente pode índice mais (por causa de menos insert / sobrecarga atualização) que você pode obter aumentou drasticamente o desempenho (principalmente, de novo, já que os índices são (relativamente) pequeno, rápido para lido em disco (ou barato para cache), e diminuir a quantidade de linhas da tabela que você precisa ler a partir do disco).

Sobre a única em cima com uma junção vem de descobrir as linhas correspondentes. SQL Server usa 3 tipos diferentes de junta, com base principalmente no conjunto de dados tamanhos para encontrar registros coincidentes. Se o otimizador escolhe o errado tipo de junção (devido a estatísticas imprecisas, índices inadequados, ou apenas um bug otimizador ou caso extremo) que pode afetar drasticamente consulta vezes.

Um loop participar é farily barato para (pelo menos 1) pequeno conjunto de dados.
Uma união de combinação requer uma espécie de ambos os conjuntos de dados em primeiro lugar. Se você juntar-se em uma coluna indexada, no entanto, em seguida, o índice já está classificado e não mais trabalho precisa ser feito. Caso contrário, existe alguma CPU e memória sobrecarga na classificação.
O hash requer tanto de memória (para armazenar o hashtable) e CPU (para construir o hash). Novamente, isso é bastante rápido em relação ao disco I / O. No entanto , se não há memória RAM suficiente para armazenar o hashtable, o SQL Server irá utilizar tempdb para armazenar partes do hashtable e as linhas encontradas, e depois processar apenas partes do hashtable de cada vez. Tal como acontece com todas as coisas do disco, este é bastante lento.

No caso ideal, estes causam nenhum disco I / O - e assim são insignificantes do ponto de vista do desempenho.

Ao todo, na pior das hipóteses - ele deve realmente ser mais rápido para ler a mesma quantidade de lógica dados de x juntou mesas, pois é a partir de uma única tabela desnormalizada por causa do disco menor lê. Para ler a mesma quantidade de físicos de dados, pode haver uma ligeira sobrecarga.

Uma vez que o tempo de consulta é geralmente dominado por custos de I / O, e do tamanho de seus dados não muda (menos alguma sobrecarga linha muito minúsculo) com desnormalização, não há uma quantidade enorme de benefício a ser tido por apenas fundindo tabelas juntos . O tipo de desnormalização que tende a aumentar o desempenho, IME, é o cache valores calculados em vez de ler as linhas 10.000 necessários para calculá-los.

A ordem em que você está juntando as tabelas é extremamente importante. Se você tem dois conjuntos de dados tentar construir a consulta de uma forma para que o menor será usado primeiro para reduzir a quantidade de dados a consulta tem que trabalhar em.

Para alguns bancos de dados não importa, por exemplo, MS SQL sabe o bom ordem de junção a maior parte do tempo. Para alguns (como IBM Informix) a ordem faz toda a diferença.

Decidir sobre a possibilidade de desnormalizar ou normalize é bastante um processo 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 (log n k), onde k é relativo à magnitude de saída desejado.

Uma maneira fácil de desnormalizar e otimizar o desempenho é pensar sobre como alterações em sua estrutura normalize afetar sua estrutura desnormalizada. Isto pode ser problemático, porém, como ele pode exigir lógica transacional para o trabalho em um denormalized estruturado.

O debate para a normalização e desnormalização não vai acabar pois os problemas são vastas. Há muitos problemas onde a solução natural requer ambas as abordagens.

Como regra geral, eu sempre armazenada uma estrutura normalizada e caches que podem ser reconstruídos denormalized. Eventualmente, esses caches salvar a minha bunda para resolver os problemas futura normalização.

Elaborar o que já foi dito,

junta são produtos apenas cartesianas com alguns lipgloss. {1,2,3,4} X {1,2,3} nos daria 12 combinações (nxn = n ^ 2). Este conjunto computadorizada atua como uma referência em que são aplicadas condições. O DBMS aplica as condições (como onde esquerda e direita são 2 ou 3) para nos dar a condição correspondente (s). Na verdade, é mais otimizado, mas o problema é o mesmo. As alterações ao tamanho dos conjuntos aumentaria o tamanho do resultado exponencialmente. A quantidade de memória e ciclos de CPU consumidos todos são efectuadas em termos exponenciais.

Quando denormalise, evitamos esse cálculo completamente, pensar em ter um colorido pegajoso, ligado a todas as páginas do seu livro. Você pode inferir a informação com usando uma referência. O pagamento penalidade que é que estamos a comprometer a essência do DBMS (melhor organização dos dados)

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow