Поиск в btree не возвращает результаты для mvarchar/mchar #6

darthunix · 2018-03-15T03:00:19Z

Тестовая схема + данные

pg1c.sql.txt

Описание проблемы

В патче 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 и не висят в воздухе (должны находиться)

Версии

Ключ попадает не на ту страницу индекса

проблема в опорной функции
не корректно сравнивается значение искомого ключа с наибольшим значением в странице

The text was updated successfully, but these errors were encountered:

akorotkov · 2018-03-15T08:41:44Z

Спасибо за подробный отчёт.
Какая используется версия ОС, локаль, версия icu?

darthunix · 2018-03-15T09:57:49Z

Проверялось на двух вариантах

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

obartunov · 2018-03-15T10:10:08Z

А вы пробовали нашу сборку с postgrespro.ru ?

darthunix · 2018-03-15T10:14:53Z

Да, использовал с вашего сайта postgres поддержкой 1с (https://postgrespro.ru/products/1c_build)

darthunix · 2018-03-15T11:09:13Z

Забыл добавить про локаль - везде была ru_RU.UTF-8

darthunix · 2018-03-15T22:48:13Z

Проверил порядок сортировки для индекса и таблицы.

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;

Результаты идентичные на тестовых данных.

darthunix · 2018-03-17T04:38:28Z

Так как вопрос не в сортировке, я решил посмотреть, какие данные в текстовом виде содержатся в проблемной странице индекса, куда попадает "Зё Г. В.".

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 строка)

Выходит полная ерунда, так как у функций сравнения отсутствует транзитивность

darthunix · 2018-03-17T04:59:04Z

Выходит, выстрелило не в значении "Зё Г. В.", а в наибольшем ключе на странице "ЗЕЙЛЕР Е. В." на котором ломаются функции сравнения. Этим и объясняется разница в поиске по таблице и индексу. В таблице идет полный перебор, и хоть наибольший ключ не проходит проверку (а "Зё Г. В." проходит) и мы получаем нужного нам "Зё Г. В.". А в индексе поиск не заходит в страницу, где лежит "Зё Г. В.", так как наибольший ключ не проходит проверку на условие сравнения

darthunix · 2018-03-17T13:33:22Z

Вот суть проблемы, если отбросить все ненужное

pg1c=# select 'ё'::mvarchar < 'е'::mvarchar;
 ?column? 
----------
 f
(1 строка)

pg1c=# select 'ёа'::mvarchar < 'еа'::mvarchar;
 ?column? 
----------
 f
(1 строка)

pg1c=# select 'ёа'::mvarchar < 'еб'::mvarchar;
 ?column? 
----------
 t
(1 строка)

darthunix · 2018-03-18T13:57:41Z

Все функции сравнения для 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" мы имеем "еа" < "ёа" < "еб".

darthunix · 2018-03-19T06:22:37Z

Я проверил как сортируются "зё", "Зё Г. В." и "ЗЕЙЛЕР Е. В." в C, ICU и сравнил результаты с mvarchar.

c: "ЗЕЙЛЕР Е. В." < "зё" < "Зё Г. В."
icu (secondary level): "зё" < "Зё Г. В." < "ЗЕЙЛЕР Е. В."
mvarchar: "зё" < "Зё Г. В." < "ЗЕЙЛЕР Е. В." < "зё"

Для проверки работы ICU полезна ссылка. В качестве вывода могу сказать, что проблема не в ICU (к счастью), а в реализации операторов сравнения mvarchar.

obartunov · 2018-03-19T10:35:43Z

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 <#6 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGFI4r-Y_qQP9mFX4JwyWCcOvPz3osAwks5tf06ugaJpZM4Sre5j> .

feodor · 2018-03-19T13:34:57Z

там все несколько хуже.
select * from (values ('е'::mchar),('ё'),('еа'),('еб'),('ее'),('еж'),('ёа'),('ёб'),('ёё'),('ёж'),('ёе'),('её')) z order by 1;
запрос возвращает неожиданное вне зависимости от флагов сравнения icu. При primary флаги Е равно Ё, что пугает разработчиков (при поднятии истории проблемы нашлось, почему secondary - иначе И и Й равны. проблема 2007 года, сейчас это не так. Но так для Е и Ё. Т.е. флаги не помогают решить). А если ставить SECONDARY, то то, что идет после ё оказывает влияние на сортировку этой буквы.

Мы нашли вариант работающий во всех случаях - посимвольное сравнение с помощью ICU. Плата - скорость, создание индекса медленне на ~6%. Но, кажется, работает.
mchar_eyo.patch.gz
Если можете и интересно, проверьте его, плз.

darthunix · 2018-03-20T06:08:54Z

Проверил, теперь сортировка работает корректно "ЗЕЙЛЕР Е. В." < "зё" < "Зё Г. В.". Поиск в индексе и таблице возвращает корректные результаты. Спасибо вам всем большое за помощь!
P.S. А когда ждать данный патч в сборку pg для 1с у вас на сайте? Он потребует перестройки всех индексов, содержащих mvarchar/mchar и я хочу быть готов к этому. Еще нужно как-то предупредить остальных, кто не задумываясь решит сделать простое минорное обновление через пакетный менеджер.

feodor · 2018-03-20T15:24:09Z

видимо, в середине мая, вместе с очередным минорным апдейтом

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Поиск в btree не возвращает результаты для mvarchar/mchar #6

Поиск в btree не возвращает результаты для mvarchar/mchar #6

darthunix commented Mar 15, 2018 •

edited

Loading

akorotkov commented Mar 15, 2018

darthunix commented Mar 15, 2018 •

edited

Loading

obartunov commented Mar 15, 2018

darthunix commented Mar 15, 2018

darthunix commented Mar 15, 2018

darthunix commented Mar 15, 2018

darthunix commented Mar 17, 2018 •

edited

Loading

darthunix commented Mar 17, 2018

darthunix commented Mar 17, 2018

darthunix commented Mar 18, 2018 •

edited

Loading

darthunix commented Mar 19, 2018 •

edited

Loading

obartunov commented Mar 19, 2018 via email

feodor commented Mar 19, 2018 •

edited

Loading

darthunix commented Mar 20, 2018 •

edited

Loading

feodor commented Mar 20, 2018

Поиск в btree не возвращает результаты для mvarchar/mchar #6

Поиск в btree не возвращает результаты для mvarchar/mchar #6

Comments

darthunix commented Mar 15, 2018 • edited Loading

Тестовая схема + данные

Описание проблемы

Воспроизведение бага

Итого

Версии

akorotkov commented Mar 15, 2018

darthunix commented Mar 15, 2018 • edited Loading

obartunov commented Mar 15, 2018

darthunix commented Mar 15, 2018

darthunix commented Mar 15, 2018

darthunix commented Mar 15, 2018

darthunix commented Mar 17, 2018 • edited Loading

darthunix commented Mar 17, 2018

darthunix commented Mar 17, 2018

darthunix commented Mar 18, 2018 • edited Loading

darthunix commented Mar 19, 2018 • edited Loading

obartunov commented Mar 19, 2018 via email

feodor commented Mar 19, 2018 • edited Loading

darthunix commented Mar 20, 2018 • edited Loading

feodor commented Mar 20, 2018

darthunix commented Mar 15, 2018 •

edited

Loading

darthunix commented Mar 15, 2018 •

edited

Loading

darthunix commented Mar 17, 2018 •

edited

Loading

darthunix commented Mar 18, 2018 •

edited

Loading

darthunix commented Mar 19, 2018 •

edited

Loading

feodor commented Mar 19, 2018 •

edited

Loading

darthunix commented Mar 20, 2018 •

edited

Loading