Быстрый поиск комбинации строк в массиве

← →
Юрий Зотов © (2015-06-02 11:08) [200]

> Romkin © (02.06.15 10:44) [199]

Вот такой запрос работает быстро:

select ... from ... where фамилия = :param1 and имя = :param2 and отчество = :param3

Но вся проблема в функциях. Как только в запрос включаем функции, начинаются тормоза:

select ... from ... where replace(upper(фамилия), "Ё", "Е") = :param1 and replace(upper(имя), "Ё", "Е") = :param2 and replace(upper(отчество), "Ё", "Е") = :param3

где параметры - это входные ФИО, соответственно подготовленные.

← →
sniknik © (2015-06-02 11:11) [201]

> Как только в запрос включаем функции, начинаются тормоза:
по вычислению индекс не используется, считай нет его там. всегда фул скан.

← →
Sha © (2015-06-02 11:13) [202]

> Romkin © (02.06.15 10:44) [199]
> Вот смотрю и думаю...

Именно это и делает предложенный код

← →
Sha © (2015-06-02 11:19) [203]

> Юрий Зотов © (02.06.15 11:08) [200]
> Но вся проблема в функциях.
> Как только в запрос включаем функции, начинаются тормоза

Понимаю, что текущая структура базы - священная корова,
но все же рискну предложить хранение фио без буквы ё,
а замены всех е-ё в фио задавать флагами в отдельном целочисленном поле.

← →
Romkin © (2015-06-02 12:06) [204]

> Но вся проблема в функциях. Как только в запрос включаем
> функции, начинаются тормоза:

Нее, where не надо. select replace(upper(фамилия || " " || имя), "Ё", "Е")... from ... order by 1 rows from 1 to 10000; и т.д., пусть БД трудится.

> Именно это и делает предложенный код

Тогда он должен быть короче, слишком много эмуляции :) Зачем делить на равные интервалы, когда можно просто читать по n строк?

← →
Romkin © (2015-06-02 12:08) [205]

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

← →
sniknik © (2015-06-02 12:15) [206]

> Понимаю, что текущая структура базы - священная корова,
предложение было на первой странице, по моему - не трогать существующее, но добавить поле поиска, индексированное, с нужными преобразованиями "replace(upper...", одно для трех (слить с разделителем). заполнялось бы при добавлении/изменении основных. т.е. вполне нормальное, ничего не ломающее, ни на что кардинально не влияющее, с возможностью "отката без потерь"...
единственное размер таблицы в 2 раза больше станет (на 1 миллионе, ИМХО, не существенно, ну было 300мб станет 600мг стоит париться?), ну и если кто работал с таблицей через "звездочку" (не буду говорить что это нельзя, плохо... все знают, и все равно многие делают. по разным причинам) те получат дополнительный тормоз на запросах.

отказались с "аргументом" боса "не нравится".

← →
Юрий Зотов © (2015-06-02 14:32) [207]

В общем, пока что сделано так:
select ... from ... where replace(upper( фамилия || " " || имя || " " || coalesce(отчество, " ")), "Ё", "Е") = :param1
При таком запросе, если в таблице есть соответствующий индекс, то DB2 его использует автоматом. В тестовой базе он есть, в боевой - нет. Но боевой сервер гораздо мощнее тестового, поэтому решили, что бороться за память/скорость будем, если возникнут проблемы на боевом.

← →
sniknik © (2015-06-02 14:54) [208]

> При таком запросе, если в таблице есть соответствующий индекс, то DB2 его использует автоматом.
DB2 умеет по выражению как фокспро?
есть сделанный (такая фигня проходит?) -
CREATE INDEX ComplexIndex ON (replace(upper(фамилия || " " || имя || " " || coalesce(отчество, " ")), "Ё", "Е"))
?

← →
Юрий Зотов © (2015-06-02 15:14) [209]

> sniknik © (02.06.15 14:54) [208]

Если верить документации IBM, то умеет, начиная с 10.5 (function-based indexes). А у нас, к сожалению, более ранняя. Но можно построить автовычисляемое поле (в котором будет это самое выражение), а индекс вешать уже на это поле. Правда, могут возникнуть небольшие тормоза (за счет переиндексации), но они не должны быть ощутимыми.

← →
SergP © (2015-06-02 15:15) [210]

> select ... from ... where
> replace(upper(
> фамилия || " " || имя || " " || coalesce(отчество, "
> ")), "Ё", "Е") = :param1

А не лучше ли один раз в таблице исправить все Ё на Е, чем потом постоянно ощущать тормоза, связанные с поиском?

← →
Юрий Зотов © (2015-06-02 15:27) [211]

> SergP © (02.06.15 15:15) [210]

Низзя. Базой командуем не мы. Но даже если было бы можно, то все равно низзя. Потому что ФИО в базе должно быть точно таким же, как в паспорте.

Ну и возможны коллизии. Мы же не знаем, какой еще софт, кроме нашего, с это базой работает. Поменяешь Ё на Е - а где-то что-то отвалиться может.

← →
SergP © (2015-06-02 16:12) [212]

1. Почему в первом посте (как собственно и в теме) речь шла о массиве, а не о базе?

2. Базой командуем не мы, но возможность ее модификации имеется?
Например если создать еще одно поле в виде ФИО где буквы Ё уже будут заменены на Е, а для того, чтобы оно заполнялось/изменялось вместе с заполнением/изменением оригинальных полей, использовать триггеры. Или так нехорошо?

← →
Юрий Зотов © (2015-06-02 16:38) [213]

> SergP © (02.06.15 16:12) [212]

> 1. Почему в первом посте (как собственно и в теме) речь шла о массиве,
> а не о базе?

Потому что, если бы удалось закачать все таблицу в массив и найти алгоритм быстрого поиска по этому массиву, то к записям в этом массиве уже можно применять любые функции. Вариант обходной и не самый лучший, но тоже вариант.

> 2. Базой командуем не мы, но возможность ее модификации имеется?

По согласованию с хозяевами. Которое не всегда удается. И об этом говорилось.

> Например если создать еще одно поле в виде ФИО где буквы
> Ё уже будут заменены на Е, а для того, чтобы оно
> заполнялось/изменялось вместе с заполнением/изменением
> оригинальных полей

Об этом тоже уже говорилось, несколько раз. Последний - [209].

← →
SergP © (2015-06-02 16:49) [214]

> Потому что, если бы удалось закачать все таблицу в массив
> и найти алгоритм быстрого поиска по этому массиву, то к
> записям в этом массиве уже можно применять любые функции.
> Вариант обходной и не самый лучший, но тоже вариант.

Ну с алгоритмом быстрого поиска по массиву проблем-то не должно быть.
Единственная проблема, как я понимаю, заключается во времени закачки таблицы в массив?

← →
Юрий Зотов © (2015-06-02 16:52) [215]

> SergP © (02.06.15 16:49) [214]

> Единственная проблема, как я понимаю, заключается во времени
> закачки таблицы в массив?

В нехватке памяти. Почему и возникла мысль грузить таблицу кусками. А Саша даже пример написал (за что ему спасибо, этот пример может очень пригодиться).

← →
sniknik © (2015-06-02 16:57) [216]

> закачать все таблицу в массив
не лучший вариант перекидывать все в массив, двойной расход памяти как минимум... почему не работать в с полученным рекордсетом (ADO например, он и индекс локальный может, и поиск по нему)? рекордсет удается получить, вот такой к примеру -
select replace(upper(фамилия || " " || имя || " " || coalesce(отчество, " ")), "Ё", "Е") AS param1 from table1
?

без условия where, без джойнов с риском неправильно составить условие и получить гетерогенное объединение, а простую "плоскую таблицу". так и не понял из ранних обсуждений.

← →
Romkin © (2015-06-02 17:51) [217]

> не лучший вариант перекидывать все в массив, двойной расход
> памяти как минимум... почему не работать в с полученным
> рекордсетом (ADO например, он и индекс локальный может,
> и поиск по нему)?

Проблема в нехватке памяти. Ява там, панимаш?
У меня Питон за секунду файл в 10000 с миллионом записей сверяет, тихо расходуя свои 30 Мб оперативы, но это несолидно.

← →
Юрий Зотов © (2015-06-02 18:06) [218]

> Romkin © (02.06.15 17:51) [217]

Out of Memory возникает в апп-сервере (почему - вопрос не ко мне). С этим приходится считаться.

← →
SergP © (2015-06-02 19:15) [219]

> не лучший вариант перекидывать все в массив, двойной расход
> памяти как минимум...

Если в таблице информация обновляется очень редко, а поисков по ФИО нужно производить очень много, типа так что загрузил утром таблицу в массив и целый день постоянно там что-то ищется, то почему бы и нет?
Тем более что в массиве информацию можно держать в несколько ином виде чем в таблице, более удобном для поиска, и чтобы минимизировать кол-во используемой памяти...

← →
Сергей Суровцев © (2015-06-02 19:29) [220]

>sniknik © (02.06.15 16:57) [216]
>без условия where, без джойнов с риском неправильно составить условие и
>получить гетерогенное объединение, а простую "плоскую таблицу". так и не
>понял из ранних обсуждений.

А почему без джойнов? Обе таблицы на сервере. И та что на 10тыс, и та что на 1 миллион. Сервак говорят мощный. Это как раз самое его дело, такие запросы обрабатывать.

>Юрий Зотов © (02.06.15 16:52) [215]
>В нехватке памяти. Почему и возникла мысль грузить таблицу кусками. А
>Саша даже пример написал (за что ему спасибо, этот пример может очень
>пригодиться).

Пример полезный, только после появления информации о наличии ID в основной таблице, пусть и строковой привязка к ФИО для задачи перекачки теряет актуальность.

← →
Сергей Суровцев © (2015-06-02 19:32) [221]

>SergP © (02.06.15 19:15) [219]
>Если в таблице информация обновляется очень редко, а поисков по ФИО
>нужно производить очень много, типа так что загрузил утром таблицу в
>массив и целый день постоянно там что-то ищется, то почему бы и нет?

То есть актуальной сегодняшней информации в обработке не будет никогда? ))

← →
SergP © (2015-06-02 19:57) [222]

> То есть актуальной сегодняшней информации в обработке не
> будет никогда? ))

Не. Ну я же не знаю что хранит эта таблица и для чего нужен поиск по ней, и насколько важно иметь ли для поиска "актуальную сегодняшнюю информацию".

Все зависит от ситуации.

← →
Юрий Зотов © (2015-06-02 20:12) [223]

> Сергей Суровцев © (02.06.15 19:29) [220]

> Обе таблицы на сервере.

Таблица одна (которая на миллион записей). Входящие ФИО (которых 10 тыс.) берутся из файла.

← →
sniknik © (2015-06-02 22:21) [224]

> А почему без джойнов?
для проверки, убедится что нет типа такого
... from table1, table2 where 1=:param2
или другой похожей глупости. достаточно допустить логическую ошибку в условии и никакой памяти не напасешься
(неявный джойн всего со всем, 1 миллион * 10 тыс = 27 гиг чисто данных, без структуры, при выборке всего 3х полей по 1 байту...)

← →
sniknik © (2015-06-02 22:25) [225]

> Сервак говорят мощный. Это как раз самое его дело, такие запросы обрабатывать.
:) ... вот бы тебя свести с нашими "бд-админами". у нас тоже сервак мощный, а проблемы похожие.

← →
Сергей Суровцев © (2015-06-02 23:38) [226]

>sniknik © (02.06.15 22:21) [224]
>для проверки, убедится что нет типа такого

Страховки от глупостей еще не придумали. Только неусыпный контроль спасет отца русской демократии.

>:) ... вот бы тебя свести с нашими "бд-админами". у нас тоже сервак мощный, а проблемы похожие.

А есть ли в природе админы, довольные своим железом?

← →
Игорь Шевченко © (2015-06-03 10:24) [227]

sniknik © (02.06.15 22:25) [225]

> вот бы тебя свести с нашими "бд-админами". у нас тоже сервак
> мощный, а проблемы похожие.

Какой-то ты нелояльный ни разу, все у вас плохо, и с XML проблемы, и с базами данных, и код корявый пишут :)

← →
Romkin © (2015-06-03 11:42) [228]

> Out of Memory возникает в апп-сервере (почему - вопрос не
> ко мне). С этим приходится считаться.

При слиянии нужна одна запись в каждый момент времени. Думаю, что фетчить по одной или пакетами понемногу возможно, просто набор должен быть уже отсортирован на сервере БД, о чем я говорю.

> Какой-то ты нелояльный ни разу, все у вас плохо, и с XML проблемы, и с базами данных, и код корявый пишут :)
ну, что есть то есть, и чем дольше работаю с тем большим количеством проблем приходится сталкиваться... а у вас не так? врете небось.

> Romkin © (03.06.15 11:42) [228]

Рома, о каком слиянии идет речь?

Есть таблица БД с миллионом ФИО. Есть 10 тыс. входных ФИО, загруженных из дискового файла (а в БД их нет - какое слияние?). Каждая входная запись может совпасть с одной или несколькими записями из БД (а может и не совпасть ни с одной).

Задача: для каждой входной записи получить все ее совпадения с БД. С минимальным расходом памяти, с приемлемой скоростью, без изменения структуры БД и считая букву Ё буквой Е.

Варианты решения "в лоб" очевидны, но ни один из них не прокатывает. Потому что либо требует модификации БД, либо слишком медленный, либо слетает по памяти апп-сервер.

> Рома, о каком слиянии идет речь?
>
> Есть таблица БД с миллионом ФИО. Есть 10 тыс. входных ФИО,
> загруженных из дискового файла (а в БД их нет - какое слияние?
> ). Каждая входная запись может совпасть с одной или несколькими
> записями из БД (а может и не совпасть ни с одной).
>
> Задача: для каждой входной записи получить все ее совпадения
> с БД. С минимальным расходом памяти, с приемлемой скоростью,
> без изменения структуры БД и считая букву Ё буквой Е.
>
> Варианты решения "в лоб" очевидны, но ни один из них не
> прокатывает. Потому что либо требует модификации БД, либо
> слишком медленный, либо слетает по памяти апп-сервер.

Я вообще ничего уже не понимаю. Просто один раз маленькими пакетами прочитать миллион записей из БД можно? Не запоминая их?
Если да, - то читать сразу с сортировкой из БД и мерджить, выявляя дубликаты. И что-то мне подсказывает, что так будет быстрее всего :)

> Потому что либо требует модификации БД

Любая модификация запрещена? Или запрещено только менять структуру и данные в имеющихся объектах?

например в БД можно создавать какие-нить временные таблицы или материализованные представления?

> Romkin © (03.06.15 15:59) [231]

Давай не примере.

Миллионная таблица в базе (первое поле - строковый ID):
a Иванов Иван Иванович
b Петров Петр Петрович
c Семенов СемЁн Семенович
d Семенов СемЕн Семенович
e Петров Петр Петрович
и т.д.

В 10-тысячном входном файле (нумерация строк условная)
1 Иванов Иван Иванович
2 Петров Петр Петрович
3 Семенов СемЕн Семенович
4 Нектов Некто Нектович
и т.д.

В цикле j := 1 to 4 идем по строкам входного файла. На каждом витке цикла должны получить следующее:

при j = 1 (на входе - Иванов Иван Иванович)
a Иванов Иван Иванович

при j = 2 (на входе - Петров Петр Петрович)
b Петров Петр Петрович
e Петров Петр Петрович

при j = 3 (на входе - Семенов СемЕн Семенович)
c Семенов СемЁн Семенович
d Семенов СемЕн Семенович

при j = 4 (на входе - Нектов Некто Нектович)
пусто

и т.д.

Все полученные таким образом записи накапливаются в общем списке и затем как-то обрабатываются. Отказаться от этого общего списка (ради экономии памяти) по ряду причин нельзя.

> например в БД можно создавать какие-нить временные таблицы
> или материализованные представления?

Нельзя ему.
Но сделать запрос вида select translate(upper(LastName), "Ё", "Е") as name ... from ... order by name или подобный, думаю, ничто не мешает.
def find_equal(seq1, seq2): it1, it2 = iter(seq1), iter(seq2) # iterators name1, name2 = next(it1), next(it2) try: d = [] #list while True: if name1 == name2: d.append(name1) name1 = next(it1) name2 = next(it2) elif name1 > name2: name2 = next(it2) elif name2 > name1: name1 = next(it1) except StopIteration: # NoSuchElementException return d

> Давай не примере.

1. Указанный запрос с order by выдаст записи в отсортированном виде. Если итерировать по нему неможно - указывать rows или limit, кусками читать.
2. Список в памяти отсортировать
3. Проитерировать оба отсортированных списка, выявляя дубликаты.

> В цикле j := 1 to 4 идем по строкам входного файла.
неужели там нет других способов, xml к примеру или table types или еще чего?
только работать как с допотопной базой можно?

> ухты © (03.06.15 16:51) [238]

> xml

В реальности, там или текстовый файл, или файл xml. По сути, это без разницы. Только парсеры разные, а в итоге все равно получаем входной список ФИО.

да я не про файл а про запросы

Быстрый поиск комбинации строк в массиве Найти похожие ветки