Antipatróns de PostgreSQL: unha historia de refinamento iterativo da busca por nome ou "Optimización de ida e volta"

Milleiros de xestores das oficinas de vendas de todo o país rexistran noso sistema CRM decenas de miles de contactos diarios — feitos de comunicación con clientes potenciais ou existentes. E para iso, primeiro debes atopar un cliente, e preferiblemente moi rapidamente. E isto ocorre a maioría das veces polo nome.

Polo tanto, non é de estrañar que, unha vez máis analizando consultas "pesadas" nunha das bases de datos máis cargadas, a nosa propia Conta corporativa VLSI, atopei "na parte superior" solicitar unha busca "rápida" polo nome para tarxetas de organización.

Ademais, unha investigación máis adiante revelou un exemplo interesante primeiro optimización e despois degradación do rendemento petición co seu perfeccionamento secuencial por parte de varios equipos, cada un dos cales actuou unicamente coas mellores intencións.

0: que quería o usuario?

[KDPV por iso]

Que adoita dicir un usuario cando fala dunha busca "rápida" polo nome? Case nunca resulta ser unha busca "honesta" dunha subcadea como ... LIKE '%роза%' - porque entón o resultado inclúe non só 'Розалия' и 'Магазин Роза'Pero 'Гроза' e aínda 'Дом Деда Мороза'.

O usuario asume a nivel diario que lle proporcionará buscar por principio de palabra no título e facelo máis relevante comeza introducido. E farás case ao instante - para entrada interlineal.

1: limitar a tarefa

E aínda máis, unha persoa non entrará especificamente 'роз магаз', para que teñas que buscar cada palabra por prefixo. Non, é moito máis doado para un usuario responder a unha suxestión rápida para a última palabra que "subspecificar" a propósito as anteriores: mira como xestiona isto calquera motor de busca.

Xeralmente, correctamente formular os requisitos para o problema é máis da metade da solución. Ás veces, análise coidadosa dos casos de uso pode influír significativamente no resultado.

Que fai un desenvolvedor abstracto?

1.0: buscador externo

Oh, a procura é difícil, non quero facer nada, dámosllo aos devops! Deixa que despreguen un motor de busca externo á base de datos: Sphinx, ElasticSearch,...

Unha opción de traballo, aínda que é laboriosa en canto á sincronización e á velocidade dos cambios. Pero non no noso caso, xa que a busca realízase para cada cliente só no marco dos datos da súa conta. E os datos teñen unha variabilidade bastante alta - e se o xestor agora entrou na tarxeta 'Магазин Роза', despois de 5-10 segundos xa pode lembrar que se esqueceu de indicar alí o seu correo electrónico e quere atopalo e corrixilo.

Polo tanto - imos buscar "directamente na base de datos". Afortunadamente, PostgreSQL permítenos facelo, e non só unha opción: mirarémolos.

1.1: subcadea "honesta".

Aferrámonos á palabra "subcadea". Pero para a busca de índice por subcadea (e mesmo por expresións regulares!) hai unha excelente módulo pg_trgm! Só entón será necesario ordenar correctamente.

Tentemos tomar a seguinte placa para simplificar o modelo:

CREATE TABLE firms(
  id
    serial
      PRIMARY KEY
, name
    text
);

Cargamos alí 7.8 millóns de rexistros de organizacións reais e indexámolos:

CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

Busquemos os 10 primeiros rexistros para a busca interlineal:

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'роза')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
, lower(name) -- остальное по алфавиту
LIMIT 10;

[Mira explicar.tensor.ru]

Ben, iso é... 26 ms, 31 MB ler datos e máis de 1.7 mil rexistros filtrados - para 10 buscados. Os custos xerais son demasiado altos, non hai algo máis eficiente?

1.2: buscar por texto? É FTS!

De feito, PostgreSQL ofrece unha ferramenta moi potente buscador de texto completo (Busca de texto completo), incluída a posibilidade de prefixar a busca. Unha excelente opción, nin sequera precisa instalar extensións! Imos probar:

CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

SELECT
  *
FROM
  firms
WHERE
  to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC
, lower(name)
LIMIT 10;

[Mira explicar.tensor.ru]

Aquí a paralelización da execución de consultas axudounos un pouco, reducindo o tempo á metade 11 ms. E tivemos que ler 1.5 veces menos, en total 20MB. Pero aquí, canto menos, mellor, porque canto maior sexa o volume que lemos, maiores serán as posibilidades de que se perda a caché e cada páxina extra de datos lida do disco é un posible "freo" para a solicitude.

1.3: aínda GUSTA?

A petición anterior é boa para todos, pero só se a tiras cen mil veces ao día, chegará 2TB ler datos. No mellor dos casos, de memoria, pero se non tes sorte, entón de disco. Entón, imos tentar facelo máis pequeno.

Lembremos o que o usuario quere ver primeiro "que comeza por...". Polo tanto, isto está na súa forma máis pura busca de prefixos coa axuda text_pattern_ops! E só se "non temos suficientes" ata 10 rexistros que buscamos, entón teremos que rematar de lelos mediante a busca FTS:

CREATE INDEX ON firms(lower(name) text_pattern_ops);

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
LIMIT 10;

[Mira explicar.tensor.ru]

Excelente rendemento - total 0.05 ms e algo máis de 100 KB ler! Só nos esquecemos ordenar polo nomepara que o usuario non se perda nos resultados:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[Mira explicar.tensor.ru]

Ah, algo xa non é tan bonito, parece que hai un índice, pero a clasificación pasa voando... Por suposto, xa é moitas veces máis eficaz que a opción anterior, pero...

1.4: "acabar cun ficheiro"

Pero hai un índice que che permite buscar por rango e seguir usando a ordenación normalmente - btree regular!

CREATE INDEX ON firms(lower(name));

Só se terá que "recoller manualmente" a solicitude:

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'роза' AND
  lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[Mira explicar.tensor.ru]

Excelente: a clasificación funciona e o consumo de recursos segue sendo "microscópico". miles de veces máis eficaz que o FTS "puro".! Só queda reunilo nunha única solicitude:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'роза' AND
    lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
    lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
  ORDER BY
    lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Teña en conta que se executa a segunda subconsulta só se o primeiro volveu menos do esperado o último LIMIT número de liñas. Estou falando deste método de optimización de consultas xa escribiu antes.

Entón si, agora temos tanto btree como gin sobre a mesa, pero estatisticamente resulta que menos do 10% das solicitudes chegan á execución do segundo bloque. É dicir, con limitacións tan típicas coñecidas de antemán para a tarefa, puidemos reducir case mil veces o consumo total de recursos do servidor.

1.5*: podemos prescindir dun ficheiro

Arriba LIKE Impedíronnos utilizar unha clasificación incorrecta. Pero pódese "definir no camiño correcto" especificando o operador USING:

Por defecto asúmese ASC. Ademais, pode especificar o nome dun operador de ordenación específico nunha cláusula USING. O operador de ordenación debe ser membro do menor ou maior que dalgunha familia de operadores de árbore B. ASC normalmente equivalente USING < и DESC normalmente equivalente USING >.

No noso caso, "menos" é ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[Mira explicar.tensor.ru]

2: como as solicitudes se tornan amargas

Agora deixamos a nosa petición de "cocer a lume lento" durante seis meses ou un ano, e sorpréndenos ao atopala de novo "no cumio" con indicadores do "bombeo" diario total da memoria (hit compartido de buffers) en 5.5TB - é dicir, aínda máis do que era orixinalmente.

Non, claro, o noso negocio creceu e a nosa carga de traballo aumentou, pero non na mesma cantidade! Isto significa que aquí hai algo de pescado, imos descubrir.

2.1: o nacemento da paginación

Nalgún momento, outro equipo de desenvolvemento quixo facer posible "saltar" dunha busca rápida de subíndices ao rexistro cos mesmos, pero ampliados resultados. Que é un rexistro sen navegación por páxina? ¡Vámonos a carallo!

( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;

Agora era posible mostrar o rexistro de resultados de busca con carga "páxina por páxina" sen ningún tipo de estrés para o programador.

Por suposto, de feito, para cada páxina posterior de datos cada vez se le máis (todo da época anterior, que descartaremos, ademais da "cola") necesaria, é dicir, este é un antipatrón claro. Pero sería máis correcto iniciar a busca na seguinte iteración desde a clave almacenada na interface, pero sobre iso noutra vez.

2.2: Quero algo exótico

Nalgún momento quería o desarrollador diversificar a mostra resultante con datos doutra táboa, para a que se enviou toda a solicitude anterior ao CTE:

WITH q AS (
  ...
  LIMIT <N> + 10
)
SELECT
  *
, (SELECT ...) sub_query -- какой-то запрос к связанной таблице
FROM
  q
LIMIT 10 OFFSET <N>;

E aínda así, non está nada mal, xa que a subconsulta só se avalía para 10 rexistros devoltos, se non...

2.3: DISTINCT é sen sentido e sen piedade

Nalgún lugar do proceso de tal evolución a partir da 2a subconsulta perdeuse NOT LIKE condición. Está claro que despois disto UNION ALL comezou a volver algunhas entradas dúas veces - primeiro atopado ao principio da liña, e despois de novo - ao comezo da primeira palabra desta liña. No límite, todos os rexistros da segunda subconsulta poderían coincidir cos rexistros da primeira.

Que fai un programador en vez de buscar a causa?.. Sen dúbida!

• dobre o tamaño mostras orixinais
• aplicar DISTINCTpara obter só instancias únicas de cada liña

WITH q AS (
  ( ... LIMIT <2 * N> + 10)
  UNION ALL
  ( ... LIMIT <2 * N> + 10)
  LIMIT <2 * N> + 10
)
SELECT DISTINCT
  *
, (SELECT ...) sub_query
FROM
  q
LIMIT 10 OFFSET <N>;

É dicir, está claro que o resultado, ao final, é exactamente o mesmo, pero a posibilidade de "voar" na segunda subconsulta CTE foi moito maior, e aínda sen isto, claramente máis lexible.

Pero isto non é o máis triste. Xa que o desenvolvedor pediu seleccionar DISTINCT non para uns específicos, senón para todos os campos á vez rexistros, entón o campo sub_query (o resultado da subconsulta) incluíuse automaticamente alí. Agora, a executar DISTINCT, a base de datos xa tiña que executarse non 10 subconsultas, senón todas <2 * N> + 10!

2.4: cooperación ante todo!

Entón, os desenvolvedores viviron - non se molestaron, porque o usuario claramente non tiña a paciencia suficiente para "axustar" o rexistro a valores N significativos cunha desaceleración crónica na recepción de cada "páxina" posterior.

Ata que os desenvolvedores doutro departamento chegaron a eles e querían usar un método tan cómodo para a busca iterativa - é dicir, collemos unha peza dalgunha mostra, filtramos por condicións adicionais, debuxamos o resultado, despois a seguinte peza (que no noso caso conséguese aumentando N), e así sucesivamente ata que enchemos a pantalla.

En xeral, no exemplar capturado N alcanzou valores de case 17K, e en só un día executáronse polo menos 4K deste tipo de solicitudes "ao longo da cadea". Os últimos foron escaneados con audacia 1 GB de memoria por iteración...

En total

Fonte: www.habr.com