Issue Details (XML | Word | Printable)

Key: CORE-4556
Type: Improvement Improvement
Status: Closed Closed
Resolution: Fixed
Priority: Major Major
Assignee: Vlad Khorsun
Reporter: Vlad Khorsun
Votes: 1
Watchers: 5
Operations

If you were logged in you would be able to see more operations.
Firebird Core

Allocate data pages in group of sequential ordered pages (extents)

Created: 18/Sep/14 10:30 PM   Updated: 23/Sep/15 12:19 PM
Component/s: Engine
Affects Version/s: None
Fix Version/s: 3.0 Beta 1

QA Status: Cannot be tested


 Description  « Hide
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.

 All   Comments   Change History   Subversion Commits      Sort Order: Ascending order - Click to sort in descending order
Vlad Khorsun made changes - 18/Sep/14 10:30 PM
Field Original Value New Value
Assignee Vlad Khorsun [ hvlad ]
Vlad Khorsun made changes - 18/Sep/14 10:32 PM
Status Open [ 1 ] Open [ 1 ]
Fix Version/s 3.0 Beta 1 [ 10332 ]
Sean Leyne added a comment - 18/Sep/14 10:38 PM
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?

Vlad Khorsun added a comment - 18/Sep/14 10:47 PM
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 ?

Sean Leyne added a comment - 18/Sep/14 11:17 PM
"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?

Sean Leyne added a comment - 18/Sep/14 11:21 PM
Small changes for readability

Sean Leyne made changes - 18/Sep/14 11:21 PM
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.
Vlad Khorsun added a comment - 19/Sep/14 07:11 AM
> 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 ?

Vlad Khorsun made changes - 28/Sep/14 09:49 AM
Status Open [ 1 ] Resolved [ 5 ]
Resolution Fixed [ 1 ]
Pavel Zotov made changes - 02/Jun/15 05:20 AM
Status Resolved [ 5 ] Resolved [ 5 ]
QA Status Cannot be tested
Pavel Cisar made changes - 23/Sep/15 12:19 PM
Status Resolved [ 5 ] Closed [ 6 ]