by

[SPO600] Project. Stage 1.

What needs to be done:

Choosing the project to work on for SPO600 was, I believe, the hardest part of that project. We had to find some piece of code, in one of the many programs, which could be improved in one of many ways. This improvement had to be noteable enough to make a difference, and we had to see it and know that we could make that difference BEFORE we actually coded it. And the community had to agree that it is that noteable, that we did a good job optimising and that we didn’t screw up something else while fixing that piece of code. So as you can see, this first (!) part of the project was pretty much the hardest 15% I had in my entire Seneca education. Heck, make it hardest 50%!

How I decided to approach:

Remembering that the ultimate goal of the project is to have a working code implemented, I decided that the best way to start is to find a very responsive community. Why? Because it will provide me with help while picking a worthy project, information on how to start, help on whatever details I need to know and fast (hopefully) implementation. I went though some programs, suggested by our professor, but none of them particularly impressed me in terms of communication, until I reached a nifty database program called “PostgreSQL”.

What I decided to go with:

The reason I decided to go with PostgreSQL is that it has IRC channel, where you can chat with developers online; very nicely customized mailing lists, so you can always stay on top of the problem advancement; a list of NEEDED optimizations, bug fixes and feature additions. I went through the list, found myself few possibilities that belong to the optimization category. I subscribed to the corresponding mail lists and contacted the community about the bugs. Then I downloaded and installed the source code.

How the community works:

In order to submit the patch, one needs to create a proposal to the community with the description of what is going to be fixed. The guidelines for how to write a proposal can be found here: http://www.perlfoundation.org/how_to_write_a_proposal. After writing and submitting the proposal, one would start on coding the project. There are the style guidelines to follow: http://www.postgresql.org/docs/devel/static/source-format.html. The guidelines to submitting the finished patch can be found here: https://wiki.postgresql.org/wiki/Submitting_a_Patch. The snapshot of that page:

There’s basically three different workflows a patch can follow after it’s been submitted that lead to it being commited:

Workflow A:

  1. You post patch to pgsql-hackers
  2. A committer picks it up immediately and commits it.

Workflow B:

  1. You post a patch to pgsql-hackers
  2. You add the patch to theopen commitfest queue
  3. A committer picks up the patch from the queue, and commits it

Workflow C:

  1. You post a patch to pgsql-hackers
  2. Bruce adds the patch to a list of unapplied patches
  3. At the beginning of the next commit fest, Alvaro (with the help from others, I hope) goes through the list, and adds the patch to theopen commitfest queue
  4. Acommitter picks up the patch from the queue, and commits it

At any of these stages, your patch might instead be rejected for technical, style, or other reasons. These rejections will normally come with feedback on whether an improved version of that patch would be more acceptable. In those cases, you should consider updating your patch based on that feedback and re-submit.

What I have decided to do, and what I am writing the proposal for:

The bug reports I was looking at are:

http://www.postgresql.org/message-id/25822.1199850664@sss.pgh.pa.us

http://www.postgresql.org/message-id/3CDAD71E9D70417290FCF66F0178D1E1@amd64

http://www.postgresql.org/message-id/1160579260.8082.121.camel@archimedes

http://www.postgresql.org/message-id/52F373CC.4050800@vmware.com

AND, this entire section:

        Miscellaneous Performance

Use mmap() rather than shared memory for shared buffers?

This would remove the requirement for SYSV SHM but would introduce portability issues. Anonymous mmap (or mmap to /dev/zero) is required to prevent I/O overhead. We could also consider mmap() for writing WAL.

Rather than consider mmap()-ing in 8k pages, consider mmap()’ing entire files into a backend?

Doing I/O to large tables would consume a lot of address space or require frequent mapping/unmapping. Extending the file also causes mapping problems that might require mapping only individual pages, leading to thousands of mappings. Another problem is that there is no way to _prevent_ I/O to disk from the dirty shared buffers so changes could hit disk before WAL is written.

Consider ways of storing rows more compactly on disk:

  • Reduce the row header size?
  • Consider reducing on-disk varlena length from four bytes to two because a heap row cannot be more than 64k in length

Consider transaction start/end performance improvements

Allow configuration of backend priorities via the operating system

Though backend priorities make priority inversion during lock waits possible, research shows that this is not a huge problem.

Consider increasing the minimum allowed number of shared buffers

Consider if CommandCounterIncrement() can avoid its AcceptInvalidationMessages() call

Consider Cartesian joins when both relations are needed to form an indexscan qualification for a third relation

Consider not storing a NULL bitmap on disk if all the NULLs are trailing

Sort large UPDATE/DELETEs so it is done in heap order

Consider decreasing the I/O caused by updating tuple hint bits

Avoid the requirement of freezing pages that are infrequently modified

If all rows on a page are visible, it is possible to set a bit in the visibility map (once the visibility map is 100% reliable) and not need to freeze the page, avoiding a page rewrite

Avoid reading in b-tree pages when replaying vacuum records in hot standby mode

Restructure truncation logic to be more resistant to failure

This also involves not writing dirty buffers for a truncated or dropped relation

Consider adding logic to increase large tables by more than 8k

This would reduce file system fragmentation

NOW. What should I go about? So far I got “on word” approval by one of the community members on IRC on http://www.postgresql.org/message-id/25822.1199850664@sss.pgh.pa.us (reason I liked it at first: memory leak, optimisation, build options, it’s all there). At the same time, after some additional research, my heart settled on “Represent ItemPointers as uint64’s, to speed up comparisons. inCompareItemPointers is inlined into only a few instructions, but it’s still more expensive than a single-instruction 64-bit comparison. ginCompareItemPointers is called very heavily in a GIN scan, so even a small improvement there would make for a noticeable speedup. It might be an improvement in code clarity, too.”

Currently I am in the process of creating two proposals, and let the community decide which one I have to go with. The whole idea behind SPO600 project is to do something useful for a community by creating a patch for a program. Well, I will let the community decide what they want more! I will post the winning proposal and the response to it as soon as I get one.

What needs to be done:

Choosing the project to work on for SPO600 was, I believe, the hardest part of that project. We had to find some piece of code, in one of the many programs, which could be improved in one of many ways. This improvement had to be noteable enough to make a difference, and we had to see it and know that we could make that difference BEFORE we actually coded it. And the community had to agree that it is that noteable, that we did a good job optimising and that we didn’t screw up something else while fixing that piece of code. So as you can see, this first (!) part of the project was pretty much the hardest 15% I had in my entire Seneca education. Heck, make it hardest 50%!

How I decided to approach:

Remembering that the ultimate goal of the project is to have a working code implemented, I decided that the best way to start is to find a very responsive community. Why? Because it will provide me with help while picking a worthy project, information on how to start, help on whatever details I need to know and fast (hopefully) implementation. I went though some programs, suggested by our professor, but none of them particularly impressed me in terms of communication, until I reached a nifty database program called “PostgreSQL”.

What I decided to go with:

The reason I decided to go with PostgreSQL is that it has IRC channel, where you can chat with developers online; very nicely customized mailing lists, so you can always stay on top of the problem advancement; a list of NEEDED optimizations, bug fixes and feature additions. I went through the list, found myself few possibilities that belong to the optimization category. I subscribed to the corresponding mail lists and contacted the community about the bugs. Then I downloaded and installed the source code.

How the community works:

In order to submit the patch, one needs to create a proposal to the community with the description of what is going to be fixed. The guidelines for how to write a proposal can be found here: http://www.perlfoundation.org/how_to_write_a_proposal. After writing and submitting the proposal, one would start on coding the project. There are the style guidelines to follow: http://www.postgresql.org/docs/devel/static/source-format.html. The guidelines to submitting the finished patch can be found here: https://wiki.postgresql.org/wiki/Submitting_a_Patch. The snapshot of that page:

There’s basically three different workflows a patch can follow after it’s been submitted that lead to it being commited:

Workflow A:

  1. You post patch to pgsql-hackers
  2. A committer picks it up immediately and commits it.

Workflow B:

  1. You post a patch to pgsql-hackers
  2. You add the patch to theopen commitfest queue
  3. A committer picks up the patch from the queue, and commits it

Workflow C:

  1. You post a patch to pgsql-hackers
  2. Bruce adds the patch to a list of unapplied patches
  3. At the beginning of the next commit fest, Alvaro (with the help from others, I hope) goes through the list, and adds the patch to theopen commitfest queue
  4. Acommitter picks up the patch from the queue, and commits it

At any of these stages, your patch might instead be rejected for technical, style, or other reasons. These rejections will normally come with feedback on whether an improved version of that patch would be more acceptable. In those cases, you should consider updating your patch based on that feedback and re-submit.

What I have decided to do, and what I am writing the proposal for:

The bug reports I was looking at are:

http://www.postgresql.org/message-id/25822.1199850664@sss.pgh.pa.us

http://www.postgresql.org/message-id/3CDAD71E9D70417290FCF66F0178D1E1@amd64

http://www.postgresql.org/message-id/1160579260.8082.121.camel@archimedes

http://www.postgresql.org/message-id/52F373CC.4050800@vmware.com

AND, this entire section:

        Miscellaneous Performance

Use mmap() rather than shared memory for shared buffers?

This would remove the requirement for SYSV SHM but would introduce portability issues. Anonymous mmap (or mmap to /dev/zero) is required to prevent I/O overhead. We could also consider mmap() for writing WAL.

Rather than consider mmap()-ing in 8k pages, consider mmap()’ing entire files into a backend?

Doing I/O to large tables would consume a lot of address space or require frequent mapping/unmapping. Extending the file also causes mapping problems that might require mapping only individual pages, leading to thousands of mappings. Another problem is that there is no way to _prevent_ I/O to disk from the dirty shared buffers so changes could hit disk before WAL is written.

Consider ways of storing rows more compactly on disk:

  • Reduce the row header size?
  • Consider reducing on-disk varlena length from four bytes to two because a heap row cannot be more than 64k in length

Consider transaction start/end performance improvements

Allow configuration of backend priorities via the operating system

Though backend priorities make priority inversion during lock waits possible, research shows that this is not a huge problem.

Consider increasing the minimum allowed number of shared buffers

Consider if CommandCounterIncrement() can avoid its AcceptInvalidationMessages() call

Consider Cartesian joins when both relations are needed to form an indexscan qualification for a third relation

Consider not storing a NULL bitmap on disk if all the NULLs are trailing

Sort large UPDATE/DELETEs so it is done in heap order

Consider decreasing the I/O caused by updating tuple hint bits

Avoid the requirement of freezing pages that are infrequently modified

If all rows on a page are visible, it is possible to set a bit in the visibility map (once the visibility map is 100% reliable) and not need to freeze the page, avoiding a page rewrite

Avoid reading in b-tree pages when replaying vacuum records in hot standby mode

Restructure truncation logic to be more resistant to failure

This also involves not writing dirty buffers for a truncated or dropped relation

Consider adding logic to increase large tables by more than 8k

This would reduce file system fragmentation

“What bug to take care of” Decision:

NOW. What should I go about? So far I got “on word” approval by one of the community members on IRC on http://www.postgresql.org/message-id/25822.1199850664@sss.pgh.pa.us (reason I liked it at first: memory leak, optimisation, build options, it’s all there). At the same time, after some additional research, my heart settled on “Represent ItemPointers as uint64’s, to speed up comparisons. inCompareItemPointers is inlined into only a few instructions, but it’s still more expensive than a single-instruction 64-bit comparison. ginCompareItemPointers is called very heavily in a GIN scan, so even a small improvement there would make for a noticeable speedup. It might be an improvement in code clarity, too.”

Currently I am in the process of creating two proposals, and let the community decide which one I have to go with. The whole idea behind SPO600 project is to do something useful for a community by creating a patch for a program. Well, I will let the community decide what they want more! I will post the winning proposal and the response to it as soon as I get one.

One thought on “[SPO600] Project. Stage 1.”

  1. [SPO600] – Step 1 – Revised | Welcome to the Cave says:
    March 15, 2015 at 3:25 pm

    […] you might remember, in my previous blog post about step 1 of the SPO600 project I decided to take on couple of bug reports for PostgreSQL […]

    Reply

Leave a comment