FWD » Core Development » Database

Recent work performed by FWD revealed a flaw in the implementation of 1st level cache of the dynamic query parser. Because this cache is meant to quickly resolve the predicates using a rather naive key, this will cause the cache to fill up rather quickly, causing a continuous overflow, reallocating the cache key (thrashing the data structure) and filling the server logs with not very useful information.

This effect comes from the L1 (syntactic) key format. Beside the buffer list, the key tries to group in same class identical queries or queries whose predicates are different by formatting, spaces or other unimportant syntax. This is good since usually there the same queries are used multiple times (90-10 rule), but we are facing situations when the predicates differ by a literal, which is hardcoded in the predicate string of the dynamic queries. Example: where f1=0, where f1=1, .. where f1=1000.

To address this issue, the L2 (semantic) cache was added some time ago. It allows the parser to execute and replaces all literals with parameters, whose values will be used later at execution time. The examples above are converted and unified to same execution tree where the predicate is equivalent to where f1=%1. The problem is that this is a much higher resource consumer and we would prefer to identify these case earlier, eventually using this knowledge and avoid filling the L1 cache with pretty similar queries.

So this is a bit of a problem: identifying the class of predicates using a more complex algorithm (but simpler than L2) and somehow storing it to L1, using special tokens instead of the constants/literals. I do not have a solution yet, but the problem keeps hunting me.

Ovidiu, there are also some patterns quite often encountered, like:

• hq:query-prepare(substitute("for each tt where f1 = &1", value))
• hq:query-prepare(substitute("for each &1 where f1 = &2", "tt", value))
• c = "for each tt where f1 = " + value. hq:query-prepare(c).
• etc.

I skimmed tens of :query-prepare in a large customer application and in most cases the query string is computed using concatenation or substitute in the same procedure (sometimes even on the previous line relative to query-prepare).

I am bringing this into spotlight because the OE code itself has this "using special tokens instead of the constants/literals" technique you mention. In FWD, we evaluate expressions eagerly and so we lose these "special tokens", so we have to re-parse them back.

I wonder if we can fix this at conversion side and/or run-time:

• Consider c = "for each tt where f1 = " + value. hq:query-prepare(c)
• We can assign c to a compoundCharacter delegate underneath the casual character, just like a StringBuilder. In other words, we defer the concatenation until the first time the character is actually needed.
• For query-prepare, we can use more information upon the compoundCharacter. We can do the actual concatenation, but keep static String s inside and replace the character s with ? (or a special token identifiable by the parser as a static value). We can query a cache with that (maybe L2?), presuming that the ? tokens are in fact variables and can be plugged as substitution parameters.
• There is a blind spot there: the presumed constants can be rather complex query parts (e.g. @a = " AND tt.f1 = "), but I think there might be a trivial algorithm to detect that for sure. If we find it risky, we simply fallback to current implementation.
  • if it is "yes", "no", has only digits and eventually ".", doesn't look risky. But I might imagine a case for for each tt&1 to dynamically select a buffer. Maybe we can be restrictive and ensure that the character before is for equality or relational =, >, etc.
  • if it is wrapped within quotes and it doesn't contain quotes, it is not risky. But we should extract the quotes and force the special token ? without being wrapped.
  • everything else is risky.
• Doing this for any arbitrary concatenation / substitute might get slow - or maybe not. This should be investigated

I am optimistic that the 90/10 ratio you are saying might actually be true if we think of this pattern. There are some patterns that might be interesting to analyze

• c = "for each tt". c = c + " where tt.f1 = 1". c = c + " and tt.f2 = 2".
  • As some are static strings, we can concatenate directly without loss of generality. Usually the dynamic parts are coming from variables: c = "for each tt". c = c + " where tt.f1 = " + a. c = c + " and tt.f2 = " + b.. I guess we can be smart with it and glue only static strings.
• I am also intrigued about c = "for each " + bufname + " where " + bufname + ".f1 = 1". cases.

Alex, whatever we do, the predicate string still needs to be parsed. An idea is to have a minimal parser which has two purposes:

• be efficient and fast
• returns a modified predicate where the literals are extracted, and replaced with a new placeholder token

This new predicate can then be used as a key in the Level 2 cache to get its real JAST. This way we avoid the expensive progress.g parsing. Level 1 cache can still be used to map the original predicate to a JAST.

An idea is to have a minimal parser which has two purposes:

This is why I think we can rely on the converted code as it already has the query string "parsed" and look like a query string where literals are extracted. It is not a 100% solution, but it is instant. We can even do some conversion shenanigans to preserve that structure, but even this run-time "compoundCharacter" approach has a negligible overhead IMHO.

In my idea, the key would look like: for each tt where tt.f1 = <token> and tt.f2 = <token>, generated by a for each tt where tt.f1 = " + a + " and tt.f2 = " + b at runtime with minimal overhead (like a semantic StringBuilder). This matches perfectly in the cache, so we can gather a JAST directly through L2. The runtime interpreter will eventually plug in the literals. The literals should be indeed parsed, but they are simple enough to be parsed trivially using a regex - otherwise they are considered risky.

While the "minimal parser" you are suggesting is more general as it will work with arbitrary strings, most probably it will be slower because it has to recover the information that was lost from conversion time (the concatenation / substitutions that were done to actually get that).

I will try to understand how this minimal parser can be designed without actually going into progress.g.

Alexandru Lungu wrote:

In my idea, the key would look like: for each tt where tt.f1 = <token> and tt.f2 = <token>, generated by a for each tt where tt.f1 = " + a + " and tt.f2 = " + b at runtime with minimal overhead (like a semantic StringBuilder). This matches perfectly in the cache, so we can gather a JAST directly through L2. The runtime interpreter will eventually plug in the literals. The literals should be indeed parsed, but they are simple enough to be parsed trivially using a regex - otherwise they are considered risky.

This does not work if the predicate is built in any other place than query-prepare. Applications build the predicate dynamically via various calls, and just reach a central point where query-prepare is executed with the character predicate argument. To me this looks like an edge case which covers only a few specific scenarios.

c = "for each tt where f1 = " + value. 
...
hq:query-prepare(c)

is also targeted by this optimization, considering that c won't eagerly do the concatenations. If you use certain 4GL constructs like substring, the semantics will be lost, but as long as the query is incrementally built using concatenations, this works. My idea is at run-time, so it will work even if c is passed as output parameter.

To me this looks like an edge case which covers only a few specific scenarios.

I can't deny that this is in fact covering some cases (not covering cases when query string comes from IO). I don't have a proper way of counting this, so I just sampled maybe 20 occurrences of query-parse in a customer application and most of them (maybe all except 2) were showcasing this pattern.

Some class has this method:

method public void queryOpen(pred as character)
   addBuffers().
   this-object:hquery:query-prepare(pred).
   this-object:hquery:queryOpen(pred).
end.

How do you know where pred has been built so that we use this special structure instead of concatenating? That's why I'm saying it will cover only specific cases/apps.

How do you know where pred has been built so that we use this special structure instead of concatenating? That's why I'm saying it will cover only specific cases/apps.

Well, my initial thought was that all concatenations would be lazy :) Any method of character would eventually do the concatenation if the actual string is needed (e.g. substring):

• a = "a" + "b". will make a store ["a", "b"] instead of "ab". TextOps.concat does:

new character(sb.toString(), caseSens, javaSpacifyNull)

so we already store the parts in sb and eagerly provide the string. We can replace that with an actual array and keep character.value as null. If we need it, we will compute it on spot.

• Now I think whether we can use this semantics in other places as well (e.g. subtring can be faster if we already have the parts as we can concatenate only some of them).
• Even entry can be improved this way, considering that there may be patterns where lists are computed dynamically.

I think the most part of the queries which causes the cache to fill are more simple, like:

buffer ht:find-first("where f1 = <val>");

This is also the case where a record is located based on its rowid, in which case the predicate looks like: "where rowid = 0x000036727"