Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 Найти ближайший PK  [new]
НеофитSQL
Member [заблокирован]

Откуда: Маями
Сообщений: 760
Что-то не вижу простого решения.

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

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


Учитывая что в примере сортировка идет по значению функции, не закончится ли это полным перебором?
17 ноя 20, 17:06    [22233971]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18351
При правильной организации данных решается за шесть логических чтений практически независимо от размера таблицы с данными.
При относительно небольших объемах и высокой потребности в производительности можно решить на ассоциативном массиве PL/SQL ценой его однократной загрузки.
17 ноя 20, 17:22    [22233989]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
graycode
Member

Откуда:
Сообщений: 461
НеофитSQL
Учитывая что в примере сортировка идет по значению функции

Зачем?
17 ноя 20, 17:23    [22233992]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
НеофитSQL
Member [заблокирован]

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


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

Чудес не бывает, хотелось бы за O(log N) в SQL, без повторных поисков по индексу.
17 ноя 20, 17:42    [22234012]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
env
Member

Откуда: Россия, Москва
Сообщений: 6727
НеофитSQL,

Тупо в лоб
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


Сообщение было отредактировано: 17 ноя 20, 17:39
17 ноя 20, 17:44    [22234014]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
НеофитSQL
Member [заблокирован]

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL
Учитывая что в примере сортировка идет по значению функции

Зачем?


Так в примере, чтоб было понятно какой ожидается результат.
Я подозреваю что пример неэффективен, т.к. функция может помешать оптимизатору, особенно если функция посложнее чем abs()
17 ноя 20, 17:47    [22234018]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
andrey_anonymous
Member

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

:)
Вам ведь уже говорили, что Btree в Oracle нифига не бинарный.
До миллионов (десятков миллионов) записей задача решается за указанные расходы, которые требуются на два индексных поиска (каждый по 2 логических чтения индекса Blevel=2 + одно за записью в таблице, if any) - один вверх и один вниз.
В принципе, env показал один из способов воспользоваться таким поиском, но не показал структуры и планы.
17 ноя 20, 17:50    [22234023]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
НеофитSQL
Member [заблокирован]

Откуда: Маями
Сообщений: 760
env
НеофитSQL,

Тупо в лоб
+
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


Спасибо, сравниваю планы.
17 ноя 20, 17:51    [22234024]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
env
Member

Откуда: Россия, Москва
Сообщений: 6727
НеофитSQL,

Да что там сравнивать, особенно, если индекс есть
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
17 ноя 20, 17:56    [22234029]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
НеофитSQL
Member [заблокирован]

Откуда: Маями
Сообщений: 760
Решение env "в лоб" выглядит оптимально. Не вижу как можно быстрее.

Индекс конечно есть - это основной ключ.
17 ноя 20, 18:03    [22234036]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
graycode
Member

Откуда:
Сообщений: 461
НеофитSQL,

Решение в "лоб" можно записать так:
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)
17 ноя 20, 18:09    [22234039]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18351
НеофитSQL
Решение env "в лоб" выглядит оптимально. Не вижу как можно быстрее.

"Быстрее" - нет, план аналогичной эффективности попроще - да, можно.
17 ноя 20, 18:10    [22234040]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
env

Тупо в лоб


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

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". Можно поколдовать:

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>


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

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.
17 ноя 20, 18:10    [22234041]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
graycode
Member

Откуда:
Сообщений: 461
graycode
НеофитSQL,

Решение в "лоб" можно записать так:
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)

нельзя((
17 ноя 20, 18:23    [22234055]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
Кстати, план не отражает short circuit:

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.
17 ноя 20, 18:25    [22234059]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
graycode
Member

Откуда:
Сообщений: 461
SY
Ну а если есть индекс, то уж:

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

Это решает задачу поиска минимального из соседних, а не ближайшего и ближайших может быть два, если они на одинаковом расстоянии.
17 ноя 20, 18:48    [22234075]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
[quot graycode#22234075]
SY

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


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

MATCH_RECOGNIZE для забавы:

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.
17 ноя 20, 19:19    [22234103]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
graycode
Member

Откуда:
Сообщений: 461
env

...

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

А где 29 ?))
17 ноя 20, 19:51    [22234120]     Ответить | Цитировать Сообщить модератору
 Re: Найти ближайший PK  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 10045
graycode

А где 29 ?))


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

SY.
17 ноя 20, 19:56    [22234124]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить