Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
stan1991
Member

Откуда:
Сообщений: 13
Добрый день!
Необходимо реализовать быстрый аналог (без FULL SCAN) запроса:

SELECT * FROM SomeTable WHERE SomeColumn LIKE '%' || :a || '%'

Насколько реально это сделать без применения дополнительных средств, только одним SQL или PL/SQL (используется Oracle 8.1.7)? Может ли такое сделать Oracle Text? Хотя, конечно, лучше без него - на текущий момент он не установлен, и мучаться с неизвестным мне средством не очень хочется.
Заранее спасибо.
28 сен 06, 14:38    [3196929]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
dmidek
Member

Откуда: Киев - Дортмунд
Сообщений: 116133
Если бы у Вас была константа, можно было бы попробовать положить
функциональный индекс на INSTR(str, 'xxx') и проверять
where INSTR(str, 'xxx') > 0
28 сен 06, 14:53    [3197043]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
stan1991
Member

Откуда:
Сообщений: 13
К сожалению, никоим образом не константа. Была бы константа, я бы и без функционального индекса обошелся - добавил бы колонку со сведениями вроде "нужная подстрока есть/нет", и искал бы по ней. Ан нет :(
28 сен 06, 15:04    [3197142]     Ответить | Цитировать Сообщить модератору
 Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
Elic
Member

Откуда:
Сообщений: 29979
stan1991
Без Oracle Text быстрее может быть:
  • Index Full Scan
  • Вынос столбца в отдельную табличку и FS по более мелкой таблице.
  • 28 сен 06, 15:13    [3197222]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    Nuri
    Member

    Откуда: Архангельск
    Сообщений: 625
    Может глупость скажу, а вот так нельзя?
    select * from SomeTable t where instr(SomeColumn,:a)>0
    28 сен 06, 15:16    [3197246]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    stan1991
    Member

    Откуда:
    Сообщений: 13
    select * from SomeTable t where instr(SomeColumn,:a)>0
    Можно. Только как FULL SCAN был, так он и остался.

    А вот это вот уже лучше:
  • Index Full Scan
  • Вынос столбца в отдельную табличку и FS по более мелкой таблице.

    Но все равно плохо - таблица то на 2 млн записей. И строки в ней - основное содержимое. Так что размер индекса или отдельной таблички будет ненамного меньше таблицы с основным содержимым, а значит не даст большого преимущества :(
  • 28 сен 06, 15:20    [3197284]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    Vasiliy Utkin
    Member

    Откуда: Rostov
    Сообщений: 47
    это уже свою поисковую систему надо писать.. или пользоваться альтернативными разработками
    28 сен 06, 16:19    [3197803]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    miksoft
    Member

    Откуда:
    Сообщений: 38540
    stan1991
    а есть какие-то зависимости между содержимым поля SomeColumn и тем, что будут искать?
    может, есть какие-то другие ограничения или зависимости?
    28 сен 06, 17:14    [3198287]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    stan1991
    Member

    Откуда:
    Сообщений: 13
    Никаких зависимостей между тем, что будут искать, и что содержится, нет. Это просто поиск по подстроке.
    Я уж согласен на Oracle Text, коли задача такая непростая. Вы только скажите - он умеет искать по подстроке, не учитывая деления на слова?
    28 сен 06, 17:18    [3198311]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    AlexOI
    Member

    Откуда: Санкт-Петербург
    Сообщений: 161
    stan1991
    Никаких зависимостей между тем, что будут искать, и что содержится, нет. Это просто поиск по подстроке.
    Я уж согласен на Oracle Text, коли задача такая непростая. Вы только скажите - он умеет искать по подстроке, не учитывая деления на слова?


    умеет. аналогично like
    28 сен 06, 17:29    [3198394]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    mcureenab
    Member

    Откуда: Murmansk
    Сообщений: 5928
    stan1991
    Никаких зависимостей между тем, что будут искать, и что содержится, нет. Это просто поиск по подстроке.
    Я уж согласен на Oracle Text, коли задача такая непростая. Вы только скажите - он умеет искать по подстроке, не учитывая деления на слова?


    Вроде нет. Oracle Text строит инвертированный индекс (т.е. список слов со ссылками на записи в которых они встречаются). Индексировать таким способом буквы нет смысла (как правило любая буква будет присутствовать в каждой строке). Индексировать нужно ключи, по которым будет выполняться поиск. А в текстах такими ключами обычно являются слова.

    Если не сложно, уточни, пзл., смысл :a. Что это такое, какую роль значение :a играет в строке? Можно ли преобразовать строку и :a так, чтобы :a' было словом в строке'?
    28 сен 06, 17:34    [3198440]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    Vasiliy Utkin
    Member

    Откуда: Rostov
    Сообщений: 47
    мне думается если в таблице немеренно строк содержащих текстовую информацию, не разделенную на слова, т.е. просто набор символов и поиск нужно также производить по набору символов без учета слов, то full scan не избежен...

    если конечно нет каких-нибудь закономерностей или особенностей хранимого текста.
    28 сен 06, 17:46    [3198525]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    Vasiliy Utkin
    Member

    Откуда: Rostov
    Сообщений: 47
    p.s. а вообще странно, что между тем что ищется и исходными данными нет никакой зависимости, непонятно зачем тогда это нужно??
    28 сен 06, 17:54    [3198570]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    miksoft
    Member

    Откуда:
    Сообщений: 38540
    stan1991
    Каково распределение длин хранящихся строк и искомых строк?
    28 сен 06, 18:05    [3198621]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    mcureenab
    Member

    Откуда: Murmansk
    Сообщений: 5928
    Vasiliy Utkin
    мне думается если в таблице немеренно строк содержащих текстовую информацию, не разделенную на слова, т.е. просто набор символов и поиск нужно также производить по набору символов без учета слов, то full scan не избежен...


    ИМХО, решение есть.
    Нарезаем строку на фрагменты, длина которых <= типичной длины :a. Таким образом в строке всегда будет фрагмент начало которого является подстрокой :a.
    И по фрагментам строк строим инвертированный индекс.
    Для того чтобы найти записи, где строка содержит :a, нарезаем :a на фрагменты по тем же правилам, по которым нарезали строки в таблице. (Поскольку :a это не вся строка, то вариантов нарезания :a на фрагменты может быть несколько). Затем используя инвертированный индекс находим записи, в которых есть искомые фрагменты (они либо целиком совпадают с врагментами :a, либо начинаются на фрагмент :a) и среди них отбираем только те где строка like '%'||:a||'%'.

    Понятно, эффективность такого подхода зависит от типичной длинны :a, искомых строк и способа фрагментирования (равными частями, слогами и т.п.).

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

    Если длина :a меньше длины фрагмента, то по индексу мы не сможем гарантированно найти все записи. Нужно использовать full scan.
    28 сен 06, 18:21    [3198737]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    miksoft
    Member

    Откуда:
    Сообщений: 38540
    mcureenab
    ИМХО, решение есть.
    Нарезаем строку на фрагменты, длина которых <= типичной длины :a. Таким образом в строке всегда будет фрагмент начало которого является подстрокой :a.
    И по фрагментам строк строим инвертированный индекс.
    Для того чтобы найти записи, где строка содержит :a, нарезаем :a на фрагменты по тем же правилам, по которым нарезали строки в таблице. (Поскольку :a это не вся строка, то вариантов нарезания :a на фрагменты может быть несколько). Затем используя инвертированный индекс находим записи, в которых есть искомые фрагменты (они либо целиком совпадают с врагментами :a, либо начинаются на фрагмент :a) и среди них отбираем только те где строка like '%'||:a||'%'.

    А можно объяснить еще раз на примере?
    Например, хранится строка "ABCDEFGHIJ" (условно, остальные строки не подходят под условие поиска), делим по 5 символов, получаем две записи "ABCDE" и "FGHIJ". Нужно найти "DEFGHI". И что дальше?
    28 сен 06, 18:30    [3198796]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    mcureenab
    Member

    Откуда: Murmansk
    Сообщений: 5928
    miksoft

    А можно объяснить еще раз на примере?
    Например, хранится строка "ABCDEFGHIJ" (условно, остальные строки не подходят под условие поиска), делим по 5 символов, получаем две записи "ABCDE" и "FGHIJ". Нужно найти "DEFGHI". И что дальше?


    Режем "DEFGHI" на "DE" и "FGHI". Фрагмент "DE" это начало :a и он короче 5ти символов, он может не находиться в голове ключа, поэтому непригоден для поиска по индексу (можно сделть второй индекс, где буквы в фрагментах переставлены в обратном порядке и искать такие фрагменты в нём). Фрагмент "FGHI" может быть головой ключа, по нему и ищем.

    Грубо говоря так
    select rowid from inv_index where key like 'FGHI'||%
    но чтобы индекс реально заработал нужно делать примерно так:
    select rowid from inv_index where 'FGHI' <= key and key <= 'FGHI'||chr(255) and key like 'FGHI'||%

    Тут chr(255) скользкое место.

    Этот запрос вернёт нам ROWID строк, которые содержат подстроку 'FGHI'. Если их относительно немного, то дальнейшее уточнение str like '%'||:a||'%' не займёт много времени.

    "DEFGHI" можно порезать еще 5ю способами. Их все нужно проверить.

    Процедуру нарезания можно оптимизировать, чтобы сократить количество проб (например фрагменты могут перекрываться), правда за счёт увеличения размера индекса.
    28 сен 06, 18:50    [3198920]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    Чисто теоретически
    Guest
    miksoft
    А можно объяснить еще раз на примере?
    Например, хранится строка "ABCDEFGHIJ" (условно, остальные строки не подходят под условие поиска), делим по 5 символов, получаем две записи "ABCDE" и "FGHIJ". Нужно найти "DEFGHI". И что дальше?

    ну можно наверно
    для сторки ABCDEFGHIJ хранить в доп таблице связки ключа и следующих строк:
    ABCDE
    BCDEF
    CDEFG
    DEFGH
    EFGHI
    FGHIJ
    GHIJ
    HIJ
    IJ
    J
    по этому строить индекс и искать по нему как like :a||'%'
    находить ключ исходной таблицы делать запрос в исходную с доп проверкой.

    хотя как я понимаю высасывать из пальца подобных алгоритмов можно много, а вот будут ли они эффективны зависят от распределения строк.
    28 сен 06, 18:52    [3198928]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    mcureenab
    Member

    Откуда: Murmansk
    Сообщений: 5928
    Чисто теоретически
    хотя как я понимаю высасывать из пальца подобных алгоритмов можно много, а вот будут ли они эффективны зависят от распределения строк.


    Точно!

    Тут наверное проще пользовательский индекс построить.
    28 сен 06, 18:54    [3198945]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    stan1991
    Member

    Откуда:
    Сообщений: 13
    Длины строк - от 1 до 60 символов. Средняя длина - 10 символов. Алгоритм с нарезкой понятен, но он приведет к тому, что появится новая таблица на примерно 20 млн записей - я же ее заколебусь создавать и поддерживать :)

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

    Точно такое нельзя реализовать с помощью Oracle Text ? На текущий момент я вижу, что есть два разных утверждения на этот счет. Если не лениво, проверьте плз, кто с ним знаком - не хочется изучать продукт только ради того, чтобы узнать его неприменимость к решению моей задачи.
    29 сен 06, 09:32    [3200016]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    andreymx
    Member

    Откуда: Запорожье
    Сообщений: 54381
    очередная тупая идея:
    создать например колонки от a до z (если только англ текст) ну или сколько надо...
    при записи в каждую колонку пишет 1 или 0 (есть-нет в строке буква)
    строим битовый индекс (если это, например, хранилище данных и текущие изменения небольшие)
    затем поиск and a=1 and c=1 and t=1 (для слова например actatatca)
    29 сен 06, 11:06    [3200715]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    MacDuck
    Member

    Откуда: Москва-Подольск
    Сообщений: 6387
    andreymx
    очередная тупая идея:


    Ребята, ну чего извращаться? контекстный индекс и усе.
    29 сен 06, 11:10    [3200743]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    miksoft
    Member

    Откуда:
    Сообщений: 38540
    stan1991
    Длины строк - от 1 до 60 символов. Средняя длина - 10 символов. Алгоритм с нарезкой понятен, но он приведет к тому, что появится новая таблица на примерно 20 млн записей - я же ее заколебусь создавать и поддерживать :)
    Ну не так уж и сложно ее будет поддерживать. А поиск зато будет практически мгновенный.
    Кстати, из оперы "очередных тупых идей" можно такую таблицу секционировать по длине строки. Тогда чем длинне искомая строка, тем больше секций можно будет откинуть.
    29 сен 06, 11:29    [3200926]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    mcureenab
    Member

    Откуда: Murmansk
    Сообщений: 5928
    Тут нужна нейронная сеть. О!
    29 сен 06, 12:02    [3201284]     Ответить | Цитировать Сообщить модератору
     Re: Быстрый поиск, аналог LIKE '%' || :a || '%'  [new]
    stan1991
    Member

    Откуда:
    Сообщений: 13
    MacDuck
    andreymx
    очередная тупая идея:


    Ребята, ну чего извращаться? контекстный индекс и усе.


    А поподробнее можно - что сие есть такое? И точно ли он позволяет искать не по словам, а по произвольной подстроке?
    29 сен 06, 12:06    [3201318]     Ответить | Цитировать Сообщить модератору
    Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
    Все форумы / Oracle Ответить