postgrespro
Поиск в btree не возвращает результаты для mvarchar/mchar
Тестовая схема + данные
Описание проблемы
В патче pg для работы с 1С наблюдается некорректное поведение при поиске в btree индексе поля типа mvarchar и mchar подстроки, содержащей букву "ё" (возможно, проблема более общая). На определенных наборах данных поиск в индексе не возвращает никаких результатов, хотя поиск по таблице успешно возвращает нужные строки (если скрыть индекс от планировщика тем же plantuner). При этом, если посмотреть индекс через pageinspect, то ключ, указывающий на искомую строку таблицы, в него успешно попадает (но не находится). Проблема проявляется на всех сборках postgresql с патчем 1С из репозитория postgres pro.
Воспроизведение бага
Инициализация базы
createdb pg1c
psql -f pg1c.sql.txt -1 pg1c
- Проверяем, что в индексе мы не можем найти 'Зё Г. В.' по подстроке, а в таблице - можем.
Ищем в индексе
explain analyze select * from t where val like 'зё%';
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Index Only Scan using t_idx on t (cost=0.42..8.44 rows=2268 width=29) (actual time=0.009..0.009 rows=0 loops=1)
Index Cond: ((val >= 'зё'::mvarchar COLLATE "default") AND (val < 'зє'::mvarchar COLLATE "default"))
Filter: (val ~~ 'зё%'::mvarchar)
Heap Fetches: 0
Planning time: 1.251 ms
Execution time: 0.028 ms
(6 строк)
select * from t where val like 'зё%';
val
-----
(0 строк)
Ищем в таблице
load 'plantuner';
set plantuner.disable_index = 't_idx';
explain analyze select * from t where val like 'зё%';
QUERY PLAN
----------------------------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..9072.00 rows=2268 width=29) (actual time=69.260..70.382 rows=2 loops=1)
Filter: (val ~~ 'зё%'::mvarchar)
Rows Removed by Filter: 453519
Planning time: 0.241 ms
Execution time: 70.397 ms
(5 строк)
select * from t where val like 'зё%';
val
------------
Зёма Л. Ф.
Зё Г. В.
(2 строки)
Проверим, что проблема не в like, но сохраняется и для поиска подстроки по диапазону (так переписывается план запроса вида "like" в индексе)
Ищем в индексе
explain analyze select * from t where (val >= 'зё'::mvarchar) AND (val < 'зє'::mvarchar);
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Index Only Scan using t_idx on t (cost=0.42..8.44 rows=1 width=29) (actual time=0.049..0.049 rows=0 loops=1)
Index Cond: ((val >= 'зё'::mvarchar) AND (val < 'зє'::mvarchar))
Heap Fetches: 0
Planning time: 0.170 ms
Execution time: 0.068 ms
(5 строк)
select * from t where (val >= 'зё'::mvarchar) AND (val < 'зє'::mvarchar);
val
-----
(0 строк)
Ищем в таблице
load 'plantuner';
set plantuner.disable_index = 't_idx';
explain analyze select * from t where (val >= 'зё'::mvarchar) AND (val < 'зє'::mvarchar);
QUERY PLAN
--------------------------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..10205.80 rows=1 width=29) (actual time=95.307..96.933 rows=2 loops=1)
Filter: ((val >= 'зё'::mvarchar) AND (val < 'зє'::mvarchar))
Rows Removed by Filter: 453519
Planning time: 0.084 ms
Execution time: 96.948 ms
(5 строк)
select * from t where (val >= 'зё'::mvarchar) AND (val < 'зє'::mvarchar);
val
------------
Зёма Л. Ф.
Зё Г. В.
(2 строки)
- Проверим, что "Зё Г. В." содержится в индексе и в таблице (и бинарные данные там одинаковые)
create extension pageinspect;
select g.g as page, i.* from generate_series(1,2823) as g, lateral bt_page_items('t_idx', g.g) as i
where regexp_replace(data,' ','','g') like '%'||right(mvarchar_send('Зё Г. В.')::text, -2)||'%';
page | itemoffset | ctid | itemlen | nulls | vars | data
------+------------+-----------+---------+-------+------+-------------------------------------------------------------------------
822 | 115 | (3402,13) | 32 | f | t | 23 17 04 51 04 20 00 13 04 2e 00 20 00 12 04 2e 00 00 00 00 00 00 00 00
(1 строка)
select * from heap_page_items(get_raw_page('t', 3402)) where lp = 13;
lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid | t_data
----+--------+----------+--------+--------+--------+----------+-----------+-------------+------------+--------+--------+-------+--------------------------------------
13 | 7504 | 1 | 41 | 1018 | 0 | 463 | (3402,13) | 1 | 2306 | 24 | | | \x2317045104200013042e00200012042e00
(1 строка)
Итого
- В кортежах индекса и таблицы для "Зё Г. В." лежат одинаковые бинарные данные типа mvarchar.
- На одинаковом наборе операторов класса mvarchar поиск из таблицы возвращает верные значения, а из индекса - нет.
- Проблема воспроизводится не на всех наборах данных.
- Проблема имеет место для mvarchar и mchar.
- Листовые страницы индекса имеют предка root и не висят в воздухе (должны находиться)
Версии
Ключ попадает не на ту страницу индекса
- проблема в опорной функции
- не корректно сравнивается значение искомого ключа с наибольшим значением в странице
Спасибо за подробный отчёт. Какая используется версия ОС, локаль, версия icu?
Проверялось на двух вариантах
- Debian (виртуалка)
- Debian GNU/Linux 8.5 (jessie)
- PostgreSQL 9.4.5 on x86_64-unknown-linux-gnu, compiled by gcc (Debian 4.9.2-10) 4.9.2, 64-bit
- ICU 52.1
- Ubuntu (контейнер Docker ubuntu:latest)
- Ubuntu 16.04.4 LTS (xenial)
- PostgreSQL 9.6.6 on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 5.4.0-6ubuntu1~16.04.2) 5.4.0 20160609, 64-bit
- ICU 55.1
Да, использовал с вашего сайта postgres поддержкой 1с (https://postgrespro.ru/products/1c_build)
Проверил порядок сортировки для индекса и таблицы.
SET enable_seqscan = off;
SELECT val FROM t ORDER BY val;
SET enable_seqscan = on;
SET enable_indexscan = off;
SET enable_indexonlyscan = off;
SELECT val FROM t ORDER BY val;
Результаты идентичные на тестовых данных.
Так как вопрос не в сортировке, я решил посмотреть, какие данные в текстовом виде содержатся в проблемной странице индекса, куда попадает "Зё Г. В.".
create table page (itemoffset integer, val mvarchar, data_idx text, data_heap text);
with bt_tuple as (
select g.g as page, i.* from generate_series(1,2823) as g, lateral bt_page_items('t_idx', g.g) as i
where regexp_replace(data,' ','','g') like '%'||right(mvarchar_send('Зё Г. В.')::text, -2)||'%'
),
bt_page as (
select itemoffset, regexp_replace(data,' ','','g')::text as data from bt_page_items('t_idx', (select page from bt_tuple))
)
insert into page(itemoffset, val, data_idx, data_heap)
select distinct i.itemoffset, h.val, i.data as data_idx, h.data as data_heap from bt_page as i
left join (select val, right(mvarchar_send(val)::text, -2) as data from t) as h
on trim(trailing '0' from right(i.data, -2)) = trim(trailing '0' from h.data)
order by i.itemoffset;
Вывод результатов в файле page.txt. Расшифровка колонок: 1 - смещение в странице индекса 2 - ключ индекса, сериализованный в mvarchar 3 - bytea представление ключа в индексе 4 - bytea представление строки (тот же ключ) в таблице.
Максимальное значение на странице индекса должно находиться по смещению 1. В данном случае, это "ЗЕЙЛЕР Е. В.". Проверим функции сравнения класса оператора mvarchar этого наибольшего значения на странице с попавшим туда ключом "Зё Г. В." (вообще уже странно, ведь "ё" идет после "е").
pg1c=# select mvarchar_icase_lt('Зё Г. В.','ЗЕЙЛЕР Е. В.');
mvarchar_icase_lt
-------------------
t
(1 строка)
pg1c=# select mvarchar_icase_ge('Зё Г. В.','зё');
mvarchar_icase_ge
-------------------
t
(1 строка)
pg1c=# select mvarchar_icase_ge('ЗЕЙЛЕР Е. В.','зё');
mvarchar_icase_ge
-------------------
f
(1 строка)
pg1c=# select mvarchar_icase_lt('ЗЕЙЛЕР Е. В.','зё');
mvarchar_icase_lt
-------------------
t
(1 строка)
pg1c=# select mvarchar_icase_gt('зё','ЗЕЙЛЕР Е. В.');
mvarchar_icase_gt
-------------------
t
(1 строка)
Выходит полная ерунда, так как у функций сравнения отсутствует транзитивность
Выходит, выстрелило не в значении "Зё Г. В.", а в наибольшем ключе на странице "ЗЕЙЛЕР Е. В." на котором ломаются функции сравнения. Этим и объясняется разница в поиске по таблице и индексу. В таблице идет полный перебор, и хоть наибольший ключ не проходит проверку (а "Зё Г. В." проходит) и мы получаем нужного нам "Зё Г. В.". А в индексе поиск не заходит в страницу, где лежит "Зё Г. В.", так как наибольший ключ не проходит проверку на условие сравнения
Вот суть проблемы, если отбросить все ненужное
pg1c=# select 'ё'::mvarchar < 'е'::mvarchar;
?column?
----------
f
(1 строка)
pg1c=# select 'ёа'::mvarchar < 'еа'::mvarchar;
?column?
----------
f
(1 строка)
pg1c=# select 'ёа'::mvarchar < 'еб'::mvarchar;
?column?
----------
t
(1 строка)
Все функции сравнения для case insensitive mvarchar/mchar под капотом используют
int
UCharCaseCompare(UChar * a, int alen, UChar *b, int blen) {
int len = Min(alen, blen);
int res;
createUObjs();
res = (int)ucol_strcoll( colCaseInsensitive,
a, len,
b, len);
if ( res == 0 && alen != blen )
return (alen > blen) ? 1 : - 1;
return res;
}
Могу ошибаться, но мне кажется, корни проблемы лежат в настройках сортировки colCaseInsensitive. Если посмотреть ее настройки из функции static void createUObjs(), то у нее стоит уровень Secondary
ucol_setStrength( colCaseInsensitive, UCOL_SECONDARY );
В документации описано поведение данного уровня, которое до боли похоже на нашу проблему
Secondary Level: Accents in the characters are considered secondary differences (for example, "as" < "às" < "at"). Other differences between letters can also be considered secondary differences, depending on the language. A secondary difference is ignored when there is a primary difference anywhere in the strings. This is also called the level-2 strength. Note: In some languages (such as Danish), certain accented letters are considered to be separate base characters. In most languages, however, an accented letter only has a secondary difference from the unaccented version of that letter.
По факту вместо "as" < "às" < "at" мы имеем "еа" < "ёа" < "еб".
Я проверил как сортируются "зё", "Зё Г. В." и "ЗЕЙЛЕР Е. В." в C, ICU и сравнил результаты с mvarchar.
c: "ЗЕЙЛЕР Е. В." < "зё" < "Зё Г. В."
icu (secondary level): "зё" < "Зё Г. В." < "ЗЕЙЛЕР Е. В."
mvarchar: "зё" < "Зё Г. В." < "ЗЕЙЛЕР Е. В." < "зё"
Для проверки работы ICU полезна ссылка. В качестве вывода могу сказать, что проблема не в ICU (к счастью), а в реализации операторов сравнения mvarchar.
Postgres Professional: http://www.postgrespro.com The Russian Postgres Company
2018-03-19 9:22 GMT+03:00 Denis Smirnov [email protected]:
Я проверил как сортируются "зё", "Зе Г. В." и "ЗЕЙЛЕР Е. В." в C, ICU и сравнил результаты с mvarchar.
c: "ЗЕЙЛЕР Е. В." < "зё" < "Зе Г. В." icu (secondary level): "зё" < "Зе Г. В." < "ЗЕЙЛЕР Е. В." mvarchar: "зё" < "Зе Г. В." < "ЗЕЙЛЕР Е. В." < "зё"
Для проверки работы ICU полезна ссылка http://demo.icu-project.org/icu-bin/collation.html. В качестве вывода могу сказать, что проблема не в ICU (к счастью), а в реализации операторов сравнения mvarchar.
Спасибо за анализ, было подозрение на все эти флаги.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/postgrespro/pgwininstall/issues/6#issuecomment-374112437, or mute the thread https://github.com/notifications/unsubscribe-auth/AGFI4r-Y_qQP9mFX4JwyWCcOvPz3osAwks5tf06ugaJpZM4Sre5j .
там все несколько хуже. select * from (values ('е'::mchar),('ё'),('еа'),('еб'),('ее'),('еж'),('ёа'),('ёб'),('ёё'),('ёж'),('ёе'),('её')) z order by 1; запрос возвращает неожиданное вне зависимости от флагов сравнения icu. При primary флаги Е равно Ё, что пугает разработчиков (при поднятии истории проблемы нашлось, почему secondary - иначе И и Й равны. проблема 2007 года, сейчас это не так. Но так для Е и Ё. Т.е. флаги не помогают решить). А если ставить SECONDARY, то то, что идет после ё оказывает влияние на сортировку этой буквы.
Мы нашли вариант работающий во всех случаях - посимвольное сравнение с помощью ICU. Плата - скорость, создание индекса медленне на ~6%. Но, кажется, работает. mchar_eyo.patch.gz Если можете и интересно, проверьте его, плз.
Проверил, теперь сортировка работает корректно "ЗЕЙЛЕР Е. В." < "зё" < "Зё Г. В.". Поиск в индексе и таблице возвращает корректные результаты. Спасибо вам всем большое за помощь!
P.S. А когда ждать данный патч в сборку pg для 1с у вас на сайте? Он потребует перестройки всех индексов, содержащих mvarchar/mchar и я хочу быть готов к этому. Еще нужно как-то предупредить остальных, кто не задумываясь решит сделать простое минорное обновление через пакетный менеджер.