Categorias
Banco de dados Programação

Access vs Filter Predicate

A maioria das aplicações desenvolvidas atualmente utilizam um banco de dados relacional para armazenar e recuperar os seus dados. Para que o tempo de resposta e escalabilidade de aplicação não seja prejudicado, é necessário que o banco de dados consiga recuperar as informações necessárias da maneira mais rápida e fácil possível.

Os índices em banco de dados são utilizados para conseguir recuperar os registros de uma maneira mais rápida e performática. Um índice é uma estrutura de dados que mantém os registros ordenados com base em algumas colunas definidas durante a sua criação. Com os dados ordenados dentro de um índice, ele pode ser utilizado para a filtragem e a ordenação dos registros.

A maioria das queries contém problemas no seu plano de execução. Os mais comuns são a falta de índices ou a utilização de índices não tão adequados para a query em execução. A falta de índice geralmente ocasiona um full table scan. Já a utilização de índices não adequados pode consumir mais CPU que o necessário para a execução da query.

Quando o índice é utilizado de forma adequada, a filtragem dos registros que devem ser recuperados são feitos totalmente através do uso do índice, nesse caso o banco está fazendo um “access predicate”. Já no caso da falta de índice ou até mesmo o uso de um índice não otimizado para a query, o banco irá fazer um “filter predicate”. O filter predicate nada mais é do que a filtragem dos dados utilizando a CPU do banco de dados.

Cada banco de dados exibe essa informação de maneira diferente. No Oracle o plano de execução mostra exatamente um “access predicate” ou um “filter predicate”. No MySQL o filter predicate é exibido através da coluna Extra do plano de execução. Nessa coluna pode ser exibida a informação “Using index condition” ou “Using where”, acompanhada da coluna “attached_condition” no plano de execução, informando quais são as colunas que estão sendo filtradas na CPU.

Exemplo

Vamos subir um Oracle XE local no docker com o seguinte comando:

docker run -d --name oracle --network host -e ORACLE_ALLOW_REMOTE=true oracleinanutshell/oracle-xe-11g

Vamos conectar nele através de alguma ferramenta como por exemplo o SQL Developer com os seguintes dados:

Hostname: 127.0.0.1
Port: 1521
SID: xe
Username: system
Password: oracle

Vamos primeiramente aumentar o tablespace para conseguir comportar todos os dados utilizados na massa de teste:

ALTER TABLESPACE SYSTEM ADD DATAFILE 'system2.dbf' SIZE 10G AUTOEXTEND ON;

Agora iremos criar a tabela e sequence utilizadas nos testes:

CREATE TABLE employees (
    id NUMBER PRIMARY KEY NOT NULL,
    name VARCHAR2(255) NOT NULL,
    organizationId NUMBER(10) NOT NULL,
    hiringDate DATE NOT NULL
);

CREATE SEQUENCE SQ_EMPLOYEES;

Vamos também preencher a tabela com alguns dados fictícios:

INSERT INTO employees (id, name, organizationId, hiringDate)
SELECT SQ_EMPLOYEES.NEXTVAL, 'Employer Name ' || L, L, TRUNC(SYSDATE) - L
FROM (
    SELECT (a.l - 1) * 1000 + b.l AS L FROM
    (SELECT level as l FROM dual CONNECT BY LEVEL <= 1000) a,
    (SELECT level as l FROM dual CONNECT BY LEVEL <= 1000) b
);

INSERT INTO employees (id, name, organizationId, hiringDate)
SELECT SQ_EMPLOYEES.NEXTVAL, 'Employer Name ' || L, 1, TRUNC(SYSDATE) - 10
FROM (
    SELECT (a.l - 1) * 1000 + b.l AS L FROM
    (SELECT level as l FROM dual CONNECT BY LEVEL <= 1000) a,
    (SELECT level as l FROM dual CONNECT BY LEVEL <= 1000) b
);

Vamos agora recuperar os empregados contratados 10 dias atrás:

SELECT *
FROM employees
WHERE hiringDate = TRUNC(SYSDATE) - 10;

Verificando o plano de execução:

Como podemos ver, está sendo feito um full table scan na tabela employees (OPTIONS igual a FULL). Além disso, é feito um “filter predicate” para verificar se cada linha da tabela satisfaz a condição da data de contratação.

Para resolver esse problema vamos criar o seguinte índice:

CREATE INDEX EMPLOYEES_IX01 ON employees(hiringDate);

Obtendo novamente o plano de execução:

Podemos ver agora que o índice foi utilizado corretamente (Access Predicates) e que não temos nenhuma condição que é feita como Filter Predicate.

Filter Predicate no Índice

Vamos agora recuperar os empregados contratados 10 dias atrás que estão na organização 1:

SELECT *
FROM employees
WHERE hiringDate = TRUNC(SYSDATE) - 10
AND organizationId = 1;

Dessa vez continuamos utilizando o índice criado, mas agora apareceu a informação de filter predicate. Isso acontece porque temos que filtrar os registros para verificar se a organizationId é igual a 1.

Antes de resolver essa query vou mostrar um outro erro que é comum. Vamos criar o índice da seguinte maneira:

DROP INDEX EMPLOYEES_IX01;
CREATE INDEX EMPLOYEES_IX01 ON employees(hiringDate, name, organizationId);

Vamos verificar o plano de execução novamente:

Como podemos ver ainda aparece a condição de Filter Predicate. Nesse caso o índice não pode ser utilizado para a filtragem da organizationId pois existe uma coluna intermediária no índice. O banco de dados faz a filtragem sempre utilizando as colunas informadas na criação do índice da esquerda para a direita, sem pular nenhuma das colunas.

Para corrigir a query é necessário criar o índice da seguinte maneira:

DROP INDEX EMPLOYEES_IX01;
CREATE INDEX EMPLOYEES_IX01 ON employees(hiringDate, organizationId);

Vamos verificar o plano de execução novamente:

Nesse caso o plano de execução nos mostra que o índice está sendo utilizado da maneira correta (somente Access Predicate, sem Filter Predicate).

Vamos agora recuperar os empregados da organização 1 que foram contratados nos últimos 2 dias:

SELECT *
FROM employees
WHERE hiringDate >= TRUNC(SYSDATE) - 2
AND organizationId = 1;

Consultando o plano de execução:

Como podemos ver, o banco está fazendo o Filter Predicate na organizationId. Esse caso em específico acontece porque trocamos a filtragem por igual por uma busca que retorna um intervalo (RANGE). Isso acontece quando fazemos a filtragem por <, >, <=, >= e BETWEEN. Para resolver esse problema é necessário que o índice comece primeiramente pelo que iremos filtrar por “=”, e após qualquer filtragem por RANGE.

Vamos criar o índice da seguinte maneira:

DROP INDEX EMPLOYEES_IX01;
CREATE INDEX EMPLOYEES_IX01 ON employees(organizationId, hiringDate);

Rodando novamente a query:

Como podemos ver agora não é feito nenhum Filter Predicate.

Nem todos os filter predicates são ruins, mas eles podem acabar virando um problema caso a quantidade de registros da tabela em questão cresça muito conforme o tempo. Para fazer uma análise correta é necessário verificar quantos registros serão retornados no Access Predicate para saber quantos registros serão filtrados no Filter Predicate. Se essa quantidade de registros for pequena e a chance de crescimento deles seja muito baixa, podemos deixar o índice como está, mas lembrando que o ideal (e o mais aconselhável) é evitar ao máximo o uso de Filter Predicate.

Para exemplificar o cálculo mencionado acima, vamos recriar o índice conforme abaixo:

DROP INDEX EMPLOYEES_IX01;
CREATE INDEX EMPLOYEES_IX01 ON employees(organizationId);

Vamos agora rodar a seguinte query:

SELECT *
FROM employees
WHERE hiringDate >= TRUNC(SYSDATE) - 2
AND organizationId = 10;

Cujo plano de execução é esse:

Para fazer a análise de quantos registros serão verificados na condição do filter predicate, é só fazermos a seguinte query:

SELECT MIN(qty), AVG(qty), MAX(qty)
FROM (
    SELECT organizationId, count(1) as qty
    FROM employees
    GROUP BY organizationId
);

No caso é necessário contar quantos registros tem no mínimo, média e máximo pelas condições do Access Predicate (nesse caso somente o organizationId). No caso da nossa massa de testes:

O que podemos ver é que na média apenas 2 registros irão passar no filter predicate. A média é baixa, porém o máximo é de 1 milhão de registros. No caso do organizationId 1, o filter predicate será executado 1 milhão de vezes, por isso o melhor seria evitar esse filter predicate e criar o índice da maneira mais adequada para essa query.

Filter Predicate vs Range Scan

Para explicar o porquê da ordem das colunas na criação do índice faz diferença no caso de busca por range, vamos verificar como funciona o índice internamente. Basicamente, ele é uma B-Tree que contém a referência pro registro.

Vamos começar com o índice por hiringDate e organizationId:

Os nós representam as tuplas com os dados hiringDate e organizationId. HiringDate está no formato de data YYYY-MM-DD.

Para buscar algum valor, basta começarmos do nó raiz, se o valor for menor que ele ir para a esquerda, senão ir para a direita. Continuamos fazendo isso até encontrarmos o valor.

Exemplificando: para fazer a busca por hiringDate = 2020-01-01 e organizationId = 5, ou seja, a tupla (2020-01-01, 5), vamos no nó raiz (2021-01-01, 5), descemos pra esquerda (2020-01-01, 1), depois para a direita (2020-01-01-10), e agora para a esquerda chegando no nó (2020-01-01, 5).

Agora quando a consulta é por organizationId = 5 AND hiringDate >= 2020-01-01 AND hiringdate <= 2021-03-01, primeiramente vamos buscar a tupla (2020-01-01, 5) na árvore (isso foi feito no exemplo acima). Agora devemos buscar a tupla (2021-03-01, 5). Começamos na raiz (2021-01-01, 5), vamos para a direita (2021-03-01, 10), esquerda (2021-03-01, 1) e direita encontrando a tupla (2021-03-01, 5). No caso do range scan, o banco deveria retornar todas as tuplas que estão entre as tuplas encontradas:

hiringDateorganizationId
2020-01-015
2020-01-0110
2021-01-011
2021-01-015
2021-01-0110
2021-03-011
2021-03-015

Isso é feito através da busca em profundidade entre os dois nós encontrados anteriormente. O problema é que o organizationId precisa ser filtrado para cada registro encontrado na busca, por isso ocorre o filter predicate. Nesse caso, ele irá filtrar os 7 registros acima para encontrar apenas os 3 seguintes:

hiringDateorganizationId
2020-01-015
2021-01-015
2021-03-015

Agora se trocarmos a ordem das colunas no índice a árvore fica dessa maneira:

Nesse caso para a consulta organizationId = 5 AND hiringDate >= 2020-01-01 AND hiringdate <= 2021-03-01, vamos começar procurando a tupla (5, 2020-01-01). Começando pela raiz (5, 2021-01-01), esquerda (1, 2021-03-01), direita (5, 2019-01-01) e finalmente direita (5, 2020-01-01). Agora devemos buscar a tupla (5, 2021-03-01), começando pela raiz (5, 2021-01-01), direita (10, 2020-01-01), esquerda (5, 2021-06-01) e finalmente esquerda em (5, 2021-03-01). No caso do range scan, o banco de dados irá retornar todas as tuplas entre essas duas. Nesse caso ele retornaria os seguintes registros:

hiringDateorganizationId
2020-01-015
2021-01-015
2021-03-015

Isso é feito através da busca em profundidade entre os dois nós encontrados anteriormente. Como podemos ver, os registros já são os corretos e não precisamos fazer o filter predicate.

Exemplo real

Um sistema em produção tinha uma query que caia exatamente no caso de filter predicate com range scan. O índice começava por uma data, onde a filtragem sempre era feita por >= e <=, e depois os campos de pesquisa por = da query. A query sempre procurava registros do dia atual e conforme o dia ia passando, iam entrando registros na data atual nessa tabela, até ter mais de milhões de linhas por dia.

Antes de recriar o índice da maneira correta, o tempo da query ia de alguns milissegundos até por volta de 350 ms. Olhando gráficos a partir do banco de dados, sempre haviam 6 ou mais sessões no banco utilizando CPU.

Observação: tinham três queries com o mesmo problema, primeiro foi aplicado em apenas uma delas (linha vermelha).

Após a aplicação do índice com a ordem correta das colunas, os dois gráficos ficaram da seguinte maneira:

Como podemos ver, a query que o índice foi corrigido (linha vermelha) melhorou significativamente. O tempo de query se tornou constante em alguns milissegundos. Já o número de sessões no banco de dados utilizando CPU caiu para aproximadamente 4.

Isso quer dizer que com a troca do índice para o correto, tivemos uma queda de mais de 90% no tempo de resposta da query e menos 33% de sessões utilizando CPU no banco de dados.

Conclusões

Todas as queries devem ter o seu plano de execução analisado antes de ir para produção. 

A ordem das colunas na criação dos índices faz uma enorme diferença principalmente no caso em que a query que irá utilizar o índice faz uma busca por range. Nesse caso, no momento de criação dos índices as colunas que serão filtradas por “=” devem vir primeiro e logo após as colunas que serão filtradas por intervalo (<, >, <=, >=, between).

Isso pode ser visto em uma das referências onde está escrito:

Rule of thumb: index for equality first—then for ranges.

Traduzindo:

Regra: faça a indexação por igualdade primeiro, depois pelo que será buscado através de intervalos.

Em uma das referências, há um trecho muito interessante:

Index filter predicates give a false sense of safety; even though an index is used, the performance degrades rapidly on a growing data volume or system load.

Traduzindo:

Filter predicates dá uma falsa sensação de segurança; apesar de um índice ser utilizado, a performance se degrada rapidamente conforme a quantidade de registros vão crescendo ou a carga do sistema aumenta.

O que esse parágrafo me faz pensar é que o filter predicate pode se tornar uma bomba relógio conforme o sistema passa mais tempo em produção. Com o tempo mais registros são criados na tabela e mais registros são verificados no filter predicate, causando um aumento do uso de CPU do banco de dados.

Referências

https://use-the-index-luke.com/sql/explain-plan/oracle/filter-predicates

https://use-the-index-luke.com/sql/where-clause/searching-for-ranges/greater-less-between-tuning-sql-access-filter-predicates

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.