On Fri, Jan 8, 2016 at 3:05 PM, Tom Lane <t...@sss.pgh.pa.us> wrote: > [ redirecting from -docs, which isn't the best place to discuss code fixes ] > > Whoever thought this was a good idea: > > StaticAssertStmt(NAMEDATALEN <= MAX_LEVENSHTEIN_STRLEN, > "Levenshtein hinting mechanism restricts NAMEDATALEN"); > > is nuts. > > A minimal fix that would not put stumbling blocks in the way of changes > to NAMEDATALEN is to redefine MAX_LEVENSHTEIN_STRLEN as > Max(255, NAMEDATALEN). But I wonder why we have to have an arbitrary limit > in this code at all. I trust nobody here believes this is the only O(N^2) > algorithm in the backend; the others don't have this sort of thing in > front of them.
The arbitrary limit in that code is not new, but the Assert is. I didn't foresee the consequence that it would become harder to change NAMEDATALEN, and I agree that needs to be fixed. Ripping the arbitrary limit out does not seem like a particularly good idea to me, even if we put CHECK_FOR_INTERRUPTS() into that path. Just because there are other ways to make the backend burn insane amounts of CPU time doesn't mean that we should try to make it easier. Actually, though, varstr_levenshtein_less_equal() never gets called from parse_relation.c with a distance bound of more than four, so it can't actually go quadratic. There's another call in that file to varstr_levenshtein(), which in retrospect looks silly, but I'm pretty sure that could also be changed to use a distance bound of 4 (well, MAX_FUZZY_DISTNACE + 1) without changing the behavior at all. Given a constant distance bound, the algorithm is, I believe, only O(max(m, n)) not O(mn). Knowing that, we could let the internal code just bypass the length check and only enforce the length restriction when the code is called from SQL via fuzzystrmatch. (There are of course other ways to solve the problem, too; this is just one that came to mind.) -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers