Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1b01fp-0004vK-0L for pgsql-hackers@arkaria.postgresql.org; Tue, 10 May 2016 07:01:41 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.84_2) (envelope-from ) id 1b01fn-0008Cl-Pa for pgsql-hackers@arkaria.postgresql.org; Tue, 10 May 2016 07:01:39 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1b01eQ-0006gP-O9 for pgsql-hackers@postgresql.org; Tue, 10 May 2016 07:00:15 +0000 Received: from newmail.postgrespro.ru ([93.174.131.138] helo=mail.postgrespro.ru) by makus.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1b01eM-0001Xh-83 for pgsql-hackers@postgresql.org; Tue, 10 May 2016 07:00:13 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id 7D03321C83AC; Tue, 10 May 2016 10:00:07 +0300 (MSK) Received: from mail.postgrespro.ru ([127.0.0.1]) by localhost (mail.postgrespro.ru [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Tn5QypKxuC3F; Tue, 10 May 2016 10:00:05 +0300 (MSK) Received: from [192.168.43.95] (unknown [213.87.130.37]) by mail.postgrespro.ru (Postfix) with ESMTPSA id CA7DC21C81E6; Tue, 10 May 2016 10:00:04 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1462863605; bh=HOrR2CUbW/60kr4XhC5e8Ecjgs2wWyo2FiREQ1HonIU=; h=Subject:From:In-Reply-To:Date:Cc:References:To; b=XFKnMBRhDSAfYBRbRicAspLzWcpjVFmSjeiHv40/IIZ16gkFT1KXPsxe9Dwn5TOx2 g/ES5aYpwfOGrwD9RVEqfovIL4ptpnNyOhALIvuRns4WadlVADRrczv9DefSMNa1nX RrqvVnmoOCMY/UyCdA44l3BHccLJ+G33+JNB4ONA= Subject: Re: asynchronous and vectorized execution Mime-Version: 1.0 (Apple Message framework v1081) Content-Type: multipart/alternative; boundary=Apple-Mail-24--774900604 From: konstantin knizhnik In-Reply-To: Date: Tue, 10 May 2016 10:00:03 +0300 Cc: "pgsql-hackers@postgresql.org" Message-Id: <49D1AF71-15BD-42C2-88FD-5E894EE4C5B8@postgrespro.ru> References: To: Robert Haas X-Mailer: Apple Mail (2.1081) X-Pg-Spam-Score: -4.1 (----) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org --Apple-Mail-24--774900604 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Hi, > 1. asynchronous execution, It seems to me that asynchronous execution can be considered as = alternative to multithreading model (in case of PostgreSQL the roles of = threads are played by workers). Async. operations are used to have smaller overhead but have scalability = problems (because in most implementation of cooperative multitasking = there is just one processing thread and so it can not consume more than = one core). So I wonder whether asynchronous execution is trying to achieve that = same goal as parallel query execution but using slightly different = mechanism. You wrote:=20 > in the meantime, any worker that arrives at that scan node has no = choice but to block. What's wrong with it that worker is blocked? You can just have more = workers (more than CPU cores) to let other of them continue to do useful = work. But I agree that=20 > Whether or not this will be efficient is a research question > 2. vectorized execution Vector IO is very important for columnar store. In IMCS extension = (in-memory columnar store) using vector operations allows to increase = speed 10-100 times depending on size of data set and query. Obviously = the best results are for grand aggregates. But there are some researches, for example: http://www.vldb.org/pvldb/vol4/p539-neumann.pdf showing that the same or even better effect can be achieved by = generation native code for query execution plan (which is not so = difficult now, thanks to LLVM). It eliminates interpretation overhead and increase cache locality. I get similar results with my own experiments of accelerating SparkSQL. = Instead of native code generation I used conversion of query plans to C = code and experiment with different data representation. "Horisontal = model" with loading columns on demands shows better performance than = columnar store. As far as I know native code generator is currently developed for = PostgreSQL by ISP RAN=20 Sorry, slides in Russian: = https://pgconf.ru/media/2016/02/19/6%20=D0=9C=D0=B5=D0=BB=D1=8C=D0=BD=D0=B8= =D0=BA%20=D0=94=D0=BC=D0=B8=D1=82=D1=80=D0=B8=D0=B9%20=D0=9C=D0=B8=D1=85=D0= =B0=D0=B9=D0=BB=D0=BE=D0=B2=D0=B8=D1=87,%2005-02-2016.pdf At this moment (February) them have implemented translation of only few = PostgreSQL operators used by ExecQuals and do not support aggregates. Them get about 2 times increase of speed at synthetic queries and 25% = increase at TPC-H Q1 (for Q1 most critical is generation of native code = for aggregates, because ExecQual itself takes only 6% of time for this = query). Actually these 25% for Q1 were achieved not by using dynamic code = generation, but switching from PULL to PUSH model in executor. It seems to be yet another interesting PostgreSQL executor = transformation. As far as I know, them are going to publish result of their work to open = source... On May 9, 2016, at 8:33 PM, Robert Haas wrote: > Hi, >=20 > I realize that we haven't gotten 9.6beta1 out the door yet, but I > think we can't really wait much longer to start having at least some > discussion of 9.7 topics, so I'm going to go ahead and put this one > out there. I believe there are other people thinking about these > topics as well, including Andres Freund, Kyotaro Horiguchi, and > probably some folks at 2ndQuadrant (but I don't know exactly who). To > make a long story short, I think there are several different areas > where we should consider major upgrades to our executor. It's too > slow and it doesn't do everything we want it to do. The main things > on my mind are: >=20 > 1. asynchronous execution, by which I mean the ability of a node to > somehow say that it will generate a tuple eventually, but is not yet > ready, so that the executor can go run some other part of the plan > tree while it waits. This case most obviously arises for foreign > tables, where it makes little sense to block on I/O if some other part > of the query tree could benefit from the CPU; consider SELECT * FROM > lt WHERE qual UNION SELECT * FROM ft WHERE qual. It is also a problem > for parallel query: in a parallel sequential scan, the next worker can > begin reading the next block even if the current block hasn't yet been > received from the OS. Whether or not this will be efficient is a > research question, but it can be done. However, imagine a parallel > scan of a btree index: we don't know what page to scan next until we > read the previous page and examine the next-pointer. In the meantime, > any worker that arrives at that scan node has no choice but to block. > It would be better if the scan node could instead say "hey, thanks for > coming but I'm really not ready to be on-CPU just at the moment" and > potentially allow the worker to go work in some other part of the > query tree. For that worker to actually find useful work to do > elsewhere, we'll probably need it to be the case either that the table > is partitioned or the original query will need to involve UNION ALL, > but those are not silly cases to worry about, particularly if we get > native partitioning in 9.7. >=20 > 2. vectorized execution, by which I mean the ability of a node to > return tuples in batches rather than one by one. Andres has opined > more than once that repeated trips through ExecProcNode defeat the > ability of the CPU to do branch prediction correctly, slowing the > whole system down, and that they also result in poor CPU cache > behavior, since we jump all over the place executing a little bit of > code from each node before moving onto the next rather than running > one bit of code first, and then another later. I think that's > probably right. For example, consider a 5-table join where all of > the joins are implemented as hash tables. If this query plan is going > to be run to completion, it would make much more sense to fetch, say, > 100 tuples from the driving scan and then probe for all of those in > the first hash table, and then probe for all of those in the second > hash table, and so on. What we do instead is fetch one tuple and > probe for it in all 5 hash tables, and then repeat. If one of those > hash tables would fit in the CPU cache but all five together will not, > that seems likely to be a lot worse. But even just ignoring the CPU > cache aspect of it for a minute, suppose you want to write a loop to > perform a hash join. The inner loop fetches the next tuple from the > probe table and does a hash lookup. Right now, fetching the next > tuple from the probe table means calling a function which in turn > calls another function which probably calls another function which > probably calls another function and now about 4 layers down we > actually get the next tuple. If the scan returned a batch of tuples > to the hash join, fetching the next tuple from the batch would > probably be 0 or 1 function calls rather than ... more. Admittedly, > you've got to consider the cost of marshaling the batches but I'm > optimistic that there are cycles to be squeezed out here. We might > also want to consider storing batches of tuples in a column-optimized > rather than row-optimized format so that iterating through one or two > attributes across every tuple in the batch touches the minimal number > of cache lines. >=20 > Obviously, both of these are big projects that could touch a large > amount of executor code, and there may be other ideas, in addition to > these, which some of you may be thinking about that could also touch a > large amount of executor code. It would be nice to agree on a way > forward that minimizes code churn and maximizes everyone's attempt to > contribute without conflicting with each other. Also, it seems > desirable to enable, as far as possible, incremental development - in > particular, it seems to me that it would be good to pick a design that > doesn't require massive changes to every node all at once. A single > patch that adds some capability to every node in the executor in one > fell swoop is going to be too large to review effectively. >=20 > My proposal for how to do this is to make ExecProcNode function as a > backward-compatibility wrapper. For asynchronous execution, a node > might return a not-ready-yet indication, but if that node is called > via ExecProcNode, it means the caller isn't prepared to receive such > an indication, so ExecProcNode will just wait for the node to become > ready and then return the tuple. Similarly, for vectorized execution, > a node might return a bunch of tuples all at once. ExecProcNode will > extract the first one and return it to the caller, and subsequent > calls to ExecProcNode will iterate through the rest of the batch, only > calling the underlying node-specific function when the batch is > exhausted. In this way, code that doesn't know about the new stuff > can continue to work pretty much as it does today. Also, and I think > this is important, nodes don't need the permission of their parent > node to use these new capabilities. They can use them whenever they > wish, without worrying about whether the upper node is prepared to > deal with it. If not, ExecProcNode will paper over the problem. This > seems to me to be a good way to keep the code simple. >=20 > For asynchronous execution, I have gone so far as to mock up a bit of > what this might look like. This shouldn't be taken very seriously at > this point, but I'm attaching a few very-much-WIP patches to show the > direction of my line of thinking. Basically, I propose to have > ExecBlah (that is, ExecBitmapHeapScan, ExecAppend, etc.) return tuples > by putting them into a new PlanState member called "result", which is > just a Node * so that we can support multiple types of results, > instead of returning them. There is also a result_ready boolean, so > that a node can return without setting this Boolean to engage > asynchronous behavior. This triggers an "event loop", which > repeatedly waits for FDs chosen by waiting nodes to become readable > and/or writeable and then gives the node a chance to react. > Eventually, the waiting node will stop waiting and have a result > ready, at which point the event loop will give the parent of that node > a chance to run. If that node consequently becomes ready, then its > parent gets a chance to run. Eventually (we hope), the node for which > we're waiting becomes ready, and we can then read a result tuple. > With some more work, this seems like it can handle the FDW case, but I > haven't worked out how to make it handle the related parallel query > case. What we want there is to wait not for the readiness of an FD > but rather for some other process involved in the parallel query to > reach a point where it can welcome assistance executing that node. I > don't know exactly what the signaling for that should look like yet - > maybe setting the process latch or something. >=20 > By the way, one smaller executor project that I think we should also > look at has to do with this comment in nodeSeqScan.c: >=20 > static bool > SeqRecheck(SeqScanState *node, TupleTableSlot *slot) > { > /* > * Note that unlike IndexScan, SeqScan never use keys in = heap_beginscan > * (and this is very bad) - so, here we do not check are keys = ok or not. > */ > return true; > } >=20 > Some quick prototyping by my colleague Dilip Kumar suggests that, in > fact, there are cases where pushing down keys into heap_beginscan() > could be significantly faster. Some care is required here because any > functions we execute as scan keys are run with the buffer locked, so > we had better not run anything very complicated. But doing this for > simple things like integer equality operators seems like it could save > quite a few buffer lock/unlock cycles and some other executor overhead > as well. >=20 > Thoughts, ideas, suggestions, etc. very welcome. >=20 > --=20 > Robert Haas > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company > = <0001-Modify-PlanState-to-include-a-pointer-to-the-parent-.patch><0002-Mod= ify-PlanState-to-have-result-result_ready-fields.patch><0003-Lightweight-f= ramework-for-waiting-for-events.patch> > --=20 > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers --Apple-Mail-24--774900604 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 1. asynchronous = execution,

It seems to me that = asynchronous execution can be considered as alternative to = multithreading model (in case of PostgreSQL the roles of threads are = played by workers).
Async. operations are used to have smaller = overhead but have scalability problems (because in most implementation = of cooperative multitasking there is just one processing thread and so = it can not consume more than one core).

So I = wonder whether asynchronous execution is trying to achieve that = same goal as parallel query execution but using slightly different = mechanism.
You wrote: 
in the meantime, any worker that arrives at that = scan node has no choice but to = block.

What's wrong with it that worker = is blocked? You can just have more workers (more than CPU cores) to let = other of them continue to do useful work.
But I agree = that 
Whether or not this = will be efficient is a research = question



2. vectorized = execution

Vector IO is very important = for columnar store. In IMCS extension (in-memory columnar store) using = vector operations allows to increase speed 10-100 times depending on = size of data set and query. Obviously the best results are for grand = aggregates.

But there are some researches, for = example:

http://www.vldb.o= rg/pvldb/vol4/p539-neumann.pdf

showing that the = same or even better effect can be achieved by generation native code for = query execution plan (which is not so difficult now, thanks to = LLVM).
It eliminates interpretation overhead and increase = cache locality.
I get similar results with my own experiments = of accelerating SparkSQL. Instead of native code generation I used = conversion of query plans to C code and experiment with different data = representation. "Horisontal model" with loading columns on demands shows = better performance than columnar store.

As far = as I know native code generator is currently developed for PostgreSQL by = ISP RAN 
Sorry, slides in = Russian:
https://pgconf.ru/media/2016/02/19/6%20=D0=9C=D0=B5=D0=BB= =D1=8C=D0=BD=D0=B8=D0=BA%20=D0=94=D0=BC=D0=B8=D1=82=D1=80=D0=B8=D0=B9%20=D0= =9C=D0=B8=D1=85=D0=B0=D0=B9=D0=BB=D0=BE=D0=B2=D0=B8=D1=87,%2005-02-2016.pd= f

At this moment (February) them have = implemented translation of only few PostgreSQL operators used = by ExecQual itself takes only 6% of = time for this query).
Actually these 25% for Q1 were achieved = not by using dynamic code generation, but switching from PULL to PUSH = model in executor.
It seems to be yet another interesting = PostgreSQL executor transformation.
As far as I know, them are = going to publish result of their work to open = source...



On May = 9, 2016, at 8:33 PM, Robert Haas wrote:

Hi,

I realize that we haven't gotten 9.6beta1 = out the door yet, but I
think we can't really wait much longer to = start having at least some
discussion of 9.7 topics, so I'm going to = go ahead and put this one
out there.  I believe there are other = people thinking about these
topics as well, including Andres Freund, = Kyotaro Horiguchi, and
probably some folks at 2ndQuadrant (but I = don't know exactly who).  To
make a long story short, I think = there are several different areas
where we should consider major = upgrades to our executor.  It's too
slow and it doesn't do = everything we want it to do.  The main things
on my mind = are:

1. asynchronous execution, by which I mean the ability of a = node to
somehow say that it will generate a tuple eventually, but is = not yet
ready, so that the executor can go run some other part of the = plan
tree while it waits.  This case most obviously arises for = foreign
tables, where it makes little sense to block on I/O if some = other part
of the query tree could benefit from the CPU; consider = SELECT * FROM
lt WHERE qual UNION SELECT * FROM ft WHERE qual. =  It is also a problem
for parallel query: in a parallel = sequential scan, the next worker can
begin reading the next block = even if the current block hasn't yet been
received from the OS. =  Whether or not this will be efficient is a
research question, = but it can be done.  However, imagine a parallel
scan of a btree = index: we don't know what page to scan next until we
read the = previous page and examine the next-pointer.  In the = meantime,
any worker that arrives at that scan node has no choice but = to block.
It would be better if the scan node could instead say "hey, = thanks for
coming but I'm really not ready to be on-CPU just at the = moment" and
potentially allow the worker to go work in some other = part of the
query tree.  For that worker to actually find useful = work to do
elsewhere, we'll probably need it to be the case either = that the table
is partitioned or the original query will need to = involve UNION ALL,
but those are not silly cases to worry about, = particularly if we get
native partitioning in 9.7.

2. = vectorized execution, by which I mean the ability of a node to
return = tuples in batches rather than one by one.  Andres has = opined
more than once that repeated trips through ExecProcNode defeat = the
ability of the CPU to do branch prediction correctly, slowing = the
whole system down, and that they also result in poor CPU = cache
behavior, since we jump all over the place executing a little = bit of
code from each node before moving onto the next rather than = running
one bit of code first, and then another later.  I think = that's
probably right.   For example, consider a 5-table = join where all of
the joins are implemented as hash tables.  If = this query plan is going
to be run to completion, it would make much = more sense to fetch, say,
100 tuples from the driving scan and then = probe for all of those in
the first hash table, and then probe for = all of those in the second
hash table, and so on.  What we do = instead is fetch one tuple and
probe for it in all 5 hash tables, and = then repeat.  If one of those
hash tables would fit in the CPU = cache but all five together will not,
that seems likely to be a lot = worse.   But even just ignoring the CPU
cache aspect of it = for a minute, suppose you want to write a loop to
perform a hash = join.  The inner loop fetches the next tuple from the
probe = table and does a hash lookup.  Right now, fetching the = next
tuple from the probe table means calling a function which in = turn
calls another function which probably calls another function = which
probably calls another function and now about 4 layers down = we
actually get the next tuple.  If the scan returned a batch of = tuples
to the hash join, fetching the next tuple from the batch = would
probably be 0 or 1 function calls rather than ... more. =  Admittedly,
you've got to consider the cost of marshaling the = batches but I'm
optimistic that there are cycles to be squeezed out = here.  We might
also want to consider storing batches of tuples = in a column-optimized
rather than row-optimized format so that = iterating through one or two
attributes across every tuple in the = batch touches the minimal number
of cache lines.

Obviously, = both of these are big projects that could touch a large
amount of = executor code, and there may be other ideas, in addition to
these, = which some of you may be thinking about that could also touch a
large = amount of executor code.  It would be nice to agree on a = way
forward that minimizes code churn and maximizes everyone's = attempt to
contribute without conflicting with each other. =  Also, it seems
desirable to enable, as far as possible, = incremental development - in
particular, it seems to me that it would = be good to pick a design that
doesn't require massive changes to = every node all at once.  A single
patch that adds some = capability to every node in the executor in one
fell swoop is going = to be too large to review effectively.

My proposal for how to do = this is to make ExecProcNode function as a
backward-compatibility = wrapper.  For asynchronous execution, a node
might return a = not-ready-yet indication, but if that node is called
via = ExecProcNode, it means the caller isn't prepared to receive such
an = indication, so ExecProcNode will just wait for the node to = become
ready and then return the tuple.  Similarly, for = vectorized execution,
a node might return a bunch of tuples all at = once.  ExecProcNode will
extract the first one and return it to = the caller, and subsequent
calls to ExecProcNode will iterate through = the rest of the batch, only
calling the underlying node-specific = function when the batch is
exhausted.  In this way, code that = doesn't know about the new stuff
can continue to work pretty much as = it does today.  Also, and I think
this is important, nodes don't = need the permission of their parent
node to use these new = capabilities.  They can use them whenever they
wish, without = worrying about whether the upper node is prepared to
deal with it. =  If not, ExecProcNode will paper over the problem. =  This
seems to me to be a good way to keep the code = simple.

For asynchronous execution, I have gone so far as to mock = up a bit of
what this might look like.  This shouldn't be taken = very seriously at
this point, but I'm attaching a few very-much-WIP = patches to show the
direction of my line of thinking. =  Basically, I propose to have
ExecBlah (that is, = ExecBitmapHeapScan, ExecAppend, etc.) return tuples
by putting them = into a new PlanState member called "result", which is
just a Node * = so that we can support multiple types of results,
instead of = returning them.  There is also a result_ready boolean, so
that a = node can return without setting this Boolean to engage
asynchronous = behavior.  This triggers an "event loop", which
repeatedly waits = for FDs chosen by waiting nodes to become readable
and/or writeable = and then gives the node a chance to react.
Eventually, the waiting = node will stop waiting and have a result
ready, at which point the = event loop will give the parent of that node
a chance to run. =  If that node consequently becomes ready, then its
parent gets a = chance to run.  Eventually (we hope), the node for which
we're = waiting becomes ready, and we can then read a result tuple.
With some = more work, this seems like it can handle the FDW case, but I
haven't = worked out how to make it handle the related parallel query
case. =  What we want there is to wait not for the readiness of an = FD
but rather for some other process involved in the parallel query = to
reach a point where it can welcome assistance executing that node. =  I
don't know exactly what the signaling for that should look = like yet -
maybe setting the process latch or something.

By = the way, one smaller executor project that I think we should = also
look at has to do with this comment in = nodeSeqScan.c:

static bool
SeqRecheck(SeqScanState *node, = TupleTableSlot *slot)
{
=        /*
=         * Note that unlike = IndexScan, SeqScan never use keys in heap_beginscan
=         * (and this is very bad) = - so, here we do not check are keys ok or not.
=         */
=        return true;
}

Some = quick prototyping by my colleague Dilip Kumar suggests that, in
fact, = there are cases where pushing down keys into heap_beginscan()
could = be significantly faster.  Some care is required here because = any
functions we execute as scan keys are run with the buffer locked, = so
we had better not run anything very complicated.  But doing = this for
simple things like integer equality operators seems like it = could save
quite a few buffer lock/unlock cycles and some other = executor overhead
as well.

Thoughts, ideas, suggestions, etc. = very welcome.

--
Robert Haas
EnterpriseDB: = http://www.enterprisedb.com
The Enterprise PostgreSQL = Company
<0001-Modify-PlanState-to-include-a-pointer-to-the-par= ent-.patch><0002-Modify-PlanState-to-have-result-result= _ready-fields.patch><0003-Lightweight-framework-for-wai= ting-for-events.patch>
--
Sent via pgsql-hackers = mailing list (pgsql-hackers@postgresql.org)
To make changes to your = subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

= --Apple-Mail-24--774900604--