Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск префикса максимальной длины / 23 сообщений из 23, страница 1 из 1
28.09.2016, 15:46:40
    #39317067
Aandr
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
1.
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, 16:02:33
    #39317088
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
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:09:20
    #39317094
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
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:12:12
    #39317100
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
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:29:07
    #39317116
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
xtenderблин, точно, перемудрил Ага, без stopkey-я смешно до слёз.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 16:43:24
    #39317144
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Elic,

а у меня под рукой 11.2 только, на нем stopkey не получается нормально...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 16:44:47
    #39317148
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Elic,

на 12с сделал бы с fetch first rows, хотя там и в подзапросы можно глубже 1-го уровня пропихивать, но для 11 не вижу нормального решения
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 17:02:03
    #39317168
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
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:04
    #39317169
Aandr
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:11:05
    #39317181
Aandr
Aandr
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Elic, xtender спасибо, но
Код: plsql
1.
Oracle Database 11g Enterprise Edition Release 11.2.0.4.0 - 64bit Production.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 17:22:22
    #39317189
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
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:23:12
    #39317191
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
AandrФункцию можно изменить так:
Код: plsql
1.
for i

Это те же яйца, только в профиль.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 17:36:32
    #39317206
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
ElicНо ты, Саян, в ссылке не заметил главного - NLS-зависимости:[SRC plsql][/SRC]ну лингвистик вообще убийца проихводительности, особенно в сочетании с функцией и функциональными индексами, поэтому у меня всегда binary
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 18:07:46
    #39317228
Aandr
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:14:15
    #39317230
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
AandrОстановился на таком вариантеКакова кардинальность prefix_list$t?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 18:22:32
    #39317233
Aandr
Aandr
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Elic,

10 000 000
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 18:24:20
    #39317235
Aandr
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:27:04
    #39317239
Aandr
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:34:50
    #39317246
Elic
Elic
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Aandr
Код: plsql
1.
prefix_list$t -- 100 000 rows

Тогда ты остановился на непроизводительном варианте: каждый поиск будет шерстить в среднем половину индекса последовательным перебором.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 21:17:10
    #39317335
Решение от Q u a d r o
Решение от Q u a d r o
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Aandr,

помогите с sql-запросом
как вариант
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2016, 21:21:10
    #39317338
Решение от Q u a d r o
Решение от Q u a d r o
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
100 000 префиксов конечно многовато, то зато хорошо параллелится функция...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.09.2016, 00:00:34
    #39317371
connect_by_isleaf
connect_by_isleaf
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск префикса максимальной длины
Решение от Q u a d r o100 000 префиксоввероятно имеют множество совпадений по началу и правильнее представить их в виде дерева однобукв.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.09.2016, 05:28:12
    #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
| Ответить | Цитировать | Написать  
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск префикса максимальной длины / 23 сообщений из 23, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 360ms
Закрыть
start [/forum/topic.php?fid=52&mobile=1&tid=1887363]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 76ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 33ms
get tp. blocked users:
 1ms
others: 211ms
total:  360ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]