Поиск префикса максимальной длины / Oracle

ReSQL.ru

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

Гость

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

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

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

Цитировать

Написать

Автор*:

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

Тема*:

Сообщение

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

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

Автор:

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

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

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

Вложение:

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

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

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

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

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

Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск префикса максимальной длины

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

Поиск префикса максимальной длины

#39317067

Aandr

Гость

Дано:
1. Таблица с уникальными перфиксами (prefix_list$t).
2. Таблица с выражениями, содержащими префикс (data_4_prefix$t).

Требуется:
Для каждой строки таблицы data_4_prefix$t найти соответствующую запись в таблице prefix_list$t,
такую, что префиксы совпадают и префикс имеет максимальную длину.

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

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

Тестовые данные:

Код: plsql

1.
2.
3.
4.
5.
6.

create table prefix_list$t as -- 100 000 rows
          select 'abc'   as prefix from dual
union all select 'def'   as prefix from dual
union all select 'def1'  as prefix from dual
union all select 'def12' as prefix from dual
;

Код: plsql

create unique index prefix_list$idx on prefix_list$t(prefix);

Код: plsql

1.
2.
3.
4.
5.
6.

create table data_4_prefix$t as -- 10 000 000 rows
          select 'abc22'  as expr_w_prefix from dual
union all select 'def19'  as expr_w_prefix from dual
union all select 'def121' as expr_w_prefix from dual
union all select 'def12'  as expr_w_prefix from dual
;

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

create or replace function get_max_len_prefix(p_str varchar2, p_prefix_len number := 10) return prefix_list$t.prefix%type is
  v_ret_val prefix_list$t.prefix%type;
begin
  select prefix into v_ret_val from prefix_list$t where prefix = substr(p_str, 1, p_prefix_len);
  return v_ret_val;
exception 
  when no_data_found then
    if p_prefix_len > 1 then
      v_ret_val := get_max_len_prefix(p_str, p_prefix_len-1);
    else
      v_ret_val := null;
    end if;  
    return v_ret_val;
end get_max_len_prefix;

Варианты решений:

Код: plsql

1.
2.
3.

select d.* -- variant 1 (context switching)
  ,get_max_len_prefix(expr_w_prefix) as max_len_prefix 
from data_4_prefix$t d;

Код: plsql

1.
2.
3.
4.
5.
6.

select d.* -- variant 2 (index not used)
  ,(select substr(max(trim(to_char(length(prefix),'00'))||prefix),3) from prefix_list$t where prefix = substr(expr_w_prefix, 1, length(prefix)))
  as max_len_prefix_1 
  ,(select substr(max(trim(to_char(length(prefix),'00'))||prefix),3) from prefix_list$t where expr_w_prefix like prefix||'%')
  as max_len_prefix_2 
from data_4_prefix$t d;

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

select d.* -- variant 3 (too many chars, support difficult)
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1,10))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 9))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 8))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 7))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 6))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 5))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 4))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 3))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 2))
  ,    (select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 1))
  )))))))))
  as max_len_prefix 
from data_4_prefix$t d;

Удаление тестовых объектов БД.

Код: plsql

1.
2.
3.

drop function get_max_len_prefix;
drop table prefix_list$t;
drop table data_4_prefix$t;

...

Рейтинг:

0 / 0

28.09.2016, 15:46:40

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

Поиск префикса максимальной длины

#39317088

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

Aandr В приведенных решениях есть недостатки: переключение контекста,

Код: plsql

1.
2.
3.

  when no_data_found then
    if p_prefix_len > 1 then
      v_ret_val := get_max_len_prefix(p_str, p_prefix_len-1);

Быдлокод.
Как можно выбрать максимум подходящую строку из таблицы?

...

Рейтинг:

0 / 0

28.09.2016, 16:02:33

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

Поиск префикса максимальной длины

#39317094

Sayan Malakshinov

Модератор форума

Откуда: Мск

Сообщения: 5 731

Рейтинг: 0 / 0

Aandr,

без индекса:

Код: plsql

1.
2.
3.
4.
5.
6.
7.

select 
   t.expr_w_prefix,
   (select max(l.prefix)keep(dense_rank first order by length(l.prefix) desc)
    from prefix_list$t l
    where t.expr_w_prefix like l.prefix||'%'
   ) prefix
from data_4_prefix$t t

с индексом:

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.

select 
   t.expr_w_prefix,
   (select/*+ leading(g l) use_nl(l) */ max(prefix)keep(dense_rank first order by length(prefix) desc)
    from 
       xmltable('0 to xs:integer(.)' passing length(t.expr_w_prefix) columns n int path '.') g
      ,prefix_list$t l
    where l.prefix = substr(t.expr_w_prefix,1,length(t.expr_w_prefix)-g.n)
   ) prefix
from data_4_prefix$t t

не смотреть
А это оптимимальная но использовать нельзя, т.к. не надежно

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

select 
   t.expr_w_prefix,
   (select/*+ leading(g l) use_nl(l) */ prefix
    from 
       xmltable('0 to xs:integer(.)' passing length(t.expr_w_prefix) columns n int path '.') g
      ,prefix_list$t l
    where l.prefix = substr(t.expr_w_prefix,1,length(t.expr_w_prefix)-g.n)
    and rownum=1
   ) prefix
from data_4_prefix$t t

надо еще подумать как это же сделать, но правильно :)

...

Рейтинг:

0 / 0

28.09.2016, 16:09:20

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

Поиск префикса максимальной длины

#39317100

Sayan Malakshinov

Модератор форума

Откуда: Мск

Сообщения: 5 731

Рейтинг: 0 / 0

Elic,

блин, точно, перемудрил

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.

select 
   t.expr_w_prefix,
   (select/*+ index_desc(l (prefix)) */ max(l.prefix)keep(dense_rank first order by l.prefix desc)
    from prefix_list$t l
    where 
          l.prefix <= t.expr_w_prefix
      and t.expr_w_prefix like l.prefix||'%'
   ) prefix
from data_4_prefix$t t

...

Рейтинг:

0 / 0

28.09.2016, 16:12:12

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

Поиск префикса максимальной длины

#39317116

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

xtenderблин, точно, перемудрил Ага, без stopkey-я смешно до слёз.

...

Рейтинг:

0 / 0

28.09.2016, 16:29:07

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

Поиск префикса максимальной длины

#39317144

Sayan Malakshinov

Модератор форума

Откуда: Мск

Сообщения: 5 731

Рейтинг: 0 / 0

Elic,

а у меня под рукой 11.2 только, на нем stopkey не получается нормально...

...

Рейтинг:

0 / 0

28.09.2016, 16:43:24

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

Поиск префикса максимальной длины

#39317148

Sayan Malakshinov

Модератор форума

Откуда: Мск

Сообщения: 5 731

Рейтинг: 0 / 0

Elic,

на 12с сделал бы с fetch first rows, хотя там и в подзапросы можно глубже 1-го уровня пропихивать, но для 11 не вижу нормального решения

...

Рейтинг:

0 / 0

28.09.2016, 16:44:47

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

Поиск префикса максимальной длины

#39317168

Sayan Malakshinov

Модератор форума

Откуда: Мск

Сообщения: 5 731

Рейтинг: 0 / 0

xtenderElic,

на 12с сделал бы с fetch first rows, хотя там и в подзапросы можно глубже 1-го уровня пропихивать, но для 11 не вижу нормального решенияПроверил и вспомнил, что я уже натыкался на то, что max()keep(dense_rank first/last) не оптимизируется с fetch first rows. Так что только латералы:

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

select 
   t.expr_w_prefix,
   l.prefix
from data_4_prefix$t t
    ,lateral(
       select prefix
       from (
             select/*+ index_desc(l (prefix)) */ l.prefix
             from prefix_list$t l
             where 
                   l.prefix <= t.expr_w_prefix
               and t.expr_w_prefix like l.prefix||'%'
             order by l.prefix desc
            )
       where rownum=1
     ) l

...

Рейтинг:

0 / 0

28.09.2016, 17:02:03

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

Поиск префикса максимальной длины

#39317169

Aandr

Гость

ElicAandr В приведенных решениях есть недостатки: переключение контекста,

Код: plsql

1.
2.
3.

  when no_data_found then
    if p_prefix_len > 1 then
      v_ret_val := get_max_len_prefix(p_str, p_prefix_len-1);

Быдлокод.

Функцию можно изменить так:

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.

create or replace function get_max_len_prefix_v2(p_str varchar2, p_prefix_len number := 10) return prefix_list$t.prefix%type is
begin
  for i in reverse 1..p_prefix_len loop
    for rr in (select prefix from prefix_list$t where prefix = substr(p_str, 1, i)) loop
      return rr.prefix;
    end loop; -- rr
  end loop; -- i
  return null;
end get_max_len_prefix_v2;

...

Рейтинг:

0 / 0

28.09.2016, 17:02:04

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

Поиск префикса максимальной длины

#39317181

Aandr

Гость

Elic, xtender спасибо, но

Код: plsql

Oracle Database 11g Enterprise Edition Release 11.2.0.4.0 - 64bit Production.

...

Рейтинг:

0 / 0

28.09.2016, 17:11:05

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

Поиск префикса максимальной длины

#39317189

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

xtenderТак что только латералы:И PL/SQL.
Но ты, Саян, в ссылке не заметил главного - NLS-зависимости:

Код: plsql

1.
2.

|*  6 |      SORT ORDER BY STOPKEY       |                 |     1 |     5 |     2  (50)| 00:00:01 |
|*  7 |       INDEX RANGE SCAN DESCENDING| PREFIX_LIST$IDX |     1 |     5 |     1   (0)| 00:00:01 |

...

Рейтинг:

0 / 0

28.09.2016, 17:22:22

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

Поиск префикса максимальной длины

#39317191

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

AandrФункцию можно изменить так:

Код: plsql

for i

Это те же яйца, только в профиль.

...

Рейтинг:

0 / 0

28.09.2016, 17:23:12

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

Поиск префикса максимальной длины

#39317206

Sayan Malakshinov

Модератор форума

Откуда: Мск

Сообщения: 5 731

Рейтинг: 0 / 0

ElicНо ты, Саян, в ссылке не заметил главного - NLS-зависимости:[SRC plsql][/SRC]ну лингвистик вообще убийца проихводительности, особенно в сочетании с функцией и функциональными индексами, поэтому у меня всегда binary

...

Рейтинг:

0 / 0

28.09.2016, 17:36:32

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

Поиск префикса максимальной длины

#39317228

Aandr

Гость

Остановился на таком варианте

Код: plsql

1.
2.
3.
4.

select d.* -- variant 4
  ,(select substr(max(lpad(length(prefix),2,'0')||prefix),3) from prefix_list$t where prefix <= expr_w_prefix and expr_w_prefix like prefix||'%') 
  as max_len_prefix 
from data_4_prefix$t d;

...

Рейтинг:

0 / 0

28.09.2016, 18:07:46

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

Поиск префикса максимальной длины

#39317230

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

AandrОстановился на таком вариантеКакова кардинальность prefix_list$t?

...

Рейтинг:

0 / 0

28.09.2016, 18:14:15

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

Поиск префикса максимальной длины

#39317233

Aandr

Гость

Elic,

10 000 000

...

Рейтинг:

0 / 0

28.09.2016, 18:22:32

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

Поиск префикса максимальной длины

#39317235

Aandr

Гость

AandrElic,

10 000 000

Ошибся

Код: plsql

1.
2.

prefix_list$t -- 100 000 rows
data_4_prefix$t -- 10 000 000 rows

...

Рейтинг:

0 / 0

28.09.2016, 18:24:20

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

Поиск префикса максимальной длины

#39317239

Aandr

Гость

Если префиксы только цифровые, то можно так

Код: plsql

1.
2.
3.

select d.* -- variant 5
  ,(select max(prefix) from prefix_list$t where prefix <= expr_w_prefix and expr_w_prefix like prefix||'%') as max_len_prefix 
from data_4_prefix$t d;

...

Рейтинг:

0 / 0

28.09.2016, 18:27:04

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

Поиск префикса максимальной длины

#39317246

Elic

Участник

Сообщения: 30 360

Рейтинг: 0 / 0

Aandr

Код: plsql

prefix_list$t -- 100 000 rows

Тогда ты остановился на непроизводительном варианте: каждый поиск будет шерстить в среднем половину индекса последовательным перебором.

...

Рейтинг:

0 / 0

28.09.2016, 18:34:50

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

Поиск префикса максимальной длины

#39317335

Решение от Q u a d r o

Гость

Aandr,

помогите с sql-запросом
как вариант

...

Рейтинг:

0 / 0

28.09.2016, 21:17:10

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

Поиск префикса максимальной длины

#39317338

Решение от Q u a d r o

Гость

100 000 префиксов конечно многовато, то зато хорошо параллелится функция...

...

Рейтинг:

0 / 0

28.09.2016, 21:21:10

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

Поиск префикса максимальной длины

#39317371

connect_by_isleaf

Гость

Решение от Q u a d r o100 000 префиксоввероятно имеют множество совпадений по началу и правильнее представить их в виде дерева однобукв.

...

Рейтинг:

0 / 0

29.09.2016, 00:00:34

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

Поиск префикса максимальной длины

#39317404

Добрый Э - Эх

Гость

Aandr[/src]

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

select d.* -- variant 3 (too many chars, support difficult)
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1,10))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 9))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 8))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 7))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 6))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 5))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 4))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 3))
  ,nvl((select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 2))
  ,    (select prefix from prefix_list$t where prefix = substr(expr_w_prefix, 1, 1))
  )))))))))
  as max_len_prefix 
from data_4_prefix$t d;

ну, если скалярные подзапросы переписать в джойны, то вполне себе решение может получиться. Единственное, что "too many chars, support difficult" такими же и останутся:

Код: plsql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

select /*variant 3 (too many chars, support difficult)*/
   d.*
  ,coalesce( pl_10.prefix,pl_09.prefix,pl_08.prefix,pl_07.prefix,pl_06.prefix
            ,pl_05.prefix,pl_04.prefix,pl_03.prefix,pl_02.prefix,pl_01.prefix
           ) as max_len_prefix 
from data_4_prefix$t d
left join prefix_list$t pl_10 on pl_0.prefix = substr(d.expr_w_prefix, 1, 10)
left join prefix_list$t pl_09 on pl_0.prefix = substr(d.expr_w_prefix, 1, 09)
left join prefix_list$t pl_08 on pl_0.prefix = substr(d.expr_w_prefix, 1, 08)
left join prefix_list$t pl_07 on pl_0.prefix = substr(d.expr_w_prefix, 1, 07)
left join prefix_list$t pl_06 on pl_0.prefix = substr(d.expr_w_prefix, 1, 06)
left join prefix_list$t pl_05 on pl_0.prefix = substr(d.expr_w_prefix, 1, 05)
left join prefix_list$t pl_04 on pl_0.prefix = substr(d.expr_w_prefix, 1, 04)
left join prefix_list$t pl_03 on pl_0.prefix = substr(d.expr_w_prefix, 1, 03)
left join prefix_list$t pl_02 on pl_0.prefix = substr(d.expr_w_prefix, 1, 02)
left join prefix_list$t pl_01 on pl_0.prefix = substr(d.expr_w_prefix, 1, 01);

...

Рейтинг:

0 / 0

29.09.2016, 05:28:12

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

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

Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск префикса максимальной длины

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

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

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

start [/forum/topic.php?fid=52&msg=39317144&tid=1887363]:	0ms
get settings:	9ms
get forum list:	13ms
check forum access:	8ms
check topic access:	8ms
track hit:	185ms
get topic data:	9ms
get forum data:	2ms
get page messages:	58ms
get tp. blocked users:	1ms
others:	231ms

total:	524ms

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