Техники Bitmap-индекса Oracle

http://www.dba-oracle.com/oracle_tips_bitmapped_indexes.htm
  • Перевод
И снова добрый вечер!

Запускаем второй поток нашего нового курса «Реляционные СУБД», который мы чуть дотюнили по итогам первого прогона: дополнительные занятия по кластерам MySQL и Postgres, оказался востребованным docker и ещё разные «доработки напильником». Так что ждите открытые уроки (в которые вынесли часть старых тем) и интересные материалы. Сегодня мы покопаемся в техниках Oracle.

Поехали.

Bitmap-индексы Oracle сильно отличаются от стандартных индексов B-дерева. В bitmap-структурах создается двухмерный массив со столбцом для каждой строки в индексируемой таблице. Каждый столбец представляет отдельное значение в bitmap-индексе. Этот двухмерный массив показывает каждое значение индекса, умноженное на количество строк в этой таблице.

Oracle распаковывает bitmap (со скоростью извлечения строки) в буфер данных ОЗУ для быстрого сканирования на предмет совпадения значений. Эти совпадающие значения передаются Oracle в виде списка Row-ID, и значения Row-ID могут напрямую обращаться к необходимой информации.



Особое преимущество bitmap-индексирования проявляется, когда одна таблица включает несколько bitmap-индексов. Мощность каждого столбца может быть невысокой. Создание нескольких bitmap-индексов предоставляет очень сильный подход для быстрого ответа на сложные SQL-запросы.



Используя методологию bitmap-объединения, Oracle обеспечивает снижение времени отклика до менее секунды при работе с несколькими столбцами с малым количеством элементов.

Также обратите внимание на важные заметки о максимальных значениях Oracle bitmap-индекса.

Например, представим, что есть база данных автомобилей с большим числом маломощных столбцов: car_color, car_make, car_model и car_year. Каждый столбец содержит менее 100 различных значений, и индекс b-дерева был бы совершенно бесполезен в такой базе данных 20 миллионов автомобилей.

Однако, слияние этих индексов в запрос может обеспечить высокое время отклика гораздо быстрее, чем традиционный метод чтения каждой из 20 миллионов строк в базовой таблице. Например, предположим мы хотим найти старые синие Toyota Corolla, произведенные в 1981 году:

select
   license_plat_nbr
from
   vehicle
where
   color = "blue"
and
   make = "toyota"
and
   year = 1981;

Для работы с этим запросом Oracle использует специализированный метод оптимизации под названием объединение bitmap-индексов. В этом методе каждый список Row-ID (кратко — RID) формируется отдельно при помощи bitmap’ов, а для сравнения RID-списков и поиска пересекающихся значений используется специальная процедура слияния.

По мере роста числа различных значений, размер bitmap увеличивается экспоненциально. Так индекс 100 значений может работать в 1000 раз быстрее, чем bitmap-индекс 1000 различных значений столбца.

Стоит помнить, что bitmap-индексы подходят только для статических таблиц и материализованных представлений, которые обновляются ночью и пересобираются после пакетной загрузки строк. Если в вашей таблице происходит несколько DML в секунду, БУДЬТЕ ОСТОРОЖНЫ при реализации bitmap-индексов!

  • 1 — 7 различных ключевых значений — Запросы bitmap-индексам с низкой мощностью выполняются очень быстро;
  • 8 — 100 различных ключевых значений — С увеличением числа различных значений, производительность пропорционально снижается;
  • 100 — 10000 различных значений — При более чем 100 различных значениях bitmap-индексы становятся огромными и SQL-производительность стремительно падает;
  • Более 10000 различных ключевых значений — на этом этапе производительность в десять раз ниже, чем при индексе с 100 различными значениями.

Bitmap-индексы Oracle — очень мощная фича Oracle, но есть и подводные камни!

Вы захотите использовать bitmap-индекс в следующих случаях:

  1. Столбец таблицы обладает малой мощностью — для ЧЕРНОВОГО руководства, рассмотрите bitmap для любого индекса с менее чем 100 различными значениями:

    select region, count(*) from sales group by region;
  2. НИЗКИЙ DML таблицы — использование вставки/обновления/удаления должно быть низком. На обновление bitmap-индексов требуется много ресурсов, поэтому они лучше подходят для таблиц, доступных только для чтения, и таблиц, пакетно обновляемых каждую ночь;
  3. Несколько столбцов — Ваши SQL-запросы ссылаются на несколько маломощных значений в их where операторах. SQL-оптимизатор Oracle на базе стоимости (кратко — CBO) будут вопить при наличии у вас bitmap-индексов.

Устранение неполадок bitmap-индексов Oracle

Самые распространенных проблемы реализации bitmap-индексов включают следующие:

  • Маленькая таблица — CBO может потребовать полного сканирования таблицы, если она слишком маленькая!
  • Плохие статы — Убедитесь, что вы анализируете bitmap с dbms_stats сразу после создания:

CREATE BITMAP INDEX 
emp_bitmap_idx
ON index_demo (gender);

exec dbms_stats.gather_index_stats(OWNNAME=>'SCOTT', INDNAME=>'EMP_BITMAP_IDX');

  • Тестирование с подсказкой — чтобы использовать ваш новый bitmap-индекс, используйте подсказку INDEX Oracle:

select /*+ index(emp emp_bitmap_idx) */ 
   count(*)
from 
   emp, dept
where 
   emp.deptno = dept.deptno;

Ждём вопросы и комментарии тут или заходите к нам на новый открытый урок.
Отус
340,00
Профессиональные онлайн-курсы для разработчиков
Поделиться публикацией

Похожие публикации

Комментарии 26

    +1

    Ещё одной ценной особенностью таких индексов является то, что индексируются NULL.

    0
    произведенные в 1981 году:

    year = 2015;


    Toyota Corolla

    make = «toyota»

    Это особенность bitmap-индексов? :-)
      0
      Очепяточка в оригинале. Зевнули. Поправили :)
      +1
      НИЗКИЙ DML таблицы — использование вставки/обновления/удаления должно быть низком. На обновление bitmap-индексов требуется много ресурсов, поэтому они лучше подходят для таблиц, доступных только для чтения, и таблиц, пакетно обновляемых каждую ночь;

      вы уж договаривайте до конца. Требуется много ресурсов — это, мягко говоря, не точно сказано. При изменении строки, накладывается блокировка на изменение всех(!) строк таблицы, содержащихся в этом ключе битмап индекса. И никак с количеством ресурсов это связано.
        0
        накладывается блокировка на изменение всех(!) строк таблицы, содержащихся в этом ключе битмап индекса.
        Как я уже ниже советовал, почитайте Ричарда Фута!
        Вообще это один из известных мифов, и является полуправдой:
        1. с одной стороны, действительно многие записи с таким же значением будут заблокированы, но
        2. на самом деле, заблокированы будут только те записи, которые находятся в том же куске со списком ROWIDs, что и изменяемая запись, тк при большом кол-ве записей они не хранятся единым куском. (про реальное строение читайте у Р.Фута или просто проанализируйте дамп индекса)
        Проверяется очень легко:
        1. создайте таблицу с битмап индексом, в которой значение только одно:
        SQL> create table tbitmap as select level id, 1 a from dual connect by level<=1e6;
        
        Table created.
        
        SQL> create bitmap index ix_bitmap on tbitmap(a);
        
        Index created.
        

        2. Измените значение индексного поля на 2 в строке с id=1:
        SQL> update tbitmap set a=2 where id=1;
        
        1 row updated.

        3. В другой сессии вы можете спокойно изменить множество строк, кроме тех которые находятся в других блоках битмап карты:
        SQL> update tbitmap set a=3 where id=1e6;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-100;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-1000;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-10000;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-100000;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-500000;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-800000;
        
        1 row updated.
        
        SQL> update tbitmap set a=3 where id=1e6-900000;
        
        1 row updated.

        4. Но если вы попытаетесь проапдейтить строку из того же куска, то тут же нарветесь на блокировку:
        SQL> update tbitmap set a=3 where id=1024;
        -- и висим...
        
          0
          Погодите товарищ, шашкой махать, похоже вы просто не внимательно прочитали. Я говорю о том же, обратите внимание на разницу — «заблокируютя все строки содержащиеся в этом ключе индекса» (т.е. в данном случае битмап ключе, а не значении поля) и «заблокируются все строки с этим же значением столбца». У меня ощущение что вы опровергаете как раз второе. Вот простой и понятный пример у Кайта, как блокировки относятся с бимап ключом: Bitmap indexes and locking
            0
            Да нет, я прочитал все верно, поэтому если вы и хотели написать то же, что и я, то вы выражаетесь не общей терминологией, в которой (как у Кайта, так и у любых других авторов) «Ключ индекса» — это key value/values, а реально блокируются только записи в изменяемой битовой карте(bitmap, bitmap piece, index entry, но никак не key)

            image
              0
              Ок, давайте о терминологии, раз так пошел разговор.
              Конечно Julian Duke авторитетный автор, но предлагаю все таки заглянуть в документацию:
              docs.oracle.com/cd/E11882_01/server.112/e40540/indexiot.htm#CNCPT1182

              If the indexed column in a single row is updated, then the database locks the index key entry (for example, M or F) and not the individual bit mapped to the updated row. Because a key points to many rows, DML on indexed data typically locks all of these rows.

              Именно key entry, а не bitmap piece и не index entry. Так что не такая она и общая, ваша терминология)
              Предложите лучше перевод — я не против.
                0

                А если внимательно прочтете этот же кусок, который привели(особое внимание на пример в скобках) и, собственно, посмотрите в других местах, что они имеют ввиду под этим, то поймёте, что они ошиблись так же как и вы, но они не так категоричны: typically locks all these rows, что им позволит сказать, что, мол, мы и не говорили, что прямо всегда и все строки

                  0

                  Вообще даже странно как-то объяснять такую банальность как, что такое index keys…

                    0
                    Гм… А мне кажется вы все таки путаете index key для b-tree, как значения полей таблицы индекса и index key для bitmap, что несколько иное. Смотрите там же:
                    In a conventional B-tree index, one index entry points to a single row. In a bitmap index, each index key stores pointers to multiple rows.

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

                      0
                      Вы меня расстраиваете… Я понимаю, что можно плохо знать английский, можно не пройти теорию реляционных баз в универе, но не осилить пару предложений? Что вам в выделенном непонятно? Как это противоречит сказанному мной? Оно же и так чрезмерно упрощенное… Замечаете, что в первом из них «index key entry»?
                      index key != index key entry
                      Ну а пройтись хотя бы поиском по страничке на фразу «index key», как я уже подсказывал?

                      1
                      Keys and Columns
                      A key is a set of columns or expressions on which you can build an index. Although the terms are often used interchangeably, indexes and keys are different. Indexes are structures stored in the database that users manage using SQL statements. Keys are strictly a logical concept.

                      The following statement creates an index on the customer_id column of the sample table oe.orders:

                      CREATE INDEX ord_customer_ix ON orders (customer_id);

                      In the preceding statement, the customer_id column is the index key. The index itself is named ord_customer_ix.


                      2
                      For a nonunique index, the rowid is included in the key in sorted order, so nonunique indexes are sorted by the index key and rowid (ascending).


                      3
                      Reverse key indexes

                      In this type of index, the bytes of the index key are reversed, for example, 103 is stored as 301.


                      4
                      The database could use a range scan because the last_name column is specified in the predicate and multiples rowids are possible for each index key.


                      5
                      In a bitmap index, the database stores a bitmap for each index key.


                      6
                      CREATE BITMAP INDEX employees_bm_idx 
                      ON     employees (jobs.job_title) 
                      FROM   employees, jobs
                      WHERE  employees.job_id = jobs.job_id;

                      As illustrated in Figure 3-2, the index key is jobs.job_title and the indexed table is employees.


                      7. ну уж их этого-то куска невозможно не понять...
                      Bitmap Storage Structure

                      Oracle Database uses a B-tree index structure to store bitmaps for each indexed key. For example, if jobs.job_title is the key column of a bitmap index, then the index data is stored in one B-tree. The individual bitmaps are stored in the leaf blocks.

                      Assume that the jobs.job_title column has unique values Shipping Clerk, Stock Clerk, and several others. A bitmap index entry for this index has the following components:

                      • The job title as the index key
                      • A low rowid and high rowid for a range of rowids
                      • A bitmap for specific rowids in the range

                      Conceptually, an index leaf block in this index could contain entries as follows:

                      Shipping Clerk,AAAPzRAAFAAAABSABQ,AAAPzRAAFAAAABSABZ,0010000100
                      Shipping Clerk,AAAPzRAAFAAAABSABa,AAAPzRAAFAAAABSABh,010010
                      Stock Clerk,AAAPzRAAFAAAABSAAa,AAAPzRAAFAAAABSAAc,1001001100
                      Stock Clerk,AAAPzRAAFAAAABSAAd,AAAPzRAAFAAAABSAAt,0101001001
                      Stock Clerk,AAAPzRAAFAAAABSAAu,AAAPzRAAFAAAABSABz,100001
                      .
                      .
                      .

                      The same job title appears in multiple entries because the rowid range differs.

                      Assume that a session updates the job ID of one employee from Shipping Clerk to Stock Clerk. In this case, the session requires exclusive access to the index key entry for the old value (Shipping Clerk) and the new value (Stock Clerk). Oracle Database locks the rows pointed to by these two entries—but not the rows pointed to by Accountant or any other key—until the UPDATE commits.



                      зы. если уж пытаетесь свалить на незнание английского, то попробуйте тогда найти определение на ключ индекса на русском…
                        0
                        Если и у меня плохо с английским, то у вас с логикой тоже как-то не сложилось.
                        Ну с английским у меня то хоть есть еще шансы)

                        Что index key != index key entry, как то опять обратное никто и не доказывает. Как раз я о втором. А вы мне все рассказываете про первое.

                        Еще раз, выше я уточнил что речь идет именно о key entry и выделил жирным (то определение доки, которое вы сочли не правильным ):
                        If the indexed column in a single row is updated, then the database locks the index key entry (for example, M or F) and not the individual bit mapped to the updated row. Because a key points to many rows, DML on indexed data typically locks all of these rows.

                        Вот Кайт, использует те же определения:
                        There is a locking implication by design in bitmap indexes, the keys point to hundreds of rows and if I lock a single key entry in a bitmap index, I've locked the key entry for hundreds of other rows.

                        В общем я не вижу смысла тут дальше спорить. Там более в таком тоне.
                        Если вам так будет спать спокойней, могу признать — в моем изначальным посте «содержашихся в этом ключе индекса» было не совсем точным. Пусть будет «содержашихся в этой записи ключа индекса», т.е. locked the index key entry, строго по определению.

                          0
                          мило, таки прочитал определение в первом же пункте из того документа, что такое index key и index key entry? :D Понаписал столько воды, вместо того, чтобы просто признать с самого начала, что это разные вещи. Ну хоть признал, и то хлеб…
                            0
                            А мне кажется вы все таки путаете index key для b-tree, как значения полей таблицы индекса и index key для bitmap, что несколько иное.
                            ну а по этому пункту-то получилось избавиться от заблуждений? Стало понятно, что смысл index keys одинаков, что для b-tree, что для bitmap?
                              0
                              ну и, пожалуй, самое интересное, если вы якобы знали то, о чем я говорил, то почему не заметили в этой статье несоответствие в описании структуры? Оно же гораздо важнее и идет в самом начале, в отличие от сентенции про ресурсы (про что тоже можно поспорить, т.к. изменение bitmap индекса более ресурсоемко)
                                0
                                Рановато вам с менторским тоном уважаемый:
                                Как же так:
                                bitmap, bitmap piece, index entry, но никак не key

                                что они ошиблись так же как и вы

                                А получилось что именно key entry? И ошиблись именно вы, со своим никак не key, а не дока и Кайт, как раз которые используют key entry.

                                Каша у вас с определениями. У самого то получится разобраться ?))
                                  0
                                  wtf?! Вы до сих пор так и не поняли, что ключ индекса — это index key? и что index key!=index entry? a index entry==entry==index key entry==key entry?

                                  Перечитайте внимательно по своим же ссылкам у Кайта и ту же доку, если лень, то хотя бы п.7, который я вам специально процитировал даже.

                                  Вернемся к самому началу:
                                  In a bitmap index, you have:
                                  a) a key value
                                  b) a low-rowid value
                                  c) a high-rowid value
                                  d) a bit map that indicates for each rowid in that range whether the row that rowid points to has that value or not.

                                  Suppose you have the EMP table and you create bitmap index bm on emp(deptno);

                                  So, in the bitmap index, you might have key values like:
                                  DEPTNO         LOW-ROWID          HIGH-ROWID        BITMAP
                                  ----------     ------------       -------------     ---------------
                                  10             afdafda            badfasd           01010101010101
                                  10             bbdafadafd         bcdafdfda         11010101010101
                                  20             afdafda            badfasd           10101010101010

                                  И вы предлагаете называть каждую такую запись ключом битмап индекса?! А что такое тогда deptno? бурлесоновщина в чистом виде…

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

                                  ззы. раньше, кстати, там тоже ошибочно было упрощено как и в этой статье(показывали, что все для каждого значения ключа свой один bitmap, и каждый из них содержит все ROWIDs, что в корне неверно), что и породило миф о блокировке всех строк для изменяемого значения. И этот ответ на асктоме лишь от 2007 года, а Джулиан Дайк эту свою презентацию в первый раз прочитал еще в 2003. Так что я рад, что добавили деталей в 11.2, но спорить о существовании этого мифа довольно глупо.
                                    0
                                    но спорить о существовании этого мифа довольно глупо.
                                    не надо мне приписывать, то чего я не делал.
                                    Я давно написал и выделил, что речь именно о key entry.

                                    Давайте теперь еще раз логике:
                                    a index entry==entry==index key entry==key entry?
                                    Речь вроде шла о общей терминологии. Это вы сейчас задним числом исправились, дописали key entry. Раньше вроде было bitmap, bitmap piece, index entry и это в сообщении о общей терминологии. Разве не так? А оказалось key entry — именно это общепринятая терминология( а не bitmap, bitmap piece и не index entry
                                    Заголовок спойлера
                                    index entry, чтоа? — где вы вообще в таком сочетании это встретили? В том смысле который вы вкладываете именно такое сочетание не используется. Это не бурлесоновщина, случаем ?)
                                    ).
                                      0
                                      еще раз для особо одаренных: п.7
                                      A bitmap index entry for this index has the following components
                                        0
                                        Я давно написал и выделил, что речь именно о key entry.
                                        продолжая утверждать, что key entry это ключ, и в который раз споря с моим «но никак не key», втыкая «key entry»?..
                                        театр абсурда:
                                        — это ключ
                                        — это не ключ, не key
                                        — нет, это ключ, так как "...key entry..."
                                        — key entry != key
                                        — да key entry!=key, но все равно entry = key

                                        WTF?!
                0
                Ох, блин, парни… Ну это же чистой воды «бурлесоновщина»! Не поленитесь, почитайте Ричарда Фута и исправьте статью!
                Например: richardfoote.wordpress.com/2010/03/03/1196
                А еще лучше всего его посты про них:
                richardfoote.wordpress.com/category/bitmap-indexes
                  0
                  А чем плох Burleson?
                  За наводку на Фута спасибо, изучу.
                    0
                    А чем плох Burleson?

                    В принципе, это не мое дело, но дабы уберечь хоть кого-нибудь от бесполезной траты времени на чтение его бреда, я думаю, что надо перечислить как минимум главное «чем он плох»:
                    1. Введение в заблуждение:
                    В первую очередь, тем, что хоть и неосознанно, но постоянно вводит огромное число людей в заблуждение, т.к. алгоритмы Google не учитывают ценность и точность информации, его сайт и форум имеют слишком широкую аудиторию.
                    2. Недостаток знаний:
                    Вообще же корень проблемы в том, что в заблуждение он вводит из-за того, что он очень поверхностно знает Oracle. В то время как профессионалы докапываются до реальных причин и детально изучают Oracle internals, он постоянно делает поверхностные поспешные выводы, да еще и на основе однократных событий: увидел А и B вместе, и сразу делает вывод, что A привело к B, да еще и если еще раз увидит B, то сразу скажет что виноват А… (кстати, почитайте еще про BAAG)
                    3. Уверенность в своих заблуждениях:
                    Чисто для сравнения: многие оракловые специалисты прямо в аннотации пишут, что не нужно слепо доверять написанному и предоставляют тест-кейсы, чтобы вы могли сами проверить и изучить все данные утверждения. Что же любит Дон Бурлесон? А он просто удаляет и банит людей за посты, в которых лишь высказывается сомнение в тех или иных его утверждениях. Мы все, конечно, бредем по кривой Даннинга-Крюгера, но ему много лет, а он где-то подзастрял и до долины отчаяния не дошел…
                    Кривая Даннинга-Крюгера
                    image


                    Вообще забавный человек :) Вам стоит почитать о нем побольше, чисто навскидку:
                    1. oracledoug.com/serendipity/index.php?/archives/1303-Why-you-cant-just-say-Stop-feeding-the-troll-....html
                    2. oraclesponge.wordpress.com/2005/04/11/banned-by-burleson
                    3. jonathanlewis.wordpress.com/2007/07/14/analysing-statspack-6
                    4. jonathanlewis.wordpress.com/2011/02/14/burleson-buys-bmc
                    5. www.rittmanmead.com/blog/2004/08/don-burleson-busting-the-oracle-myth-busters
                      0
                      Спасибо за ссылки, но некоторые из них похожи на личные разборки. Хотя поведение Бурлесона в них не выглядит достойным. Вот третья показалась исключительно по существу.
                      Припоминаю, когда был новичком в Oracle, некоторые советы Бурлесона действительно казались нелепыми… и не работали.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое