5 ms·

Can someone put this in lay terms for a casual postgresql user?

p4lindromica 8y ago
A perfect hash is one in which their are no collisions for a given data set, which guarantees O(1), or constant, lookup time. This patch introduces a perl script which computes a perfect hash function at build time given the current set of SQL keywords. The old keyword lookup method uses binary search. Binary search is a search algorithm that must compare at most O(log n) entries before finding a match. Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup.
- anarazel 8y ago
  > Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup. Worthwhile to note that that speedup is for the raw parsing, without parse-analysis (i.e. looking up the tables referenced and such), planning (figuring out how to execute the query) and execution. So end-user impact will be much smaller than 20%. But for some cases, e.g. when many columns are referenced, it'll be measurable.
  - the_duke 8y ago
    Column names aren't keywords though, are they?. Using a perfect hash table is definitely cool, but it's hard to imagine a query with so many keywords that this would have a measurable impact on total query execution time.
    - anarazel 8y ago
      Due to the desire to have keywords that aren't fully reserved (we have keyword classes that are fully reserved, can appear as type names, can appear as column names, or can appear nearly everywhere) we/PG need to look up whether a specific string is a keyword or an identifier in a number of places in the scanner/parser. Addendum: And that indeed means that column references, unless quoted with "", used to go through the binary search and now go through the perfect hash. Edit: Typo
      - the_duke 8y ago
        Ah that makes sense. Thanks for that insight!
chrismorgan 8y ago
Parsing SQL is made faster. Imagine a language with five keywords, for simplicity. keywords = ["AS", "FROM", "INSERT", "SELECT", "WHERE"]; tokens = [As, From, Insert, Select, Where]; Now you have a token that you need to interpret: let token_raw = "FROM"; let index = keywords.binary_search(token_raw); let token = tokens[index]; As a binary search, that’s O(log N) string comparisons. In this worst case, it may try comparing with INSERT, then AS, then FROM before deciding index is 1, but for more keywords you have more comparisons. With perfect hashing, you devise a single hash function that hashes all possible values uniquely. Now we have something like this: tokens = {914576: As, 73932: From, 5791456: Insert, 21596: Select, 86548: Where}; … with all the numbers calculated by hashing the strings at compile time. Then, instead of O(log N) string comparisons, you only need one hash and one hash table lookup: let token_raw = "FROM"; let token = tokens[hash(token_raw)];
- deleted 8y ago
  [deleted]
- jules 8y ago
  Why is this necessary at all? The lexer is recognising tokens with a finite state machine, so it already knows which keyword it's got.
  - gizmo 8y ago
    The lexer knows it has a token, but it still has to match the token identifier to the corresponding keyword. Whether this happens at the lexing or parsing stage doesn't matter much, it's still expensive when strcmp is called a bunch of times for every keyword token.
    - jules 8y ago
      Lexers don't do strcmps, they use a finite state machine to determine tokens. For instance if we have the tokens ALTER, AND, ANY, SELECT, FROM it will compile into a state machine like this: switch(str[i++]){ case 'A': switch(str[i++]){ case 'L': ... case 'N': switch(str[i++]){ case 'D': found token! case 'Y: found token! default: syntax error! } ... } case 'S': ... case 'F': ... ... } Lexers already do this, and in each place where a token is found, it can know which token it was based on the DFA state that it's in.

A perfect hash is one in which their are no collisions for a given data set, which guarantees O(1), or constant, lookup time. This patch introduces a perl script which computes a perfect hash function at build time given the current set of SQL keywords. The old keyword lookup method uses binary search. Binary search is a search algorithm that must compare at most O(log n) entries before finding a match. Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup.

anarazel 8y ago
> Making 1 keyword comparison instead of log n keyword comparisons yields the 20% speedup. Worthwhile to note that that speedup is for the raw parsing, without parse-analysis (i.e. looking up the tables referenced and such), planning (figuring out how to execute the query) and execution. So end-user impact will be much smaller than 20%. But for some cases, e.g. when many columns are referenced, it'll be measurable.
- the_duke 8y ago
  Column names aren't keywords though, are they?. Using a perfect hash table is definitely cool, but it's hard to imagine a query with so many keywords that this would have a measurable impact on total query execution time.
  - anarazel 8y ago
    Due to the desire to have keywords that aren't fully reserved (we have keyword classes that are fully reserved, can appear as type names, can appear as column names, or can appear nearly everywhere) we/PG need to look up whether a specific string is a keyword or an identifier in a number of places in the scanner/parser. Addendum: And that indeed means that column references, unless quoted with "", used to go through the binary search and now go through the perfect hash. Edit: Typo
    - the_duke 8y ago
      Ah that makes sense. Thanks for that insight!

chrismorgan 8y ago

Parsing SQL is made faster. Imagine a language with five keywords, for simplicity. keywords = ["AS", "FROM", "INSERT", "SELECT", "WHERE"]; tokens = [As, From, Insert, Select, Where]; Now you have a token that you need to interpret: let token_raw = "FROM"; let index = keywords.binary_search(token_raw); let token = tokens[index]; As a binary search, that’s O(log N) string comparisons. In this worst case, it may try comparing with INSERT, then AS, then FROM before deciding index is 1, but for more keywords you have more comparisons. With perfect hashing, you devise a single hash function that hashes all possible values uniquely. Now we have something like this: tokens = {914576: As, 73932: From, 5791456: Insert, 21596: Select, 86548: Where}; … with all the numbers calculated by hashing the strings at compile time. Then, instead of O(log N) string comparisons, you only need one hash and one hash table lookup: let token_raw = "FROM"; let token = tokens[hash(token_raw)];

deleted 8y ago
[deleted]
jules 8y ago
Why is this necessary at all? The lexer is recognising tokens with a finite state machine, so it already knows which keyword it's got.
- gizmo 8y ago
  The lexer knows it has a token, but it still has to match the token identifier to the corresponding keyword. Whether this happens at the lexing or parsing stage doesn't matter much, it's still expensive when strcmp is called a bunch of times for every keyword token.
  - jules 8y ago
    Lexers don't do strcmps, they use a finite state machine to determine tokens. For instance if we have the tokens ALTER, AND, ANY, SELECT, FROM it will compile into a state machine like this: switch(str[i++]){ case 'A': switch(str[i++]){ case 'L': ... case 'N': switch(str[i++]){ case 'D': found token! case 'Y: found token! default: syntax error! } ... } case 'S': ... case 'F': ... ... } Lexers already do this, and in each place where a token is found, it can know which token it was based on the DFA state that it's in.