ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Близкострочные операции
25 сообщений из 52, страница 1 из 3
  1  все
Близкострочные операции
    #40011054
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
Задумался - а как в SQL делается поиск не по строчке, не по группе, а по отношению к соседним строчкам (когда задан сортировочный порядок, естессно).

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

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

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

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

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

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

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

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

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

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

Есть более простая но похожая задача - эффективно найти самый большой промежуток в уже отсортированном ряде чисел, средствами SQL не используя LAG().
...
Рейтинг: 0 / 0
23.10.2020, 08:01
| Ответить | Цитировать | Написать  
Близкострочные операции
    #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:22
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011077
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andreymx
Участник
локальный минимум - это когда ближайшие левое и правое значение больше среднего?
...
Рейтинг: 0 / 0
23.10.2020, 08:31
| Ответить | Цитировать | Написать  
Близкострочные операции
    #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:41
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011082
123йй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
123йй
Участник
andreymx
не усложняй.ему подходит Lag. поэтому
если значание слева и справа больше - значит это локальный минимум
...
Рейтинг: 0 / 0
23.10.2020, 08:43
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011086
Фотография env
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
env
Участник
НеофитSQL
Я вас тут раньше не видел, вы наверное новенький.

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

Действительно, все, кто по какой-то причине не стал отвечать в предыдущих ваших темах точно новички. Не в профиле же смотреть, с какого года человек на форуме.
...
Рейтинг: 0 / 0
23.10.2020, 09:20
| Ответить | Цитировать | Написать  
Близкострочные операции
    #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:50
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011158
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
graycode
Гость
123йй
не усложняй.ему подходит Lag.

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

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

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

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

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

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

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

Что нужно, что нет, да кто же этого неофита знает что ему нужно, понятно только одно, нахождением экстремумов функций он тоже не занимался))
...
Рейтинг: 0 / 0
23.10.2020, 14:06
| Ответить | Цитировать | Написать  
Близкострочные операции
    #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:09
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011237
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
xtender,

1,2,2,2,3

ps
1,2,3

3,2,1

1

.....
stax
...
Рейтинг: 0 / 0
23.10.2020, 14:50
| Ответить | Цитировать | Написать  
Близкострочные операции
    #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, 15:42
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011284
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
xtender

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


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

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

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

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

Спасибо, очень полезный прием. Я копал в этом направлении, но пока не вспомнил про rownum, мой подход требовал ключа без дырок.
...
Рейтинг: 0 / 0
23.10.2020, 16:36
| Ответить | Цитировать | Написать  
Близкострочные операции
    #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, 16:58
| Ответить | Цитировать | Написать  
Близкострочные операции
    #40011310
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
Stax
xtender

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


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

.....
stax


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

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

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

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

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

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


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