Гость
Войти | Профиль | Очистить
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Близкострочные операции / 25 сообщений из 52, страница 1 из 3
  1  все
23.10.2020, 02:26
    #40011054
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
Задумался - а как в SQL делается поиск не по строчке, не по группе, а по отношению к соседним строчкам (когда задан сортировочный порядок, естессно).

Нашел LAG(), что делает такие операции простыми, но непонятно как справлялись до нее. Очевидное решение - циклом, но тогда оптимизатор не у дел.

Например, не используя встроенную функцию LAG или подобные, как можно быстро из таблицы в миллионы строк найти все локальные минимумы для val?

В таблице две колонки: id/PK и val/number.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 07:22
    #40011066
123йй
123йй
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQLЗадумался
ты не думай, ты читай
читай
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 08:01
    #40011070
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
123йй
НеофитSQLЗадумался

ты не думай, ты читай
читай

Я вас тут раньше не видел, вы наверное новенький.

В Оракле сортировка делается оператором "order by".
Какой именно алгоритм, я не знаю, но сортировка по индексу очень эффективна, свою писать вряд ли есть необходимость.

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

Например.в ряде 3 2 7 4 3 8 локальные минимумы находятся в позициях 2 и 5.

С помощью цикла, или встроенной функции Lag() эта задача решается в пару строчек, второй эффективнее первого.

Мне интересно, среди людей которые помнят разницу между сортировкой и поиском минимумов, встречался ли кто-то с такой задачей?

Есть более простая но похожая задача - эффективно найти самый большой промежуток в уже отсортированном ряде чисел, средствами SQL не используя LAG().
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 08:22
    #40011074
Вячеслав Любомудров
Вячеслав Любомудров
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
Обычно это делалось через упорядочивание, нумерование, и самосоединение (self-join) или деревяшка (connect by)
В этом случае есть гарантия что следующая строка будет как номер текущей+1
Если есть подходящий индекс, то можно по минимумам/максимумам превышающих/непревышающих значений порядка
 
Что-то типо такого
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
SQL> create table t_neofit (id primary key, val) as select rownum, trunc(dbms_random.value(1, 1000)) from dual connect by level <= 10;

Table created.

SQL> with t as (
  2       select a.id, a.val, b.id next_id, b.val next_val
  3       from t_neofit a, t_neofit b
  4       where b.id=(select min(id) from t_neofit where id > a.id)
  5  ), d as (
  6       select t.*, next_val-val diff, sign(next_val-val) sdiff from t
  7  ), diffs as (
  8       select a.*, b.next_id next_next_id, b.next_val next_next_val, b.diff next_diff, b.sdiff next_sdiff
  9       from d a, d b
 10       where b.id=(select min(id) from t_neofit where id > a.id)
 11  )
 12  select id from_id, next_id id, next_next_id to_id, val from_value, next_val value, next_next_val to_value,
 13         case when sdiff=-1 and next_sdiff=1 then '*' end minimum
 14   from diffs;

   FROM_ID         ID      TO_ID FROM_VALUE      VALUE   TO_VALUE M
---------- ---------- ---------- ---------- ---------- ---------- -
         1          2          3        272        759        336
         2          3          4        759        336        773 *
         3          4          5        336        773        543
         4          5          6        773        543        182
         5          6          7        543        182        335 *
         6          7          8        182        335        622
         7          8          9        335        622         47
         8          9         10        622         47        139 *

8 rows selected.

SQL> @plan_last

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------
SQL_ID  bhcxzht2xk7sy, child number 0
-------------------------------------
with t as (      select a.id, a.val, b.id next_id, b.val next_val
from t_neofit a, t_neofit b      where b.id=(select min(id) from
t_neofit where id > a.id) ), d as (      select t.*, next_val-val diff,
sign(next_val-val) sdiff from t ), diffs as (      select a.*,
b.next_id next_next_id, b.next_val next_next_val, b.diff next_diff,
b.sdiff next_sdiff      from d a, d b      where b.id=(select min(id)
from t_neofit where id > a.id) ) select id from_id, next_id id,
next_next_id to_id, val from_value, next_val value, next_next_val
to_value,        case when sdiff=-1 and next_sdiff=1 then '*' end
minimum  from diffs

Plan hash value: 2458627781

-----------------------------------------------------------------------------------------------------------------
| Id  | Operation                         | Name                        | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                  |                             |       |       |    19 (100)|          |
|   1 |  TEMP TABLE TRANSFORMATION        |                             |       |       |            |          |
|   2 |   LOAD AS SELECT                  |                             |       |       |            |          |
|   3 |    NESTED LOOPS                   |                             |       |       |            |          |
|   4 |     NESTED LOOPS                  |                             |     1 |    52 |    13   (0)| 00:00:01 |
|   5 |      TABLE ACCESS FULL            | T_NEOFIT                    |    10 |   260 |     3   (0)| 00:00:01 |
|*  6 |      INDEX UNIQUE SCAN            | SYS_C0079998                |     1 |       |     0   (0)|          |
|   7 |       SORT AGGREGATE              |                             |     1 |    13 |            |          |
|   8 |        FIRST ROW                  |                             |     1 |    13 |     1   (0)| 00:00:01 |
|*  9 |         INDEX RANGE SCAN (MIN/MAX)| SYS_C0079998                |     1 |    13 |     1   (0)| 00:00:01 |
|  10 |     TABLE ACCESS BY INDEX ROWID   | T_NEOFIT                    |     1 |    26 |     1   (0)| 00:00:01 |
|* 11 |   FILTER                          |                             |       |       |            |          |
|  12 |    MERGE JOIN CARTESIAN           |                             |     1 |   117 |     4   (0)| 00:00:01 |
|  13 |     VIEW                          |                             |     1 |    65 |     2   (0)| 00:00:01 |
|  14 |      TABLE ACCESS FULL            | SYS_TEMP_0FD9D6611_13C03C8B |     1 |    52 |     2   (0)| 00:00:01 |
|  15 |     BUFFER SORT                   |                             |     1 |    52 |     4   (0)| 00:00:01 |
|  16 |      VIEW                         |                             |     1 |    52 |     2   (0)| 00:00:01 |
|  17 |       TABLE ACCESS FULL           | SYS_TEMP_0FD9D6611_13C03C8B |     1 |    52 |     2   (0)| 00:00:01 |
|  18 |    SORT AGGREGATE                 |                             |     1 |    13 |            |          |
|  19 |     FIRST ROW                     |                             |     1 |    13 |     1   (0)| 00:00:01 |
|* 20 |      INDEX RANGE SCAN (MIN/MAX)   | SYS_C0079998                |     1 |    13 |     1   (0)| 00:00:01 |
-----------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   6 - access("B"."ID"=)
   9 - access("ID">:B1)
  11 - filter("B"."ID"=)
  20 - access("ID">:B1)

Note
-----
   - dynamic sampling used for this statement (level=2)


53 rows selected.

Но профессионалы-разработчики наверное и более лучший вариант подскажут
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 08:31
    #40011077
andreymx
andreymx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
локальный минимум - это когда ближайшие левое и правое значение больше среднего?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 08:41
    #40011080
Stax
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQL

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


зачем lag, есть же match_recognize (в примере какраз ищут W)

гляньте Oracle для профессионалов Том Кайт (есть отличный перевод)
там примеры как "без LAG"
авторSQL — очень мощный язык и лишь очень немногие запросы в нем нельзя создать.
По опыту знаю, что можно придумать хитрый SQL-запрос для получения ответа прак-
тически на любой вопрос относительно любых данных. Однако производительность
некоторых из этих запросов крайне низкая , да и придумать их непросто. Ряд запросов,
которые сложно сформулировать на обычном языке SQL, весьма типичны:
....
Аналитические функции, появившиеся в версии Oracle 8.1.6, создавались для реше-
ния именно этих задач. Они расширяют язык SQL так, что подобные операции не толь-
ко проще записываются, но и быстрее выполняются по сравнению с использованием
чистого языка SQL.


ps
почему 5
Например.в ряде 3 2 7 4 3 8 локальные минимумы находятся в позициях 2 и 5 .


.....
stax
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 08:43
    #40011082
123йй
123йй
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
andreymx
не усложняй.ему подходит Lag. поэтому
если значание слева и справа больше - значит это локальный минимум
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 09:20
    #40011086
env
env
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQL
Я вас тут раньше не видел, вы наверное новенький.

Восхохотамши под лавкою.

Действительно, все, кто по какой-то причине не стал отвечать в предыдущих ваших темах точно новички. Не в профиле же смотреть, с какого года человек на форуме.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 12:50
    #40011155
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQL
Задумался - а как в SQL делается поиск не по строчке, не по группе, а по отношению к соседним строчкам (когда задан сортировочный порядок, естессно).

Нашел LAG(), что делает такие операции простыми, но непонятно как справлялись до нее. Очевидное решение - циклом, но тогда оптимизатор не у дел.

Например, не используя встроенную функцию LAG или подобные, как можно быстро из таблицы в миллионы строк найти все локальные минимумы для val?

В таблице две колонки: id/PK и val/number.

Как же ты любишь забивать гвозди микроскопом и не желаешь учиться))

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

"id/PK и val/number" - таблица представляет собой кучу, первичный ключ не отвечает за последовательность записей, другими словами для твоего ряда 3 2 7 4 3 8 ты должен определить поле по которому ты получишь именно такой порядок сортировкой.

"как справлялись до нее" - императивные языки, но ты можешь написать запрос и без lag, он очень простой, справишься?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 12:55
    #40011158
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
123йй
не усложняй.ему подходит Lag.

На самом деле не подходит, 3 2 7 4 3 3 3 3 2 8.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 12:58
    #40011162
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQL
С помощью цикла, или встроенной функции Lag() эта задача решается в пару строчек, второй эффективнее первого.
бред. На большом наборе(например, попробуй на паре миллионов записей) цикл будет эффективнее. Задача идеально решается с помощью match_recognize, но тебе с твоей 11.2.0.1 он не светит. Решений на оракле вообще масса - еще не перечислены другие аналитические функции (причем аналитический min()over(order by ... rows between 1 preceding and 1 following) гораздо интуитивнее, чем lag(), но ты же доку не читаешь и других функций не знаешь...), рекурсивный cte, model и тд
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 13:02
    #40011168
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
graycode
Как же ты любишь забивать гвозди микроскопом и не желаешь учиться))
+1. Сам себе идиотские ограничения придумывает, да еще и книжки и доку игнорирует


graycode
123йй
не усложняй.ему подходит Lag.

На самом деле не подходит, 3 2 7 4 3 3 3 3 2 8.
пойдут lag/lead, просто следующее должно быть больше текущего
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 13:08
    #40011174
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
xtender
пойдут lag/lead, просто следующее должно быть больше текущего

На "площадке" неизвестно является ли она локальным минимумом, длина ее тоже неизвестна, т.е. если убрать 2, то вся площадка с трешками является локальным минимумом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 13:26
    #40011187
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
graycode,

последняя трешка выведется, а нужно ли реально все выводить? и если нужно, то не лучше ли их сначала в диапазоны свернуть
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 14:02
    #40011207
123йй
123йй
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
graycode
123йй
не усложняй.ему подходит Lag.

На самом деле не подходит, 3 2 7 4 3 3 3 3 2 8.

ты знаешь лучше ТС что ему надо ?
авторС помощью цикла, или встроенной функции Lag() эта задача решается в пару строчек, второй эффективнее первого.

ЗЫж andreymx. не сразу понял какой смысл несет слово "среднее".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 14:06
    #40011210
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
xtender,

Вы правы, если свернуть в диапазоны, то хватит lead/lag.

Что нужно, что нет, да кто же этого неофита знает что ему нужно, понятно только одно, нахождением экстремумов функций он тоже не занимался))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 14:09
    #40011212
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
 
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
with t(n, val) as (select rownum, column_value from table(sys.odcinumberlist(
-1,3,2,7,10,5,5,5,5,3,8,0,0,0,0,1,2,3,-1
)))
select *
from t
match_recognize (
  order by n
  measures 
      first(s.n) as first_n,
      last(s.n) last_n,
      min(s.val) as lmin
  pattern (s+ u+)
  define 
    s as val <= least(prev(val),next(val)),
    u as val > prev(val)
);

   FIRST_N     LAST_N       LMIN
---------- ---------- ----------
         3          3          2
        10         10          3
        12         15          0

+nvl при необходимости обработки крайних точек
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 14:50
    #40011237
Stax
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
xtender,

1,2,2,2,3

ps
1,2,3

3,2,1

1

.....
stax
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 15:42
    #40011264
Sayan Malakshinov
Sayan Malakshinov
Модератор форума
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
Stax,


xtender
+nvl при необходимости обработки крайних точек


 
с крайними точками
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
  with t(n, val) as (select rownum, column_value from table(sys.odcinumberlist(
  1,2,2,2,3
  )))
  select *
  from t
  match_recognize (
    order by n
    measures 
        first(d.n) as first_n,
        last(d.n) last_n,
        min(d.val) as lmin
    --all rows per match with unmatched rows
    pattern (d*)
    define 
      d as (val < prev(val) or prev(val) is null) and nvl(next(val),val) >= d.val
  );


вообще я не думаю, что крайние точки должны учитываться, т.к. у них окрестность не определена
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 16:09
    #40011284
Stax
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
xtender

вообще я не думаю, что крайние точки должны учитываться, т.к. у них окрестность не определена


Неофит ищет минимум (не V|U), поетому карайние надо учитывать
хотя, надо уточнять у бухов

.....
stax
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 16:36
    #40011294
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
Вячеслав Любомудров,

Круто. Я вчера ломал голову как для решения такой задачи селф-джойн таблицу с непоследовательными ID, пока не вспомнил про rownum. D'oh! Наверное и через rank() можно селф-джойнить.

Из вашего примера я вижу что через селф-джойн функция LAG эмулируется, и возможно очень эффективно.

Спасибо, очень полезный прием. Я копал в этом направлении, но пока не вспомнил про rownum, мой подход требовал ключа без дырок.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 16:58
    #40011305
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
xtender
НеофитSQL
С помощью цикла, или встроенной функции Lag() эта задача решается в пару строчек, второй эффективнее первого.
бред. На большом наборе(например, попробуй на паре миллионов записей) цикл будет эффективнее.


Я ожидал, что цикл хуже, т.к. не параллелится. Вот самый короткий цикл для простого случая (без обработки плато, или конечных точек)

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
prev TESTl%ROWTYPE;
diff TEST.val%TYPE;
...

for trow in (select val from TEST order by id)
loop
  if diff < 0 and trow.val > prev.val 
  then 
    -- prev содержит локальный минимум
  end if;
  diff := trow.val -prev.val;
  prev := trow;
end loop;



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

Вы считаете что на двух миллионах строчек цикл Неофита обгонит контору инженеров Оракла на этой несложной задаче?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 17:08
    #40011310
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
Stax
xtender

вообще я не думаю, что крайние точки должны учитываться, т.к. у них окрестность не определена


Неофит ищет минимум (не V|U), поетому карайние надо учитывать
хотя, надо уточнять у бухов

.....
stax


Я не знаю кто такие бухи, но в данном случае интересовался общей идеей поиска по массиву без цикла.
Было несколько полезных ответов, а также упоминания оконных функций и новой для 12.х функции match, о которой я не знал.

Остается нераскрытым вопрос, так ли плох цикл для скорости запроса как его малюют в учебниках и руководствах.
Надеюсь, xtender или другой опытный ораклист это сможет прояснить.
Цикл я написал в другом сообщении, там места для оптимизации немного.
Смотрит на строчки по одной, скорость линейная, индексы не помогают.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 17:19
    #40011317
env
env
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQL
кто такие бухи

Бухгалтеры. Зачастую постановки задач на поиск минимума в цепочке сумм накладных, но с перламутровыми пуговицами, и только если Сатурн был в Тельце три последних дня по производственному календарю Бангладеша, приходят от них. Стас в основном в этой предметной области работает.

НеофитSQL
Цикл я написал в другом сообщении, там места для оптимизации немного

Попробуйте с коллекциями.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
23.10.2020, 17:44
    #40011332
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Близкострочные операции
НеофитSQL
Я ожидал, что цикл хуже, т.к. не параллелится.

Многопоточность в других языках программирования уже отменили?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Близкострочные операции / 25 сообщений из 52, страница 1 из 3
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 183ms
Закрыть
start [/forum/topic.php?fid=52&mobile=1&tid=1880775]:
 0ms
get settings:
 9ms
get forum list:
 12ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 62ms
get topic data:
 12ms
get forum data:
 2ms
get page messages:
 64ms
get tp. blocked users:
 2ms
others: 12ms
total:  183ms
x
x
Закрыть


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