Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск принадлежности к интервалу - какой стандартное решение? / 12 сообщений из 12, страница 1 из 1
25.11.2016, 16:34
    #39354706
Поиск принадлежности к интервалу - какой стандартное решение?
Есть ли стандартная реализация поиска на предмет вхождения значения в интервал, границы которого лежат в таблице?
Код: plsql
1.
2.
3.
create table edge (min_val number, max_val number);
insert into edge select rownum-10, rownum+10 from dual connect by level<1000;
select * from edge where 500 between min_val and max_val;


Выполняется FULL SCAN по таблице - можно переписать запрос на индексный поиск?
...
Рейтинг: 0 / 0
25.11.2016, 16:40
    #39354712
AmKad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Сорри, ткните, плиз,

А ты индекс-то создал?
...
Рейтинг: 0 / 0
25.11.2016, 17:02
    #39354721
--Eugene--
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Сорри, ткните, плиз,

кроме индекса, еще неплохо бы колонки min_val и max_val сделать NOT NULL
...
Рейтинг: 0 / 0
25.11.2016, 17:34
    #39354748
Поиск принадлежности к интервалу - какой стандартное решение?
Нет, в том то и дело, что это не поможет - TABLE ACCESS FULL:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
create table edge (min_val number not null, max_val number not null);
insert into edge select rownum-10, rownum+10 from dual connect by level<100000;
create index edge_min on edge(min_val);
create index edge_max on edge(max_val);
create index edge_min_max on edge(min_val,max_val);
create index edge_max_min on edge(max_val,min_val);
begin
  dbms_stats.gather_table_stats(ownname => 'XXX', tabname => 'EDGE', estimate_percent => 100, degree => 8, cascade => true);
end;


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
SQL> select * from table(dbms_xplan.display);
 
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 2016960632
--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      | 25011 |   244K|    60   (4)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| EDGE | 25011 |   244K|    60   (4)| 00:00:01 |
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("MIN_VAL"<=50000 AND "MAX_VAL">=50000)
 
13 rows selected
 
Executed in 0,187 seconds


Код: 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.
SQL> select * from edge where 50000 between min_val and max_val;
 
   MIN_VAL    MAX_VAL
---------- ----------
     49980      50000
     49981      50001
     49982      50002
     49983      50003
     49984      50004
     49985      50005
     49986      50006
     49987      50007
     49988      50008
     49989      50009
     49990      50010
     49991      50011
     49992      50012
     49993      50013
     49994      50014
     49995      50015
     49996      50016
     49997      50017
     49998      50018
     49999      50019
 
   MIN_VAL    MAX_VAL
---------- ----------
     50000      50020
 
21 rows selected
 
Executed in 0,141 seconds
...
Рейтинг: 0 / 0
25.11.2016, 17:47
    #39354760
AmKad
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Если ты уверен в высокой селективности предиката, то можно прибить хинтами.
Код: 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.
92.
93.
94.
95.
96.
97.
drop table edge purge;
create table edge (nullable number, min_val number not null, max_val number not null);
insert into edge select rownum, rownum-10, rownum+10 from dual connect by level<100000;
create index edge_min on edge(min_val);
create index edge_max on edge(max_val);
create index edge_min_max on edge(min_val,max_val);
create index edge_max_min on edge(max_val,min_val);
begin
  dbms_stats.gather_table_stats(ownname => user, tabname => 'EDGE', estimate_percent => 100, degree => 8, cascade => true);
end;

commit;

set autotrace traceonly
select count(nullable) from edge t where 50000 between min_val and max_val;

Затрач.время: 00:00:00.04

План выполнения
----------------------------------------------------------
Plan hash value: 3004890546

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |    15 |    71   (2)| 00:00:01 |
|   1 |  SORT AGGREGATE    |      |     1 |    15 |            |          |
|*  2 |   TABLE ACCESS FULL| EDGE | 25011 |   366K|    71   (2)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - filter("MIN_VAL"<=50000 AND "MAX_VAL">=50000)

Note
-----
   - automatic DOP: Computed Degree of Parallelism is 1 because of parallel threshold


Статистика
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        174  consistent gets
          0  physical reads
          0  redo size
        357  bytes sent via SQL*Net to client
        360  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed



select /*+ index(t edge_min_max) */ count(nullable) from edge t where 50000 between min_val and max_val;

Затрач.время: 00:00:00.04

План выполнения
----------------------------------------------------------
Plan hash value: 720509129

---------------------------------------------------------------------------------------------
| Id  | Operation                    | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |              |     1 |    15 |   108   (1)| 00:00:01 |
|   1 |  SORT AGGREGATE              |              |     1 |    15 |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID| EDGE         | 25011 |   366K|   108   (1)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | EDGE_MIN_MAX | 25011 |       |    73   (0)| 00:00:01 |
---------------------------------------------------------------------------------------------

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

   3 - access("MAX_VAL">=50000 AND "MIN_VAL"<=50000)
       filter("MAX_VAL">=50000)

Note
-----
   - automatic DOP: Computed Degree of Parallelism is 1 because of parallel threshold


Статистика
----------------------------------------------------------
          1  recursive calls
          0  db block gets
         73  consistent gets
          0  physical reads
          0  redo size
        357  bytes sent via SQL*Net to client
        360  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
25.11.2016, 17:54
    #39354764
andreymx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Сорри, ткните, плиз,

в таблице других ключей нет?
...
Рейтинг: 0 / 0
25.11.2016, 18:18
    #39354777
Maxim Demenko
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
AmKad Если ты уверен в высокой селективности предиката, то можно прибить хинтами.
Бросается в глаза, что Optimizer на 3 порядка ошибается в оценке кардинальности (причем ситуация не меняется по крайней мере на 11.2.0.4 - даже при наличии extended stats на column group).

Regards

Maxim
...
Рейтинг: 0 / 0
25.11.2016, 18:20
    #39354780
Поиск принадлежности к интервалу - какой стандартное решение?
AmKad, это не решение - просто выкидывается пол-диапазона, а хотелось бы больше.

andreymx, в реальной таблице есть уникальный индекс на min, max и ещё пару полей - а как это поможет?
...
Рейтинг: 0 / 0
25.11.2016, 18:55
    #39354804
Flash Gordon
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Я недавно думал об этом и мне кажется, что B-tree индекс в этом никак не поможет. Насколько я понял подошел бы R-tree, но его можно сделать только для геоданных. Моя задача была аналогичная — найти подсеть для айпи-адреса, в таблице хранятся начало и конец для каждой подсети.
...
Рейтинг: 0 / 0
26.11.2016, 02:42
    #39354908
ora601
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Maxim DemenkoAmKad Если ты уверен в высокой селективности предиката, то можно прибить хинтами.
Бросается в глаза, что Optimizer на 3 порядка ошибается в оценке кардинальности (причем ситуация не меняется по крайней мере на 11.2.0.4 - даже при наличии extended stats на column group).

Regards

Maxim


А на ХЕ не ошибаеться .... :

Код: plsql
1.
2.
...
Рейтинг: 0 / 0
26.11.2016, 02:46
    #39354909
ora601
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Maxim DemenkoAmKad Если ты уверен в высокой селективности предиката, то можно прибить хинтами.
Бросается в глаза, что Optimizer на 3 порядка ошибается в оценке кардинальности (причем ситуация не меняется по крайней мере на 11.2.0.4 - даже при наличии extended stats на column group).

Regards

Maxim


А на ХЕ не ошибаеться .... :

Код: 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.
SQL> select * from edge where 500 between min_val and max_val;

   MIN_VAL    MAX_VAL
---------- ----------
       480        500
       481        501
       482        502
       483        503
       484        504
       485        505
       486        506
       487        507
       488        508
       489        509
       490        510

   MIN_VAL    MAX_VAL
---------- ----------
       491        511
       492        512
       493        513
       494        514
       495        515
       496        516
       497        517
       498        518
       499        519
       500        520

21 rows selected.


Execution Plan
----------------------------------------------------------
Plan hash value: 2231248040

--------------------------------------------------------------------------------

-

| Id  | Operation        | Name         | Rows  | Bytes | Cost (%CPU)| Time
|

--------------------------------------------------------------------------------

-

|   0 | SELECT STATEMENT |              |   508 |  5080 |     3   (0)| 00:00:01
|

|*  1 |  INDEX RANGE SCAN| EDGE_MIN_MAX |   508 |  5080 |     3   (0)| 00:00:01
|

--------------------------------------------------------------------------------

-


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

   1 - access("MAX_VAL">=500 AND "MIN_VAL"<=500)
       filter("MAX_VAL">=500)


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          5  consistent gets
          0  physical reads
          0  redo size
        885  bytes sent via SQL*Net to client
        430  bytes received via SQL*Net from client
          3  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         21  rows processed

SQL>



Ну да B-Tree никак не помог)
...
Рейтинг: 0 / 0
26.11.2016, 02:47
    #39354910
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск принадлежности к интервалу - какой стандартное решение?
Сорри, ткните, плизAmKad, это не решение - просто выкидывается пол-диапазона, а хотелось бы больше.
...

если ваш пример
Код: plsql
1.
2.
create table edge (min_val number not null, max_val number not null);
insert into edge select rownum-10, rownum+10 from dual connect by level<100000;



как-то соотносится с реальными данными, то примите в расчет такие соображения:

из rownum-10, rownum+10 возникает гипотеза, что сами по себе длины ваших интервалов небольшие и, может быть, есть "по бизнесу" представление о значении максимально
допустимого интервала.
Тогда условие поиска может быть задано вообще по отношению только к одной границе интервала.
Также может быть полезен явный констрейнт, запрещающий ввод интервалов размером больше максимально допустимого.
Для вашего тестового случая, например так
Код: plsql
1.
alter table edge add constraint chk_edge check (max_val  <= min_val + 20 );



тогда запрос
Код: plsql
1.
2.
3.
4.
5.
select * 
from edge where 1 = 1
--And 50000 between min_val and max_val
And max_val - 50000 < (Max_val - min_val)
And  max_val between  50000  and 50000 + 20 /*максимальный размер возможного окна*/ --cast(:max_interval as number)




имеет все шансы не перебирать "половину индекса", перебирать его всегда в пределах чисел,
расположенных в максимально допустимом интервальном окне по отношению к искомой точке.
...
Рейтинг: 0 / 0
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск принадлежности к интервалу - какой стандартное решение? / 12 сообщений из 12, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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