Здравствуйте, wildwind, Вы писали:
W>Здравствуйте, Овощ, Вы писали:
О>>Привет. У тебя наверняка есть под рукой одна из книжек Кайта по внутреннему устройству Oracle. Там в конце главы о индексах есть пункт:
W>Вот так и надо писать — Кайт мол в такой-то книге пишет то-то (цитата), касается это Oracle такой-то версии.
О>>Говорить в общем случае "о сравнение целым вектором" я считаю вполне возможным, поскольку это относится не к конкретной реализации, а к фундаментальным алгоритмам для структуры данных B+tree.
W>Неверно.
В таком случае нужно назвать субд и версию в которой это не так (желательно с ссылкой на доку). Или хотя бы пояснить теорию, зачем может понадобится использовать неэффективные алгоритмы вместо эффективных.
Здравствуйте, cargo, Вы писали:
C>Друзья! Подскажите, плиз, как лучше индексы организовать. Есть три поля f1, f2, f3, комбинация которых определяет условие SQL-запроса, т.е. грубо говоря может быть вот так:
C>WHERE f1 C>WHERE f2 C>WHERE f3 C>WHERE f1, f2 C>WHERE f1, f3 C>WHERE f2, f3 C>WHERE f1, f2, f3
C>Хочется обойтись минимальным количеством индексов, чтобы сэкономить время на инсертах. Записей будет много. Какие лучше сделать индексы и сколько? БД, если важно, SQLite.
"Базюлька" конкретно какая? Тогда могу сказать... Oracle, MS SQL, MySQL или что-то другое... Типы данных по колонкам еще уточни, плиз! Что есть f(i+j)?
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, MasterZiv, Вы писали:
MZ>>Индексы такие ( в первом приближении ):
MZ>>f1, f2, f3 MZ>>f1, f3 MZ>>f2, f3 MZ>>f3
Z>выделенные индексы можно заменить на один, (f3, f1) без ущерба для любых запросов.
Здравствуйте, _d_m_, Вы писали:
MZ>>>f1, f2, f3 MZ>>>f1, f3 MZ>>>f2, f3 MZ>>>f3
Z>>выделенные индексы можно заменить на один, (f3, f1) без ущерба для любых запросов.
___>Нет.
Какой запрос пострадает? Селективность, как я уже говорил, не учитываем. Или имеется ввиду именно размер самого индекса?
Здравствуйте, MasterZiv, Вы писали:
MZ>Вот есть у нас индекс на поля MZ>MyTable (Cl, C2)
MZ>Напомним, если кто забыл, что для запроса MZ>типа MZ>select * from MyTable where C2 = ? MZ>данный индекс будет безполезен.
Это не всегда верно. Например в Oracle реализована операция INDEX SKIP SCAN именно для такого случая, иногда бывает весьма полезна. Наверняка и в других СУБД есть аналоги.
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, _d_m_, Вы писали:
MZ>>>>f1, f2, f3 MZ>>>>f1, f3 MZ>>>>f2, f3 MZ>>>>f3
Z>>>выделенные индексы можно заменить на один, (f3, f1) без ущерба для любых запросов.
___>>Нет.
Z>Какой запрос пострадает? Селективность, как я уже говорил, не учитываем. Или имеется ввиду именно размер самого индекса?
Здравствуйте, wildwind, Вы писали:
W>Это не всегда верно. Например в Oracle реализована операция INDEX SKIP SCAN именно для такого случая, иногда бывает весьма полезна. Наверняка и в других СУБД есть аналоги.
Конечно есть. Но бескомпромиссные DBA счиают выигрыш от index scan (вместо table scan) пренебрежимо малым по сравнению с выигрышем от index seek.
Потому, что index scan отличается только константой перед N, а index seek — это log(N) по весьма большому основанию.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Sinclair wrote:
> Конечно есть. Но бескомпромиссные DBA счиают выигрыш от index scan > (вместо table scan) пренебрежимо малым по сравнению с выигрышем от index > seek.
+1
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, wildwind, Вы писали:
W>>Это не всегда верно. Например в Oracle реализована операция INDEX SKIP SCAN именно для такого случая, иногда бывает весьма полезна. Наверняка и в других СУБД есть аналоги. S>Конечно есть. Но бескомпромиссные DBA счиают выигрыш от index scan (вместо table scan) пренебрежимо малым по сравнению с выигрышем от index seek. S>Потому, что index scan отличается только константой перед N, а index seek — это log(N) по весьма большому основанию.
index skip scan — это не index full scan (когда читается весь индекс в порядке сортировки строк в этом индексе).
index skip scan — это не index fast full scan (когда индекс используется просто как несортированная (heap) таблица).
index skip scan — это как раз и есть доступ с использованием b-tree структуры индекса, но с "фичей" не только искать нужные записи в этом индексе, но и пропускать не нужные.
По эффективности он может быть как не отличим от "классического" index seek, так и быть медленнее full (table) scan`a.
Как раз для его эффективности имеет значение кардинальность отдельных колонок в индексе (ведущих).
Вот пример:
создаем большую таблицу
SQL> create table t as select mod(rownum, 2) c_low, rownum c_high from dual connect by level <= 10000000;
Table created.
поля в ней имеют весьма различную кардинальность
SQL> select count(*), count(distinct c_low), count(distinct c_high) from t;
COUNT(*) COUNT(DISTINCTC_LOW) COUNT(DISTINCTC_HIGH)
---------- -------------------- ---------------------
10000000 2 10000000
это "плохой" индекс
SQL> create index i1_clow_chigh on t(c_low, c_high);
Index created.
а это вроде как хороший
SQL> create index i2_chigh on t(c_high);
Index created.
статистика для оптимизатора
SQL> exec dbms_stats.gather_table_stats(ownname=>user, cascade=>true, tabname=>'T');
PL/SQL procedure successfully completed.
SQL> set autotrace on
доступ по "плохому" индексу по "плохому" предикату. однако же Cost=4
SQL> select/*+ index(t i1_clow_chigh) */count(*) from t where c_high = 999;
COUNT(*)
----------
1
Execution Plan----------------------------------------------------------Plan hash value: 2275081951
----------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 6 | 4 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 6 | | |
|* 2 | INDEX SKIP SCAN| I1_CLOW_CHIGH | 1 | 6 | 4 (0)| 00:00:01 |
----------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("C_HIGH"=999)
filter("C_HIGH"=999)
доступ по хорошему индексу по хорошему предикату. Cost=3. Лишь чуть меньше чем в предыдущем "плохом" случае.
SQL> select/*+ index(t i1_chigh) */count(*) from t where c_high = 999;
COUNT(*)
----------
1
Execution Plan----------------------------------------------------------Plan hash value: 2726032430
------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 6 | 3 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 6 | | |
|* 2 | INDEX RANGE SCAN| I2_CHIGH | 1 | 6 | 3 (0)| 00:00:01 |
------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("C_HIGH"=999)
полный скан таблицы. с ужасным Cost=4494.
SQL> select/*+ full(t) */count(*) from t where c_high = 999;
COUNT(*)
----------
1
Execution Plan----------------------------------------------------------Plan hash value: 2966233522
---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 6 | 4494 (9)| 00:00:54 |
| 1 | SORT AGGREGATE | | 1 | 6 | | |
|* 2 | TABLE ACCESS FULL| T | 1 | 6 | 4494 (9)| 00:00:54 |
---------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - filter("C_HIGH"=999)
Так что в данном случае получаем что index skip scan (cost=4) оказался таким же быстрым как и index seek (cost=3), и намного лучше full scan (cost=4494).
В других случаях все может быть и по другому.
Такая вот чудная операция, позволяющая в индексе по полям (c1, c2) искать с условиями только по (с2).
Здравствуйте, Овощ, Вы писали:
О>index skip scan — это не index full scan (когда читается весь индекс в порядке сортировки строк в этом индексе). О>index skip scan — это не index fast full scan (когда индекс используется просто как несортированная (heap) таблица). О>index skip scan — это как раз и есть доступ с использованием b-tree структуры индекса, но с "фичей" не только искать нужные записи в этом индексе, но и пропускать не нужные.
Я не понимаю, как это работает. О>Так что в данном случае получаем что index skip scan (cost=4) оказался таким же быстрым как и index seek (cost=3), и намного лучше full scan (cost=4494). О>В других случаях все может быть и по другому. О>Такая вот чудная операция, позволяющая в индексе по полям (c1, c2) искать с условиями только по (с2).
Прикольно.
What Oracles does not mention is that the cardinality of the leading column has a direct impact on the speed of the index skip scan. In our example, the first column, sex has two columns
While Oracle does not publish the internals of the index skip scan, we can infer from the execution plans that Oracle is internally generating multiple queries, thereby satisfying the query with multiple sub-queries
Ну, то есть на самом деле используется оптимизация index scan — когда мы "перепрыгиваем" между значениями первого ключа.
Правда, не очень понятно, зачем добавлять в индекс первую колонку со столь низкой селективностью. Но, наверное, это имеет смысл в каких-то особенных случаях.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>we can infer from the execution plans that Oracle is internally generating multiple queries, thereby satisfying the query with multiple sub-queries
Это чушь, можно не обращать внимания.
S>Ну, то есть на самом деле используется оптимизация index scan — когда мы "перепрыгиваем" между значениями первого ключа.
Примерно так.
S>Правда, не очень понятно, зачем добавлять в индекс первую колонку со столь низкой селективностью. Но, наверное, это имеет смысл в каких-то особенных случаях.
Ты имел в виду "с низкой каридинальностью"? Селективность может быть и высокой, например, в случае сильно неравномерного распределения значений.
Еще случай, когда это имеет смысл — если мы хотим создать сжатый индекс.
Здравствуйте, wildwind, Вы писали: S>>Правда, не очень понятно, зачем добавлять в индекс первую колонку со столь низкой селективностью. Но, наверное, это имеет смысл в каких-то особенных случаях. W>Ты имел в виду "с низкой каридинальностью"?
В данном примере именно селективность получилась крайне неудачной — отбрасываем всего половину значений.
Хуже только
create table t as select42 c_low, rownum c_high from dual connect by level <= 10000000;
W> Селективность может быть и высокой, например, в случае сильно неравномерного распределения значений.
Ну да. Это я и хотел сказать — при существенной неравномерности такой индекс может давать хороший результат для запросов по любому из ключей.
В вырожденном случае имеем, например, 1000 значений high для low1, и по одному значению high для low1-low99.
Что ж, век живи — век учись.
W>Еще случай, когда это имеет смысл — если мы хотим создать сжатый индекс.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
