Full index scan

На данный момент, при сканировании любого индекса в PostgreSQL, дерево обходится в логическом порядке. В то же время, если для выполнения запроса нужно прочитать значительную часть индекса, то может быть более эффективно, с точки зрения диска, прочитать страницы диска подряд в их физическом порядке (full index scan). Реализовать такую возможность мешает проблема кокурентного доступа. Если в процессе full index scan произойдёт split определённой страницы, то есть шанс прочитать одни и те же данные два раза (“двойное чтение”) или не прочитать часть данных вообще (“потерянное чтение”, происходит если для split’а была использована страница с младшим адресом). Проблема двойного чтения не сущетсвенна при использовании bitmap index scan. Проблема потерянного чтения может быть решена, если использовать такой механизм concurrency, как в GiST, на основе sequence number’ов (SN). Благодаря им можно понять, что split страницы произошёл во время full index scan и нужно посетить right link. Задача состоит в том, чтобы реализовать full index scan для GiST. В дальнейшем нужно попробовать внедрить SN в B-tree и реализовать full index scan там.

В работе