4 ms·

From the post: "The time savings is indeed significant: preliminary testing suggests that the total time for raw [SQL] parsing (flex + bison phases) drops by ~

by sjroot 8y ago

From the post: "The time savings is indeed significant: preliminary testing suggests that the total time for raw [SQL] parsing (flex + bison phases) drops by ~20%." Very impressive work!

amelius 8y ago
Impressive? They changed one textbook algorithm by another one. It turns out to be faster, but it might as well be slower for certain inputs (which might be common). Also, when they increase the number of keywords in the future, they might have to reconsider the implementation.
- jimktrains2 8y ago
  I'm having trouble coming up with a scenario where perfect hashing Vs a binary search tree is slower. Also, yes, the very nature of perfect hashing means it will very potential need to be updated with additional keywords. However, that doesn't happen often and this is a small amount of work for what all would be entailed with a new keyword.
- molyss 8y ago
  I think it's impressive, but maybe not for the same reasons as the OP : that means that keyword lookup accounted for at least 20% of total SQL parsing time. That's a surprise to me !
  - anarazel 8y ago
    Note it's the "raw" parsing time. If you include the semantic parse-analysis phase, i.e. looking up table names etc, it's a much smaller portion.
  - sjroot 8y ago
    This is basically what I was thinking -- that a relatively minor change to the parsing process could yield such significant results.
- geophile 8y ago
  Wow. Three errors in three lines. 1) Yes, a 20% improvement is impressive, especially in such a major component of such an important and long-lived piece of software. 2) What do you mean "certain inputs"? There is a fixed set of keywords. The set of inputs is known. It's a great application for perfect hashing. Or do you mean that some keys are going to be slower to search for than others? The best case of binary search is that you search for the key in the exact middle of the table, which requires to compare each character of the search key. (Searching for any other key will require cache misses, possibly, and additional scans of the key's characters.) By contrast, for perfect hashing, you scan the key once to compute the hash value and go directly to the correct slot. So the hash lookup for any key is pretty close to identical to the best case of the binary search. 3) When they add new keywords, they generate a different hash function. That's easy. The implementation does not have to be reconsidered.

by sjroot 8y ago

From the post: "The time savings is indeed significant: preliminary testing suggests that the total time for raw [SQL] parsing (flex + bison phases) drops by ~20%." Very impressive work!

amelius 8y ago

Impressive? They changed one textbook algorithm by another one. It turns out to be faster, but it might as well be slower for certain inputs (which might be common). Also, when they increase the number of keywords in the future, they might have to reconsider the implementation.

jimktrains2 8y ago
I'm having trouble coming up with a scenario where perfect hashing Vs a binary search tree is slower. Also, yes, the very nature of perfect hashing means it will very potential need to be updated with additional keywords. However, that doesn't happen often and this is a small amount of work for what all would be entailed with a new keyword.
molyss 8y ago
I think it's impressive, but maybe not for the same reasons as the OP : that means that keyword lookup accounted for at least 20% of total SQL parsing time. That's a surprise to me !
- anarazel 8y ago
  Note it's the "raw" parsing time. If you include the semantic parse-analysis phase, i.e. looking up table names etc, it's a much smaller portion.
- sjroot 8y ago
  This is basically what I was thinking -- that a relatively minor change to the parsing process could yield such significant results.
geophile 8y ago
Wow. Three errors in three lines. 1) Yes, a 20% improvement is impressive, especially in such a major component of such an important and long-lived piece of software. 2) What do you mean "certain inputs"? There is a fixed set of keywords. The set of inputs is known. It's a great application for perfect hashing. Or do you mean that some keys are going to be slower to search for than others? The best case of binary search is that you search for the key in the exact middle of the table, which requires to compare each character of the search key. (Searching for any other key will require cache misses, possibly, and additional scans of the key's characters.) By contrast, for perfect hashing, you scan the key once to compute the hash value and go directly to the correct slot. So the hash lookup for any key is pretty close to identical to the best case of the binary search. 3) When they add new keywords, they generate a different hash function. That's easy. The implementation does not have to be reconsidered.