From: Andrew Dunstan <andrew.dunstan@2ndquadrant.com>
Subject: Re: reducing the footprint of ScanKeyword (was Re: Large writable
 variables)
To: Tom Lane <tgl@sss.pgh.pa.us>, Andres Freund <andres@anarazel.de>
Cc: Robert Haas <robertmhaas@gmail.com>,
 Andrew Gierth <andrew@tao11.riddles.org.uk>, John Naylor
 <jcnaylor@gmail.com>,
 "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
References: 
 <CAJVSVGX4vTuLhmSgmOWK0FQSuhsvYxb1tj_i41k+OP=qMY9+Mg@mail.gmail.com>
 <31505.1545149557@sss.pgh.pa.us>
 <CAJVSVGXsY_HQ8TUt--PXiE0U9A6JqS+C7HqatR6h-ukQOE0ATA@mail.gmail.com>
 <87lg4luimz.fsf@news-spur.riddles.org.uk>
 <20181220010114.k3wv6r25sc7sr7z5@alap3.anarazel.de>
 <CA+TgmoamFb6tT7DgyatrsKOtN-XqBHaCELo4teKnfFm0FGx8ug@mail.gmail.com>
 <28725.1545841359@sss.pgh.pa.us>
 <CA+TgmoaAo01LhyG0apjh6EAvOnvOwKPQ7_FMd0gO1s33p8Q0ew@mail.gmail.com>
 <20181226180217.qad6ahkkzk4g5poy@alap3.anarazel.de>
 <4585.1545851037@sss.pgh.pa.us>
 <20181227131953.fnspabit3lq56lej@alap3.anarazel.de>
 <4029.1545930759@sss.pgh.pa.us>
Openpgp: preference=signencrypt
Autocrypt: addr=andrew.dunstan@2ndQuadrant.com; prefer-encrypt=mutual;
 keydata=
 xsBNBE7KWFkBCAClridxur2AIc7eW2AR7izbfp3EnNefie2HbLF0izW5Ik5UjX2HBXBx4syI
 gY6b0ugohXrr274+baoAlvSbq6cAoQuEVrk5IZFzt20b1Xkx65FwGSEj526yiKLocqkJceSq
 Xr9xcA5SGY+FZv441chh5SU92v4q6z+6LPpoHOh97ptAVXZYNTtU0LevyvD5lja0TzbvJm6C
 eFXitJfnm1pLEr0DGJCR/iUOl/N62Kh4855zZC7NHIjQHPOvV5Stz/l5ilDhvGVk+xkXFPys
 SjZoUr1rXhYLpiyi5sR0X9FHXT0KnGuz1F5ERO7ZTLSSQ6fJwPj6gOk9K+vvoKvoeql5ABEB
 AAHNL0FuZHJldyBEdW5zdGFuIDxhbmRyZXcuZHVuc3RhbkAybmRRdWFkcmFudC5jb20+wsCY
 BBMBAgBCAhsDBgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAUJDyV6hBYhBOQ+WEYd/Hy/RGkV
 pZn6f8tZ/DuBBQJcH/EVAhkBAAoJEJn6f8tZ/DuB7BEH/iDWZEbVft2m2MT6SPjARzTupt/l
 xLLZ/Cl6n2US2hov5+fBbnR5xvECk/YCOfG9ICvKNlpFjceqNLRKStd8cmndnI+kDw91uNM2
 hpL4aJMeW65XCHvqXlOLSwv5chBpXz9NG7FMaJ+q+59sWEWjcTNmjXgkEHn53y+1pc7nSLDe
 cr5ZI1aB3nGXRm1SoDY5PYZkUKMykW+YBZwgcs/Q5tRaE+siN7DKbz8E628+PerwAkmHPVXN
 MdJFD6gs4S0gDFA8IxcyIwZU2v4By+brzcJ9Se3FK5BYxBDHtaYZxgSrJAvOUOrLIZPQTQfL
 TtnVs3C3JTfrxCH1ceHtnA6dRuTOwE0ETspYWQEIANGc4zQULOxhbqO2dyD51YhqCNRmm9oK
 Waqf+wmW4tpDe/VVcxAnNizd4LWCHfzpb5cHAtGkOPePMfzWVf6nvdF7d3eglbtf59+zG7O7
 llV0xSSoFiieQBsrGvqDInXYX/4mRRXMtyhM353/tixC9RWLs1oofyYmCPPXXY7h9R7en3B8
 BoVrRFcdzlIY/NFNhFGW/9dkEiGjgna2Rk6e15kln4ZvFBWUg23p93w/pqXcxY6+k/8TEk+C
 4R+M6w7o2PLGOjdZ+kPiUcw5H85zf/yZJwQXzisXaNduwWB6Vads9YC9dj6kPR1c4VGRqAaY
 L++LAEOqrlvm2TvqQqZRtnEAEQEAAcLAZQQYAQIADwIbDAUCXA6fpAUJDyV6xAAKCRCZ+n/L
 Wfw7geU4B/9vFFsVmWxerDWgNjyiK80zIPmlw/iwdUlU6FIu0JWLMg4093kvxBs7RMZV9hBq
 n3ekBvD4IvFsVLJrw9qzSI2FH3UeYy5WXpEs01Ppia60NOlvRDqXbryzuvfe+iYo6bVP3Ikr
 TPTNYL/BePUTD2DPvSI82SbGTyzuA7SJv6NRqqQDMIy1fU6KyQFLmQJp/QJyhKWzm9jWh8ee
 w8jVaoMY0Kbq5N7RqisEx1Lu/Iw646UphdYzQNymf+kbiU5Kf4I6DhzV8w9sie1Bo1juNj3I
 c5/fFJsmxljbnaDbXPcnFsur1Oo9mIHFakgWgOBMuxoWfjONiLjjLh/9+ZIqSSLX
Message-ID: <ceb23715-78dd-81b0-4760-da00a8b08ffd@2ndQuadrant.com>
Date: Thu, 27 Dec 2018 13:54:05 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.3.0
MIME-Version: 1.0
In-Reply-To: <4029.1545930759@sss.pgh.pa.us>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Content-Language: en-MW
Precedence: bulk


On 12/27/18 12:12 PM, Tom Lane wrote:

>> I don't buy that we're inable to write a descent parser that way.
> I do not think that we could write one for the current state of the
> PG grammar without an investment of effort so large that it's not
> going to happen.  Even if such a parser were to spring fully armed
> from somebody's forehead, we absolutely cannot expect that it would
> continue to work correctly after non-wizard contributors modify it.

I just did a quick survey of generator tools. Unfortunately, the best
candidate alternative (ANTLR) no longer supports generating plain C
code. I don't know of another tool that is well maintained, supports C,
and generates top down parsers. Twenty-five years ago or so I wrote a
top-down table-driven parser generator, but that was in another country,
and besides, the wench is dead.


There are well known techniques (See s 4.4 of the Dragon Book, if you
have a copy) for formal analysis of grammars to determine predictive
parser action. They aren't hard, and the tables they produce are
typically much smaller than those used for LALR parsers. Still, probably
not for the faint of heart.


The tools that have moved to using hand cut RD parsers have done so
precisely because they get a significant performance benefit from doing so.


RD parsers are not terribly hard to write. Yes, the JSON grammar is
tiny, but I think I wrote the basics of the RD parser we use for JSON in
about an hour. I think arguing that our hacker base is not competent to
maintain such a thing for the SQL grammar is wrong.  We successfully
maintain vastly more complex pieces of code.


Having said all that, I don't intend to spend any time on implementing
an alternative parser. It would as you say involve a heck of a lot of
time, which I don't have. It would be a fine academic research project
for some student.


A smaller project might be to see if we can replace the binary keyword
search  in ScanKeyword with a perfect hashing function generated by
gperf, or something similar. I had a quick look at that, too.
Unfortunately the smallest hash table I could generate for our 440
symbols had 1815 entries, so I'm not sure how well that would work.
Worth investigating, though.


cheers


andrew


-- 
Andrew Dunstan                https://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services