07.02.2017 23:46
nightwolf_du 14 11200 Источник

Вступление


Волей судеб, я работаю в enterprise около 5 лет, за это время набрался пул вопросов о реляционных базах данных, и оные регулярно всплывают в голове перед сном.

Но выяснять подробные ответы на них дорого по времени, ибо отправляют в чудесную страну многотомных мануалов, лингвистики & статистики и толстых книг.

Прошу помощи у сообщества в искоренении своего и чужого невежества.
Примечание: ответы на часть вопросов были освещены в этой статье, но раскрыты не полностью.

Свои эмпирические предположения спрячу под кат.

Вопросы


  1. Что происходит в субд при размере таблицы+кэш+индексы << оперативной памяти?

    Предположения и новые вопросы
    Логика и некоторый опыт подсказывают, что если у базы в настройках указан размер меньше оперативной памяти, и в системе есть достаточно памяти для её размещения — база должна уложиться целиком в оперативку, но, т.к. ACID требует согласованность и долговечность — должна происходить фиксация на диск, хотя бы через подсистему логов. Так ли это на самом деле? Если не так- можно ли настроить субд таким образом, чтобы чтение всегда осуществлялось из оперативной памяти?

  2. Если размер таблицы >> оперативной памяти, а индекса по ней нет(или мы в него не попадаем) как менеджер памяти определяет, какое количество места может занять под выборку из таблицы?

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

  3. Как и куда осуществляется поочередная выборка записей таблицы(и откуда, память/диск) для фильтрации? Какие при этом произойдут блокировки (для бд с версионированием записей и без)?

    Предположения
    • Скорее всего, есть фасад единого менеджера памяти, который в состоянии выдернуть значение из кэша/индекса, и если его там нет — взять с диска.
    • Наверняка, он имеет очередь обработки запросов на получение строк. Наверняка, порядок архитектуры: оптимизатор запросов, определяющий откуда выбираем значение — таблица/индекс, менеджер, определяющий где индекс/таблица — в памяти или на диске, кэш — есть ли там строки индекса/таблицы с заданным идентификатором, подтягивание потоком в память индекса/таблицы, прогон нужной части индекса/таблицы через оперативку с выборкой нужных значений.
    • Куда — скорее всего, в отдельный пул памяти процесса, если места нет — ос или сами мапим его на диск


  4. Что произойдет, если размер подходящей выборки >> оперативной памяти? Какие базы умеют отдавать данные потоком входе выборки, а какие — только по полной готовности выборки? Можно ли это поведение настроить?

    Предположения и новые вопросы
    • Блокировки будут, определенно, зависеть от настроек требуемой согласованности бд(wiki, Уровень_изолированности_транзакций).
    • Вопрос, на который у меня всё-таки нет легкого ответа — могут ли строки меняться при чтении большого объема, несмотря на поток чтения? Будет ли это подпадать под ситуацию «грязного чтения»? Что произойдет, если другая транзакция пытается изменить строку, которую мы сейчас читаем? Является ли чтение транзакцией, которая может блокировать другие транзакции? При версионировании строк всё проще — читаем строки с версией = последняя закоммиченная на момент старта чтения
    • Теоретически, должна класться на диск средствами бд/ос


  5. Как оптимизатор запросов формально доказывает эквивалентность условий в предложении ON для JOIN-запроса, и предложении WHERE этого запроса? Пример под катом.

    Пример и предположения
    • В pg неоднократно замечал отсутствие разницы в производительности и плане запросов 

      select * from a 
inner join b 
on a.id = b.id 
where a.n > N and b.n <N
      и 
      select * from (select * from a where a.n > N)  as a
inner join (select * from b where b.n <N ) a b 
on a.id = b.id

    • Даже для более сложных запросов, где условия были несколько «выше» в дереве построения запросов pg неким образом доказывал эквивалентность и выбирал на join не весь объем данных, а только подходящий под выборку.
    • Т.е. есть некий мехнизм распространения условий выборки по дереву запросов. MS-SQl 2008 вел себя хуже и показывал существенную разницу во времени прохождения запросов. Почему?
      Какими методами из логики/программирования можно доказать эквивалентность on и where?
      Когда и где это работает?


  6. Как происходит работа с индексом по более чем одному полю? Как происходит работа с b-tree индекcом, если он не влазит целиком в оперативную память? Через виртуальную память ос? Или есть способ загружать индекс частично?

    С чем связан вопрос
    Мне не удаётся понять, как организовано b-tree, когда колонок в индексе > 1 и они разных типов. Логичное предположение — ключом дерева является некоторая хэш функция от колонок, но тогда явно требуется соблюдение условия, что
    H(a,b) > H(a) & H(a,b) > H(b) & H(a,b) < H(a +1, b) & H(a, b+1) < H(a+1)
    я догадываюсь, что с этим может помочь перцептивный хэш с некоторыми «разрядами», где разряд соответствует колонке, но меня смущает длина хэша.
    Другим вариантом мне видится не делать хэш, а явно сравнивать значения полей индекса при загрузке/выгрузке из него. Но тогда не ясно, как сработает 

    select * from A 
where  A.b > 1 A.c < 3
    если индекс объявлен как
    <A.a, A.b, A.c>
    Как мы будем обходить дерево не имея ограничения по первому уровню?
    Будет ли планировщик использовать данный индекс?
    Связанные вопросы — имеет ли значение порядок перечисления полей индекса в условии WHERE?
    Сможем ли мы попасть в индекс, если часть полей перечислено в предложении ON подзапроса, а часть в WHERE более общего запроса, т.е. работает ли перераспределение условий вместе с оценкой попали/не попали в индекс?
    Как на это можно повлиять?

    Более специализированные вопросы, на которые также тяжело дается ответ.

    1. При каких условиях стоит делать таблицу партиционированной?
    2. Когда партиций слишком много?
    3. На каком размере стоит задуматься о шардировании?
    4. Когда нормализовывать, а когда денормализовывать схему данных?
    5. На какой длине строки и почему именно на такой многие бд выносят её в отдельное хранилище?
    6. Почему в pg использование CTE в запросах значительно быстрее реализации с временной таблицей? Так ли это? Если так — есть ли исключения?

    Пояснения


    Я рад был бы найти подобные ответы сам, но большая часть вопросов тонет под потоками флуда, или скрывается глубоко в документации/исходниках крупных проектов. Ответы из комментариев будут приложены к соответствующим вопросам. Что смогу — постараюсь найти сам.

    Спасибо за понимание.
Поделиться с друзьями
-->

Комментарии (14)


  1. musicriffstudio
    08.02.2017 09:55
    #10058436
    +1

    Я рад был бы найти подобные ответы сам, но большая часть вопросов тонет под потоками флуда, или скрывается глубоко в документации/исходниках крупных проектов


    См. переводную статью на этом же сайте:
    https://habrahabr.ru/company/mailru/blog/266811/


  1. Siemargl
    08.02.2017 10:21
    #10058474
    -7

    Вопросы достаточно сложные.

    Потому придется читать большие и серьезные учебники по теории программирования, алгоритмам (можно начинать прямо с Кнута — там кое на что есть ответы), а потом уже по теории реляционных БД и их устройству.

    Вариант: посаны, расскажите по быстренькому, как устроена ядерная бомба, не прокатывает.

    P.S.Можно взять СУБД с количеством исходников поменьше для изучения «в натуральной среде обитания», вроде sqlite или firebird


    1. x512
      08.02.2017 10:50
      #10058536
      +3

      Вариант: посаны, расскажите по быстренькому, как устроена ядерная бомба, не прокатывает.

      Если цель создать такую бомбу, то вы совершенно правы. А вот если надо объснить как эксплуатировать уже созданную, то можно и на фене объяснить)


  1. smagen
    08.02.2017 11:25
    #10058602
    +1

    Вопрос 5

    В тексте вопроса вы говорите об эквивалентности ON и WHERE условий. Но пример приводите когда, условия WHERE проваливаются из верхнего запроса в подзапросы для отдельных таблиц, а условие ON остаётся неизменным.

    Вообще, в случае с INNER JOIN всё достаточно просто. Для начала нет никакой разницы между условиями, которые вы пишете в ON и в WHERE запроса верхнего уровня.

    Т.е. можно затолкать всё в ON.

    SELECT *
FROM a INNER JOIN b
ON a.id = b.id AND a.n > N AND b.n <N


    А можно запихнуть всё в WHERE – результат не изменится.

    SELECT *
FROM a INNER JOIN b ON true 
WHERE a.id = b.id AND a.n > N AND b.n <N


    Точно также те условия, которые касаются только одной из соединяемых таблиц, можно выносить к ним в подзапрос, что вы показали на примере. А можно и наоборот условия из подзапросов вытаскивать наверх.

    В случае с LEFT/RIGHT/FULL OUTER JOIN всё несколько сложнее и оптимизатор более ограничен в действиях, потому что нужно не потерять среди результатов тех строк, которые не имеют соответствующих с другой стороны JOIN'а.


  1. smagen
    08.02.2017 11:27
    #10058612
    +2

    Вопрос 4

    В случае PostgreSQL большие выборки нужно получать с помощью курсоров. С помощью курсоров можно получать результат запроса кусками, не материализуя его полностью в оперативной памяти. Например, так поступает pg_dump.


  1. smagen
    08.02.2017 11:45
    #10058650
    +4

    Вопрос 6

    OMG, ну какой ещё хэш? :)

    Двухколоночный индекс по колонкам a, b – это фактически индекс по композитному ключу (a, b). Т.е. нужно пару (a, b) рассмативать как единое целое. Когда мы сравниваем два композитных ключа, то сравнивается вначале первая часть, потом вторая и т.д. Т.е. для случая двух колонок сравнение будет осуществляться следующим образом.

    (a1, b1) = (a2, b2) <=> a1 = a2 AND b1 = b2
    (a1, b1) > (a2, b2) <=> (a1 > a2) OR (a1 = a2 AND b1 > b2)
    (a1, b1) < (a2, b2) <=> (a1 < a2) OR (a1 = a2 AND b1 < b2)

    Отсюда следует то, какие заапросы мы можем хорошо ускорять с помощью такого индекса, например:
    WHERE a = 1 AND b = 1
    WHERE a > 1 AND a < 10
    WHERE a = 1 AND b > 1 AND b < 10
    WHERE a = 2 ORDER BY b LIMIT 10
    ORDER BY (a, b) LIMIT 10

    В вашем примере, особой пользы от индекса нет. Но, всё равно, можно полностью отсканировать индекс, проверяя данное условие. Это может быть быстрее, чем полностью сканировать таблицу, хотя не всегда. Также если у колонки a не много уникальных значений, то можно таки исхитриться оптимизировать этот запрос, не проходя весь индекс целиком. Фактически придётся перебрать все значения колонки a, и для каждого из них осуществлять поиск. Но это очень нетривиально, PostgreSQL, к примеру, так не делает.

    Ещё про индексы рекомендую почитать use-the-index-luke.com.

    По поводу попадания индекса в память. Вообще b-tree – это специальная структура данных, которая призвана уметь работать во внешней памяти. В частности, имеенно поэтому данные храняться страницами, чтобы в случае чего не дёргать диск слишком маленькими запросами. Т.е. b-tree специально так задумано, чтобы нормально работать будучи загруженным в память лишь частично. У большинства СУБД есть свой собственный кэш для данных, например у PostgreSQL это shared buffers. Файловый кэш ОС в PostgreSQL также используется, но в некоторых других СУБД он специально отключается, чтобы избегать двойного кэширования.


  1. Melkij
    08.02.2017 12:38
    #10058806
    +7

    Важно: невозможно ответить в отрыве от конкретной СУБД. Т.к. реализация и поведение может быть в корне различным, SQL предписывает только определённое поведение, а как оно достигается — проблема реализации.
    Могу чуток написать про Postgresql. Не разработчик этой субд, но постараюсь сильно не наврать =)

    Как происходит работа с индексом по более чем одному полю? Как происходит работа с b-tree индекcом, если он не влазит целиком в оперативную память? Через виртуальную память ос? Или есть способ загружать индекс частично?

    С каким именно индексом? Многоколоночные btree и gin ведут себя по разному.
    Хорошее описание btree есть вот тут: http://use-the-index-luke.com/sql/anatomy
    btree изначально оптимизирован для размещения на диске, а не в памяти. Поэтому состояние «индекс не влез в память» — это штатная картина. Что не исключает того, что картина эта очень медленная. Возьмите железку, в которую хотя бы индексы влезают, это не так дорого даже за 256гб ram.
    Многоколоночный btree: http://use-the-index-luke.com/sql/where-clause/the-equals-operator/concatenated-keys
    Postgresql разбивает всё, и таблицы и индексы на странички памяти в 8кб. Поэтому всё состоит из кусочков по 8кб каждый. В память и файлового кэша ОС и shared_buffers подтягиваются только запрошенные блоки по 8кб и вытесняются чем-то родственным LRU. Что было найдено в буфере, а что просили ОС прочитать (из файлового кэша или с диска) — см. explain (analyze, buffers). Лучше с track_io_timing = On

    Как оптимизатор запросов формально доказывает эквивалентность условий в предложении ON для JOIN-запроса, и предложении WHERE этого запроса?

    Оптимизатор может переписать исходный запрос полностью, он не строго следует написанному (но не изменяя результат запроса). Заинлайнить вложенный подзапрос и в соответствии с этом выбрать план получше — да, это может сделать.
    Оптимизатор — это основная и весьма сложная часть СУБД. Ему надо делать много работы и делать её очень быстро. Поэтому может делать разные интересные вещи, а другие вещи делать не может. Что именно может делать — только в исходник, вероятно. На слуху только некоторые отдельные моменты.

    Какими методами из логики/программирования можно доказать эквивалентность on и where?

    Для inner join — тождественны, доказательства не требуют.
    Какие части будут проверены при объединении, а что после — на усмотрение оптимизатора.

    Что происходит в субд при размере таблицы+кэш+индексы << оперативной памяти?

    Что такое кэш? В смысле почему вы его указываете наравне с таблицами и данными?
    Вся база влезла в shared_buffers — запросы чтения к дискам не обращаются.
    Вся база не влезла в shared_buffers, но влезла в файловый кэш ОС — запросы чтения к дискам не обращаются. Планировщик будет смотреть в effective_cache_size (это ваша обязанность сказать, на какой объём кэша ОС может рассчитывать база), если видит что вроде помещается — то будет использовать более агрессивные алгоритмы поиска.
    Читать с дисков всё-таки могут — сами воркеры, если им потребовались временные файлы/таблицы, куда предварительно что-то понаписали.
    Операции записи — WAL с fsync при коммите, сами изменения в страницах данных — только в памяти и когда-нибудь попозже будут сброшены на диск чекпоинтером или самим воркером, если ему не хватит чистых shared_buffers (не надо так, тюньте свой checkpointer на более агрессивную работу).

    Если размер таблицы >> оперативной памяти, а индекса по ней нет(или мы в него не попадаем) как менеджер памяти определяет, какое количество места может занять под выборку из таблицы?

    Никак. Делать ему больше нечего.
    Поднимает очередную страничку памяти с диска, кладёт в shared_buffers. Если в shared_buffers нет места — выкидывает наименее используемую страничку оттуда и кладёт свою. И так пока не переберёт всю табличку.

    При каких условиях стоит делать таблицу партиционированной?

    Она очень большая. И по результату тестов вы что-то выиграете от нарезки на части. Например, возможность не делать delete по много записей, а дропнуть партицию целиком, например при переносе в архив.

    Когда партиций слишком много?

    Когда время планирования раздувается до неинтересных величин. Партицирование в pg делается не предназначенными для того методами. До сотни партиций должно работать внятно.
    https://www.postgresql.org/docs/current/static/ddl-partitioning.html
    All constraints on all partitions of the master table are examined during constraint exclusion, so large numbers of partitions are likely to increase query planning time considerably. Partitioning using these techniques will work well with up to perhaps a hundred partitions; don't try to use many thousands of partitions.


    На каком размере стоит задуматься о шардировании?

    Когда вы упёрлись в производительность записи.

    Когда нормализовывать, а когда денормализовывать схему данных?

    Конкретная задача. Опыт.

    На какой длине строки и почему именно на такой многие бд выносят её в отдельное хранилище?

    Большая строка плохо помещается в страничку памяти фиксированного размера. Простенький апдейт рядом лежащего счётчика — и из-за MVCC нам нужно копировать всю эту огромную строчку. А если её выкинуть в toast — то только ссылку на toast запись.
    А уж если вы нормально пишете запросы, а не select *, то из toast данные можно и вообще не вычитывать, если их не запросили явно.

    Почему в pg использование CTE в запросах значительно быстрее реализации с временной таблицей? Так ли это? Если так — есть ли исключения?

    Временные таблицы в pg сделаны не слишком качественно. Они работают, работают хорошо. И становится не очень хорошо, если их создавать и удалять много и часто.
    Временная таблица выполняет запись на диск при своём создании, а так же регистрируется в pg_catalog — что ведёт к распуханию последнего. А распухание каталога — замедление абсолютно всех других запросов.
    CTE так же материализует свой результат (поэтому нехорошо, если в cte части получается гигантский объём данных, который потом фильтруется в других частях запроса), но в каталог не попадает.
    Для какого-нибудь OLAP — надо смотреть конкретику. Вероятно, нет статистики для временной таблицы — потому что автовакуум не видит временные таблицы и analyze надо дёргать вручную — и, как следствие, план выбирается наугад.
    По временной таблице зато можно индексы повесить.


  1. michael_vostrikov
    08.02.2017 13:47
    #10059092

    Интересует такой вопрос.
    Если добавить в СУБД возможность каким-то образом отмечать внешние ключи как one-to-one или one-to-many, может ли это дать какое-то улучшение производительности в выборках с джойнами?


    1. Melkij
      08.02.2017 14:08
      #10059186

      Внешние ключи проверяются при записи. Чтение они трогают только одним моментом — для работы внешнего ключа создаётся индекс (иногда создаётся неявно) и этот индекс может использоваться при чтении.
      Соответственно вся разница 1:1 и 1: м связи в том, уникальный индекс создан или нет.


      1. michael_vostrikov
        08.02.2017 16:51
        #10059654

        Ок, немного непонятно сформулировал. Например, есть грид со строками, в основной сущности используются поля типа state_id, category_id, а в гриде нужны текстовые значения, и при выборке делаются джойны. Вопрос в том, что если вместо INNER JOIN ON condition указывать что-то типа INNER JOIN BY foreign_key, а для foreign_key указать, что внешняя запись точно одна, можно ли в движке СУБД как-то использовать эту информацию для улучшения производительности? Например, при изменении сохранять в метаинформации прямую ссылку на строку из другой таблицы. Или пользы от этого будет мало?


        1. Melkij
          08.02.2017 17:34
          #10059742

          для foreign_key указать, что внешняя запись точно одна

          По стандарту FK вообще указывает исключительно на уникальный ключ. Ссылка на неуникальное значение — это отхождение от стандарта, в mysql такое помню было.
          Разница лишь в том, уникальный там индекс или нет. Уникальный индекс знает, что если строку нашли — можно сразу поиск прекращать. Неуникальный — пробежит по индексным записям до нарушения условия.

          при изменении сохранять в метаинформации прямую ссылку на строку

          А что считаем прямой ссылкой? Значение ключа? Так его и храним. И потом ищем по индексу.
          Позиция в датафайле? Так их там много разных одновременно. Мультиверсионник же, что postgresql что innodb. При одной видимой в таблице строке может одновременно существовать много копий, видимых в других транзакциях (или никому не видимых, и они будут вычищаться потом).
          Всё равно хранить всё ссылки на страницы? Тогда при обновлении записи в таблице надо обновлять индексы, надо обновить все версии строк ссылающейся на эту таблицы, при сборе мусора опять же обновлять не только один индекс, но и все связанные таблицы.
          И всё это ради экономии поиска по индексу, который всё-таки весьма быстро сделан. И при этом всё равно во внешнюю таблицу надо ходить.

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


          1. michael_vostrikov
            08.02.2017 18:06
            #10059804

            Действительно, не подумал. Спасибо за разъяснение.


      1. michael_vostrikov
        09.02.2017 08:51
        #10060536

        Еще один странный вопрос. Есть тип фиксированной длины CHAR(N) с дополнением пробелами. Почему нет какого-нибудь типа ZEROCHAR(N) с дополнением нулями? Мне кажется, это позволит иметь строки с текстом, но фиксированной длины, и некоторые запросы могут работать быстрее. В MySQL например VARCHAR хранится в строке, и строки получаются разной длины.

        ZEROCHAR(4) и ZEROCHAR(8) можно использовать как uint4 и uint8, что позволит иметь строковые первичные/внешние ключи, но обрабатывать их как целые числа, без строковых операций. Что думаете по этому поводу?


        1. Melkij
          09.02.2017 11:43
          #10060814
          +1

          Зачем может быть нужно дополнение нулями?
          Postgresql открытым текстом говорит, что от строки текста фиксированной длины никаких плюсов не получает и, наоборот, char обычно медленнее varchar как по причине большего занимаемого места, так и из-за необходимости дополнительной обработки процессором.

          There is no performance difference among these three types, apart from increased storage space when using the blank-padded type, and a few extra CPU cycles to check the length when storing into a length-constrained column. While character(n) has performance advantages in some other database systems, there is no such advantage in PostgreSQL; in fact character(n) is usually the slowest of the three because of its additional storage costs. In most situations text or character varying should be used instead.


          varchar в postgresql тоже непосредственно в строке живёт. Короткие text, кстати тоже. Вот если строка не влезает в страничку памяти — уезжает гарантированно. А так — мануал говорит что дефолтное пороговое значение — размер строки данных превышает 2кб. Получается, всё живёт непосредственно в строке, пока строка не достигает порогового значения. А когда превышает — что-нибудь большое сжимается и уезжает жить отдельно.

          позволит иметь строковые первичные/внешние ключи, но обрабатывать их как целые числа

          Есть нативный enum. Строковое представление для целочисленного перечисления и есть, без требования ограничиться 4 или 8 символами.