Найти ближайший PK / Oracle

ReSQL.ru

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

Гость

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

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

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

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

Форумы / Oracle [игнор отключен] [закрыт для гостей] / Найти ближайший PK

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

Найти ближайший PK

#40019571

НеофитSQL

Гость

Что-то не вижу простого решения.

Задана таблица с числовым 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:06

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

Найти ближайший PK

#40019579

andrey_anonymous

Участник

Откуда: Москва

Сообщения: 18 719

Рейтинг: 0 / 0

При правильной организации данных решается за шесть логических чтений практически независимо от размера таблицы с данными.
При относительно небольших объемах и высокой потребности в производительности можно решить на ассоциативном массиве PL/SQL ценой его однократной загрузки.

...

Рейтинг:

0 / 0

17.11.2020, 17:22

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

Найти ближайший PK

#40019581

graycode

Гость

НеофитSQL

Учитывая что в примере сортировка идет по значению функции

Зачем?

...

Рейтинг:

0 / 0

17.11.2020, 17:23

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

Найти ближайший PK

#40019594

НеофитSQL

Гость

andrey_anonymous

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

Чудес не бывает, хотелось бы за O(log N) в SQL, без повторных поисков по индексу.

...

Рейтинг:

0 / 0

17.11.2020, 17:42

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

Найти ближайший PK

#40019595

env

Участник

Откуда: Россия, Москва

Сообщения: 6 692

Рейтинг: 0 / 0

Неофит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:44

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

Найти ближайший PK

#40019599

НеофитSQL

Гость

graycode

НеофитSQL

Учитывая что в примере сортировка идет по значению функции

Зачем?

Так в примере, чтоб было понятно какой ожидается результат.
Я подозреваю что пример неэффективен, т.к. функция может помешать оптимизатору, особенно если функция посложнее чем abs()

...

Рейтинг:

0 / 0

17.11.2020, 17:47

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

Найти ближайший PK

#40019602

andrey_anonymous

Участник

Откуда: Москва

Сообщения: 18 719

Рейтинг: 0 / 0

НеофитSQL

Поиск по B-tree неограниченного размера за шесть чтений? Вы конечно шутите.
Чудес не бывает, хотелось бы за O(log N) в SQL, без повторных поисков по индексу.

:)
Вам ведь уже говорили, что Btree в Oracle нифига не бинарный.
До миллионов (десятков миллионов) записей задача решается за указанные расходы, которые требуются на два индексных поиска (каждый по 2 логических чтения индекса Blevel=2 + одно за записью в таблице, if any) - один вверх и один вниз.
В принципе, env показал один из способов воспользоваться таким поиском, но не показал структуры и планы.

...

Рейтинг:

0 / 0

17.11.2020, 17:50

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

Найти ближайший PK

#40019603

НеофитSQL

Гость

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:51

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

Найти ближайший PK

#40019605

env

Участник

Откуда: Россия, Москва

Сообщения: 6 692

Рейтинг: 0 / 0

Неофит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, 17:56

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

Найти ближайший PK

#40019610

НеофитSQL

Гость

Решение env "в лоб" выглядит оптимально. Не вижу как можно быстрее.

Индекс конечно есть - это основной ключ.

...

Рейтинг:

0 / 0

17.11.2020, 18:03

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

Найти ближайший PK

#40019612

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:09

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

Найти ближайший PK

#40019613

andrey_anonymous

Участник

Откуда: Москва

Сообщения: 18 719

Рейтинг: 0 / 0

НеофитSQL

Решение env "в лоб" выглядит оптимально. Не вижу как можно быстрее.

"Быстрее" - нет, план аналогичной эффективности попроще - да, можно.

...

Рейтинг:

0 / 0

17.11.2020, 18:10

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

Найти ближайший PK

#40019614

Участник

Откуда: Middlebury, CT USA

Сообщения: 10 588

Рейтинг: 0 / 0

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

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:10

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

Найти ближайший PK

#40019618

graycode

Гость

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:23

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

Найти ближайший PK

#40019620

Участник

Откуда: Middlebury, CT USA

Сообщения: 10 588

Рейтинг: 0 / 0

Кстати, план не отражает 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:25

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

Найти ближайший PK

#40019626

graycode

Гость

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

Код: 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, 18:48

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

Найти ближайший PK

#40019641

Участник

Откуда: Middlebury, CT USA

Сообщения: 10 588

Рейтинг: 0 / 0

[quot graycode#22234075]

Упс. Да, 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:19

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

Найти ближайший PK

#40019652

graycode

Гость

env

Код: plsql

1.
2.
3.
4.
5.

...

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

А где 29 ?))

...

Рейтинг:

0 / 0

17.11.2020, 19:51

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

Найти ближайший PK

#40019656

Участник

Откуда: Middlebury, CT USA

Сообщения: 10 588

Рейтинг: 0 / 0

graycode

А где 29 ?))

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

SY.

...

Рейтинг:

0 / 0

17.11.2020, 19:56

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

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

Форумы / Oracle [игнор отключен] [закрыт для гостей] / Найти ближайший PK

Цитировать

Написать

Автор*:

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

Тема*:

Сообщение

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

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

Автор:

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

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

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

Вложение:

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

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

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

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

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

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

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

start [/forum/topic.php?fid=52&msg=40019605&tid=1880706]:	0ms
get settings:	11ms
get forum list:	15ms
check forum access:	4ms
check topic access:	4ms
track hit:	162ms
get topic data:	10ms
get forum data:	3ms
get page messages:	50ms
get tp. blocked users:	1ms
others:	17ms

total:	277ms