[GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions

Hi, all

My name is Mengxing Liu. I am interested in the project "Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions”. After discussing with Kevin off-list, I think it's time to post discussion here. I am afraid that there are two things that I need your help. Thank you very much.

>
> > So the task is clear. We can use a tree-like or hash-like data
> > structure to speed up this function.
>
> Right -- especially with a large number of connections holding a
> large number of conflicts. In one paper with high concurrency, they
> found over 50% of the CPU time for PostgreSQL was going to these
> functions (including functions called by them). This seems to me to
> be due to the O(N^2) (or possibly worse) performance from the number
> of connections.

Anyone knows the title of this paper? I want to reproduce its workloads.

>
> Remember, I think most of the work here is going to be in
> benchmarking. We not only need to show improvements in simple test
> cases using readily available tools like pgbench, but think about
> what types of cases might be worst for the approach taken and show
> that it still does well -- or at least not horribly. It can be OK
> to have some slight regression in an unusual case if the common
> cases improve a lot, but any large regression needs to be addressed
> before the patch can be accepted. There are some community members
> who are truly diabolical in their ability to devise "worst case"
> tests, and we don't want to be blind-sided by a bad result from one
> of them late in the process.
>

Are there any documents or links introducing how to test and benchmark PostgreSQL? I may need some time to learn about it.

Thanks.

--
Mengxing Liu