Index & Primary Key, быстрый поиск больших строковых полей / Firebird, InterBase

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Index & Primary Key, быстрый поиск больших строковых полей

19 сообщений из 19, страница 1 из 1

Index & Primary Key, быстрый поиск больших строковых полей

#32318343

IBNovice

Гость

Hi All..
Начал изучать Interbase...
1) Кто нибудь может объяснить какая принципиальная разница между primary key и index unique?
2) В Interbase есть ограничение на размер полей, включенных в индекс, есть ли какой-нибудь клон Interbase, где это ограничение отсутствует? Мне нужен быстрый поиск по большому полю (varchar(800)) в большой базе (>600Мб, > 1 000 000 записей ) . Частично выкрутился с помощью дополнительного поля (проиндексированного), trigger-а, hash, UDF и какой-то матери .
Сейчас запрос выглядит типа select * from table where hashed_field=hash_code(somestring))
Ну и триггеры before update и before insert : new.hashed_field = hash_code(new.big_field)
Однако есть существенный недостаток - невозможность использовать like . При ручном поиске вбивать до 800 символов несколько утомительно :(. В принципе есть варианты, но хотелось бы
избежать всякого рода извращений. Если кто сталкивался с подобными проблемами и сумел их победить, поделитесь опытом, пожалуйста.

...

Рейтинг:

0 / 0

09.11.2003, 13:33

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32318834

Gold

Участник

Откуда: Харьков

Сообщения: 2 958

Рейтинг: 0 / 0

Тебе нужны фразовые индексы. Где они вобще есть - я затрудняюсь ответить. В ИБ их точно нету. Всё равно индексы могут быть использованы только если совпадения ищутся по началу строки. Так что хэш в данном случае - самый лучший вариант.
Воюще-то ещё я слышал, что где-то есть примочка к ИБ, предназначенная как раз для такого поиска, но она вроде платная и ссылки я не помню.

...

Рейтинг:

0 / 0

10.11.2003, 13:28

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32319475

IBNoice

Гость

Будем извращаться В принципе hash пока устраивает - просто хэширую по upper и вместо like использую between или > and < . Но все таки жаль, что размер ключа ограничен (в MySQL такого ограничения вроде нет)

...

Рейтинг:

0 / 0

11.11.2003, 06:23

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32319823

StarWind

Участник

Откуда: г. Иркутск

Сообщения: 1 850

Рейтинг: 0 / 0

Gold
есть они в MS SQL... если я тя правильно понял и называется эта ерунда, полнотекстовый поиск... очень приятная штука....

IBNovice
а можно узнать, что за задача такая, в которой требуется поиск по полю и вводить придется 800 символов?

...

Рейтинг:

0 / 0

11.11.2003, 11:38

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32319992

Gold

Участник

Откуда: Харьков

Сообщения: 2 958

Рейтинг: 0 / 0

2 StarWind:

Интересно, а как это устроено? Вы не в курсе?

...

Рейтинг:

0 / 0

11.11.2003, 12:51

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32320052

IBNovice

Гость

2 StarWind
Вы бы внимательнее суть проблемы читали бы, если хотите что-то ответить или спросить .

База представляет из себя кое-какое логирование кое-каких событий. Максимальная длина значения интересуемого меня поля пока достигала ~700 символов. Нужен был быстрый поиск
по этому полю (по моему довольно часто встречающаяся задач, нет?). С индексом вышел облом, поэтому пришлось немного поизгалятся. Сначала был не очень удачный алгоритм хэширования - для быстрого поиска приходилось вводить искомое значение целиком, что естественно меня не устраивало. Так что задача была как раз наоборот: быстрый поиск по полю и как избежать набора до 800 символов.

Частично решил эту задачу так (по крайней мере не придется набирать эти 800 символов ):

Изменил алгоритм хэширования, теперь гарантировано hash код строки 'B...' будет больше
чем hash код строки 'A...', 'aB' чем 'AA' и т.д. Например, если мне нужно быстро найти строки,
начинающиеся на 'ABC' (или 'abc'), делаю запрос

select big_field from table where hash_field>=hash_code('ABC') and hash_field<hash_code('ABD')
который отрабатывает за считанные секунды (не более 7-8, а то и меньше 1 секунды, не знаю точно от чего зависит), в то время как при использовании

where upper(big_field) like 'ABC%'
или
where upper(big_field) starting with 'ABC'
на поиск уходит минимум минута, а то и 2-3

Но все равно, как то кривовато получилось :(((

...

Рейтинг:

0 / 0

11.11.2003, 13:15

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32320889

StarWind

Участник

Откуда: г. Иркутск

Сообщения: 1 850

Рейтинг: 0 / 0

IBNovice
прочитал то я внимательно... вот только в нем не было ЗАЧЕМ это надо....
сейчас стало немного понятно, что нужен именно полнотекстовый поиск... Если у вас именно IB да еще и шестерка, то боюсь это не возможно. в FB слышал что можно было создавать индексы по результатам функций, а это означает что есть шанс найти библиотеку для возможностей полнотекстового поиска... А вообще, мой бы совет, может стоит подумать над задачей внимательно и стоит разбить эти логи на какие-нить категории, на какие-то блоки? и тогда соответственно ищем сперва нужный блок данных, а там глядишь и в нем окажется строчек так немного... в районе сотни? там можно и обычным like ом пройтись... По тому-то я и спрашивал что за задача... то то бы что подсказал кто-нить на форуме...
Да и по поводу первого вопроса... Принципиальная разница состоит в том, что для того чтобы на поле можно было установить ссылочную целостность на это поле (foreign key) это поле должно быть primary key. И еще, на опыте было замечено, что по primary key поиск идет быстрее чем по уникальному индексу.

Gold
честно говоря не скажу как работает (в смысле внутренности), но есть у тебя в каком-то поле фраза "Головной убор" задаем поиск по слову "Голова" и находим эту фразу. Причем если есть слово "Мониторинг", то оно не будет найдено по слову "Монитор". Грубо говоря поиск идет однокоренных слов (хотя это несколько не верно). В MS SQL эта штука встроена для английских слов, для русских качали специально примочку с www.alesta.ru . Причем поиск весь разумеется по индексам ведется. Посмотрите, может что приятное для себя найдете.

PS да, при все при этом в MS SQL не создается дополнительных таблиц и при внесении новых данных не нужно пересчитывать этот полнотекстовый индекс. Т.е. он не хранит информацию о том что записано в полях.

...

Рейтинг:

0 / 0

12.11.2003, 03:45

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32320969

IBNovice

Гость

2 StartWind
> прочитал то я внимательно... вот только в нем не было ЗАЧЕМ это надо....

А зачем знать ЗАЧЕМ мне это надо По моему вопрос был достаточно ясен: как осуществить быстрый поиск по большому полю и все.

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

>Да и по поводу первого вопроса... Принципиальная разница состоит в том, что для того чтобы на поле
>можно было установить ссылочную целостность на это поле (foreign key) это поле должно быть
>primary key. И еще, на опыте было замечено, что по primary key поиск идет быстрее чем по
>уникальному индексу.

А за это спасибо. Теперь понятно.

...

Рейтинг:

0 / 0

12.11.2003, 09:18

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32320998

StarWind

Участник

Откуда: г. Иркутск

Сообщения: 1 850

Рейтинг: 0 / 0

может тогда стоти переделать структуру и написать представление, которое будет генерить набор данных под старые проги, а твоя будет работать с нормальной базой

...

Рейтинг:

0 / 0

12.11.2003, 09:51

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321073

IBNovice

Гость

2 StarWind
>может тогда стоти переделать структуру и написать представление, которое будет генерить набор
>данных под старые проги, а твоя будет работать с нормальной базой

Проанализировал я эту базу. Подавляющее большинство записей имееют длину не более 100 символов для данного поля. А что если создать еще одно поле varchar(100), которое проиндексировать и вставлять туда не более первых 100 символов большого поля? Вставку осуществлять через тригеры, с помощью UDF substr, тогда в логере менять совсем ничего не нужно, а в интерфейсных прогах слегка изменить процедуру поиска ( изменить имя поля, по которому осуществляется поиск). Все равно для поиска обычно достаточно порядка 10 символов.

...

Рейтинг:

0 / 0

12.11.2003, 10:46

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321200

Gold

Участник

Откуда: Харьков

Сообщения: 2 958

Рейтинг: 0 / 0

Индекс всё равно будет использован только если поиск будет вестись по началу строки, т.к. с помощью STARTING WITH или LIKE 'zzz%'

...

Рейтинг:

0 / 0

12.11.2003, 11:49

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321259

Zmeishe

Участник

Откуда: Нижний Новгород

Сообщения: 1 266

Рейтинг: 0 / 0

Наконец-то я дополз до форума после жуткого аврала на работе!

Теперь по теме.
Писал я такой алгоритм поиска по длинным строкам и BLOB-типа текст.
Делал разбор пейджерных сообщений, нормально получилось.
Что-то вроде полнотекстового индексирования.
Юзер мог задать 'шк18' или '18 шко' или 'Школа №18' без разницы в каком прядке, с разделителями между буквами и цифрами или без. Всё равно найдёт и довольно шустро. Притормаживает если слишком много слов задать. Хотя анализ показал, что IB использует только индексированные чтения, в основном PK.

Одну проблему так и не смог решить. Если задать одинаковые слова в поисковой строке - ничего не найдёт.
Например, задано 'иван иван' вместо 'иван иваныч' или 'иванов иван' будет <null>. Если 'н н' тоже <null>. Если 'но ни' - всё Ok - 'Нижний Новгород'.

Обошёлся четырьмя ХП, тремя UDF и двумя триггерами.

...

Рейтинг:

0 / 0

12.11.2003, 12:15

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321347

IBNovice

Гость

2 Gold
>Индекс всё равно будет использован только если поиск будет вестись по началу строки, т.к. с
>помощью STARTING WITH или LIKE 'zzz%'
Да я в курсе Мне оно собственно и нужно - по первым n буквам - иначе нафига мне индекс ? Сейчас (с hash-извращением) на такой поиск уходит до 8 секунд, раньше до 3 минут. Но у очередного хэш-алгоритма опять недостаток нашелся - для нормальной работы нужно чтобы в базе было не более 4096 * 4 * 128 различных значений данного поля (величины этого поля могут совпадать в различных записях). А потом фигня начнется :(

2 Zmeishe
А принцип действия какой? Тоже хэш?

...

Рейтинг:

0 / 0

12.11.2003, 12:59

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321355

Zmeishe

Участник

Откуда: Нижний Новгород

Сообщения: 1 266

Рейтинг: 0 / 0

Я не знаю, что такое хэш. Наверно поэтому и взялся за изобретение велосипеда. Наверно поэтому и получилось.
В самом деле, объясни, что такое хэш?

...

Рейтинг:

0 / 0

12.11.2003, 13:03

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321440

IBNovice

Гость

2 Zmeishe
>Я не знаю, что такое хэш. Наверно поэтому и взялся за изобретение велосипеда. Наверно поэтому и
>получилось.
>В самом деле, объясни, что такое хэш?

Грубо говоря преобразование строки переменной длины в строку фиксированной длины. В моем случае строка преобразовывается в целое число. Причем должно выполнятся условие: hash_code(string1)==hash_code(string2) тогда и только тогда когда string1==string2. Таким образом по hash_code(string) можно найти соответствующую запись (where hash_code(string)==hash_field)

Пример на С (Unix) (первый алгоритм):

//---------------------------------------------
#include <stdio.h>

unsigned long hash_code(unsigned char *str,unsigned int len)
{
unsigned long res;

res = 800;
while (len) {
--len;
res += (res << 11);
res ^= (unsigned long) *str++;
}
return res;
}

main() {
char buf [1024];
while(fgets(buf,sizeof(buf)-1,stdin)) {
buf[strlen(buf)-1]=0; //обрезать LF (для ДОС/Виндовс надо еще обрезать CR)
printf("%s:%u\n",buf,hash_code(buf,strlen(buf)));
}

}
//--------------------------------------------

В нынешнем алгоритме при хэшировании учитывается еще и позиция и ASCI код символа

...

Рейтинг:

0 / 0

12.11.2003, 13:48

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32321457

Zmeishe

Участник

Откуда: Нижний Новгород

Сообщения: 1 266

Рейтинг: 0 / 0

Не, у меня не так. Но мысль интересная, если попробовать скомбинировать одно с другим???

У меня не на равно, а на starting with.
Результатом будут те строки, в которых слова, начинающиеся на заданные куски слов, встречаются >= количества заданных кусков.
Формулировка получилась мутная, но вроде логичная. Отражает суть метода.

...

Рейтинг:

0 / 0

12.11.2003, 13:57

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32322322

IBNovice

Гость

2 Zmeishe
>Не, у меня не так. Но мысль интересная, если попробовать скомбинировать одно с другим???

Мысль конечно интересная - жаль не моя
В принципе , если подобрать удачный hash алгоритм, гарантирующий, что строка с большим ASCI - значением ( в смысле 'aaaaa' < 'b', 'z'>'yzzz' , 'z'='Z' и т.д.) , возвращала больший hash код, то можно перед хэшировании строку преобразовывать в верхний регистр и отсортировать. Поле, содержащее hash код, проиндексировать, ну и написать хранимку для поиска. Тогда поля, содержащих какую-нибудь строку можно искать по соответствующим hash-кодам. Например для строк, содержащих только буквы, пробелы и знаки препинания, поиск полей, содержащих строку поиска , скажем 'abC, будет равносилен запросу select * from table where hash_field>=hash_code( 'ABC') and hash_field< hash_code('ABD').

P.S. Если для hash использовать unsigned long (4 байта), то хватит на 2^32-1 =4 294 967 295 различных значений - должно хватить на ближайшее будущее

...

Рейтинг:

0 / 0

13.11.2003, 07:18

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32322424

Zmeishe

Участник

Откуда: Нижний Новгород

Сообщения: 1 266

Рейтинг: 0 / 0

Я тут ещё немного поразмышлял.
Как-то не очень мне нравится алгоритм с hash кодами.
Есть официальное наименование предприятия (в одном поле)
'Муниципальное лечебно-профилактическое учреждение Больница №5 имени профессора Мышьяковича'
У этого предприятия есть альтернативное наименование (в другом поле)
'Первая градская'
Есть скрытое поле содержащее
'1-ая пятая' на тот случай если юзер при поиске введёт вместо слова 'Первая' цифру '1' или вместо цифры '5' слово 'пятая'

В моём алгоритме пользователь может ввести следующие комбинации
'1мыш5'
'бол5'
'1град'
'5град'
'град мыш'
'мыш проф бол'
В общем случае - непредсказуемая комбинация кусков слов в перемешку с цифрами.

Результатом поиска будет именно это учереждение.

А как будет(должен) работать hash алгоритм - я пока не дотягиваю.

...

Рейтинг:

0 / 0

13.11.2003, 09:29

| Ответить | Цитировать | Написать

Index & Primary Key, быстрый поиск больших строковых полей

#32322562

IBNovice

Гость

Мой предыдущий пост - полная фигня. Репу заклинило после очередной бессонной ночи Короче стереть и забыть

...

Рейтинг:

0 / 0

13.11.2003, 10:58

| Ответить | Цитировать | Написать

19 сообщений из 19, страница 1 из 1

Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Index & Primary Key, быстрый поиск больших строковых полей

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=40&msg=32320969&tid=1579664]:	0ms
get settings:	10ms
get forum list:	18ms
check forum access:	3ms
check topic access:	3ms
track hit:	163ms
get topic data:	10ms
get forum data:	2ms
get page messages:	51ms
get tp. blocked users:	1ms
others:	248ms

total:	509ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы