В первой части мы разбирались, как Firebird забирает строку таблицы с диска. Во второй и третьей частях мы разбирались, что происходит с прочитанной строкой в процессе выполнения SELECT-запроса. Но остался неотвеченным такой вопрос: а как указать на строку таблицы, которую надо прочитать? В первой части рассматривались функции DPM_get() и DPM_fetch(), которые брали номер строки из параметра rpb->rpb_number. Но мы до сих пор не видели, откуда этот rpb_number берётся. Этим вопросом мы займёмся в этой части, разбираясь с подсистемами RecordSource, VIO и DPM.
RecordSource
В третьей части мы остановились в нашем погружении в глубины стектрейса на классе FullTableScan. Он не очень большой, и для понимания давайте сначала посмотрим на метод internalOpen(), который, скорее всего, будет вызван один раз в начале запроса, перед тем, как читать строки.
void FullTableScan::internalOpen(thread_db* tdbb) const
{
Database* const dbb = tdbb->getDatabase();
Attachment* const attachment = tdbb->getAttachment();
Request* const request = tdbb->getRequest();
Impure* const impure = request->getImpure<Impure>(m_impure);
impure->irsb_flags = irsb_open;
RLCK_reserve_relation(tdbb, request->req_transaction, m_relation, false);
record_param* const rpb = &request->req_rpb[m_stream];
rpb->getWindow(tdbb).win_flags = 0;
// Unless this is the only attachment, limit the cache flushing
// effect of large sequential scans on the page working sets of
// other attachments
if (attachment && (attachment != dbb->dbb_attachments || attachment->att_next)) {
BufferControl* const bcb = dbb->dbb_bcb;
if (attachment->isGbak() || DPM_data_pages(tdbb, m_relation) > bcb->bcb_count) {
rpb->getWindow(tdbb).win_flags = WIN_large_scan;
rpb->rpb_org_scans = m_relation->rel_scan_count++;
}
}
rpb->rpb_number.setValue(BOF_NUMBER);
if (m_dbkeyRanges.hasData()) {
impure->irsb_lower.setValid(false);
impure->irsb_upper.setValid(false);
EVL_dbkey_bounds(tdbb, m_dbkeyRanges, rpb->rpb_relation,
impure->irsb_lower, impure->irsb_upper);
if (impure->irsb_lower.isValid()) {
auto number = impure->irsb_lower.getValue();
const auto ppages = rpb->rpb_relation->getPages(tdbb)->rel_pages;
const auto maxRecno = (SINT64) ppages->count() *
dbb->dbb_dp_per_pp * dbb->dbb_max_records - 1;
if (number > maxRecno)
number = maxRecno;
rpb->rpb_number.setValue(number - 1); // position prior to the starting one
}
}
}Отметим тут вот что. Во-первых, выставляется флаг irsb_open. Во-вторых, получаем rpb из хранилища req_rpb, используя m_stream как ключ. Сто пудов m_steam - неизменяемое поле, уникальное для каждого RecordSource внутри запроса. И самое важное для нас в этом методе: rpb->rpb_number.setValue(BOF_NUMBER) , причём BOF_NUMBER = -1 . Почему именно -1 , может любое отрицательное значение подойдёт? Скоро узнаем. В завершающей части метода вычисляются ограничители irsb_lower и irsb_upper, в нашем случае этого не произойдёт, потому что m_dbkeyRanges не содержит данных.
Код метода FullTableScan::internalGetRecord() я уже приводил в третьей части, но тогда он оставил много вопросов. Поэтому я его приведу ещё раз, он небольшой, и рядом с предыдущим методом его проще будет понять.
bool FullTableScan::internalGetRecord(thread_db* tdbb) const
{
JRD_reschedule(tdbb);
Request* const request = tdbb->getRequest();
record_param* const rpb = &request->req_rpb[m_stream];
Impure* const impure = request->getImpure<Impure>(m_impure);
if (!(impure->irsb_flags & irsb_open)) {
rpb->rpb_number.setValid(false);
return false;
}
const RecordNumber* upper = impure->irsb_upper.isValid() ? &impure->irsb_upper : nullptr;
if (VIO_next_record(tdbb, rpb, request->req_transaction, request->req_pool, DPM_next_all, upper)) {
rpb->rpb_number.setValid(true);
return true;
}
rpb->rpb_number.setValid(false);
return false;
}Поскольку m_steam не меняется между вызовами internalOpen() и internalGetRecord(), и request также не меняется, то rpb будет тем же самым, что в internalOpen(), включая rpb_number. Дальше проверяется, что флаг irsb_open выставлен, его выставил internalOpen(). Ну и вызывается VIO_next_record().
Но прежде, чем мы туда пойдём, сделаем отступление.
Сборка Firebird
До сих пор мы только изучали исходный код, но что если мы захотим что-то поменять? Нам понадобится собрать исполняемый файл сервера из исходников. Пока мы ещё ничего не поменяли, но давайте просто попробуем собрать Firebird. Тогда потом не так страшно будет.
Инструкция по сборке не очень большая. Хорошая новость: она работает. Я собирал на Windows 10, используя Visual Studio 2022. В инструкции упомянуто, что нужен sed , это чистая правда, без него не собирается, при вызове make_all.bat будут ошибки вида "......\src\dsql\parse.cpp: No such file or directory". Я взял sed.exe из msys2, положил в firebird/builds/win32 его вместе с нужными ему dll-ками, и больше ошибок не было. Но копирование - не самый лучший вариант, в процессе сборки sed.exe удаляется из этого каталога, правильнее будет добавить в PATH каталог, где он лежит.
Для чего нам может пригодиться умение собирать Firebird из исходников на этом этапе?
Во-первых, в предыдущих частях статьи мы уже сталкивались с файлами, которые имеют расширение .epp . Эти файлы обрабатываются специальным препроцессором, и полученные .cpp файлы уже компилируются. Это означает, что использовать отладчик в .epp-файле не получится. Но в процессе билда будет создан .cpp-файл, и мы сможем в отладчике ставить там точки останова.
Во-вторых, мы можем собрать отладочный билд. Отладочный не в том смысле, что у нас будет информация о символах исполняемого файла, она у нас и так есть. В отладочном билде включены дополнительные функции в коде:
Функцию devNodePrint() можно будет вызывать из отладчика, чтобы получить текстовое описание иерархии узлов StmtNode. В не-отладочных билдах эта функция отсутствует. Иметь такое текстовое описание будет сильно удобнее, чем ходить по указателям в VSCode.
Для систем VIO и DPM будут работать VIO_trace(), который будет писать в log-файл подробности низкоуровневых операций, это мы очень хотим!
Для сборки отладочного билда нужно вызывать сначала "make_boot.bat DEBUG" , потом "make_all.bat DEBUG". Чтобы выполнять запросы к новой базе, вам нужно будет заново пройти шаги по созданию пользователей в security5.fdb, но есть способ проще: можно в firebird.conf прописать в свойстве SecurityDatabase путь к какой-нибудь существующей security5.fdb. В обоих случаях нужно помнить, что при пересборке всё это перезапишется: и свежая security5.fdb, и чистый firebird.conf.
Очень важный момент: в процессе сборки будут сформированы новые pdb-файлы с отладочной информацией (например temp/x64/debug/engine/engine13.pdb) и нужно сослаться на них из вашего отладчика.
Отладочная функция devNodePrint() печатает результат в стандартный вывод. На windows проще всего действовать так: перенаправить стандартный вывод в файл, запустив firebird.exe > output.log . А дальше ставим, например, точку останова в EXE_looper(), в строке, где вызывается node->execute(), и когда эта точка сработает, то в консоли отладчика пишем
devNodePrint((Jrd::DmlNode*)node)и после этого в файле output.log будет большая портянка с деревом узлов, очень удобно.
В каталоге gen будут созданы .cpp-файлы на основе .epp-файлов. Если вы работаете в VSCode, то можете столкнуться с тем, что вам не показывают каталог gen, VSCode правильно понимает, что это создаваемая и удаляемая штука, но нам он нужен, поэтому в settings.json в свойстве "files.exclude" убираем этот каталог.
С VIO_trace() на первых порах возникла проблема: я не видел никакого вывода в firebird.log! При внимательном чтении оказалось, что в файле vio_debug.h нужно раскомментировать строчку "#define VIO_DEBUG". Я это сделал, запустил пересборку, и словил ошибку компиляции в vio.cpp. Ай-ай, получается, разработчики сами не пользуются функциональностью VIO_trace(), иначе бы словили. Ладно, не беда, поправил, снова сборка. На этот раз make_boot.bat отработал без ошибок, но в make_all.bat вылезло очень много ошибок о ненайденных символах на стадии линковки. Чёрт, я надеялся, что это будет проще.
До меня не сразу дошло, в чём проблема. Я только что рассказывал про генерацию .cpp-файлов в каталоге gen. Так вот, после включения VIO_DEBUG часть этих сгенерированных файлов оказались пустыми. Эти файлы создавались на предыдущем этапе make_boot.bat. Я полез разбираться, как эти файлы генерируются, оказалось: вспомогательной утилитой gpre, которая сама собирается чуть раньше. При копании в cmd-файлах очень помогает расставлять echo и убирать начальную @ перед командами, от этого исполняемые команды начинают выводиться в консоли. Поняв, с какими параметрами запускается gpre, я вручную запустил генерацию, воспроизвёл пустой результат. Ну что же, мало нам было отладки firebird, будем отлаживать gpre. Для него даже pdb-файл создался. Кодогенерация должна была помочь в отладке, а теперь отладка приходит на помощь кодогенерации.
Чем прекрасен отладчик, так это тем, что он ловит всякие жёсткие ошибки сам. Я сначала отлаживался в пошаговом режиме, но потом мне наскучило, я тупо запустил программу на выполнение, и отладчик перехватил ACCESS VIOLATION. Хо-хо, при генерации .cpp-файлов используется VIO, и в функции VIO_record() прямо перед вызовом VIO_trace() происходило обращение по null-указателю. Я в первой части статьи приводил код VIO_record(), и там я для краткости убрал вызовы VIO_trace(), по ссылке можно увидеть первозданный вариант, а проблема вот тут:
Record* VIO_record(thread_db* tdbb, record_param* rpb, const Format* format, MemoryPool* pool)
{
SET_TDBB(tdbb);
#ifdef VIO_DEBUG
jrd_rel* relation = rpb->rpb_relation;
VIO_trace(DEBUG_TRACE,
"VIO_record (rel_id %u, record_param %" QUADFORMAT"d, format %d, pool %p)\n",
relation->rel_id, rpb->rpb_number.getValue(), format ? format->fmt_version : 0,
(void*) pool);
#endifОтладчик показывает, что параметр format не null, а relation вполне себе null. Ладно, не проблема, исправил и это.
После второго исправления всё собралось, и я смог созерцать в firebird.log подробное логирование систем VIO и DPM, красота! На всякий случай по тем ошибкам, которые я нашёл, завёл issue, создал PR в ветку 5.0, и его даже приняли.
Для нас, помимо удобства отладки, главным выводом будет то, что функции подсистемы VIO используются даже когда нет реального ввода-вывода, например при кодогенерации. Потом внимательнее проверим, каким образом.
А gpre - забавная штука. Судя по коду, который мелькал перед моими глазами в процессе пошаговой отладки, он поддерживает С, C++, Pascal, Ada и COBOL, что-то из восьмидесятых. Я уверен, в скором времени наткнёмся на код, который им сгенерирован.
VIO и DPM
Возвращаемся к коду. Функция VIO_next_record() небольшая (для наглядности я убрал VIO_trace, ради которых собирал debug build).
bool VIO_next_record(thread_db* tdbb, record_param* rpb, jrd_tra* transaction, MemoryPool* pool, FindNextRecordScope scope, const RecordNumber* upper)
{
SET_TDBB(tdbb);
const USHORT lock_type = (rpb->rpb_stream_flags & RPB_s_update) ? LCK_write : LCK_read;
do {
if (!DPM_next(tdbb, rpb, lock_type, scope))
return false;
if (upper && rpb->rpb_number > *upper) {
CCH_RELEASE(tdbb, &rpb->getWindow(tdbb));
return false;
}
} while (!VIO_chase_record_version(tdbb, rpb, transaction, pool, false, false));
if (rpb->rpb_runtime_flags & RPB_undo_data)
fb_assert(rpb->getWindow(tdbb).win_bdb == NULL);
else
fb_assert(rpb->getWindow(tdbb).win_bdb != NULL);
if (pool && !(rpb->rpb_runtime_flags & RPB_undo_data)) {
if (rpb->rpb_stream_flags & RPB_s_no_data) {
CCH_RELEASE(tdbb, &rpb->getWindow(tdbb));
rpb->rpb_address = NULL;
rpb->rpb_length = 0;
}
else
VIO_data(tdbb, rpb, pool);
}
tdbb->bumpRelStats(RuntimeStatistics::RECORD_SEQ_READS, rpb->rpb_relation->rel_id);
return true;
}Тут мы видим цикл do/while, внутри которого вызывается DPM_next(), если у него не получилось, то выходим, а если получилось, то вызывается VIO_chase_record_version(). Как же эти функции обмениваются данными? Ну, скорее всего через rpb, этакий контекст на все случаи.
Давайте посмотрим на DPM_next(). Как же прекрасно, что у нас теперь есть сгенерированный dpm.cpp, и мы можем зайти сюда отладчиком! Эта функция будет звездой нашей статьи, мы главным образом будем рассматривать именно её, иногда отвлекаясь, но всегда возвращаясь. Начнём же.
bool DPM_next(thread_db* tdbb, record_param* rpb, USHORT lock_type, FindNextRecordScope scope)
{
SET_TDBB(tdbb);
Database* dbb = tdbb->getDatabase();
CHECK_DBB(dbb);
WIN* window = &rpb->getWindow(tdbb);
RelationPages* relPages = rpb->rpb_relation->getPages(tdbb);
if (window->win_flags & WIN_large_scan) {
// Try to account for staggered execution of large sequential scans.
window->win_scans = rpb->rpb_relation->rel_scan_count - rpb->rpb_org_scans;
if (window->win_scans < 1)
window->win_scans = rpb->rpb_relation->rel_scan_count;
}
rpb->rpb_prior = NULL;
// Find starting point
rpb->rpb_number.increment();
USHORT slot, line;
ULONG pp_sequence;
rpb->rpb_number.decompose(dbb->dbb_max_records, dbb->dbb_dp_per_pp, line, slot, pp_sequence);
// If I'm a sweeper I don't need to look at swept pages. Also I should
// check processed pages if they were swept.
const bool sweeper = (rpb->rpb_stream_flags & RPB_s_sweeper);
jrd_tra* transaction = tdbb->getTransaction();
const TraNumber oldest = transaction ? transaction->tra_oldest : 0;
if (sweeper && (pp_sequence || slot) && !line) {
// The last record at previous data page was returned to caller.
// It is time now to check if previous data page was swept.
const RecordNumber saveRecNo = rpb->rpb_number;
rpb->rpb_number.decrement();
check_swept(tdbb, rpb);
rpb->rpb_number = saveRecNo;
}
ULONG dpSequence = rpb->rpb_number.getValue() / dbb->dbb_max_records;
ULONG page_number = relPages->getDPNumber(dpSequence);
if (page_number) {
fb_assert(window->win_page.getPageSpaceID() == relPages->rel_pg_space_id);
window->win_page = page_number;
const data_page* dpage = (data_page*) CCH_FETCH(tdbb, window, lock_type, pag_undefined);
const bool pageOk =
dpage->dpg_header.pag_type == pag_data &&
!(dpage->dpg_header.pag_flags & (dpg_secondary | dpg_orphan)) &&
dpage->dpg_relation == rpb->rpb_relation->rel_id &&
dpage->dpg_sequence == dpSequence &&
(dpage->dpg_count > 0);
if (pageOk) {
for (; line < dpage->dpg_count; ++line) {
if (get_header(window, line, rpb) &&
!(rpb->rpb_flags & (rpb_blob | rpb_chained | rpb_fragment)))
{
if (sweeper && !rpb->rpb_b_page && !(rpb->rpb_flags & rpb_deleted) && rpb->rpb_transaction_nr <= oldest)
continue;
rpb->rpb_number.compose(dbb->dbb_max_records, dbb->dbb_dp_per_pp,
line, slot, pp_sequence);
return true;
}
}
}
CCH_RELEASE(tdbb, window);
}
// Find the next pointer page, data page, and record
while (true) {
const pointer_page* ppage = get_pointer_page(tdbb, rpb->rpb_relation,
relPages, window, pp_sequence, LCK_read);
if (!ppage)
BUGCHECK(249); // msg 249 pointer page vanished from DPM_next
for (; slot < ppage->ppg_count;) {
const ULONG page_number = ppage->ppg_page[slot];
const UCHAR* bits = (UCHAR*) (ppage->ppg_page + dbb->dbb_dp_per_pp);
if (page_number && !PPG_DP_BIT_TEST(bits, slot, ppg_dp_secondary) &&
!PPG_DP_BIT_TEST(bits, slot, ppg_dp_empty) &&
(!sweeper || !PPG_DP_BIT_TEST(bits, slot, ppg_dp_swept)) )
{
dpSequence = ppage->ppg_sequence * dbb->dbb_dp_per_pp + slot;
relPages->setDPNumber(dpSequence, page_number);
const data_page* dpage = (data_page*) CCH_HANDOFF(tdbb, window,
page_number, lock_type, pag_data);
for (; line < dpage->dpg_count; ++line) {
if (get_header(window, line, rpb) &&
!(rpb->rpb_flags & (rpb_blob | rpb_chained | rpb_fragment)))
{
if (sweeper && !rpb->rpb_b_page && !(rpb->rpb_flags & rpb_deleted) && rpb->rpb_transaction_nr <= oldest)
continue;
rpb->rpb_number.compose(dbb->dbb_max_records, dbb->dbb_dp_per_pp,
line, slot, pp_sequence);
return true;
}
}
// Prevent large relations from emptying cache. When scrollable
// cursors are surfaced, this logic may need to be revisited.
if (window->win_flags & WIN_large_scan)
CCH_RELEASE_TAIL(tdbb, window);
else if (window->win_flags & WIN_garbage_collector &&
window->win_flags & WIN_garbage_collect)
{
CCH_RELEASE_TAIL(tdbb, window);
window->win_flags &= ~WIN_garbage_collect;
}
else
CCH_RELEASE(tdbb, window);
if (sweeper) {
// The last record at data page was not returned to caller.
// It is time now to check if this data page was swept.
const RecordNumber saveRecNo = rpb->rpb_number;
rpb->rpb_number.compose(dbb->dbb_max_records, dbb->dbb_dp_per_pp, line, slot, pp_sequence);
rpb->rpb_number.decrement();
check_swept(tdbb, rpb);
rpb->rpb_number = saveRecNo;
tdbb->checkCancelState();
}
if (scope == DPM_next_data_page)
return false;
if (!(ppage = get_pointer_page(tdbb, rpb->rpb_relation, relPages, window, pp_sequence, LCK_read))) {
BUGCHECK(249); // msg 249 pointer page vanished from DPM_next
}
}
if (scope == DPM_next_data_page)
{
CCH_RELEASE(tdbb, window);
return false;
}
slot++;
line = 0;
}
const UCHAR flags = ppage->ppg_header.pag_flags;
pp_sequence++;
slot = 0;
line = 0;
if (window->win_flags & WIN_large_scan)
CCH_RELEASE_TAIL(tdbb, window);
else
CCH_RELEASE(tdbb, window);
if ((flags & ppg_eof) || (scope != DPM_next_all))
return false;
}
}В самом начале выполняется rpb->rpb_number.increment() . Именно поэтому в FullTableScan::internalOpen() значение rpb_number было выставлено в -1 , после инкремента оно станет 0 и будет указывать на начальную строку таблицы. Поскольку rpb_number - это порядковый номер строки в таблице, его можно разложить на физические координаты: номер страницы указателей (pp_sequence), индекс страницы данных внутри страницы указателей (slot), и индекс строки внутри страницы данных (line). Это разложение выполнит rpb_number.decompose() , параметры slot, line и pp_sequence передаются по ссылке. Теперь можно попробовать прочитать страницу данных, в которой находится требуемая строка, и для этого понадобится ещё немного математики. Сначала посчитаем порядковый номер страницы данных dbSequence, поделив номер строки на количество строк в таблице данных. Чтобы превратить порядковый номер страницы в таблице в глобальный номер страницы page_number выполняется relPages->getDPNumber(dpSequence). Задержимся на этом месте поподробнее.
Вот как выглядит нужная нам функциональность класса RelationPages, а именно методы getDPNumber() и его друг setDPNumber():
struct DPItem
{
ULONG seqNum;
ULONG physNum;
ULONG mark;
static ULONG generate(const DPItem& item)
{
return item.seqNum;
}
};
Firebird::SortedArray<DPItem, Firebird::InlineStorage<DPItem, MAX_DPMAP_ITEMS>, ULONG, DPItem> dpMap;
ULONG getDPNumber(ULONG dpSequence) {
FB_SIZE_T pos;
if (dpMap.find(dpSequence, pos)) {
if (dpMap[pos].mark != dpMapMark)
dpMap[pos].mark = ++dpMapMark;
return dpMap[pos].physNum;
}
return 0;
}
void setDPNumber(ULONG dpSequence, ULONG dpNumber) {
FB_SIZE_T pos;
if (dpMap.find(dpSequence, pos)) {
if (dpNumber) {
dpMap[pos].physNum = dpNumber;
dpMap[pos].mark = ++dpMapMark;
}
else
dpMap.remove(pos);
}
else if (dpNumber) {
dpMap.insert(pos, {dpSequence, dpNumber, ++dpMapMark});
if (dpMap.getCount() == MAX_DPMAP_ITEMS)
freeOldestMapItems();
}
}Поле dpMap - это плоская мапа, выполненная в виде сортированного массива структур DPItem. Поля у структуры простые: порядковый номер внутри таблицы seqNum, глобальный номер страницы physNum и некий счётчик использования mark. Когда я назвал эту мапу плоской, я имел в виду, что в ней нет никаких деревьев, и нет отдельного хранения ключей, ключом является одно из полей хранимых структур, в нашем случае seqNum. Поскольку массив отсортирован, то можно использовать двоичный поиск. Повторять, как выглядит двоичный поиск, никому не рано и никогда не будет лишним, так что вот его здешний вариант:
bool find(const Key& item, size_type& pos) const
{
fb_assert(sorted);
size_type highBound = this->count, lowBound = 0;
while (highBound > lowBound) {
const size_type temp = (highBound + lowBound) >> 1;
if (Cmp::greaterThan(item, KeyOfValue::generate(this->data[temp])))
lowBound = temp + 1;
else
highBound = temp;
}
pos = lowBound;
return highBound != this->count &&
!Cmp::greaterThan(KeyOfValue::generate(this->data[lowBound]), item);
}Возвращаемся в DPM_next(). Получив физический/глобальный номер страницы page_number мы сохраняем его в window->win_page. Зачем? Потому что window - это ещё один контекст, через который будут передаваться всякие параметры в DPM и VIO. Зачитываем страницу, вызвав CCH_FETCH(), номер страницы лежит в window.
pag* CCH_fetch(thread_db* tdbb, WIN* window, int lock_type, SCHAR page_type, int wait,
const bool read_shadow)
{
SET_TDBB(tdbb);
const LockState lockState = CCH_fetch_lock(tdbb, window, lock_type, wait, page_type);
BufferDesc* bdb = window->win_bdb;
SyncType syncType = (lock_type >= LCK_write) ? SYNC_EXCLUSIVE : SYNC_SHARED;
switch (lockState) {
case lsLocked:
CCH_fetch_page(tdbb, window, read_shadow); // must read page from disk
if (syncType != SYNC_EXCLUSIVE)
bdb->downgrade(syncType);
break;
case lsLatchTimeout:
case lsLockTimeout:
return NULL; // latch or lock timeout
}
adjust_scan_count(window, lockState == lsLocked);
// Validate the fetched page matches the expected type
if (bdb->bdb_buffer->pag_type != page_type && page_type != pag_undefined)
page_validation_error(tdbb, window, page_type);
return window->win_buffer;
}Глубже погружаться не будем, запомним только, что страница зачиталась в window->win_buffer.
Продолжаем разбор DPM_next(). Имея страницу, начинаем искать подходящую строку, проходя в цикле по строкам страницы, начиная с номера строки line. Вызываем так хорошо знакомую нам по первой части функцию get_header(), сама страница передаётся через параметр window, а номер строки через параметр line. Функция get_header() зачитает заголовочную часть строки и заполнит rpb->rpb_flags. Если всё прошло хорошо и флаги нас устраивают, то мы готовы возвращаться. Поскольку мы могли пропустить в цикле часть строк, и текущее значение line может отличаться от начального, то rpb_number, соответствующий реально прочитанной строке, склеивается из компонент, чтобы при чтении следующей строки начать уже с этого места.
На этом месте половина читателей должна уже спать от скуки, поэтому, чтобы взбодриться, вопрос на внимательность: если SortedArray::find() вернёт false, то что вернёт RelationPages::getDPNumber() как номер страницы? Она вернёт 0, это точно норм? Да, потому что страница с физическим номером 0 является специальной страницей базы и не может принадлежать ни одной таблице. Почему я об этом спросил? Потому что в нашем случае именно это и произойдёт, при первом вызове DPM_next() в relPages.dpMap будет пусто, отладчик не даст соврать. Поэтому всё, что мы только что рассматривали про DPM_next(), всё выполнение ветки "if (page_number)" произойдёт только при втором и последующих вызовах, а при первом мы провалимся ко второй половине DPM_next().
Мы на строке 80, тут в цикле while(true) происходит такая последовательность шагов. Сначала вызовом get_pointer_page() зачитывается страница указателей. Далее в цикле идём по указателям на страницы данных, начиная с рассчитанного номера slot, и проверяем разные флаги. Если страница нам подошла, то мы готовы читать строки из неё, поскольку в таблице указателей хранятся глобальные/физические номера страниц. Но перед этим посчитаем локальный порядковый номер страницы dpSequence и сохраним отображение локального номера на глобальный, вызвав relPages->setDPNumber(dpSequence, page_number) . Это очень важная оптимизация, она позволит при последующих чтениях строк не обращаться к странице указателей, и будет выполняться первая часть DPM_next(). Таким образом получается, что relPages.dpMap - это такой лениво наполняемый кеш соответствий между логическими страницами и физическими. Производительность этого кеша - логарифмическая, и у него есть ограничение MAX_DPMAP_ITEMS. Поскольку кеш хранится как отсортированный массив, то весьма важно, чтобы элементы добавлялись в порядке возрастания, что позволит просто добавить элемент в конец, а не раздвигать массив внутри. Но вроде бы именно добавление в конец и происходит, а вообще я добавлю в своей отладочной сборке какое-нибудь логирование в случае, если происходит вставка в середину.
Загрузив страницу данных, выполняем цикл по строкам, начиная с рассчитанного номера line. Этот цикл полностью аналогичен тому, который выполняется в первой части этой функции: зачитываем заголовки, проверяем флаги, если нашли подходящую, то склеиваем номер строки и выходим.
Если на странице не подошла ни одна строка, то страницу нужно выгрузить. При этом проверяется флаг WIN_large_scan, если он выставлен, то страница выгружается в конец страничного кеша. Если вернуться к началу статьи и поглядеть в код функции FullTableScan::internalOpen(), но можно увидеть, что флаг WIN_large_scan выставляется в случае, когда у таблицы много страниц.
У функции DPM_next() есть параметр scope. Одно из возможных значений DPM_next_data_page означает, что если не найдена строка на текущей странице данных, то дальше искать не надо. Но это не наш случай, у нас DPM_next_all (см. FullTableScan::internalGetRecord(), как вызывается VIO_next_record()). В нашем же случае при достижении конца строк на странице увеличивается slot и пробуем страницы дальше.
Итак, что же будет результатом выполнения DPM_next() ? Результатов много:
Выходное значение true, если нашли строку, false если нет
Поле rpb->rpb_number хранит полный номер строки
Поле window->win_buffer содержит страницу данных
В rpb заполнены те поля, которые заполнила get_header(), включая rpb_address и rpb_length, которые указывают на данные в строке.
После возврата в VIO_next_record() происходит проверка, что rpb->rpb_number не превысил заказанный предел, если он есть. В случае превышения цикл заканчивается, а если предела нет или он не превышен, то управление переходит в VIO_chase_record_version().
Забавный факт, который я заметил, выполняя код в отладчике. Я тестирую на небольшой таблице, для которой все строки помещаются в одну страницу данных. Так вот, помимо этой страницы Firebird создал ещё одну страницу данных, пустую. Не жадный, а домовитый.
Заключение
Оказалось, что FullTableScan тупо начинает номера строк от 0. А DPM_next() перебирает строки по возрастанию номеров, превращает номер в набор компонент, зачитывает строку, возможно пропускает её и переходит к следующей, пока не найдёт подходящую, и возвращает номер прочитанной строки.
Мы не рассмотрели несколько интересных функций, которые вызываются из кода, который мы смотрели: DPM_data_pages() вызывается из FullTableScan::internalOpen(), get_pointer_page() вызывается из DPM_next(). Их смысл был нам понятен из названия, а подробности их устройства мы обязательно рассмотрим в следующих частях.
Упражнения
Мапа преобразования локальных номеров страниц в физические предоставляет логарифмическую производительность. Для чтения каждой строки на странице нужно отыскивать физический номер страницы, и поиск в большой мапе может быть медленным. Поскольку в хорошем случае в мапе хранится непрерывная возрастающая последовательность, то есть идея для оптимизации: уменьшить размер этого кеша до 1. Шутка. Идея такая: попробовать сразу получить элемент по индексу dbSequence и проверить значение seqNum, если не получилось, то откат на двоичный поиск. Попробуйте.