Use of systable_beginscan_ordered in event trigger patch

On Tuesday, August 28, 2012 06:39:50 PM Tom Lane wrote:

Or maybe we should disable event triggers altogether in standalone mode?
I can think of plenty of ways that a broken event trigger could cause
enough havoc that you'd wish there was a way to suppress it, at least
for long enough to drop it again.

+1

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Aug 28, 2012 at 12:47 PM, Andres Freund <andres@2ndquadrant.com> wrote:

On Tuesday, August 28, 2012 06:39:50 PM Tom Lane wrote:

Or maybe we should disable event triggers altogether in standalone mode?
I can think of plenty of ways that a broken event trigger could cause
enough havoc that you'd wish there was a way to suppress it, at least
for long enough to drop it again.

+1

+1. I initially suggested a PGC_SUSET GUC to disable event triggers,
and I'm still not entirely convinced that we shouldn't have one.
Maybe we could just force it to disabled in standalone mode.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Tom Lane <tgl@sss.pgh.pa.us> writes:

I find $SUBJECT fairly scary, because systable_beginscan_ordered() is
dependent on having a working, non-corrupt index. If you are trying
to run the backend with ignore_system_indexes so that you can rebuild
corrupt indexes, uses of systable_beginscan_ordered() represent places
where you can't turn that off, and are entirely at the mercy of the
indexes being good.

Ooops. Didn't see that, thanks for noticing!

Or maybe we should disable event triggers altogether in standalone mode?

+1

I can think of plenty of ways that a broken event trigger could cause
enough havoc that you'd wish there was a way to suppress it, at least
for long enough to drop it again.

I fail to see how enabling Event Triggers in standalone mode would help
you get out of the situation that lead you there. It's a last resort
facility where you want the bare PostgreSQL behavior, I think. Now that
you mention it.

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

Tom Lane <tgl@sss.pgh.pa.us> writes:

Or maybe we should disable event triggers altogether in standalone mode?

Would something as simple as the attached work for doing that? (passes
make check and I did verify manually that postmaster --single is happy
with it and skipping Event Triggers).

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

Hi,

I don't remember that we fixed that case, I did attach a patch in the
previous email, what do you think?

Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:

Tom Lane <tgl@sss.pgh.pa.us> writes:

Or maybe we should disable event triggers altogether in standalone mode?

Would something as simple as the attached work for doing that? (passes
make check and I did verify manually that postmaster --single is happy
with it and skipping Event Triggers).

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

*** a/src/backend/commands/event_trigger.c
--- b/src/backend/commands/event_trigger.c
***************
*** 567,572 **** EventTriggerDDLCommandStart(Node *parsetree)
--- 567,585 ----
EventTriggerData	trigdata;

/*
+ 	 * Event Triggers are completely disabled in standalone mode so as not to
+ 	 * prevent fixing a problematic situation.
+ 	 *
+ 	 * To enable Event Triggers in standalone mode we would have to stop using
+ 	 * systable_beginscan_ordered so that it's still possible to rebuild
+ 	 * corrupt indexes (thanks to ignore_system_indexes). One way to do that is
+ 	 * implementing a heapscan-and-sort code path to use when
+ 	 * ignore_system_indexes is set.
+ 	 */
+ 	if (!IsUnderPostmaster)
+ 		return;
+ 
+ 	/*
* We want the list of command tags for which this procedure is actually
* invoked to match up exactly with the list that CREATE EVENT TRIGGER
* accepts.  This debugging cross-check will throw an error if this

--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:

I don't remember that we fixed that case, I did attach a patch in the
previous email, what do you think?

Yeah, I had forgotten about that loose end, but we definitely need
something of the sort. Committed with additional documentation.
(I put something in the CREATE EVENT TRIGGER ref page, but do we
need anything about it in chapter 37?)

BTW, is the example in the CREATE EVENT TRIGGER ref page meant as an
IQ test for unwary readers? You do know there are people who will
copy-and-paste just about any example that's put in front of them.
Perhaps we just want to make sure they internalize the advice about how
to get out of a broken-event-trigger situation.

Kidding aside, I think we need either a big WARNING, or a different
example.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Tom Lane <tgl@sss.pgh.pa.us> writes:

Yeah, I had forgotten about that loose end, but we definitely need
something of the sort. Committed with additional documentation.
(I put something in the CREATE EVENT TRIGGER ref page, but do we
need anything about it in chapter 37?)

Thanks!

I guess we could add a note at the end of the "Overview of Event Trigger
Behavior" section. Then maybe we should explain in that section that you
can't set an event trigger to fire on event trigger commands.

BTW, is the example in the CREATE EVENT TRIGGER ref page meant as an
IQ test for unwary readers? You do know there are people who will
copy-and-paste just about any example that's put in front of them.
Perhaps we just want to make sure they internalize the advice about how
to get out of a broken-event-trigger situation.

For those following at home, the example is:

CREATE OR REPLACE FUNCTION abort_any_command()
RETURNS event_trigger
LANGUAGE plpgsql
AS $$
BEGIN
RAISE EXCEPTION 'command % is disabled', tg_tag;
END;
$$;

CREATE EVENT TRIGGER abort_ddl ON ddl_command_start
EXECUTE PROCEDURE abort_any_command();

Maybe we could just append to it how to remove such an event trigger,
which is easy to do because you can't target an event trigger related
command with event triggers, so the following is not disabled:

DROP EVENT TRIGGER abort_ddl;

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:

Tom Lane <tgl@sss.pgh.pa.us> writes:

BTW, is the example in the CREATE EVENT TRIGGER ref page meant as an
IQ test for unwary readers?

Maybe we could just append to it how to remove such an event trigger,
which is easy to do because you can't target an event trigger related
command with event triggers, so the following is not disabled:
DROP EVENT TRIGGER abort_ddl;

Oh really? The explanation of the example certainly doesn't say that.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Tom Lane <tgl@sss.pgh.pa.us> writes:

Maybe we could just append to it how to remove such an event trigger,
which is easy to do because you can't target an event trigger related
command with event triggers, so the following is not disabled:
DROP EVENT TRIGGER abort_ddl;

Oh really? The explanation of the example certainly doesn't say that.

I remember than in my proposals somewhere we had support for a very
limited form of command triggers for any command in the system. Of
course as that included transaction control commands we made that
better. I'm quite tired so maybe my memory is playing tricks to me, but
I kind of remember that we also had quite a discussion about just that
example and its phrasing in the docs and did came out with something
satisfactory.

Robert, does that ring a bell to you? I'm going to crawl the archives
tomorrow if not…

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Dec 12, 2012 at 3:51 PM, Dimitri Fontaine
<dimitri@2ndquadrant.fr> wrote:

Tom Lane <tgl@sss.pgh.pa.us> writes:

Maybe we could just append to it how to remove such an event trigger,
which is easy to do because you can't target an event trigger related
command with event triggers, so the following is not disabled:
DROP EVENT TRIGGER abort_ddl;

Oh really? The explanation of the example certainly doesn't say that.

I remember than in my proposals somewhere we had support for a very
limited form of command triggers for any command in the system. Of
course as that included transaction control commands we made that
better. I'm quite tired so maybe my memory is playing tricks to me, but
I kind of remember that we also had quite a discussion about just that
example and its phrasing in the docs and did came out with something
satisfactory.

Robert, does that ring a bell to you? I'm going to crawl the archives
tomorrow if not…

Yeah, I'm pretty sure you can't set event triggers of any kind on
event triggers. You proposed to allow some stuff that would affect
"every command", but I yelled and screamed about that until we got rid
of it, 'cuz it just seemed way too dangerous.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

On Wed, Dec 12, 2012 at 3:51 PM, Dimitri Fontaine
<dimitri@2ndquadrant.fr> wrote:

Robert, does that ring a bell to you? I'm going to crawl the archives
tomorrow if not�

Yeah, I'm pretty sure you can't set event triggers of any kind on
event triggers. You proposed to allow some stuff that would affect
"every command", but I yelled and screamed about that until we got rid
of it, 'cuz it just seemed way too dangerous.

In that case the docs should probably mention it more prominently;
the example in CREATE EVENT TRIGGER is misleadingly described, for sure.

I suspect there are still ways to shoot yourself in the foot with a
broken event trigger, but it's not quite as trivial as I thought.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Dec 13, 2012 at 6:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Wed, Dec 12, 2012 at 3:51 PM, Dimitri Fontaine
<dimitri@2ndquadrant.fr> wrote:

Robert, does that ring a bell to you? I'm going to crawl the archives
tomorrow if not…

Yeah, I'm pretty sure you can't set event triggers of any kind on
event triggers. You proposed to allow some stuff that would affect
"every command", but I yelled and screamed about that until we got rid
of it, 'cuz it just seemed way too dangerous.

In that case the docs should probably mention it more prominently;
the example in CREATE EVENT TRIGGER is misleadingly described, for sure.

I suspect there are still ways to shoot yourself in the foot with a
broken event trigger, but it's not quite as trivial as I thought.

I'm smart enough not to doubt you, but I'd sure appreciate a hint as
to what you're worried about before we start building more on top of
it. I don't want to sink a lot of work into follow-on commits and
then discover during beta we have to rip it all out or disable it. It
seems to me that if you can always drop an event trigger without
interference from the event trigger system, you should at least be
able to shut it off if you don't like what it's doing. I'm a little
worried that there could be ways to crash the server or corrupt data,
but I don't know what they are. ISTM that, at least for the firing
point we have right now, it's not much different than executing the
event trigger code before you execute the DDL command, and therefore
it should be safe. But I'm very aware that I might be wrong, hence
the extremely conservative first commit.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Dec 13, 2012 at 6:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I suspect there are still ways to shoot yourself in the foot with a
broken event trigger, but it's not quite as trivial as I thought.

I'm smart enough not to doubt you, but I'd sure appreciate a hint as
to what you're worried about before we start building more on top of
it. I don't want to sink a lot of work into follow-on commits and
then discover during beta we have to rip it all out or disable it. It
seems to me that if you can always drop an event trigger without
interference from the event trigger system, you should at least be
able to shut it off if you don't like what it's doing.

I doubt that not firing on DROP EVENT TRIGGER, per se, will be
sufficient to guarantee that you can execute such a drop. Even
if that's true in the current state of the code, we're already
hearing requests for event triggers on lower-level events, eg
http://archives.postgresql.org/pgsql-hackers/2012-12/msg00314.php

Sooner or later there will be one somewhere in the code path involved
in doing a heap_delete on pg_event_trigger, or one of the subsidiary
catalogs such as pg_depend, or maybe one that just manages to fire
someplace during backend startup, or who knows what.

Hence, I want a kill switch for all event triggers that will most
certainly work, and the just-committed patch provides one.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Dec 14, 2012 at 2:00 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Dec 13, 2012 at 6:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I suspect there are still ways to shoot yourself in the foot with a
broken event trigger, but it's not quite as trivial as I thought.

I'm smart enough not to doubt you, but I'd sure appreciate a hint as
to what you're worried about before we start building more on top of
it. I don't want to sink a lot of work into follow-on commits and
then discover during beta we have to rip it all out or disable it. It
seems to me that if you can always drop an event trigger without
interference from the event trigger system, you should at least be
able to shut it off if you don't like what it's doing.

I doubt that not firing on DROP EVENT TRIGGER, per se, will be
sufficient to guarantee that you can execute such a drop. Even
if that's true in the current state of the code, we're already
hearing requests for event triggers on lower-level events, eg
http://archives.postgresql.org/pgsql-hackers/2012-12/msg00314.php

Yep, true.

Sooner or later there will be one somewhere in the code path involved
in doing a heap_delete on pg_event_trigger, or one of the subsidiary
catalogs such as pg_depend, or maybe one that just manages to fire
someplace during backend startup, or who knows what.

Yeah. :-(

Hence, I want a kill switch for all event triggers that will most
certainly work, and the just-committed patch provides one.

I'm definitely not disputing the need for that patch.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

Robert, does that ring a bell to you? I'm going to crawl the archives
tomorrow if not…

Yeah, I'm pretty sure you can't set event triggers of any kind on
event triggers. You proposed to allow some stuff that would affect
"every command", but I yelled and screamed about that until we got rid
of it, 'cuz it just seemed way too dangerous.

I meant about the way the documentation is phrased to introduce the
example, which is somewhat wrong because not all commands are concerned,
quite a bunch of them will not be disabled by such a command trigger.

Tom Lane <tgl@sss.pgh.pa.us> writes:

Sooner or later there will be one somewhere in the code path involved
in doing a heap_delete on pg_event_trigger, or one of the subsidiary
catalogs such as pg_depend, or maybe one that just manages to fire
someplace during backend startup, or who knows what.

You're right that we need to be careful here, in ways that I didn't
foresee. The first thing I can think of is to disable such low level
events on system catalogs, of course.

Hence, I want a kill switch for all event triggers that will most
certainly work, and the just-committed patch provides one.

We absolutely need that, and running Event Triggers in standalone mode
seems counter productive to me anyway. That said maybe we need to be
able to have a per-session "leave me alone" mode of operation. What do
you think of

ALTER EVENT TRIGGER DISABLE ALL; -- just tried, no conflict

I don't think we need the ENABLE ALL variant, and it would not be
symetric anyway as you would want to be able to only enable those event
triggers that were already enabled before, and it seems to me that
"cancelling" a statement is best done with "ROLLBACK;" or "ROLLBACK TO
SAVEPOINT …;".

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Dec 14, 2012 at 3:46 PM, Dimitri Fontaine
<dimitri@2ndquadrant.fr> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

Robert, does that ring a bell to you? I'm going to crawl the archives
tomorrow if not…

Yeah, I'm pretty sure you can't set event triggers of any kind on
event triggers. You proposed to allow some stuff that would affect
"every command", but I yelled and screamed about that until we got rid
of it, 'cuz it just seemed way too dangerous.

I meant about the way the documentation is phrased to introduce the
example, which is somewhat wrong because not all commands are concerned,
quite a bunch of them will not be disabled by such a command trigger.

Tom Lane <tgl@sss.pgh.pa.us> writes:

Sooner or later there will be one somewhere in the code path involved
in doing a heap_delete on pg_event_trigger, or one of the subsidiary
catalogs such as pg_depend, or maybe one that just manages to fire
someplace during backend startup, or who knows what.

You're right that we need to be careful here, in ways that I didn't
foresee. The first thing I can think of is to disable such low level
events on system catalogs, of course.

Hence, I want a kill switch for all event triggers that will most
certainly work, and the just-committed patch provides one.

We absolutely need that, and running Event Triggers in standalone mode
seems counter productive to me anyway. That said maybe we need to be
able to have a per-session "leave me alone" mode of operation. What do
you think of

ALTER EVENT TRIGGER DISABLE ALL; -- just tried, no conflict

I don't think we need the ENABLE ALL variant, and it would not be
symetric anyway as you would want to be able to only enable those event
triggers that were already enabled before, and it seems to me that
"cancelling" a statement is best done with "ROLLBACK;" or "ROLLBACK TO
SAVEPOINT …;".

ISTM that a PGC_SUSER GUC, as I proposed previously, would serve this
need adequately, without the cost of more cruft in gram.y.

Am I wrong?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

ISTM that a PGC_SUSER GUC, as I proposed previously, would serve this
need adequately, without the cost of more cruft in gram.y.

I can't help but think about the experiments you did some time ago about
splitting the grammar into differents sub-grammars (for lack of a better
term). If I remember correctly, your result showed no performance gain
from separating away Queries and DML on the one side from the rest, DDL
and DCL and such like.

IIRC, you didn't have a regression either.

Now, what about splitting those grammars in order to freely add any new
production rules with or without new keywords for administrative
commands, without a blink of though about the main parser grammar.

I guess that the "traffic cop" would need to have a decent fast path to
very quickly get to use the right parser, and I suppose you did already
implement that in your previous experiment.

If that's sensible as a way forward, that can also be the basis for
allowing extensions to implement their own command set too. The trick
would be how to implement extensible grammar routing. That would come
way after we have the initial split, though.

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Dimitri Fontaine <dimitri@2ndQuadrant.fr> writes:

Now, what about splitting those grammars in order to freely add any new
production rules with or without new keywords for administrative
commands, without a blink of though about the main parser grammar.

Let me explain to you why there will never be a situation where we can
consider new keywords to be zero-cost.

$ size src/backend/parser/gram.o
text data bss dec hex filename
952864 104 0 952968 e8a88 src/backend/parser/gram.o
$ size src/backend/postgres
text data bss dec hex filename
6815102 123416 239356 7177874 6d8692 src/backend/postgres

That is, the grammar tables already amount to 14% of the total bulk of
the server executable. (The above numbers exclude debug symbols BTW.)
That bloat is not free; for one thing, it's competing for L1 cache with
all the actual code in the backend. And the main cause of it is that
we have lots-and-lots of keywords, because the parser tables are
basically number-of-tokens wide by number-of-states high. (In HEAD
there are 433 tokens known to the grammar, all but 30 of which are
keywords, and 4367 states.)

Splitting the grammar into multiple grammars is unlikely to do much to
improve this --- in fact, it could easily make matters worse due to
duplication. Rather, we just have to be careful about adding new
keywords. In this connection, I quite like the fact that recent syntax
extensions such as EXPLAIN (...options...) have managed to avoid making
the option names into grammar keywords at all.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Tom Lane <tgl@sss.pgh.pa.us> writes:

Let me explain to you why there will never be a situation where we can
consider new keywords to be zero-cost.

Thanks for taking the time to do this.

Splitting the grammar into multiple grammars is unlikely to do much to
improve this --- in fact, it could easily make matters worse due to
duplication. Rather, we just have to be careful about adding new
keywords. In this connection, I quite like the fact that recent syntax
extensions such as EXPLAIN (...options...) have managed to avoid making
the option names into grammar keywords at all.

I'm still pretty unhappy about this state of affairs. I would like to
have a fast path and a "you can go crazy here" path.

Apparently the solutions to reduce the footprint involve hand made
recursive decent parsers which are harder to maintain.

I've read a little about the packrat parsing techniques, but far from
enough to understand how much they could help us solve the binary bloat
problem we have here while not making it harder to maintain our grammar.

Maybe some other techniques are available…

Ideas? Or should I just bite the bullet?
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Tom Lane wrote:

the parser tables are basically number-of-tokens wide by
number-of-states high. (In HEAD there are 433 tokens known to the
grammar, all but 30 of which are keywords, and 4367 states.)

Splitting the grammar into multiple grammars is unlikely to do
much to improve this --- in fact, it could easily make matters
worse due to duplication.

I agree that without knowing what percentage would be used by each
parser in a split, it could go either way.  Consider a hypothetical
situation where one parser has 80% and the other 50% of the current
combined parser -- 30% overlap on both tokens and grammer
constructs. (Picking numbers out of the air, for purposes of
demonstration.)

Combined = 433 * 4,367 = 1,890,911

80% = 346 * 3,493 = 1,208,578
50% = 216 * 2,183 =   471,528

Total for split =   1,680,106

Of course if they were both at 80% it would be a higher total than
combined, but unless you have a handle on the percentages, it
doesn't seem like a foregone conclusion. Do you have any feel for
what the split would be?

-Kevin

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

"Kevin Grittner" <kgrittn@mail.com> writes:

Tom Lane wrote:

the parser tables are basically number-of-tokens wide by
number-of-states high. (In HEAD there are 433 tokens known to the
grammar, all but 30 of which are keywords, and 4367 states.)

Splitting the grammar into multiple grammars is unlikely to do
much to improve this --- in fact, it could easily make matters
worse due to duplication.

Of course if they were both at 80% it would be a higher total than
combined, but unless you have a handle on the percentages, it
doesn't seem like a foregone conclusion. Do you have any feel for
what the split would be?

I don't really, but I will note that the scalar-expression subgrammar is
a pretty sizable part of the whole, and it's difficult to see how you'd
make a useful split that didn't duplicate it. I guess you could push
CREATE TABLE, ALTER TABLE, CREATE DOMAIN, ALTER DOMAIN, COPY, and
anything else that included expression arguments over into the "main"
grammar. But that path leads to more and more stuff getting moved to
the "main" grammar over time, making the whole thing more and more
questionable. The whole concept seems ugly and unmaintainable in any
case.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Dec 15, 2012 at 11:52 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

"Kevin Grittner" <kgrittn@mail.com> writes:

Tom Lane wrote:

the parser tables are basically number-of-tokens wide by
number-of-states high. (In HEAD there are 433 tokens known to the
grammar, all but 30 of which are keywords, and 4367 states.)

Splitting the grammar into multiple grammars is unlikely to do
much to improve this --- in fact, it could easily make matters
worse due to duplication.

Of course if they were both at 80% it would be a higher total than
combined, but unless you have a handle on the percentages, it
doesn't seem like a foregone conclusion. Do you have any feel for
what the split would be?

I don't really, but I will note that the scalar-expression subgrammar is
a pretty sizable part of the whole, and it's difficult to see how you'd
make a useful split that didn't duplicate it. I guess you could push
CREATE TABLE, ALTER TABLE, CREATE DOMAIN, ALTER DOMAIN, COPY, and
anything else that included expression arguments over into the "main"
grammar. But that path leads to more and more stuff getting moved to
the "main" grammar over time, making the whole thing more and more
questionable. The whole concept seems ugly and unmaintainable in any
case.

I thought a little bit about the sort of thing that Dimitri is
proposing in the past, and it seemed to me that one could put DML in
one grammar and everything else in another grammar and then decide,
based on the first word of the input, which grammar to use. But there
are a couple of problems with this. First, the DML grammar has to
include an awful lot of stuff, because the grammar for expressions is
really complicated and involves a lot of things like special-case
syntax for XML that are probably not really carrying their weight but
which cannot easily be factored out. Second, the DDL grammar would
have to duplicate a lot of stuff that also shows up in the DML
grammar, because things like expressions can also show up in DEFAULT
or USING clauses which show up in things like CREATE TABLE and ALTER
TABLE and CREATE SCHEMA .. CREATE TABLE.

Now either one of these problems by itself might not be sufficient to
kill the idea: if the DML grammar were a small subset of the full
grammar, one might not mind duplicating some stuff, on the grounds
that in most cases that full grammar would not be used, and using only
the smaller tables most of the time would be easier on the L1 cache.
And on the other hand, if you could get a clean split between the two
grammars, then regardless of exactly what the split was, it might seem
a win. But it seemed to me when I looked at this that you'd have to
duplicate a lot of stuff and the small parser still wouldn't end up
being very small, which I found hard to get excited about.

I'm frankly kind of shocked at the revelation that the parser is
already 14% of the backend. I knew it was big; I didn't realize it
was THAT big.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

I'm frankly kind of shocked at the revelation that the parser is
already 14% of the backend. I knew it was big; I didn't realize it
was THAT big.

Yeah, likewise. It makes me wonder whether we aren't past the size
of grammar that bison is a good choice for: considering that gram.y
is only circa 1% of the source text, it's surprising to find that
it compiles to >10% of the object code.

I'm not sure what other tool might be better though. I looked through
http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages
but it seems our options are a bit limited if we want something
that produces C. It's not clear to me that any of the likely options
are as mature as bison, let alone likely to substantially outperform it.
(For instance, Hyacc sounded pretty promising until I got to the part
about it doesn't yet support %union or %type.) Still, I didn't spend
much time on this --- maybe somebody else would like to do a bit more
research.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

And on the other hand, if you could get a clean split between the two
grammars, then regardless of exactly what the split was, it might seem
a win. But it seemed to me when I looked at this that you'd have to
duplicate a lot of stuff and the small parser still wouldn't end up
being very small, which I found hard to get excited about.

I think the goal is not so much about getting a much smaller parser, but
more about have a separate parser that you don't care about the "bloat"
of, so that you can improve DDL without fearing about main parser
performance regressions.

If we come out with no regression and no gain on the main query parser,
I say it still worth the separation effort. And anyway we only add
things to the main parser (queries) when the standard saith we have to.

Tom Lane <tgl@sss.pgh.pa.us> writes:

I'm not sure what other tool might be better though. I looked through
http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages
but it seems our options are a bit limited if we want something
that produces C. It's not clear to me that any of the likely options
are as mature as bison, let alone likely to substantially outperform it.
(For instance, Hyacc sounded pretty promising until I got to the part
about it doesn't yet support %union or %type.) Still, I didn't spend
much time on this --- maybe somebody else would like to do a bit more
research.

I did spend a very little time on it too, with a different search angle,
and did find that "experimental" thing that might be worth looking at,
or maybe not.

http://en.wikipedia.org/wiki/Parsing_expression_grammar
http://piumarta.com/software/peg/

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Dec 18, 2012 at 4:33 AM, Dimitri Fontaine
<dimitri@2ndquadrant.fr> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

And on the other hand, if you could get a clean split between the two
grammars, then regardless of exactly what the split was, it might seem
a win. But it seemed to me when I looked at this that you'd have to
duplicate a lot of stuff and the small parser still wouldn't end up
being very small, which I found hard to get excited about.

I think the goal is not so much about getting a much smaller parser, but
more about have a separate parser that you don't care about the "bloat"
of, so that you can improve DDL without fearing about main parser
performance regressions.

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I can't help but suspect that the way we handle keywords today is
monumentally inefficient. The unreserved_keyword products, et al,
just seem somehow badly wrong-headed. We take the trouble to
distinguish all of those cases so that we an turn around and not
distinguish them. I feel like there ought to be some way to use lexer
states to handle this - if we're in a context where an unreserved
keyword will be treated as an IDENT, then have the lexer return IDENT
when it sees an unreserved keyword. I might be wrong, but it seems
like that would eliminate a whole lot of parser state transitions.
However, even if I'm right, I have no idea how to implement it. It
just seems very wasteful that we have so many parser states that have
no purpose other than (effectively) to convert an unreserved_keyword
into an IDENT when the lexer could do the same thing much more cheaply
given a bit more context.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 12/18/12 5:10 PM, Robert Haas wrote:

I can't help but suspect that the way we handle keywords today is
monumentally inefficient. The unreserved_keyword products, et al,
just seem somehow badly wrong-headed. We take the trouble to
distinguish all of those cases so that we an turn around and not
distinguish them. I feel like there ought to be some way to use lexer
states to handle this - if we're in a context where an unreserved
keyword will be treated as an IDENT, then have the lexer return IDENT
when it sees an unreserved keyword.

The problem would be the lookahead. You need to know the next token
before you can decide what context the current one is in.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Dec 18, 2012 at 5:24 PM, Peter Eisentraut <peter_e@gmx.net> wrote:

On 12/18/12 5:10 PM, Robert Haas wrote:

I can't help but suspect that the way we handle keywords today is
monumentally inefficient. The unreserved_keyword products, et al,
just seem somehow badly wrong-headed. We take the trouble to
distinguish all of those cases so that we an turn around and not
distinguish them. I feel like there ought to be some way to use lexer
states to handle this - if we're in a context where an unreserved
keyword will be treated as an IDENT, then have the lexer return IDENT
when it sees an unreserved keyword.

The problem would be the lookahead. You need to know the next token
before you can decide what context the current one is in.

Yeah, that's why I don't know how to make it work. It feels like this
is partly artifact of the tool, though. I mean, suppose we haven't
read anything yet. Then, the next token can't be an IDENT, so if we
see an unreserved keyword, we know we're not going to convert it to an
IDENT. OTOH, if we've seen CREATE TABLE, the next token cannot be an
unreserved keyword that is intended as a keyword; it has to be
something that will reduce to ColId.

I guess the problem situation is where we can shift the keyword and
then use the following token to decide whether to reduce it to
ColId/type_function_name/ColLabel or use some other rule instead; the
CREATE INDEX CONCURRENTLY productions might be such a case.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Dec 18, 2012 at 10:33:12AM +0100, Dimitri Fontaine wrote:

Robert Haas <robertmhaas@gmail.com> writes:

And on the other hand, if you could get a clean split between the two
grammars, then regardless of exactly what the split was, it might seem
a win. But it seemed to me when I looked at this that you'd have to
duplicate a lot of stuff and the small parser still wouldn't end up
being very small, which I found hard to get excited about.

I think the goal is not so much about getting a much smaller parser, but
more about have a separate parser that you don't care about the "bloat"
of, so that you can improve DDL without fearing about main parser
performance regressions.

In addition to this, there could well be uses for a more modular
parser. For example, if it turns out to be possible to do our parser
in a way that is exportable and (can be converted to a type that)
looks forward, client code could do a lot of interesting (and provably
correct) things.

If we come out with no regression and no gain on the main query parser,
I say it still worth the separation effort. And anyway we only add
things to the main parser (queries) when the standard saith we have to.

Tom Lane <tgl@sss.pgh.pa.us> writes:

I'm not sure what other tool might be better though. I looked through
http://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages
but it seems our options are a bit limited if we want something
that produces C. It's not clear to me that any of the likely options
are as mature as bison, let alone likely to substantially outperform it.
(For instance, Hyacc sounded pretty promising until I got to the part
about it doesn't yet support %union or %type.) Still, I didn't spend
much time on this --- maybe somebody else would like to do a bit more
research.

I did spend a very little time on it too, with a different search angle,
and did find that "experimental" thing that might be worth looking at,
or maybe not.

http://en.wikipedia.org/wiki/Parsing_expression_grammar
http://piumarta.com/software/peg/

More angles:

http://wwwiti.cs.uni-magdeburg.de/~rosenmue/publications/SKS+08.pdf

Might anyone here wish to investigate this, given some kind of
resources for the initial study?

Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Dec 18, 2012 at 10:44 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Yeah, that's why I don't know how to make it work. It feels like this
is partly artifact of the tool, though. I mean, suppose we haven't
read anything yet. Then, the next token can't be an IDENT, so if we
see an unreserved keyword, we know we're not going to convert it to an
IDENT. OTOH, if we've seen CREATE TABLE, the next token cannot be an
unreserved keyword that is intended as a keyword; it has to be
something that will reduce to ColId.

I guess the problem situation is where we can shift the keyword and
then use the following token to decide whether to reduce it to
ColId/type_function_name/ColLabel or use some other rule instead; the
CREATE INDEX CONCURRENTLY productions might be such a case.

It seems to me the avenue for simplifying the transition table would
be keywords that can never be used in the same place. That is, if we
replaced all the elements of such a set with a single token then the
grammar would be unambigous and we could insert a check that the right
actual token was present in each place it's used. I'm thinking of the
various "noise words" that the SQL standard introduces which are all
going to be reduced to IDENT except for a few places each of which
will only admit one such noise word anyways.

I think doing this manually would be unmaintainable since every time
we modified the grammar it would introduce random unpredictable
conflicts which would be hard to debug. But I wonder if we could
preparse the transitions table, find any such large sets and rewrite
either the transition table or regenerate the grammar and rerun bison
on it.

Alternately we could just replace the transition table with a
representation that is less wasteful such as a list of perfect hash
tables just large enough to hold the valid transition. Or even a
single very large perfect hash table where the key is <state,token>.

But I'm not entirely convinced any of this is actually useful. Just
becuase the transition table is large doesn't mean it's inefficient.
Most of these bytes are being wasted on transitions which can never
occur or which can never occur in syntactically valid SQL. The
transitions which can occur will still be present in any condensed
representation we come up with. The L2 cache might still be large
enough to hold these hot transitions which might not be a very large
subset at all.

valgrind comes with a tool called cachegrind which can emulate the
cache algorithm on some variants of various cpus and produce reports.
Can it be made to produce a report for a specific block of memory?

--
greg

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Greg Stark <stark@mit.edu> writes:

But I'm not entirely convinced any of this is actually useful. Just
becuase the transition table is large doesn't mean it's inefficient.

That's a fair point. However, I've often noticed base_yyparse() showing
up rather high on profiles --- higher than seemed plausible at the time,
given that its state-machine implementation is pretty tight. Now I'm
wondering whether that isn't coming from cache stalls from trying to
touch all the requisite parts of the transition table.

valgrind comes with a tool called cachegrind which can emulate the
cache algorithm on some variants of various cpus and produce reports.
Can it be made to produce a report for a specific block of memory?

I believe that oprofile can be persuaded to produce statistics about
where in one's code are the most cache misses, not just the most
wall-clock ticks; which would shed a lot of light on this question.
However, my oprofile-fu doesn't quite extend to actually persuading it.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Dec 19, 2012 at 10:18 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

valgrind comes with a tool called cachegrind which can emulate the
cache algorithm on some variants of various cpus and produce reports.
Can it be made to produce a report for a specific block of memory?

I believe that oprofile can be persuaded to produce statistics about
where in one's code are the most cache misses, not just the most
wall-clock ticks; which would shed a lot of light on this question.
However, my oprofile-fu doesn't quite extend to actually persuading it.

perf can certainly do this.

$ perf record -a -e cache-misses pgbench -n -S -T 30
...output elided...
$ perf report -d postgres | grep -v '^#' | head
8.88% postgres base_yyparse
7.05% swapper 0x807c
4.67% postgres SearchCatCache
3.77% pgbench 0x172dd58
3.47% postgres hash_search_with_hash_value
3.23% postgres AllocSetAlloc
2.58% postgres core_yylex
1.87% postgres LWLockAcquire
1.83% postgres fmgr_info_cxt_security
1.75% postgres 0x4d1054

For comparison:

$ perf record -a -e cycles -d postgres pgbench -n -S -T 30
$ perf report -d postgres | grep -v '^#' | head
6.54% postgres AllocSetAlloc
4.08% swapper 0x4ce754
3.60% postgres hash_search_with_hash_value
2.74% postgres base_yyparse
2.71% postgres MemoryContextAllocZeroAligned
2.57% postgres MemoryContextAlloc
2.36% postgres SearchCatCache
2.10% postgres _bt_compare
1.70% postgres LWLockAcquire
1.54% postgres FunctionCall2Coll

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 12/18/12 5:10 PM, Robert Haas wrote:

I can't help but suspect that the way we handle keywords today is
monumentally inefficient. The unreserved_keyword products, et al,
just seem somehow badly wrong-headed. We take the trouble to
distinguish all of those cases so that we an turn around and not
distinguish them. I feel like there ought to be some way to use lexer
states to handle this - if we're in a context where an unreserved
keyword will be treated as an IDENT, then have the lexer return IDENT
when it sees an unreserved keyword. I might be wrong, but it seems
like that would eliminate a whole lot of parser state transitions.
However, even if I'm right, I have no idea how to implement it. It
just seems very wasteful that we have so many parser states that have
no purpose other than (effectively) to convert an unreserved_keyword
into an IDENT when the lexer could do the same thing much more cheaply
given a bit more context.

Another way of attack along these lines might be to use the %glr-parser
and then try to cut back on all those redundant rules that were put in
to avoid conflicts. The number of key words categories and such could
perhaps also be reduced that way.

Of course, this is mostly speculation.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 18 December 2012 22:10, Robert Haas <robertmhaas@gmail.com> wrote:

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I don't think the size of the parser binary is that relevant. What is
relevant is how much of that is regularly accessed.

Increasing parser cache misses for DDL and increasing size of binary
overall are acceptable costs if we are able to swap out the unneeded
areas and significantly reduce the cache misses on the well travelled
portions of the parser.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

On 18 December 2012 22:10, Robert Haas <robertmhaas@gmail.com> wrote:

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I don't think the size of the parser binary is that relevant. What is
relevant is how much of that is regularly accessed.

Increasing parser cache misses for DDL and increasing size of binary
overall are acceptable costs if we are able to swap out the unneeded
areas and significantly reduce the cache misses on the well travelled
portions of the parser.

I generally agree. We don't want to bloat the size of the parser with
wild abandon, but yeah if we can reduce the cache misses on the
well-travelled portions that seems like it ought to help. My previous
hacky attempt to quantify the potential benefit in this area was:

http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php

On my machine there seemed to be a small but consistent win; on a very
old box Jeff Janes tried, it didn't seem like there was any benefit at
all. Somehow, I have a feeling we're missing a trick here.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2012-12-20 09:11:46 -0500, Robert Haas wrote:

On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

On 18 December 2012 22:10, Robert Haas <robertmhaas@gmail.com> wrote:

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I don't think the size of the parser binary is that relevant. What is
relevant is how much of that is regularly accessed.

Increasing parser cache misses for DDL and increasing size of binary
overall are acceptable costs if we are able to swap out the unneeded
areas and significantly reduce the cache misses on the well travelled
portions of the parser.

I generally agree. We don't want to bloat the size of the parser with
wild abandon, but yeah if we can reduce the cache misses on the
well-travelled portions that seems like it ought to help. My previous
hacky attempt to quantify the potential benefit in this area was:

http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php

On my machine there seemed to be a small but consistent win; on a very
old box Jeff Janes tried, it didn't seem like there was any benefit at
all. Somehow, I have a feeling we're missing a trick here.

I don't think you will see too many cache misses on such a low number of
extremly simply statements, so its not too surprising not to see a that
big difference with that.

Are we sure its really cache-misses and not just the actions performed
in the grammar that make bison code show up in profiles? I remember the
latter being the case...

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2012-12-20 15:45:47 +0100, Andres Freund wrote:

On 2012-12-20 09:11:46 -0500, Robert Haas wrote:

On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

On 18 December 2012 22:10, Robert Haas <robertmhaas@gmail.com> wrote:

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I don't think the size of the parser binary is that relevant. What is
relevant is how much of that is regularly accessed.

Increasing parser cache misses for DDL and increasing size of binary
overall are acceptable costs if we are able to swap out the unneeded
areas and significantly reduce the cache misses on the well travelled
portions of the parser.

I generally agree. We don't want to bloat the size of the parser with
wild abandon, but yeah if we can reduce the cache misses on the
well-travelled portions that seems like it ought to help. My previous
hacky attempt to quantify the potential benefit in this area was:

http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php

On my machine there seemed to be a small but consistent win; on a very
old box Jeff Janes tried, it didn't seem like there was any benefit at
all. Somehow, I have a feeling we're missing a trick here.

I don't think you will see too many cache misses on such a low number of
extremly simply statements, so its not too surprising not to see a that
big difference with that.

Are we sure its really cache-misses and not just the actions performed
in the grammar that make bison code show up in profiles? I remember the
latter being the case...

Hm. A very, very quick perf stat -dvvv of pgbench -S -c 20 -j 20 -T 20 later:

218350.885559 task-clock # 10.095 CPUs utilized
1,676,479 context-switches # 0.008 M/sec
2,396 cpu-migrations # 0.011 K/sec
796,038 page-faults # 0.004 M/sec
506,312,525,518 cycles # 2.319 GHz [20.00%]
405,944,435,754 stalled-cycles-frontend # 80.18% frontend cycles idle [30.32%]
236,712,872,641 stalled-cycles-backend # 46.75% backend cycles idle [40.51%]
193,459,120,458 instructions # 0.38 insns per cycle
# 2.10 stalled cycles per insn [50.70%]
36,433,144,472 branches # 166.856 M/sec [51.12%]
3,623,778,087 branch-misses # 9.95% of all branches [50.87%]
50,344,123,581 L1-dcache-loads # 230.565 M/sec [50.33%]
5,548,192,686 L1-dcache-load-misses # 11.02% of all L1-dcache hits [49.69%]
2,666,461,361 LLC-loads # 12.212 M/sec [35.63%]
112,407,198 LLC-load-misses # 4.22% of all LL-cache hits [ 9.67%]

21.629396701 seconds time elapsed

So there definitely a noticeable rate of cache misses...

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2012-12-20 15:51:37 +0100, Andres Freund wrote:

On 2012-12-20 15:45:47 +0100, Andres Freund wrote:

On 2012-12-20 09:11:46 -0500, Robert Haas wrote:

On Thu, Dec 20, 2012 at 8:55 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

On 18 December 2012 22:10, Robert Haas <robertmhaas@gmail.com> wrote:

Well that would be nice, but the problem is that I see no way to
implement it. If, with a unified parser, the parser is 14% of our
source code, then splitting it in two will probably crank that number
up well over 20%, because there will be duplication between the two.
That seems double-plus un-good.

I don't think the size of the parser binary is that relevant. What is
relevant is how much of that is regularly accessed.

Increasing parser cache misses for DDL and increasing size of binary
overall are acceptable costs if we are able to swap out the unneeded
areas and significantly reduce the cache misses on the well travelled
portions of the parser.

I generally agree. We don't want to bloat the size of the parser with
wild abandon, but yeah if we can reduce the cache misses on the
well-travelled portions that seems like it ought to help. My previous
hacky attempt to quantify the potential benefit in this area was:

http://archives.postgresql.org/pgsql-hackers/2011-05/msg01008.php

On my machine there seemed to be a small but consistent win; on a very
old box Jeff Janes tried, it didn't seem like there was any benefit at
all. Somehow, I have a feeling we're missing a trick here.

I don't think you will see too many cache misses on such a low number of
extremly simply statements, so its not too surprising not to see a that
big difference with that.

Are we sure its really cache-misses and not just the actions performed
in the grammar that make bison code show up in profiles? I remember the
latter being the case...

Hm. A very, very quick perf stat -dvvv of pgbench -S -c 20 -j 20 -T 20 later:

218350.885559 task-clock # 10.095 CPUs utilized
1,676,479 context-switches # 0.008 M/sec
2,396 cpu-migrations # 0.011 K/sec
796,038 page-faults # 0.004 M/sec
506,312,525,518 cycles # 2.319 GHz [20.00%]
405,944,435,754 stalled-cycles-frontend # 80.18% frontend cycles idle [30.32%]
236,712,872,641 stalled-cycles-backend # 46.75% backend cycles idle [40.51%]
193,459,120,458 instructions # 0.38 insns per cycle
# 2.10 stalled cycles per insn [50.70%]
36,433,144,472 branches # 166.856 M/sec [51.12%]
3,623,778,087 branch-misses # 9.95% of all branches [50.87%]
50,344,123,581 L1-dcache-loads # 230.565 M/sec [50.33%]
5,548,192,686 L1-dcache-load-misses # 11.02% of all L1-dcache hits [49.69%]
2,666,461,361 LLC-loads # 12.212 M/sec [35.63%]
112,407,198 LLC-load-misses # 4.22% of all LL-cache hits [ 9.67%]

21.629396701 seconds time elapsed

So there definitely a noticeable rate of cache misses...

L1 misses:
# Samples: 997K of event 'L1-dcache-load-misses'
# Overhead Command Shared Object Symbol
# ........ ........ ...............................................................
6.49% postgres postgres [.] SearchCatCache
3.65% postgres postgres [.] base_yyparse
3.48% postgres postgres [.] hash_search_with_hash_value
3.41% postgres postgres [.] AllocSetAlloc
1.84% postgres postgres [.] LWLockAcquire
1.40% postgres postgres [.] fmgr_info_cxt_security
1.36% postgres postgres [.] nocachegetattr
1.23% postgres libc-2.13.so [.] _int_malloc
1.20% postgres postgres [.] core_yylex
1.15% postgres postgres [.] MemoryContextAllocZeroAligned
0.94% postgres postgres [.] PostgresMain
0.94% postgres postgres [.] MemoryContextAlloc
0.91% postgres libc-2.13.so [.] __memcpy_ssse3_back
0.89% postgres postgres [.] CatalogCacheComputeHashValue
0.86% postgres postgres [.] PinBuffer
0.86% postgres [kernel.kallsyms] [k] __audit_syscall_entry
0.80% postgres libc-2.13.so [.] __strcmp_sse42
0.80% postgres postgres [.] _bt_compare
0.78% postgres postgres [.] FunctionCall2Coll
0.77% postgres libc-2.13.so [.] malloc
0.73% postgres libc-2.13.so [.] __memset_sse2
0.72% postgres postgres [.] GetSnapshotData
0.69% postgres [kernel.kallsyms] [k] fget_light
0.69% postgres postgres [.] DirectFunctionCall1Coll
0.67% postgres postgres [.] hash_search
0.67% postgres libc-2.13.so [.] 0x000000000011a3a5
0.66% postgres postgres [.] pgstat_initstats
0.66% postgres postgres [.] AllocSetFree
0.65% postgres libc-2.13.so [.] __strlen_sse42
0.60% postgres libc-2.13.so [.] _int_free
0.60% postgres [kernel.kallsyms] [k] cpuacct_charge
0.59% postgres postgres [.] heap_getsysattr
0.59% postgres postgres [.] MemoryContextAllocZero
0.58% postgres postgres [.] PopActiveSnapshot
0.53% postgres libc-2.13.so [.] __memcmp_sse4_1
0.51% postgres postgres [.] ReadBuffer_common
0.49% postgres postgres [.] ScanKeywordLookup
0.49% postgres postgres [.] LockAcquireExtended
0.47% postgres [kernel.kallsyms] [k] update_cfs_shares
0.45% postgres postgres [.] SearchCatCacheList
0.45% postgres postgres [.] new_list
0.44% postgres postgres [.] get_relation_info

LLC misses:
# Samples: 1M of event 'LLC-load-misses'
# Event count (approx.): 143379713
# Overhead Command Shared Object Symbol
# ........ ........ ...............................................................
25.08% postgres postgres [.] _bt_compare
12.84% postgres postgres [.] PinBuffer
9.18% postgres postgres [.] LWLockAcquire
6.31% postgres postgres [.] GetSnapshotData
6.08% postgres postgres [.] heap_hot_search_buffer
5.13% postgres postgres [.] hash_search_with_hash_value
4.85% postgres postgres [.] _bt_checkpage
3.95% postgres postgres [.] _bt_moveright
3.09% postgres postgres [.] heap_page_prune_opt
2.12% postgres postgres [.] slot_deform_tuple
1.98% postgres postgres [.] LWLockRelease
1.82% postgres libc-2.13.so [.] __memcmp_sse4_1
1.16% postgres postgres [.] ExecProject
1.16% postgres postgres [.] FunctionCall2Coll
0.94% postgres [kernel.kallsyms] [k] copy_user_generic_string
0.94% postgres [kernel.kallsyms] [k] tg_load_down
0.78% postgres [kernel.kallsyms] [k] find_get_page
0.73% postgres postgres [.] ProcArrayEndTransaction
0.73% postgres postgres [.] pfree
0.71% postgres postgres [.] pgstat_report_xact_timestamp
0.69% postgres postgres [.] index_fetch_heap
0.66% postgres postgres [.] LockAcquireExtended
0.56% postgres postgres [.] LockBuffer
0.45% postgres postgres [.] slot_getsomeattrs
0.40% postgres postgres [.] _bt_readpage

So it seems L1 misses are the interesting thing wrt to parsing.

When doing a source/assembly annotation in SearchCatCache about half of
the misses are attributed to the memcpy() directly at the beginning.
In base_yyparse the three biggest offenders (15%, 10.5%, 5.58%) really
seem to be various kinds of table lookups.

So it seems to confirm the various suspicious that the table size might
be rather relevant.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2012-12-20 16:04:49 +0100, Andres Freund wrote:

On 2012-12-20 15:51:37 +0100, Andres Freund wrote:
When doing a source/assembly annotation in SearchCatCache about half of
the misses are attributed to the memcpy() directly at the beginning.

Using a separate array for storing the arguments instead of copying &
modifying cache->cc_skey yields a 2% speedup in pgbench -S for me...

The attached patch is clearly not ready and I don't really have time &
energy to pursue it right now, but it seems interesting enough to
post. The approach seems solid and sensible although the implementation
is not (too much c&p, no comments).

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Thu, Dec 20, 2012 at 3:18 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Greg Stark <stark@mit.edu> writes:

But I'm not entirely convinced any of this is actually useful. Just
becuase the transition table is large doesn't mean it's inefficient.

That's a fair point. However, I've often noticed base_yyparse() showing
up rather high on profiles --- higher than seemed plausible at the time,
given that its state-machine implementation is pretty tight. Now I'm
wondering whether that isn't coming from cache stalls from trying to
touch all the requisite parts of the transition table.

For what it's worth the bloat isn't in the parser transition table at all:
516280 yy_transition
147208 yytable
147208 yycheck
146975 base_yyparse
17468 yypact
9571 core_yylex
8734 yystos
8734 yydefact

Unless I'm confused yy_transition is in fact the *lexer* transition
table. I'm not sure how to reconcile that with the profiling results
showing the cache misses in base_yyparse() though.

--
greg

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2012-12-20 15:58:12 +0000, Greg Stark wrote:

On Thu, Dec 20, 2012 at 3:18 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Greg Stark <stark@mit.edu> writes:

But I'm not entirely convinced any of this is actually useful. Just
becuase the transition table is large doesn't mean it's inefficient.

That's a fair point. However, I've often noticed base_yyparse() showing
up rather high on profiles --- higher than seemed plausible at the time,
given that its state-machine implementation is pretty tight. Now I'm
wondering whether that isn't coming from cache stalls from trying to
touch all the requisite parts of the transition table.

For what it's worth the bloat isn't in the parser transition table at all:
516280 yy_transition
147208 yytable
147208 yycheck
146975 base_yyparse
17468 yypact
9571 core_yylex
8734 yystos
8734 yydefact

Unless I'm confused yy_transition is in fact the *lexer* transition
table. I'm not sure how to reconcile that with the profiling results
showing the cache misses in base_yyparse() though.

The scanner is compiled together with the parser, so its not unlikely
that the compiler bunches them together making only base_yyparse visible
in the profile.
I quickly checked though, and the top three offenders for L1 caches are
in bison not in the lexer... Its not implausible that the state
transitions in the lexer are better cached and/or predicted...

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Another way of attack along these lines might be to use the %glr-parser
and then try to cut back on all those redundant rules that were put in
to avoid conflicts. The number of key words categories and such could
perhaps also be reduced that way.

Of course, this is mostly speculation.

The GLR output from Bison is licensed under the GPL (unlike the LALR output).
So using Bison's GLR mode isn't an option.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2012-12-20 23:12:55 +0000, McDevitt, Charles wrote:

Another way of attack along these lines might be to use the %glr-parser
and then try to cut back on all those redundant rules that were put in
to avoid conflicts. The number of key words categories and such could
perhaps also be reduced that way.

Of course, this is mostly speculation.

The GLR output from Bison is licensed under the GPL (unlike the LALR output).
So using Bison's GLR mode isn't an option.

Thats not the case anymore:
http://www.gnu.org/software/bison/manual/html_node/Conditions.html

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

The GLR output from Bison is licensed under the GPL (unlike the LALR output).
So using Bison's GLR mode isn't an option.

Thats not the case anymore:
http://www.gnu.org/software/bison/manual/html_node/Conditions.html

Sorry! My mistake... I didn't realize they changed the rules.
I'll be more careful to check these things in the future.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Andres Freund <andres@2ndquadrant.com> writes:

On 2012-12-20 23:12:55 +0000, McDevitt, Charles wrote:

Another way of attack along these lines might be to use the %glr-parser
and then try to cut back on all those redundant rules that were put in
to avoid conflicts. The number of key words categories and such could
perhaps also be reduced that way.

The GLR output from Bison is licensed under the GPL (unlike the LALR output).
So using Bison's GLR mode isn't an option.

Thats not the case anymore:
http://www.gnu.org/software/bison/manual/html_node/Conditions.html

This does mean that we'd have to specify a minimum bison version of 2.2
in order to be squeaky-clean license wise, if we went over to using the
GLR mode. However, that would likely be a good idea anyway from a
technical standpoint --- the GLR mode may exist in ancient bison
versions, but who knows how bug-free it is.

Anyway, this is all merest speculation until somebody actually tries it
and sees if a performance gain is possible. Having just re-read
the description of GLR mode, I wouldn't be surprised if any savings in
table size is squandered by its handling of ambiguous cases (ie, the
need to track and merge multiple parser states).

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers