Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allocate data pages in group of sequential ordered pages (extents) [CORE4556] #4874

Closed
firebird-issue-importer opened this issue Sep 19, 2014 · 11 comments

Comments

@firebird-issue-importer

Submitted by: @hvlad

Votes: 1

DIscussed in fb-devel (see "RFC: Data page allocation algorithm" at 26 Dec 2013)

I offer to allocate data pages not one-by-one (as currently) but in group of sequential ordered pages. Such group of pages is often called "extent".

I offer to change page allocation algorithm for tables as follows:
- if table is empty or small (have no full extent allocated) then data pages is allocated one-by-one (as currently)
- if table already have at least one full extent allocated, next request for new page will allocate the whole extent of pages
- size of extent is 8 pages
- every such extent is aligned at 8-pages boundary

This new algorithm will:
- reduce page-level fragmentation (all pages in extent are adjacent),
- allow OS-level prefetch to work more efficient (it will read not just a bunch of pages of random objects but pages related to the same table), and
- allow in the future to read and write in a large chunks making IO more efficient.

Commits: 8ba9d33 FirebirdSQL/fbt-repository@6e6dbbe

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Modified by: @hvlad

assignee: Vlad Khorsun [ hvlad ]

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Modified by: @hvlad

status: Open [ 1 ] => Open [ 1 ]

Fix Version: 3.0 Beta 1 [ 10332 ]

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Commented by: Sean Leyne (seanleyne)

Vlad,

Isn't it a reality that other engines allocate an "extent" as the minimum table size?

Why would we add extra overhead for checking if a page has already been assigned/used, why not use an 'extent' each time?

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Commented by: @hvlad

Sean,

> Isn't it a reality that other engines allocate an "extent" as the minimum table size?
If we have a lot of small tables we wont waste space allocating whole extent for them.
This is how MSSQL work.

> Why would we add extra overhead for checking if a page has already been assigned/used, why not use an 'extent' each time?
Not sure i understand you correctly. Could you explain ?

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Commented by: Sean Leyne (seanleyne)

"If we have a lot of small tables we wont waste space allocating whole extent for them"
The logic you have outlined means that while we would not allocate 8 pages for pages with only 1 page in use -- which is less space.

But the "minimal space is good' rational overlooks:
1 - cases where only 9 pages are in use, but 16 will be allocated. (This has just as much 'wasted space' as allocating 8 pages for 1 page of real use)
2 - the fragmentation within the first 8 pages of all tables

It would seem to be simpler to have the engine always allocate in "extents" and allow for the size of the extents to be defined as a database parameter [default = 8] to manage the size of an empty database (this would also address size issues for ultra small deployment -- ie. mobile), rather than having to 'count' the number of pages to decide if allocation will be in pages or extents.

Q: What would happen if a data had "master" and "details" tables where the data ratio between the tables was 1 to 4? Based on the description, after sometime had passed, the resulting disk page usage for the tables could be:
Master = Page 1, 6, 11, 20, 29
Details = Page 2, 3, 4, 5, 7, 8, 9, 10, 12-19, 21-28, 30-37

Am I correct? (if so, then to describe the extents as aligned on 8 page boundary is incorrect)

Q: If pages 21-28 were released from the Details table, would those tables be released for use a single pages or only full extents?

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Commented by: Sean Leyne (seanleyne)

Small changes for readability

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Modified by: Sean Leyne (seanleyne)

description: DIscussed in fb-devel (see "RFC: Data page allocation algorithm" at 26 Dec 2013)

I offer to allocate data pages not one\-by\-one \(as currently\) but in group of sequential ordered pages\.

Such group of pages is often called "extent". I offer to change page allocation algorithm for tables as following:
- if table is empty or small (have no full extent allocated) then data pages is allocated one-by-one (as currently)
- if table already have at least one full extent allocated, next request for new page will allocate the whole extent of pages
- size of extent is 8 pages
- every such extent is aligned at 8-pages boundary

Such algoritm will reduce page\-level fragmentation \(all pages in extent are adjacent\), allows

OS-level prefetch to work more efficient (it will read not just a bunch of pages of random objects but
pages related to the same table) and allows us in the future to read and write in a large chunks
making IO more efficient.

=>

DIscussed in fb-devel (see "RFC: Data page allocation algorithm" at 26 Dec 2013)

I offer to allocate data pages not one-by-one (as currently) but in group of sequential ordered pages. Such group of pages is often called "extent".

I offer to change page allocation algorithm for tables as follows:
- if table is empty or small (have no full extent allocated) then data pages is allocated one-by-one (as currently)
- if table already have at least one full extent allocated, next request for new page will allocate the whole extent of pages
- size of extent is 8 pages
- every such extent is aligned at 8-pages boundary

This new algorithm will:
- reduce page-level fragmentation (all pages in extent are adjacent),
- allow OS-level prefetch to work more efficient (it will read not just a bunch of pages of random objects but pages related to the same table), and
- allow in the future to read and write in a large chunks making IO more efficient.

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 19, 2014

Commented by: @hvlad

> But the "minimal space is good' rational overlooks:
> 1 - cases where only 9 pages are in use, but 16 will be allocated. (This has just as much 'wasted space' as allocating 8 pages for 1 page of real use)
> 2 - the fragmentation within the first 8 pages of all tables

1. Consider following:
a) 8 pages allocated and 1 is used - 87.5% of wasted space (for this particular table)
b) 16 pages allocated and 9 is used - 43.75% of wasted space (for this particular table)

2. Yes, there will be fragmentation of first 8 pages. We can live with it.

> It would seem to be simpler to have the engine always allocate in "extents" and allow for the size of the extents to be defined as a database parameter [default = 8] to manage the size of an empty database (this would also address size issues for ultra small deployment -- ie. mobile),

It *would seem to be simpler* only until you start to implement it. Also, we trying to avoid new configuration parameters when not needed.

> rather than having to 'count' the number of pages to decide if allocation will be in pages or extents.
Does you looked at code which 'count the number of pages' ???
Please, look at it (or ask) first, next time you make such (totally wrong) estimates.

> Q: What would happen if a data had "master" and "details" tables where the data ratio between the tables was 1 to 4? Based on the description,
> after sometime had passed, the resulting disk page usage for the tables could be:
> Master = Page 1, 6, 11, 20, 29
> Details = Page 2, 3, 4, 5, 7, 8, 9, 10, 12-19, 21-28, 30-37
>
> Am I correct? (if so, then to describe the extents as aligned on 8 page boundary is incorrect)

You are wrong when calculate extent boundary as 12-19, 21-28 and 30-37 :) It could be 8-15, 16-24, etc.
So, page space allocation in your example could be:
Master = Page 1, 6, 11, 25, 29
Details = Page 2, 3, 4, 5, 7, 8, 9, 10, 16-24, 32-39, 40-47

> Q: If pages 21-28 were released from the Details table, would those tables be released for use a single pages or only full extents?
It will allocate full extents. Only first 8 slots allocated one-by-one, all other slots are filled using 8 pages at one time.

PS why do you prefer to discuss all this stuff here (at tracker) and 10 months after my initial post in fb-devel ?

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 28, 2014

Modified by: @hvlad

status: Open [ 1 ] => Resolved [ 5 ]

resolution: Fixed [ 1 ]

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Jun 2, 2015

Modified by: @pavel-zotov

status: Resolved [ 5 ] => Resolved [ 5 ]

QA Status: Cannot be tested

@firebird-issue-importer
Copy link
Author

firebird-issue-importer commented Sep 23, 2015

Modified by: @pcisar

status: Resolved [ 5 ] => Closed [ 6 ]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants