page

package
v0.0.0-...-b72ed76 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 18, 2023 License: MIT Imports: 4 Imported by: 0

Documentation

Overview

In postgres, page is implemented with the data layout called `slotted page`. Slotted page has slot array in page header which points to tuple(kind-of row) within the page. The figure below may be helpful to understand the structure. This is cited from postgres comment. `linp` in the figure is `slot` and the space from `pd_lower` to `pd_upper` is free space where the tuple will be inserted later.

  • +----------------+---------------------------------+
  • | PageHeaderData | linp1 linp2 linp3 ... |
  • +-----------+----+---------------------------------+
  • | ... linpN | |
  • +-----------+--------------------------------------+
  • | ^ pd_lower |
  • | |
  • | v pd_upper |
  • +-------------+------------------------------------+
  • | | tupleN ... |
  • +-------------+------------------+-----------------+
  • | ... tuple3 tuple2 tuple1 | "special space" |
  • +--------------------------------+-----------------+

see: https://github.com/postgres/postgres/blob/bfcf1b34805f70df48eedeec237230d0cc1154a6/src/include/storage/bufpage.h#L29-L42

The structure of slotted page is mainly for the table's tuple, But this structure is also used with fsm/vm/clog/wal although slot is not used. `slot` within the structure is beneficial for mainly two reasons - the variable size of tuple can be stored

  • without slot, the offset of each tuple whose size is variable cannot be identified easily while the offset can be calculated easily without slot when the size of tuple is fixed

- tuple can be moved/removed if necessary

  • for example, index points to slot, not the actual location of tuple. when the tuple is moved to other location within the page, index doesn't have to be updated. just update the slot and make the slot point to the new location of tuple. this happens when vacuum removes dead tuples and compact the page

`item` is interchangeably used with `heap tuple` / `index tuple` ...

item-related interface is - GetItem(PagePtr, SlotIndex): gets item from page. the location of the item is calculated from SlotIndex's Slot - AddItem(PagePtr, ItemPtr, SlotIndex): adds item to the page. if the page does not have enough space, return error.

Page is the unit of I/O in ppdb. Disk manager organizes file as a collection of pages. Page in ppdb may be called `block“ in postgres. Page is used not only by the main disk manager but also by the clog/wal disk manager

Index

Constants

View Source 
const (

	// lower offset exported for fsm and vm
	LowerOffsetOffset = uint16(flagsOffset) + 2
)

byte offset of page header

View Source 
const PageSize = 8192

PageSize is the byte size of page. 8KB is the default size in postgres see block_size parameter in https://www.postgresql.org/docs/current/runtime-config-preset.html

Linux OS page size is probably 4KB so torn page(partial writes) can happen. This can be avoided by full page writes (the functionality of WAL) Full page writes is probably so-called `physical logging` (not `logical logging` or `physiological logging`) see https://github.com/postgres/postgres/blob/5e7bbb528638c0f6d585bab107ec7a19e3a39deb/src/backend/storage/page/README#L36-L46

Variables

This section is empty.

Functions

func AddItem 

func AddItem(page PagePtr, item ItemPtr, si SlotIndex) error

AddItem adds item to the page AddItem does the following - get slot index where the item will be inserted: find free slot or, when no free slot, extend new slot - generate slot data and insert it to the slot index. - insert item to the page - update page header see https://github.com/postgres/postgres/blob/2cd2569c72b8920048e35c31c9be30a6170e1410/src/backend/storage/page/bufpage.c#L194

func CalculateFileOffset 

func CalculateFileOffset(pageID PageID) int64

CalculateFileOffset calculates the page's offset within the file the page size is fixed (8KB) so that it is easy to calculate the offset

func CalculateFreeSpace 

func CalculateFreeSpace(page PagePtr) int

CalculateFreeSpace calculates free space within the page see: https://github.com/postgres/postgres/blob/2cd2569c72b8920048e35c31c9be30a6170e1410/src/backend/storage/page/bufpage.c#L907

func ClearAllVisible 

func ClearAllVisible(p PagePtr)

ClearAllVisible clears allVisible bit

func CompactPage 

func CompactPage(page PagePtr) error

CompactPage compacts the tuples within page. this does not compact slot.

After vacuum removes dead tuples and sets the slot flag unused, then the page can be compacted. VACUUM command does not compact slot so unused slot is unused even after VACUUM command is executed. VACUUM FULL command compacts even slot so unused slot is compacted. ex: - slot index 0, 1, 2 is used and slot 1 points to dead tuple - when VACUUM FULL command is executed, the data within slot index 2 is moved to slot index 1 - when VACUUM command is executed, the data within slot index 2 is still there slot index is called ctid in postgres, and you can confirm it like the query below - SELECT s.ctid, s.* from sample s; - VACUUM;

TODO: the logic in ppdb is not optimized, so fix this later ex: should consider whether the slots are sorted or not, and moves only tuples necessary for re-location the case slots are not sorted can happen after the page is compacted and freed slot is used when insert new tuple see https://github.com/postgres/postgres/blob/2cd2569c72b8920048e35c31c9be30a6170e1410/src/backend/storage/page/bufpage.c#L474 see https://github.com/postgres/postgres/blob/2cd2569c72b8920048e35c31c9be30a6170e1410/src/backend/storage/page/bufpage.c#L682-L699

func GetFlags 

func GetFlags(p PagePtr) uint16

GetFlags returns flags

func GetLSN 

func GetLSN(p PagePtr) common.WALRecordPtr

GetLSN returns lsn

func GetLowerOffset 

func GetLowerOffset(p PagePtr) offset

GetLowerOffset returns lower offset

func GetSpecialSpaceOffset 

func GetSpecialSpaceOffset(p PagePtr) offset

GetSpecialSpaceOffset returns special space offset

func GetUpperOffset 

func GetUpperOffset(p PagePtr) offset

GetUpperOffset returns upper offset

func InitializePage 

func InitializePage(p PagePtr, specialSpaceSize uint16)

InitializePage initializes page when extending new page, the page is 0-filled, so should be initialized with this function see https://github.com/postgres/postgres/blob/2cd2569c72b8920048e35c31c9be30a6170e1410/src/backend/storage/page/bufpage.c#L35-L42

func IsAllVisible 

func IsAllVisible(p PagePtr) bool

IsAllVisible is whether the flags allVisible is set

func IsDead 

func IsDead(s SlotPtr) bool

IsDead checks whether the page slot is dead

func IsInitialized 

func IsInitialized(p PagePtr) bool

IsInitialized checks whether the page has been already initialized when the upperOffset is 0, then the page isn't initialized see https://github.com/postgres/postgres/blob/bfcf1b34805f70df48eedeec237230d0cc1154a6/src/include/storage/bufpage.h#L231

func IsNormal 

func IsNormal(s SlotPtr) bool

IsNormal checks whether the page slot is normal

func IsRedirected 

func IsRedirected(s SlotPtr) bool

IsRedirected checks whether the page slot is redirected

func IsUnused 

func IsUnused(s SlotPtr) bool

IsUnused checks whether the page slot is used

func SetAllVisible 

func SetAllVisible(p PagePtr)

SetAllVisible sets allVisible bit

func SetDead 

func SetDead(s SlotPtr)

SetDead sets flag to dead

func SetFlags 

func SetFlags(p PagePtr, flags uint16)

SetFlags sets flags

func SetLSN 

func SetLSN(p PagePtr, lsn common.WALRecordPtr)

SetLSN sets lsn

func SetLowerOffset 

func SetLowerOffset(p PagePtr, o offset)

SetLowerOffset sets lower offset

func SetNormal 

func SetNormal(s SlotPtr)

SetNormal sets flag to normal this is expected to be used mainly when unused slot is re-used

func SetRedirected 

func SetRedirected(s SlotPtr)

SetRedirected sets flag to redirected

func SetSpecialSpaceOffset 

func SetSpecialSpaceOffset(p PagePtr, o offset)

SetSpecialSpaceOffset sets special space offset

func SetUnused 

func SetUnused(s SlotPtr)

SetUnused sets flag to unused this is expected to be used mainly when vacuum frees up tuple

func SetUpperOffset 

func SetUpperOffset(p PagePtr, o offset)

SetUpperOffset sets upper offset

Types

type ItemPtr 

type ItemPtr []byte

ItemPtr points to item within page item length is variable

func GetItem 

func GetItem(page PagePtr, idx SlotIndex) (ItemPtr, error)

GetItem returns the item pointed by the slot

type PageID 

type PageID uint32

PageID is the unique identifier given to each page, which is called blockNumber in postgres see https://github.com/postgres/postgres/blob/d63d957e330c611f7a8c0ed02e4407f40f975026/src/include/storage/block.h#L17-L31 

const (
	// first page id in file
	FirstPageID PageID = 0
	// invalid page id
	InvalidPageID PageID = math.MaxUint32
	// max page id
	MaxPageID PageID = math.MaxUint32 - 1
	// special page id for buffer manager
	NewPageID PageID = InvalidPageID
)

type PagePtr 

type PagePtr *[PageSize]byte

PagePtr is pointer to page ppdb defines page as pointer explicitly because page should not be passed by value in many cases (for concurrent access and space-efficiency) (although, using pointer here may be controversial)

func NewPagePtr 

func NewPagePtr() PagePtr

NewPagePtr returns 0-filled page pointer

func TestingNewRandomPage 

func TestingNewRandomPage() (PagePtr, error)

type Slot 

type Slot uint32

Slot is used for calculation or bit operation of slot basically, SlotPtr type is used instead of Slot

Slot consists of three fields - item offset/uint15. this is the offset of the item which slot points to - flag/uint2. flag indicates whether this slot is normal/unused/HOT redirected/dead - item size/uint15. this is the byte size of the item. this field is necessary because the item's length can be variable see: https://github.com/postgres/postgres/blob/27b77ecf9f4d5be211900eda54d8155ada50d696/src/include/storage/itemid.h#L17-L30

type SlotIndex 

type SlotIndex uint16

SlotIndex is the index of the slot within page this is not byte offset. the first slot's index is 0 and the next one's index is 1.... 

const (
	// first slot index
	FirstSlotIndex SlotIndex = 0
	// max slot index
	MaxSlotIndex SlotIndex = PageSize / slotSize
	// invalid slot index
	// maybe this invalid thing should be expressed with error type
	InvalidSlotIndex SlotIndex = MaxSlotIndex + 1
)

see: https://github.com/postgres/postgres/blob/27b77ecf9f4d5be211900eda54d8155ada50d696/src/include/storage/off.h#L26-L28

func GetNSlotIndex 

func GetNSlotIndex(page PagePtr) SlotIndex

GetNSlotIndex returns the index of biggest page slot index which has been allocated this returns invalid slot index when no slot has been allocated

type SlotPtr 

type SlotPtr *[slotSize]byte

SlotPtr is pointer to slot WITHIN PAGE basically this type is used for slot

func GetSlot 

func GetSlot(page PagePtr, idx SlotIndex) (SlotPtr, error)

GetSlot returns page slot

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.