Tuesday, May 10, 2005
Índices, Falando Livremente
Sempre quando imaginamos performance/otimização, logo vem a nossa cabeça: índice. Interessante, vou tentar dissertar livremente sobre índices. Esse artigo foi baseado em uma resposta ao um colega em uma lista de discussão.
A base do texto é na experiência vivida com os assuntos abordados, vou tentar passar, mesmo que as vezes empiricamente, o que eu entendo e uso no meu dia-a-dia. Estou tomando a versão 9i (9.2.0) como base para minha explicação.
Os índices não são 100% o bem e nem 100% o mal. Eles são um instrumento, uma ferramenta, que, se bem utilizada, servirá para bons resultados de desempenho. O conhecimento dos dados é essencial para criar índices eficientes. E não considere índice como magia onde fast=true, porque não é.
Em tudo quanto é lista de discussão que eu participo, sempre tem uma solução para performance igual a:
"Ah, voce SEMPRE tem que usar índice para acelerar sua consulta. Tá vendo, tá fazendo FULL TABLE SCAN (FTS). Isso é mal. Isso é o demônio!"
Recordem o que eu disse sobre os índices não serem 100% o bem, consequentemente FTS, não é de todo mal.
Então, considere a tabela T com (x int, y char(2000)) --> Ora, se SEMPRE os índices resolvem meus problemas de performance, eu vou forçar meu otimizador a fazer o caminho através do índice.
Vamos forçar o fts e verificar o comportamento.
Agora vamos pensar: 7 MINUTOS para 11 SEGUNDOS!! Absurdo não? Por que isso acontece? Quando o otimizador faz a pesquisa por índice, isso não assegura que ele irá visitar o bloco #1 apenas uma vez. Sabemos que em um bloco podemos ter várias linhas e em uma árvore binária vários mapas apontando para o bloco #1. Conforme vamos caminhando na pesquisa, para buscar outras linhas, naturalmente voltaremos ao bloco #1. -- Bum! Overhead. Estamos visitando e re-visitando, quem sabe quantas vezes o mesmo bloco para ler outras linhas. Se um bloco tem 10 linhas, por exemplo, e o índice, no decorrer da árvore tiver 10 entradas para o #1, haverá 10 leituras para o mesmo bloco. Já o FTS passa no bloco uma única vez e já agarra tudo pela frente, ele sabe que a pesquisa é grande, então ele leva tudo que for possível de forma otimizada.
Por outro lado, se utilizássemos a mesma tabela usando um predicado que retornarnasse de 1-5% da tabela, o índice me ajudaria muito, já FTS, não seria uma grande escolha. Isso pode ser provado através de:
Menos de UM para 6 segundos, diferença não tão grande, porém veja a quantidade de esforço (LIOs) que foi necessários para atender as 2 queries. A primeira com índice 15 LIOs + 12 PIOs e a segunda (fts) ~10.000 LIOs + ~8.000 PIOs. Isso mostra a necessidade de conhecimento dos dados, seu predicado, qual a finalidade da query, enfim -- cuidado com o que pede ao banco, porque ele trabalha com o que tem.
Antes de começar a discutir índices, vamos falar um pouco de tipos de tabelas, porque também elas influenciam no desempenho. 98% das tabelas que eu utilizo são heap ou IOT. Heap é a tabela normal, os blocos são armazenados de forma aleatória no storage, enquanto que a IOT (Index Organized Table), os dados "conhecem" onde devem ir, já que eles são organizados pela primary key. Isso tem um preço, ou seja, este tipo de tabela não é candidata a receber milhôes de inserções por minuto.
Quando uso IOT? Para tabelas lookup (pai e filho por exemplo). Sabe aquelas tabelas que orbitam no sistema. Exemplo: Empregado 1-m Endereço, ou tabelas muito pequenas com necessidade de primary key - não gasto dois segmentos, isto é, espaço para os dados e para o índice.
O que eu ganho? Ora, se os dados estão armazenados juntos, estão próximos, quando houver um JOIN ou um /*+ first_rows */, FTS com sort, eu ganho pela proximidade, portanto eles chegaram mais rápido a área de sort e levaram menos tempo para serem organizados.
O que eu perco? Overhead de insert e manutenção. IOT requer mais cuidado, export, import, rowid, etc.
Voltando aos índices. Vou me manifestar sobre os índices que eu já trabalhei em produção, ou seja, b*tree, bitmap e Function Based Index (FBI). Vamos a eles.
b*tree -> Quando eu uso no predicado muitas vezes o mesmo campo, dt_inclusao, por exemplo, esse campo é candidato a estar indexado pela b*tree, para conhecer um pouco mais sobre todos os índices, aconselho a leitura do Manual Concepts. Este tipo de índice tem alguns subgrupos. Um já comentei acima, IOT, os outros -- Cluster b*tree e Hash b*tree -- Já "brinquei" com os dois, mas não tenho experiência em produção, portanto, não farei menção.
O índice b*tree tem uma cláusula legal para economizar espaço - COMPRESS. Imagine que voce quer montar um índice composto, tipo de (autor, genero, obra) e suas entradas são parecidas com:
Jorge Amado, Romance, Gabriela
Jorge Amado, Romance, Capitães de Areia
Jorge Amado, Romance, Tieta
...
Na página de índice, voce teria examente estas entradas, porém lembre-se da matemática e fatore.
-> xa+xb+xc=0 = x(a+b+c)=0,
Então, podemo usar COMPRESS 1 e teríamos como resultado:
Jorge Amado
Romance, Gabriela
Romance, Capitães de Areia
Romance, Tieta
Notem, dimunímos bem o espaço, mas... poderíamos usar ainda o COMPRESS 2 e armazenarmos assim:
Jorge Amado, Romance
Gabriela
Capitães de Areia
Tieta
Uma bela e enxuta página de índices b*tree. Não posso esquecer também do REVERSE dentro do b*tree, que armazena ABC como CBA.
Concluindo, Quando uso b*tree:
a) O(s) campo(s) envolvidos no predicado, sempre me devolvem 1-5% de registros em relação ao total (regra de dedão, significa que começo por aí.)
b) Responder a pergunta da query com todas as colunas indexadas. Mais adiante, juntamente com o índice do tipo bitmap, dou um exemplo da resposta da query em índice
Partimos agora para o índice bitmap. Quando existe pouca cardinalidade em uma coluna e essa coluna é exigida em predicados, é candidata a ser indexada em bitmap. O bitmap, usa um mapa binário (0/1) para identificar a linha, isso o torna extremamente enxuto e ótimo para responder contagens, estatísticas e outras exigências de uma Data warehousing, Veja o exemplo -- também, estou colocando o caso de responder queries com índices, ao invés de FTS.
Vou criar 2 índices, um bitmap e outro para responder a query. Preste atenção que enquanto o otimizador não conhece o histograma da coluna bm, ele não usa o bitmap -- estamos falando do CBO, porque o RBO não usa mesmo.
Veja que, ao invés de FTS, está fazendo RANGE SCAN no índice, isso não é de todo mal nem de todo bem. Porém, para o caso serviu, trouxe a resposta em menos de 1 segundo, porém gastou um pouco a mais de recurso que o bitmap iria gastar. No caso de escalabilidade, sempre economize recurso -- Outra regrinha que eu tenho é no máximo 10 LIOs para trazer um registro, encontre esse número dividindo LIOs/número de linhas processadas (também uma regra de polegar).
Prossigamos.
Coletando estatísticas e gerando histogramas.
Depois da coleta de estatística, o otimizador passou a ser o CBO -- com o histograma da coluna bm pode fazer rapidamente a contagem dos registros.
Para finalizar, FBI (Function Based Indexes). Índices baseados em funções, ou seja, voce pode construir um índice que seja resultado de uma função. Podemos pegar a tabela emp do SCOTT e fazer uma função DETERMINISTIC, ou seja, para a mesma entrada eu sempre tenho a mesma saída. Exemplo UPPER('x') será sempre igual a 'X', isto é uma função deterministic. Mais uma vez o CBO é player aqui e teremos que setar dois novos parâmetros:
Pequeno exemplo:
Concluímos que não existe o parâmetro fast=true, índices são apenas ferramentas e devem ser usados conforme necessidade e aplicabilidade. Também é muito importante conhecer os dados e a finalidade das queries, quantidade de registros e como são organizados.
Abraço,
A base do texto é na experiência vivida com os assuntos abordados, vou tentar passar, mesmo que as vezes empiricamente, o que eu entendo e uso no meu dia-a-dia. Estou tomando a versão 9i (9.2.0) como base para minha explicação.
Os índices não são 100% o bem e nem 100% o mal. Eles são um instrumento, uma ferramenta, que, se bem utilizada, servirá para bons resultados de desempenho. O conhecimento dos dados é essencial para criar índices eficientes. E não considere índice como magia onde fast=true, porque não é.
Em tudo quanto é lista de discussão que eu participo, sempre tem uma solução para performance igual a:
"Ah, voce SEMPRE tem que usar índice para acelerar sua consulta. Tá vendo, tá fazendo FULL TABLE SCAN (FTS). Isso é mal. Isso é o demônio!"
Recordem o que eu disse sobre os índices não serem 100% o bem, consequentemente FTS, não é de todo mal.
Então, considere a tabela T com (x int, y char(2000)) --> Ora, se SEMPRE os índices resolvem meus problemas de performance, eu vou forçar meu otimizador a fazer o caminho através do índice.
ops$marcio@MRP920> create table t
2 ( x int, y char(2000) );
Table created.
ops$marcio@MRP920>
ops$marcio@MRP920> insert into t
2 select rownum, rpad('*', 75, '*')
3 from all_objects
4 order by dbms_random.value
5 /
29304 rows created.
ops$marcio@MRP920>
ops$marcio@MRP920> create index t_idx on t ( x );
Index created.
ops$marcio@MRP920>
ops$marcio@MRP920> set timing on
ops$marcio@MRP920> set autotrace traceonly
ops$marcio@MRP920>
ops$marcio@MRP920> select * from t where x > 20;
29284 rows selected.
Elapsed: 00:07:26.06 (7 minutos)
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'T'
2 1 INDEX (RANGE SCAN) OF 'T_IDX' (NON-UNIQUE)
Pseudo código:
for x in ( select rowid from t )
loop
select t_idx.rowid
from t_idx
where x.rowid = t_idx.rowid
end loop
Statistics
----------------------------------------------------------
33248 consistent gets
24893 physical reads
Vamos forçar o fts e verificar o comportamento.
ops$marcio@MRP920> select /*+ full(t) */ * from t where x > 20;
29284 rows selected.
Elapsed: 00:00:11.07
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=4 Bytes=8060)
1 0 TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=4 Bytes=8060)
Statistics
----------------------------------------------------------
11240 consistent gets
7362 physical reads
Agora vamos pensar: 7 MINUTOS para 11 SEGUNDOS!! Absurdo não? Por que isso acontece? Quando o otimizador faz a pesquisa por índice, isso não assegura que ele irá visitar o bloco #1 apenas uma vez. Sabemos que em um bloco podemos ter várias linhas e em uma árvore binária vários mapas apontando para o bloco #1. Conforme vamos caminhando na pesquisa, para buscar outras linhas, naturalmente voltaremos ao bloco #1. -- Bum! Overhead. Estamos visitando e re-visitando, quem sabe quantas vezes o mesmo bloco para ler outras linhas. Se um bloco tem 10 linhas, por exemplo, e o índice, no decorrer da árvore tiver 10 entradas para o #1, haverá 10 leituras para o mesmo bloco. Já o FTS passa no bloco uma única vez e já agarra tudo pela frente, ele sabe que a pesquisa é grande, então ele leva tudo que for possível de forma otimizada.
Por outro lado, se utilizássemos a mesma tabela usando um predicado que retornarnasse de 1-5% da tabela, o índice me ajudaria muito, já FTS, não seria uma grande escolha. Isso pode ser provado através de:
ops$marcio@MRP920> select * from t where x between 20 and 30;
1 rows selected.
lapsed: 00:00:00.04
Execution Plan
---------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'T'
2 1 INDEX (RANGE SCAN) OF 'T_IDX' (NON-UNIQUE)
statistics
---------------------------------------------------------
15 consistent gets
12 physical reads
ops$marcio@MRP920> select /*+ full(t) */ * from t where x between 20 and 30;
11 rows selected.
Elapsed: 00:00:06.02
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=1 Bytes=2015)
1 0 TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=1 Bytes=2015)
Statistics
----------------------------------------------------------
9852 consistent gets
7672 physical reads
Menos de UM para 6 segundos, diferença não tão grande, porém veja a quantidade de esforço (LIOs) que foi necessários para atender as 2 queries. A primeira com índice 15 LIOs + 12 PIOs e a segunda (fts) ~10.000 LIOs + ~8.000 PIOs. Isso mostra a necessidade de conhecimento dos dados, seu predicado, qual a finalidade da query, enfim -- cuidado com o que pede ao banco, porque ele trabalha com o que tem.
Antes de começar a discutir índices, vamos falar um pouco de tipos de tabelas, porque também elas influenciam no desempenho. 98% das tabelas que eu utilizo são heap ou IOT. Heap é a tabela normal, os blocos são armazenados de forma aleatória no storage, enquanto que a IOT (Index Organized Table), os dados "conhecem" onde devem ir, já que eles são organizados pela primary key. Isso tem um preço, ou seja, este tipo de tabela não é candidata a receber milhôes de inserções por minuto.
Quando uso IOT? Para tabelas lookup (pai e filho por exemplo). Sabe aquelas tabelas que orbitam no sistema. Exemplo: Empregado 1-m Endereço, ou tabelas muito pequenas com necessidade de primary key - não gasto dois segmentos, isto é, espaço para os dados e para o índice.
O que eu ganho? Ora, se os dados estão armazenados juntos, estão próximos, quando houver um JOIN ou um /*+ first_rows */, FTS com sort, eu ganho pela proximidade, portanto eles chegaram mais rápido a área de sort e levaram menos tempo para serem organizados.
O que eu perco? Overhead de insert e manutenção. IOT requer mais cuidado, export, import, rowid, etc.
Voltando aos índices. Vou me manifestar sobre os índices que eu já trabalhei em produção, ou seja, b*tree, bitmap e Function Based Index (FBI). Vamos a eles.
b*tree -> Quando eu uso no predicado muitas vezes o mesmo campo, dt_inclusao, por exemplo, esse campo é candidato a estar indexado pela b*tree, para conhecer um pouco mais sobre todos os índices, aconselho a leitura do Manual Concepts. Este tipo de índice tem alguns subgrupos. Um já comentei acima, IOT, os outros -- Cluster b*tree e Hash b*tree -- Já "brinquei" com os dois, mas não tenho experiência em produção, portanto, não farei menção.
O índice b*tree tem uma cláusula legal para economizar espaço - COMPRESS. Imagine que voce quer montar um índice composto, tipo de (autor, genero, obra) e suas entradas são parecidas com:
Jorge Amado, Romance, Gabriela
Jorge Amado, Romance, Capitães de Areia
Jorge Amado, Romance, Tieta
...
Na página de índice, voce teria examente estas entradas, porém lembre-se da matemática e fatore.
-> xa+xb+xc=0 = x(a+b+c)=0,
Então, podemo usar COMPRESS 1 e teríamos como resultado:
Jorge Amado
Romance, Gabriela
Romance, Capitães de Areia
Romance, Tieta
Notem, dimunímos bem o espaço, mas... poderíamos usar ainda o COMPRESS 2 e armazenarmos assim:
Jorge Amado, Romance
Gabriela
Capitães de Areia
Tieta
Uma bela e enxuta página de índices b*tree. Não posso esquecer também do REVERSE dentro do b*tree, que armazena ABC como CBA.
Concluindo, Quando uso b*tree:
a) O(s) campo(s) envolvidos no predicado, sempre me devolvem 1-5% de registros em relação ao total (regra de dedão, significa que começo por aí.)
b) Responder a pergunta da query com todas as colunas indexadas. Mais adiante, juntamente com o índice do tipo bitmap, dou um exemplo da resposta da query em índice
Partimos agora para o índice bitmap. Quando existe pouca cardinalidade em uma coluna e essa coluna é exigida em predicados, é candidata a ser indexada em bitmap. O bitmap, usa um mapa binário (0/1) para identificar a linha, isso o torna extremamente enxuto e ótimo para responder contagens, estatísticas e outras exigências de uma Data warehousing, Veja o exemplo -- também, estou colocando o caso de responder queries com índices, ao invés de FTS.
ops$marcio@MRP920> create table t_bitmap
2 as
3 select rownum x, decode(mod(rownum,3),2,'B',0,'C',null) bm, object_name
4 from all_objects
5 /
Table created.
ops$marcio@MRP920>
ops$marcio@MRP920> insert into t_bitmap select * from t_bitmap;
468864 rows created.
Vou criar 2 índices, um bitmap e outro para responder a query. Preste atenção que enquanto o otimizador não conhece o histograma da coluna bm, ele não usa o bitmap -- estamos falando do CBO, porque o RBO não usa mesmo.
ops$marcio@MRP920> create bitmap index bm_idx on t_bitmap ( bm);
Index created.
ops$marcio@MRP920> create index bm_idx_conv on t_bitmap ( bm, x);
Index created.
ops$marcio@MRP920>
ops$marcio@MRP920> set timing on
ops$marcio@MRP920> set autotrace traceonly
ops$marcio@MRP920>
ops$marcio@MRP920> select count(*)
2 from t_bitmap
3 where bm = 'C'
4 /
1 row selected.
Elapsed: 00:00:00.07
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 SORT (AGGREGATE)
2 1 INDEX (RANGE SCAN) OF 'BM_IDX_CONV' (NON-UNIQUE)
Veja que, ao invés de FTS, está fazendo RANGE SCAN no índice, isso não é de todo mal nem de todo bem. Porém, para o caso serviu, trouxe a resposta em menos de 1 segundo, porém gastou um pouco a mais de recurso que o bitmap iria gastar. No caso de escalabilidade, sempre economize recurso -- Outra regrinha que eu tenho é no máximo 10 LIOs para trazer um registro, encontre esse número dividindo LIOs/número de linhas processadas (também uma regra de polegar).
Prossigamos.
Statistics
----------------------------------------------------------
771 consistent gets
770 physical reads
Coletando estatísticas e gerando histogramas.
ops$marcio@MRP920> analyze table t_bitmap compute statistics;
Table analyzed.
Elapsed: 00:00:45.09
ops$marcio@MRP920>
ops$marcio@MRP920> select count(*)
2 from t_bitmap
3 where bm = 'C'
4 /
1 row selected.
Elapsed: 00:00:00.02
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=22 Card=1 Bytes=1)
1 0 SORT (AGGREGATE)
2 1 BITMAP CONVERSION (COUNT)
3 2 BITMAP INDEX (SINGLE VALUE) OF 'BM_IDX'
Statistics
----------------------------------------------------------
22 consistent gets
22 physical reads
Depois da coleta de estatística, o otimizador passou a ser o CBO -- com o histograma da coluna bm pode fazer rapidamente a contagem dos registros.
Para finalizar, FBI (Function Based Indexes). Índices baseados em funções, ou seja, voce pode construir um índice que seja resultado de uma função. Podemos pegar a tabela emp do SCOTT e fazer uma função DETERMINISTIC, ou seja, para a mesma entrada eu sempre tenho a mesma saída. Exemplo UPPER('x') será sempre igual a 'X', isto é uma função deterministic. Mais uma vez o CBO é player aqui e teremos que setar dois novos parâmetros:
query_rewrite_enabled = true e
query_rewrite_integrity = trusted.
Pequeno exemplo:
ops$marcio@MRP920> alter session set query_rewrite_enabled = true;
Session altered.
ops$marcio@MRP920> alter session set query_rewrite_integrity = trusted;
Session altered.
ops$marcio@MRP920>
ops$marcio@MRP920> drop table emp;
Table dropped.
ops$marcio@MRP920> create table emp as select * from scott.emp;
Table created.
ops$marcio@MRP920>
ops$marcio@MRP920> update emp set ename = lower(ename);
14 rows updated.
ops$marcio@MRP920>
ops$marcio@MRP920> set autotrace on explain
ops$marcio@MRP920>
ops$marcio@MRP920> select *
2 from emp
3 where upper(ename) = 'KING'
4 /
EMPNO ENAME JOB MGR HIREDATE SAL COMM DEPTNO
---------- ---------- --------- ---------- --------------------- ---------- --------- ----------
7839 king PRESIDENT 17/11/1981 - 00:00:00 5000 10
1 row selected.
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 TABLE ACCESS (FULL) OF 'EMP'
ops$marcio@MRP920>
ops$marcio@MRP920> create index emp_fbi on emp ( upper(ename) );
Index created.
ops$marcio@MRP920>
ops$marcio@MRP920> analyze table emp compute statistics;
Table analyzed.
ops$marcio@MRP920>
ops$marcio@MRP920> select *
2 from emp
3 where upper(ename) = 'KING'
4 /
EMPNO ENAME JOB MGR HIREDATE SAL COMM DEPTNO
---------- ---------- --------- ---------- --------------------- ---------- ---------- ----------
7839 king PRESIDENT 17/11/1981 - 00:00:00 5000 10
1 row selected.
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=1 Bytes=32)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (Cost=2 Card=1 Bytes=32)
2 1 INDEX (RANGE SCAN) OF 'EMP_FBI' (NON-UNIQUE) (Cost=1 Card=1)
Concluímos que não existe o parâmetro fast=true, índices são apenas ferramentas e devem ser usados conforme necessidade e aplicabilidade. Também é muito importante conhecer os dados e a finalidade das queries, quantidade de registros e como são organizados.
Abraço,
