В первой части серии статей про работу с адресами по КЛАДР мы научились импортировать данные этого справочника к себе в базу и превращать их во что-то более удобное для дальнейшей работы.
Сегодня же займемся реализацией конкретных прикладных алгоритмов на этой структуре и рассмотрим, как можно реализовать мгновенную помощь пользователю при вводе адреса, используя возможности префиксного поиска в PostgreSQL.
А какая помощь будет наиболее полезной с точки зрения пользователя?
-
понятная — пользователь сразу должен увидеть, что подсказанное нами — именно то, что он хочет написать
-
подходящая — при прочих равных, с большей вероятностью пользователи будут выбирать адреса из более значимых адресных объектов (райцентр, а не деревню / столицу региона, а не поселок) — их там просто статистически больше
-
быстрая — должна требовать минимум данных от пользователя, при этом давать нужный результат практически мгновенно
Мы хотим помочь пользователю быстрее и проще ввести свой адрес — и при этом получить его уже сразу «по КЛАДР», чтобы не пришлось дополнительно разбирать.
Иерархия объектов КЛАДР
А адрес вводится всегда «вложенно» — то есть на каждом следующем шаге нам необходимо искать только объекты с зафиксированным на предыдущем шаге префиксом:
-
76 - Ярославская обл. -
76 000 001 - г.Ярославль -
76 000 001 000 0492 - Московский пр-т
В худшем (для нас) случае пользователь может начать вводить сразу «с улицы», но и в этом варианте мы можем его привязать к населенному пункту по GeoIP.
Помимо этого, с точки зрения «бытового» приоритета, населенные пункты могут принадлежать к одной из трех категорий (поле kladr.lvl в структуре нашей БД):
-
lvl = 1— центр района -
lvl = 2— центр региона -
lvl = 3— центр региона и района одновременно
Формирование адреса объекта
Чтобы дать пользователю понять, что мы ему подсказываем ровно то, что он хочет, мы должны показать ему нормальный адрес того объекта (города, поселка или улицы), который он видит.
При этом часть участвующих в «иерархии» объектов может в результирующую строку не выводиться — например, для объекта 76 000 001 = г.Ярославль незачем выводить 76 = Ярославская обл., поскольку он и так является региональным центром (lvl = 3), а вот для 76 015 001 = Ярославская обл., г.Рыбинск такое указание является необходимым — зато без указания 76 015 = Рыбинский р-н, поскольку это райцентр (lvl = 1).
Давайте напишем функцию, которая по коду объекта вернет его актуальный адрес:
CREATE OR REPLACE FUNCTION code2addr(code varchar) RETURNS text AS $$ -- определяем все возможные коды "надобъектов" КЛАДРа WITH T AS( SELECT ARRAY[ substr(code, 1, 15) -- улица , substr(code, 1, 11) -- поселок/деревня , substr(code, 1, 8) -- город , substr(code, 1, 5) -- район , substr(code, 1, 2) -- регион ] FROM (VALUES($1)) T(code) ) -- находим актуальные объекты по субкодам , obj AS ( SELECT * , length(code) lnc -- максимальный "уровень" объекта среди найденных , max(lvl) -- убираем "улицы" FILTER(WHERE length(code) < 15) -- заполняем одним значением по всем строкам OVER(ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) np FROM ( SELECT DISTINCT ON(code) * FROM kladr WHERE code = ANY((TABLE T)::varchar[]) -- индексный поиск по массиву ключей ORDER BY code, status = '00' DESC -- приоритет у статуса 00 ) T ) SELECT -- собираем все нормализованные названия через запятую string_agg( norm , ', ' ) FILTER( -- убираем невыводимые объекты из результирующей строки WHERE (np, lnc) NOT IN ( (1, 5) -- райцентр -> район , (2, 2) -- регцентр -> регион , (2, 5) -- регцентр -> район , (3, 2) -- allцентр -> регион , (3, 5) -- allцентр -> район ) ) FROM obj WHERE norm IS NOT NULL $$ LANGUAGE sql; -- SELECT code2addr('760000010000492'); -- -> 'г.Ярославль, Московский пр-т'«Двумерный» LIKE-поиск
Теперь давайте вернемся к основной задаче — допустим, на предыдущем шаге ввода пользователь выбрал объект с кодом 76000001 (г.Ярославль) и дальше продолжает вводить "Мос".
Мы знаем, что это префикс названия искомого объекта, а код — это префикс кода того же объекта, поэтому примитивная реализация поиска подходящих записей будет выглядеть примерно вот так:
SELECT * FROM kladr WHERE code LIKE '76000001%' AND name LIKE 'Мос%' AND length(code) = 15; -- ищем только улицыИ… все будет работать не слишком весело, вплоть до полного сканирования таблицы (Seq Scan on kladr) из-за «двумерно-упорядоченного» префиксного поиска, о проблемах которого я рассказывал в статье «SQL HowTo: префиксный FTS-поиск с релевантностью по дате».
Даже если мы возьмем префиксный специндекс по коду из прошлой части kladr(code varchar_pattern_ops) WHERE length(code) = 15, он поможет нам не слишком сильно:
Index Scan using "kladr-15" on kladr (actual time=0.071..0.854 rows=10 loops=1) Index Cond: (((code)::text ~>=~ '76000001'::text) AND ((code)::text ~<~ '76000002'::text)) Filter: (((code)::text ~~ '76000001%'::text) AND ((name)::text ~~ 'Мос%'::text)) Rows Removed by Filter: 1625 Buffers: shared hit=984 Planning Time: 0.347 ms Execution Time: 0.878 msК тому же он не позволит нам найти названия вроде «Малый Московский«, где искомый префикс стоит не в первом слове.
Двойной varchar_pattern_ops
Но способ есть — ведь мы уже вычленили все ключевые слова из названия объекта, привели их к одному нижнему регистру и положили в kladr_kw! А там и подходящий индекс:
CREATE INDEX "kladr-kw-kwcd-15" ON kladr_kw( keyword varchar_pattern_ops , code varchar_pattern_ops ) WHERE length(code) = 15;Вот только «двойной LIKE» полностью на него все равно не садится — вместо него подхватывается другой, с префиксом только по keyword:
SELECT * FROM kladr_kw WHERE code LIKE '76000001%' AND keyword LIKE 'мос%' AND length(code) = 15;Index Scan using "kladr-kw-15" on kladr_kw (actual time=3.168..6.487 rows=17 loops=1) Index Cond: (((keyword)::text ~>=~ 'мос'::text) AND ((keyword)::text ~<~ 'мот'::text)) Filter: (((code)::text ~~ '76000001%'::text) AND ((keyword)::text ~~ 'мос%'::text)) Rows Removed by Filter: 7072 Buffers: shared hit=5661 Planning Time: 0.547 ms Execution Time: 6.507 msМожно ли посадить наш запрос на более подходящий индекс? Да, мы уже применяли такой вариант в «PostgreSQL Antipatterns: сказ об итеративной доработке поиска по названию, или «Оптимизация туда и обратно»» — это «разворачивание» LIKE вручную:
SELECT * FROM kladr_kw WHERE code ~>=~ '76000001' AND code ~<~ '76000002' AND -- code LIKE '76000001%' keyword ~>=~ 'мос' AND keyword ~<~ 'мот' AND -- keyword LIKE 'мос%' length(code) = 15;Index Scan using "kladr-kw-kwcd-15" on kladr_kw (actual time=0.464..0.879 rows=17 loops=1) Index Cond: (((keyword)::text ~>=~ 'мос'::text) AND ((keyword)::text ~<~ 'мот'::text) AND ((code)::text ~>=~ '76000001'::text) AND ((code)::text ~<~ '76000002'::text)) Buffers: shared hit=92 Planning Time: 0.333 ms Execution Time: 0.896 msПравая граница LIKE
Но чтобы иметь возможность применить эту технику, нам необходимо научиться формировать условие для оператора ~<~ и превращать '76000001' в '76000002', а 'мос' в 'мот':
SELECT * FROM (VALUES('76000001', 'мос')) T(code, keyword) , LATERAL ( SELECT code codeB , CASE WHEN kw = '' THEN NULL ELSE substr(kw.kw, 1, length(kw.kw) - 1) || chr(ascii(substr(kw.kw, length(kw.kw))) + 1) END codeE FROM regexp_replace(T.code, E'я*$', E'') kw -- убрали все 'я' на конце ) Lc , LATERAL ( SELECT keyword keywordB , CASE WHEN kw = '' THEN NULL ELSE substr(kw.kw, 1, length(kw.kw) - 1) || chr(ascii(substr(kw.kw, length(kw.kw))) + 1) END keywordE FROM regexp_replace(T.keyword, E'я*$', E'') kw ) Lk;Заметим, что если значение заканчивается на 'я', то мы их просто убираем: 'мося' -> 'мос' -> 'мот'. А если состоит из одних только букв 'я', то «невключающей» правой границы нет, и мы получаем NULL, и этот кейс нам придется поддержать отдельно.
One Query to Get Them All
Итак, нам понадобилось меньше 1ms и прочитать всего 92 страницы данных, чтобы найти все 17 подходящих записей об улицах с таким префиксом. Но ведь у нас есть и другие варианты — когда внутри города сначала находится поселок, и пользователь может искать именно его.
Придется собирать универсальный запрос, который сможет принимать 4 аргумента:
-- $1 - prefix code ::varchar -- $2 - prefix keyword ::varchar -- $3 - lengths ::smallint[] -- $4 - limit ::integerЗамечу, что искать регионы вообще незачем — гораздо проще искать хотя бы с населенных пунктов, но с каких именно?
Города-миллионники
Начнем с самого простого варианта: пользователь вообще еще ничего не набрал — что лучше всего ему показать? То, что с наибольшей вероятностью позволит ему найти ожидаемое в показанном списке. И в нашей стране это будут города-миллионники:
SELECT kl.* , code2addr(kl.code) addr -- собираем полный адрес объекта FROM unnest(ARRAY[ '77' -- Москва , '78' -- Санкт-Петербург , '54000001' -- Новосибирск , '66000001' -- Екатеринбург , '52000001' -- Нижний Новгород , '63000001' -- Самара , '55000001' -- Омск , '16000001' -- Казань , '74000001' -- Челябинск , '61000001' -- Ростов-на-Дону , '02000001' -- Уфа , '34000001' -- Волгоград , '59000001' -- Пермь ]) WITH ORDINALITY T(code, rn) -- сохраним порядок для последующей сортировки NATURAL JOIN -- USING(code) kladr kl WHERE ($1, $2) IS NOT DISTINCT FROM ('', '') AND -- работает только при "пусто-пусто" kl.status = '00' -- только актуальные записи ORDER BY T.rn;Здесь мы применили методику ветвления алгоритма запроса в зависимости от условия:
( SELECT ... -- branch #A WHERE cond ) UNION ALL ( SELECT ... -- branch #B WHERE NOT cond )В плане такого запроса будут присутствовать обе ветви, но фактически одна из них не будет исполняться будет помечена как (never executed).
Копипаста? Да! Иногда…
Еще и месяца не прошло, с момента публикации «PostgreSQL Antipatterns: «слишком много золота»», где я подробно разбирал вред от автогенерируемых запросов и повторяющихся блоков в них. Но иногда предгенерация запроса с конкретными значениями — наиболее эффективный способ «посадить» его на наиболее подходящий индекс, избежав при этом лишней работы для СУБД.
Добавим щепотку из «PostgreSQL Antipatterns: убираем медленные и ненужные сортировки» — и сможем получить наиболее релевантные объекты без использования ORDER BY:
-- отбираем объекты с кодом длины 2, если они нужны SELECT ... WHERE 2 = ANY(lns) AND length(code) = 2 -- садимся на конкретный индекс UNION ALL SELECT ... WHERE 5 = ANY(lns) AND length(code) = 5 UNION ALL SELECT ... WHERE 8 = ANY(lns) AND length(code) = 8 UNION ALL SELECT ... WHERE 11 = ANY(lns) AND length(code) = 11 UNION ALL SELECT ... WHERE 15 = ANY(lns) AND length(code) = 15 LIMIT $4Напомню, что вместо одного индекса (length(code), keyword, code) мы создали 5 специндексов в соответствии со всеми возможными значениями length(code), каждый из которых, в результате, имеет меньший размер:
(keyword, code) WHERE length(code) = 2 (keyword, code) WHERE length(code) = 5 (keyword, code) WHERE length(code) = 8 (keyword, code) WHERE length(code) = 11 (keyword, code) WHERE length(code) = 15Теперь вспомним про ветвление, когда codeE или keywordE могут превратиться в NULL, и получаем, что блок поиска улиц (length(code) = 15) будет состоять аж из 4 сегментов, отрабатывать из которых, правда, будет не более одного:
SELECT ... FROM kladr_kw WHERE -- надо искать улицы 15 = ANY(lns) AND -- садимся на индекс по улицам length(code) = 15 AND -- код искомого объекта должен быть больше префикса length(code) > length(codeB) AND -- только актуальные объекты status = '00' AND -- вариант NN codeE IS NULL AND code ~>=~ codeB AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL ... -- вариант N+ codeE IS NULL AND code ~>=~ codeB AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL ... -- вариант +N codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL ... -- вариант ++ codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordEГорода-регионы
Единственным отличием от общей схемы является кейс для length(code) = 2. Как я написал выше, регионы искать незачем, но есть такие города, которые «сами себе регионы» — это города федерального значения. В настоящий момент их 4:
77 - Москва 78 - Санкт-Петербург 92 - Севастополь 99 - БайконурВ этом случае к каждому варианту подзапроса поиска по регионам мы просто добавим условие code IN ('77', '78', '92', '99').
Финальная сборка
Оформим теперь это все в единую SQL-функцию:
kladr_by_prefix
-- $1 - prefix code ::varchar -- $2 - prefix keyword ::varchar -- $3 - lengths ::smallint[] -- $4 - limit ::integer CREATE OR REPLACE FUNCTION kladr_by_prefix(code varchar, keyword varchar, lns smallint[], lim integer) RETURNS SETOF kladr AS $$ ( SELECT kl.* FROM unnest(ARRAY[ '77' -- Москва , '78' -- Санкт-Петербург , '54000001' -- Новосибирск , '66000001' -- Екатеринбург , '52000001' -- Нижний Новгород , '63000001' -- Самара , '55000001' -- Омск , '16000001' -- Казань , '74000001' -- Челябинск , '61000001' -- Ростов-на-Дону , '02000001' -- Уфа , '34000001' -- Волгоград , '59000001' -- Пермь ]) WITH ORDINALITY T(code, rn) -- сохраним порядок для последующей сортировки NATURAL JOIN -- USING(code) kladr kl WHERE ($1, $2) IS NOT DISTINCT FROM ('', '') AND -- работает только при "пусто-пусто" kl.status = '00' -- только актуальные записи ORDER BY T.rn ) UNION ALL ( WITH src AS ( SELECT * FROM (VALUES($1::varchar, $2::varchar, $3::integer[])) T(code, keyword, lns) , LATERAL ( SELECT code codeB , CASE WHEN kw = '' THEN NULL ELSE substr(kw.kw, 1, length(kw.kw) - 1) || chr(ascii(substr(kw.kw, length(kw.kw))) + 1) END codeE FROM regexp_replace(T.code, E'я*$', E'') kw -- убрали все 'я' на конце ) Lc , LATERAL ( SELECT keyword keywordB , CASE WHEN kw = '' THEN NULL ELSE substr(kw.kw, 1, length(kw.kw) - 1) || chr(ascii(substr(kw.kw, length(kw.kw))) + 1) END keywordE FROM regexp_replace(T.keyword, E'я*$', E'') kw ) Lk ) , codes AS ( SELECT ARRAY( -- ln = 2 SELECT code FROM kladr_kw WHERE 2 = ANY(lns) AND length(code) = 2 AND length(code) > length(codeB) AND code IN ('77', '78', '92', '99') AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 2 = ANY(lns) AND length(code) = 2 AND length(code) > length(codeB) AND code IN ('77', '78', '92', '99') AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL SELECT code FROM kladr_kw WHERE 2 = ANY(lns) AND length(code) = 2 AND length(code) > length(codeB) AND code IN ('77', '78', '92', '99') AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 2 = ANY(lns) AND length(code) = 2 AND length(code) > length(codeB) AND code IN ('77', '78', '92', '99') AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL -- ln = 5 SELECT code FROM kladr_kw WHERE 5 = ANY(lns) AND length(code) = 5 AND length(code) > length(codeB) AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 5 = ANY(lns) AND length(code) = 5 AND length(code) > length(codeB) AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL SELECT code FROM kladr_kw WHERE 5 = ANY(lns) AND length(code) = 5 AND length(code) > length(codeB) AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 5 = ANY(lns) AND length(code) = 5 AND length(code) > length(codeB) AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL -- ln = 8 SELECT code FROM kladr_kw WHERE 8 = ANY(lns) AND length(code) = 8 AND length(code) > length(codeB) AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 8 = ANY(lns) AND length(code) = 8 AND length(code) > length(codeB) AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL SELECT code FROM kladr_kw WHERE 8 = ANY(lns) AND length(code) = 8 AND length(code) > length(codeB) AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 8 = ANY(lns) AND length(code) = 8 AND length(code) > length(codeB) AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL -- ln = 11 SELECT code FROM kladr_kw WHERE 11 = ANY(lns) AND length(code) = 11 AND length(code) > length(codeB) AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 11 = ANY(lns) AND length(code) = 11 AND length(code) > length(codeB) AND status = '00' AND codeE IS NULL AND code ~>=~ codeB AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL SELECT code FROM kladr_kw WHERE 11 = ANY(lns) AND length(code) = 11 AND length(code) > length(codeB) AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 11 = ANY(lns) AND length(code) = 11 AND length(code) > length(codeB) AND status = '00' AND codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL -- ln = 15 SELECT code FROM kladr_kw WHERE -- надо искать улицы 15 = ANY(lns) AND -- садимся на индекс по улицам length(code) = 15 AND -- код искомого объекта должен быть больше префикса length(code) > length(codeB) AND -- только актуальные объекты status = '00' AND -- вариант NN codeE IS NULL AND code ~>=~ codeB AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 15 = ANY(lns) AND length(code) = 15 AND length(code) > length(codeB) AND status = '00' AND -- вариант N+ codeE IS NULL AND code ~>=~ codeB AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE UNION ALL SELECT code FROM kladr_kw WHERE 15 = ANY(lns) AND length(code) = 15 AND length(code) > length(codeB) AND status = '00' AND -- вариант +N codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NULL AND keyword ~>=~ keywordB UNION ALL SELECT code FROM kladr_kw WHERE 15 = ANY(lns) AND length(code) = 15 AND length(code) > length(codeB) AND status = '00' AND -- вариант ++ codeE IS NOT NULL AND code ~>=~ codeB AND code ~<~ codeE AND keywordE IS NOT NULL AND keyword ~>=~ keywordB AND keyword ~<~ keywordE LIMIT $4 ) FROM src ) SELECT kl.* FROM kladr kl WHERE ($1, $2) IS DISTINCT FROM ('', '') AND kl.code = ANY((TABLE codes)::varchar[]) AND kl.status = '00' ORDER BY length(code) , lvl DESC NULLS LAST , lower(name) = $2::varchar DESC -- приоритет полному совпадению с введенным , lower(name) LIKE ($2::varchar || '%') DESC -- приоритет совпадению с началом , name ) $$ LANGUAGE sql;Проверим на наших данных:
SELECT * , code2addr(code) addr FROM kladr_by_prefix('76000001', 'мос', '{11,15}', 16);Примерно 341 buffers/15ms с использованием code2addr и 137 buffers/13ms без него.
Весьма неплохо для сложного поиска в справочнике на 2M позиций! И мы спокойно можем интегрировать вызов этого помощника хоть после ввода каждого следующего символа в поле ввода адреса.
ссылка на оригинал статьи https://habr.com/ru/articles/575704/
Добавить комментарий