Гость
Войти | Профиль | Очистить
Действия ...
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Найти ближайший PK / 19 сообщений из 19, страница 1 из 1
17.11.2020, 17:06
    #40019571
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
Что-то не вижу простого решения.

Задана таблица с числовым PK, нужно для одного конкретного числа найти ближайший к этому числу PK наиболее эффективным способом. Если таковых два, то наименьший из двух.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
with t(id) as (
select 2 from dual union all
select 3 from dual union all
select 5 from dual union all
select 7 from dual union all
select 11 from dual union all
select 13 from dual union all
select 17 from dual union all
select 19 from dual union all
select 23 from dual union all
select 29 from dual union all
select 31 from dual
)
select id from t order by abs(26-id), id
fetch first 1 rows only



Учитывая что в примере сортировка идет по значению функции, не закончится ли это полным перебором?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:22
    #40019579
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
При правильной организации данных решается за шесть логических чтений практически независимо от размера таблицы с данными.
При относительно небольших объемах и высокой потребности в производительности можно решить на ассоциативном массиве PL/SQL ценой его однократной загрузки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:23
    #40019581
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
НеофитSQL
Учитывая что в примере сортировка идет по значению функции

Зачем?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:42
    #40019594
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
andrey_anonymous
При правильной организации данных решается за шесть логических чтений практически независимо от размера таблицы с данными.
При относительно небольших объемах и высокой потребности в производительности можно решить на ассоциативном массиве PL/SQL ценой его однократной загрузки.


Поиск по B-tree неограниченного размера за шесть чтений? Вы конечно шутите.

Чудес не бывает, хотелось бы за O(log N) в SQL, без повторных поисков по индексу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:44
    #40019595
env
env
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
НеофитSQL,

Тупо в лоб
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
SQL> var id number;
SQL> exec :id := 26;

SQL>  with t(id) as (
  2  select 2 from dual union all
  3  select 3 from dual union all
  4  select 5 from dual union all
  5  select 7 from dual union all
  6  select 11 from dual union all
  7  select 13 from dual union all
  8  select 17 from dual union all
  9  select 19 from dual union all
 10  select 23 from dual union all
 11  select 29 from dual union all
 12  select 31 from dual
 13  ),
 14  minmax as (select min(id) id from t where id > :id union all select max(id) from t where id <= :id)
 15 select min(id) keep (dense_rank first order by abs(:id-id)) id from minmax
 16 /

        ID
----------
        23
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:47
    #40019599
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
graycode
НеофитSQL
Учитывая что в примере сортировка идет по значению функции

Зачем?


Так в примере, чтоб было понятно какой ожидается результат.
Я подозреваю что пример неэффективен, т.к. функция может помешать оптимизатору, особенно если функция посложнее чем abs()
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:50
    #40019602
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
НеофитSQL
Поиск по B-tree неограниченного размера за шесть чтений? Вы конечно шутите.
Чудес не бывает, хотелось бы за O(log N) в SQL, без повторных поисков по индексу.

:)
Вам ведь уже говорили, что Btree в Oracle нифига не бинарный.
До миллионов (десятков миллионов) записей задача решается за указанные расходы, которые требуются на два индексных поиска (каждый по 2 логических чтения индекса Blevel=2 + одно за записью в таблице, if any) - один вверх и один вниз.
В принципе, env показал один из способов воспользоваться таким поиском, но не показал структуры и планы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:51
    #40019603
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
env
НеофитSQL,

Тупо в лоб
 
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
SQL> var id number;
SQL> exec :id := 26;

SQL>  with t(id) as (
  2  select 2 from dual union all
  3  select 3 from dual union all
  4  select 5 from dual union all
  5  select 7 from dual union all
  6  select 11 from dual union all
  7  select 13 from dual union all
  8  select 17 from dual union all
  9  select 19 from dual union all
 10  select 23 from dual union all
 11  select 29 from dual union all
 12  select 31 from dual
 13  ),
 14  minmax as (select min(id) id from t where id > :id union all select max(id) from t where id <= :id)
 15 select min(id) keep (dense_rank first order by abs(:id-id)) id from minmax
 16 /

        ID
----------
        23



Спасибо, сравниваю планы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 17:56
    #40019605
env
env
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
НеофитSQL,

Да что там сравнивать, особенно, если индекс есть
Код: 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.
SQL> create table dropme_t as select level id from dual connect by level < 1e5 order by dbms_random.value;

Table created.

SQL> create index dropme_t_ix on dropme_t(id);

Index created.

SQL> set autotrace on explain stat
SQL> with
  2  minmax as (
  3   select min(id) id from dropme_t where id > :id union all select max(id) from dropme_t where id <= :id
  4  )
  5  select min(id) keep (dense_rank first order by abs(:id-id)) id from minmax
  6  /

        ID
----------
        26

Execution Plan
----------------------------------------------------------
Plan hash value: 1972860826

-----------------------------------------------------------------------------------------------
| Id  | Operation                       | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |             |     1 |    13 |     4   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE                 |             |     1 |    13 |            |          |
|   2 |   VIEW                          |             |     2 |    26 |     4   (0)| 00:00:01 |
|   3 |    UNION-ALL                    |             |       |       |            |          |
|   4 |     SORT AGGREGATE              |             |     1 |     5 |            |          |
|   5 |      FIRST ROW                  |             |     1 |     5 |     2   (0)| 00:00:01 |
|*  6 |       INDEX RANGE SCAN (MIN/MAX)| DROPME_T_IX |     1 |     5 |     2   (0)| 00:00:01 |
|   7 |     SORT AGGREGATE              |             |     1 |     5 |            |          |
|   8 |      FIRST ROW                  |             |     1 |     5 |     2   (0)| 00:00:01 |
|*  9 |       INDEX RANGE SCAN (MIN/MAX)| DROPME_T_IX |     1 |     5 |     2   (0)| 00:00:01 |
-----------------------------------------------------------------------------------------------

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

   6 - access("ID">TO_NUMBER(:ID))
   9 - access("ID"<=TO_NUMBER(:ID))


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          4  consistent gets
          0  physical reads
          0  redo size
        353  bytes sent via SQL*Net to client
        612  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:03
    #40019610
НеофитSQL
НеофитSQL
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
Решение env "в лоб" выглядит оптимально. Не вижу как можно быстрее.

Индекс конечно есть - это основной ключ.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:09
    #40019612
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
НеофитSQL,

Решение в "лоб" можно записать так:
Код: plsql
1.
2.
3.
select least(coalesce(a, b), coalesce(b, a)) as id
  from (select (select min(id) id from t where id > :id) as a
             , (select max(id) from t where id <= :id) as b from dual)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:10
    #40019613
andrey_anonymous
andrey_anonymous
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
НеофитSQL
Решение env "в лоб" выглядит оптимально. Не вижу как можно быстрее.

"Быстрее" - нет, план аналогичной эффективности попроще - да, можно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:10
    #40019614
SY
SY
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
env

Тупо в лоб


И с кaкого перепуга 3 GROUP BY? А главное тут все зависит от наличия индекса по id. Без него 2 FULL SCAN плюс 3 SORT AGGREGATE что в разы хуже. При отсутствии индекса

Код: plsql
1.
2.
select id from t order by abs(26-id), id
fetch first 1 rows only



совсем неплох: 1 FULL SCAN + WINDOWS SORT PUSHED RANK который согласно Jonathan Lewis ( 12c First N ) 'may still have to generate the entire pre-sorted data set". Можно поколдовать:

Код: 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.
explain plan for
select id from test order by abs(26-id), id
fetch first 1 rows only
/
select * from table(dbms_xplan.display)
/
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 1672797393

----------------------------------------------------------------------------------
| Id  | Operation                 | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT          |      |     1 |    52 |     5  (40)| 00:00:01 |
|   1 |  SORT ORDER BY            |      |     1 |    52 |     5  (40)| 00:00:01 |
|*  2 |   VIEW                    |      |     1 |    52 |     4  (25)| 00:00:01 |
|*  3 |    WINDOW SORT PUSHED RANK|      |    11 |    33 |     4  (25)| 00:00:01 |
|   4 |     TABLE ACCESS FULL     | TEST |    11 |    33 |     3   (0)| 00:00:01 |
----------------------------------------------------------------------------------

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

   2 - filter("from$_subquery$_002"."rowlimit_$$_rownumber"<=1)
   3 - filter(ROW_NUMBER() OVER ( ORDER BY ABS(26-"ID"),"ID")<=1)

17 rows selected.

explain plan for
with t as (
           select  id
             from  test
             order by abs(26-id),id
           )
select  id
  from  t
  where rownum <= 2
/
select * from table(dbms_xplan.display)
/

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 1607412806

--------------------------------------------------------------------------------
| Id  | Operation               | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |      |     2 |    26 |     4  (25)| 00:00:01 |
|*  1 |  COUNT STOPKEY          |      |       |       |            |          |
|   2 |   VIEW                  |      |    11 |   143 |     4  (25)| 00:00:01 |
|*  3 |    SORT ORDER BY STOPKEY|      |    11 |    33 |     4  (25)| 00:00:01 |
|   4 |     TABLE ACCESS FULL   | TEST |    11 |    33 |     3   (0)| 00:00:01 |
--------------------------------------------------------------------------------

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

   1 - filter(ROWNUM<=2)
   3 - filter(ROWNUM<=2)

17 rows selected.

SQL>



Ну а если есть индекс, то уж:

Код: 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.
explain plan for
with t as (
           select  max(id) id
             from  test
             where id <= 26
          )
select  case
          when id is not null then id
          else (
                select  min(id)
                  from  test
                  where id > 26
               )
        end id
  from  t
/
select * from table(dbms_xplan.display)
/

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------------------------------------------------------
Plan hash value: 3863477731

------------------------------------------------------------------------------------------
| Id  | Operation                     | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |          |     1 |    13 |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE               |          |     1 |     3 |            |          |
|   2 |   FIRST ROW                   |          |     1 |     3 |     1   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN (MIN/MAX) | TEST_IDX |     1 |     3 |     1   (0)| 00:00:01 |
|   4 |  VIEW                         |          |     1 |    13 |     1   (0)| 00:00:01 |
|   5 |   SORT AGGREGATE              |          |     1 |     3 |            |          |
|   6 |    FIRST ROW                  |          |     1 |     3 |     1   (0)| 00:00:01 |
|*  7 |     INDEX RANGE SCAN (MIN/MAX)| TEST_IDX |     1 |     3 |     1   (0)| 00:00:01 |
------------------------------------------------------------------------------------------

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

   3 - access("ID">26)
   7 - access("ID"<=26)

20 rows selected.

SQL>



SY.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:23
    #40019618
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
graycode
НеофитSQL,

Решение в "лоб" можно записать так:
Код: plsql
1.
2.
3.
select least(coalesce(a, b), coalesce(b, a)) as id
  from (select (select min(id) id from t where id > :id) as a
             , (select max(id) from t where id <= :id) as b from dual)


нельзя((
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:25
    #40019620
SY
SY
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
Кстати, план не отражает short circuit:

Код: 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.
create or replace
  function zerodivide
    return number
    is
    begin
        return 1 / 0;
end;
/
select  case
          when deptno is not null then deptno
          else (
                select  zerodivide
                  from  dept
                  where rownum = 1
               )
        end x
  from  dept
/

         X
----------
        10
        20
        30
        40

SQL>



SY.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 18:48
    #40019626
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
SY
Ну а если есть индекс, то уж:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
explain plan for
with t as (
           select  max(id) id
             from  test
             where id <= 26
          )
select  case
          when id is not null then id
          else (
                select  min(id)
                  from  test
                  where id > 26
               )
        end id
  from  t


Это решает задачу поиска минимального из соседних, а не ближайшего и ближайших может быть два, если они на одинаковом расстоянии.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 19:19
    #40019641
SY
SY
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
[quot graycode#22234075]
SY

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


Упс. Да, MIN и MAX придется вычислять всегда.

MATCH_RECOGNIZE для забавы:

Код: 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.
select  case
          when abs(fid - 26) <= abs(lid - 26) then fid
          else lid
        end closest_id
  from  test
  match_recognize(
                  order by id
                  measures id fid,
                           nvl(next(id),id) lid
                  pattern(p)
                  define p as (id <= 26 or prev(id) is null) and nvl(next(id),26) >= 26
                 )
/

CLOSEST_ID
----------
        23


Execution Plan
----------------------------------------------------------
Plan hash value: 3948817958

-------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                              | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                       |          |    11 |   286 |     1   (0)| 00:00:01 |
|   1 |  VIEW                                                  |          |    11 |   286 |     1   (0)| 00:00:01 |
|   2 |   MATCH RECOGNIZE BUFFER DETERMINISTIC FINITE AUTOMATON|          |    11 |    33 |     1   (0)| 00:00:01 |
|   3 |    INDEX FULL SCAN                                     | TEST_IDX |    11 |    33 |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------------------------



SY.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 19:51
    #40019652
graycode
graycode
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
env

Код: plsql
1.
2.
3.
4.
5.
...

        ID
----------
        23


А где 29 ?))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.11.2020, 19:56
    #40019656
SY
SY
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти ближайший PK
graycode

А где 29 ?))


"Если таковых два, то наименьший из двух".

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


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