none
Seletividade x Densidade x Cardinalidade

    Pergunta

  • Pessoal,

     

    Alguém conhece algum artigo ou poderia explicar o significado desses três conceitos em banco de dados e sua aplicação a índices?!

     

    Att.

    Sérgio Duarte

    quarta-feira, 20 de agosto de 2008 01:59

Respostas

  • Boa Noite,

     

    Esses são conceitos importantes para entender quando um índice pode ou não ser utilizado. Vamos então a uma explicação introdutória. Antes vamos pensar na seguinte reflexão:

     

    Se eu estivesse em um concessionária com 100 carros dentre os quais um Astra fosse o mais "fraco", certamente eu escolheria qualquer carro já que se um Astra me deixaria muito satisfeito então qualquer um dos 100 carros me atenderia. Se alguém com um poder aquisitivo de um jogador de futebol do Milan por exemplo fosse a essa mesma concessionária certamente que com o dinheiro que tem o Astra seria o último carro que ele iria se interessar sendo que poderia escolher um Audi, uma BMW, uma Ferrari, etc

     

    Seletividade

    Seletividade é um derivado de seleção e envolve de certa forma uma escolha entre um determinado grupo. Eu na dita concessionária não seria nenhum pouco seletivo visto que qualquer um dos carros, ou melhor dizendo, todos os carros me atenderiam prontamente. O jogador do Milan por exemplo seria muito mais seletivo do que eu, visto que talvez um ou dois carros estivessem na sua lista de possíveis aquisições.

     

    Da mesma forma, os índices também trabalham com o conceito de seletividade. Se um índice por exemplo ajuda a filtrar poucas linhas de um universo de milhões de linhas, ele será dito seletivo. Se um índice não ajuda a recuperar muitas de um determinado universo, ele será dito pouco seletivo ou não seletivo. Ex:

     

    Code Snippet
    SELECT
    * FROM Clientes WHERE CPF = '766.456.331-20'

     

    Considerando que o CPF é único e que exista um CPF por clientes, se tivermos um universo de 5 milhões de clientes, poderemos dizer que esse índice é altamente seletivo já que em um universo de 5 milhões de clientes, ele foi capaz de filtrar um único registro. Agora se observarmos a consulta abaixo:

     

    Code Snippet
    SELECT
    * FROM Clientes WHERE Sexo = 'M'

     

    Se desconsiderarmos algumas instituições governamentais que consideram nove possibilidades para definir o sexo de uma pessoa, só temos duas respostas possíveis (M ou F). Nesse caso, esse índice tende a ser muito pouco seletivo já que possivelmente retornaria metade da tabela. Se considerarmos os mesmos 5 milhões de clientes, o índice favoreceria a recuperação de 2,5 milhões de registros e certamente gastaria muitos recursos (teríamos de ler as páginas de índices para depois chegar possivelmente na metade das páginas de dados). Esse índice então possui baixíssima seletividade e certamente não servirá para auxiliar as consultas (e ainda tem gente que indexa o campo sexo por default, total desperdício de recursos).

     

    Densidade

    Densidade é conhecida na física como a divisão entre massa e volume. Quanto maior a massa e menor o volume mais "denso" é a matéria. Isso explica porque em um copo de 100ml com suco vale pode parecer bem mais grosso que um copo de 100ml com água (mais massa em um mesmo volume). Um índice é dito muito denso, quando consegue retornar um grande conjunto de resultados em potencial. Se eu estivesse na concessionária por exemplo, minha escolha seria muito "densa", pois eu seria capaz de escolher todos os carros (ainda que não tivesse dinheiro para comprá-los). O jogador do Milan teria uma escolha pouco densa, pois, escolheria poucos carros no universo da dita concessionária.

     

    Observe que seletividade e densidade são conceitos são opostos. Quanto mais seletivo for um índice melhor para as pesquisas. Quanto mais denso for um índice pior para as pesquisas. Um campo com uma chave primária será o índice mais seletivo possível, pois, seus valores nunca irão se repetir e a busca por qualquer um desses valores será uma ocorrência contra todos os registros da tabela.

     

    Existe mais a explorar sobre esse assunto e certamente esse raciocínio é apenas o primeiro passo. Se quiser algo em português, dê uma olhada na SQL Magazine 9 onde Paulo Ribeiro explora bastante os conceitos de estatísticas, seletividade, densidade, etc. Após essa leitura, teste seu conhecimento testando a instrução DBCC SHOW_STATISTICS e vendo realmente o que significam aqueles campos (será muito mais esclarescedor agora).

     

    Para fins comparativos, você pode se basear no seguinte:

     

    Code Snippet

    -- Cálculo da Seletividade para a coluna CustomerID (FK)

    SELECT

    CAST(COUNT(DISTINCT CustomerID) AS DECIMAL(10,4))/ COUNT(CustomerID)

    FROM

    Sales.SalesOrderHeader

     

    -- Cálculo da Seletividade para a coluna SalesOrderNumber (PK)

    SELECT

    CAST(COUNT(DISTINCT SalesOrderNumber) AS DECIMAL(10,4))/ COUNT(SalesOrderNumber)

    FROM

    Sales.SalesOrderHeader

     

    -- Cálculo da Densidade para a coluna CustomerID (FK)

    SELECT 1.00 / (

    CAST(COUNT(DISTINCT CustomerID) AS DECIMAL(10,4))/ COUNT(CustomerID))

    FROM

    Sales.SalesOrderHeader

     

    -- Cálculo da Densidade para a coluna SalesOrderNumber (PK)

    SELECT 1.00 / (

    CAST(COUNT(DISTINCT SalesOrderNumber) AS DECIMAL(10,4))/ COUNT(SalesOrderNumber))

    FROM

    Sales.SalesOrderHeader

     

     

    Observe que a coluna CustomerID é uma FK e por isso tem um índice de repetições maior (é mais densa e menos seletiva) enquanto a coluna SalesOrderNumber é uma PK e por isso tem um índice de repetições igual a zero (é menos densa e mais seletiva). Esses cálculos são apenas uma representação de um conceito, mas seu cálculo real não é feito da forma descrita (não lembro da regra do cálculo no momento). Normalmente índices abaixo de 10% de densidade são utilizados nas consultas, índices entre 10% e 25% podem ser utilizados nas consultas e índices com mais de 50% não serão utilizados nas consultas (na PK a densidade é praticamente nula).

     

    Terminei o post, mas deixei um item para trás... Não falei da cardinalidade... Bom, essa palavra é ambígua e não sei qual das linhas postar aqui (nem o Books OnLine se manifesta). Vou deixar para algum dos colegas falar a respeito ou você descobrir nas referências. Já está tarde e amanhã tenho um Webcast para participar também (rs)

     

    [ ]s,

     

    Gustavo

    quarta-feira, 20 de agosto de 2008 04:59

Todas as Respostas

  • Boa Noite,

     

    Esses são conceitos importantes para entender quando um índice pode ou não ser utilizado. Vamos então a uma explicação introdutória. Antes vamos pensar na seguinte reflexão:

     

    Se eu estivesse em um concessionária com 100 carros dentre os quais um Astra fosse o mais "fraco", certamente eu escolheria qualquer carro já que se um Astra me deixaria muito satisfeito então qualquer um dos 100 carros me atenderia. Se alguém com um poder aquisitivo de um jogador de futebol do Milan por exemplo fosse a essa mesma concessionária certamente que com o dinheiro que tem o Astra seria o último carro que ele iria se interessar sendo que poderia escolher um Audi, uma BMW, uma Ferrari, etc

     

    Seletividade

    Seletividade é um derivado de seleção e envolve de certa forma uma escolha entre um determinado grupo. Eu na dita concessionária não seria nenhum pouco seletivo visto que qualquer um dos carros, ou melhor dizendo, todos os carros me atenderiam prontamente. O jogador do Milan por exemplo seria muito mais seletivo do que eu, visto que talvez um ou dois carros estivessem na sua lista de possíveis aquisições.

     

    Da mesma forma, os índices também trabalham com o conceito de seletividade. Se um índice por exemplo ajuda a filtrar poucas linhas de um universo de milhões de linhas, ele será dito seletivo. Se um índice não ajuda a recuperar muitas de um determinado universo, ele será dito pouco seletivo ou não seletivo. Ex:

     

    Code Snippet
    SELECT
    * FROM Clientes WHERE CPF = '766.456.331-20'

     

    Considerando que o CPF é único e que exista um CPF por clientes, se tivermos um universo de 5 milhões de clientes, poderemos dizer que esse índice é altamente seletivo já que em um universo de 5 milhões de clientes, ele foi capaz de filtrar um único registro. Agora se observarmos a consulta abaixo:

     

    Code Snippet
    SELECT
    * FROM Clientes WHERE Sexo = 'M'

     

    Se desconsiderarmos algumas instituições governamentais que consideram nove possibilidades para definir o sexo de uma pessoa, só temos duas respostas possíveis (M ou F). Nesse caso, esse índice tende a ser muito pouco seletivo já que possivelmente retornaria metade da tabela. Se considerarmos os mesmos 5 milhões de clientes, o índice favoreceria a recuperação de 2,5 milhões de registros e certamente gastaria muitos recursos (teríamos de ler as páginas de índices para depois chegar possivelmente na metade das páginas de dados). Esse índice então possui baixíssima seletividade e certamente não servirá para auxiliar as consultas (e ainda tem gente que indexa o campo sexo por default, total desperdício de recursos).

     

    Densidade

    Densidade é conhecida na física como a divisão entre massa e volume. Quanto maior a massa e menor o volume mais "denso" é a matéria. Isso explica porque em um copo de 100ml com suco vale pode parecer bem mais grosso que um copo de 100ml com água (mais massa em um mesmo volume). Um índice é dito muito denso, quando consegue retornar um grande conjunto de resultados em potencial. Se eu estivesse na concessionária por exemplo, minha escolha seria muito "densa", pois eu seria capaz de escolher todos os carros (ainda que não tivesse dinheiro para comprá-los). O jogador do Milan teria uma escolha pouco densa, pois, escolheria poucos carros no universo da dita concessionária.

     

    Observe que seletividade e densidade são conceitos são opostos. Quanto mais seletivo for um índice melhor para as pesquisas. Quanto mais denso for um índice pior para as pesquisas. Um campo com uma chave primária será o índice mais seletivo possível, pois, seus valores nunca irão se repetir e a busca por qualquer um desses valores será uma ocorrência contra todos os registros da tabela.

     

    Existe mais a explorar sobre esse assunto e certamente esse raciocínio é apenas o primeiro passo. Se quiser algo em português, dê uma olhada na SQL Magazine 9 onde Paulo Ribeiro explora bastante os conceitos de estatísticas, seletividade, densidade, etc. Após essa leitura, teste seu conhecimento testando a instrução DBCC SHOW_STATISTICS e vendo realmente o que significam aqueles campos (será muito mais esclarescedor agora).

     

    Para fins comparativos, você pode se basear no seguinte:

     

    Code Snippet

    -- Cálculo da Seletividade para a coluna CustomerID (FK)

    SELECT

    CAST(COUNT(DISTINCT CustomerID) AS DECIMAL(10,4))/ COUNT(CustomerID)

    FROM

    Sales.SalesOrderHeader

     

    -- Cálculo da Seletividade para a coluna SalesOrderNumber (PK)

    SELECT

    CAST(COUNT(DISTINCT SalesOrderNumber) AS DECIMAL(10,4))/ COUNT(SalesOrderNumber)

    FROM

    Sales.SalesOrderHeader

     

    -- Cálculo da Densidade para a coluna CustomerID (FK)

    SELECT 1.00 / (

    CAST(COUNT(DISTINCT CustomerID) AS DECIMAL(10,4))/ COUNT(CustomerID))

    FROM

    Sales.SalesOrderHeader

     

    -- Cálculo da Densidade para a coluna SalesOrderNumber (PK)

    SELECT 1.00 / (

    CAST(COUNT(DISTINCT SalesOrderNumber) AS DECIMAL(10,4))/ COUNT(SalesOrderNumber))

    FROM

    Sales.SalesOrderHeader

     

     

    Observe que a coluna CustomerID é uma FK e por isso tem um índice de repetições maior (é mais densa e menos seletiva) enquanto a coluna SalesOrderNumber é uma PK e por isso tem um índice de repetições igual a zero (é menos densa e mais seletiva). Esses cálculos são apenas uma representação de um conceito, mas seu cálculo real não é feito da forma descrita (não lembro da regra do cálculo no momento). Normalmente índices abaixo de 10% de densidade são utilizados nas consultas, índices entre 10% e 25% podem ser utilizados nas consultas e índices com mais de 50% não serão utilizados nas consultas (na PK a densidade é praticamente nula).

     

    Terminei o post, mas deixei um item para trás... Não falei da cardinalidade... Bom, essa palavra é ambígua e não sei qual das linhas postar aqui (nem o Books OnLine se manifesta). Vou deixar para algum dos colegas falar a respeito ou você descobrir nas referências. Já está tarde e amanhã tenho um Webcast para participar também (rs)

     

    [ ]s,

     

    Gustavo

    quarta-feira, 20 de agosto de 2008 04:59
  • Valeu Gustavo,

     

    A explicação foi ótima

     

    Sérgio

    quarta-feira, 20 de agosto de 2008 23:16
  • Gustavo,

     

    Vale citar que a seletividade de um índice é calculada da seguinte forma:

     

    Total de registros únicos / total geral de registros.

     

    Ou seja, seletividade, quanto maior é melhor e a máxima seletividade é 1.

     

    Abraços.

     

     

    quinta-feira, 23 de outubro de 2008 15:25
  • Otima Explicação. Sem comentários.

    sexta-feira, 28 de novembro de 2008 16:46
  • muito boa a respostaaa =D

     

    e sobre a cardinalidade?

     

    segunda-feira, 15 de dezembro de 2008 14:51
  • Boa noite p,

    Sou novo no MSDN mais posso escrever alguma coisa sobre cardinalidade.

    Eu encontro este assunto ligado mais a livros de Projetos de Banco de Dados, que tratam exclusivamente da estrutura de um banco. Ás vezes livros que centralizam em alguma ferramenta específica deixam de citar esse importantíssimo detalhe

    Cardinalidade é uma propriedade que está relacionada a quantidade de ocorrências que podem ocorrer em um relacionamento.

     

    Um bom exemplo é um relacionamento de empregado e departamento. Neste caso um empregado pode estar associado à no máximo um departamento. Em direção contrária um departamento pode estar associado com vários (n) empregados.

     

    Sendo assim apenas duas cardinalidades são relevantes, a cardinalidade máxima 1(um) e a cardinalidade máxima muitos (n)

     

    Espero ter ajudado.


    sábado, 9 de maio de 2009 23:50
  • Olá Alexandre,

    Sim, você está correto. Na verdade, a cardinalidade no sentido da sua explicação está se tornando um termo "ultrapassado". A maioria dos autores (influenciados pela UML) está substituindo esse termo por "multiplicidade".

    É justamente na sua explicação que disse haver uma certa ambigüidade. Se analisarmos o termo "cardinalidade" em relação a uma proposta de modelagem, a sua explicação se faz totalmente válida, ou seja, cardinalidade refere-se exatamente a uma quantidade de ocorrências em podem ocorrer em um relacionamento.

    Do ponto de vista físico e nos planos de consulta, entendemos cardinalidade como a quantidade de ocorrências para uma determinada coluna ou grupo de colunas. A cardinalidade pode dizer que o cliente 1 se repete duas vezes, o cliente 2 se repete 10 vezes e que o cliente 3 possui apenas uma ocorrência. Com base nessas quantidades (mantidas pelas estatísticas), o otimizador de consulta poderá decidir se vale a pena ou não utilizar um índice (afinal a cardinalidade será utilizada para os cálculos de seletividade e densidade).

    Quando vi as três expressões juntas, imaginei que o sentido fosse o físico, mas ainda assim há ambigüidade. Se voltarmos a atenção para a modelagem, o uso de índices é o que garante as "constraints". Assim sendo, para garantir uma cardinalidade 1 para 1 é necessário criar um índice Unique (que nada mais é que uma implementação física de um PK ou de uma Unique Constraint).

    [ ]s,

    Gustavo Maia Aguiar
    http://gustavomaiaaguiar.spaces.live.com

    Criando uma tabela com uma seqüência de números – Parte II
    http://gustavomaiaaguiar.spaces.live.com/blog/cns!F4F5C630410B9865!556.entry
    Classifique as respostas. O seu feedback é imprescindível
    domingo, 10 de maio de 2009 23:58
  • Boa tarde Gustavo, Blz?

    Perfeito Gustavo. Realmente os livros que mencionam o nome cardinalidade são mais antigos. Enriqueceu bastante o assunto com o seu comentário.

    Muito obrigado.
    segunda-feira, 18 de maio de 2009 16:51