FWD » Core Development » Database

This is deferred work from #8495 and refers to the replacement of expr1 begins expr2 with expr1 >= low_bound and expr1 < lowbound + 1 (pseudo-code used). There are some conditions that should be accounted for like expr1 should be indexed or stuff like that. In #8495, this optimization proved to drastically improve time, because it didn't use the slow begins UDF anymore. The customer applied the change manually to their legacy code, but the goal of this task is to improve FqlPreprocessor in FWD to automatically apply this optimization, when possible.

The conversion of a simple find first tt where tt.f1 begins tst yields:

 new FindQuery(tt, "upper(tt.f1) like ?", null, "tt.f1 asc", new Object[]
         {
            toUpperCase(convertToSQLBegins(tst))
         }, LockType.NONE).silentFirst();

The actual SQL has (upper(tt_1_1__im0_.f1) like ?) clause. At plan time, PG doesn't know this is a "prefix" and most probably it will plan it as a seq-scan. The parameter is indeed like "abc%", but PG finds out that too late. I wonder if we should rather inline the parameter if used for begins. I think it is always sub-optimal to favor parsing and planning time with a prepared statement at the cost of not knowing this is a "prefix" search.

• if the pattern is tt.f1 like ?, then we should inline
• if the pattern is tt.f1 line <expr> then better solutions are needed (maybe the one from #8495).

Alexandru Lungu wrote:

The conversion of a simple find first tt where tt.f1 begins tst yields:
[...]

The actual SQL has (upper(tt_1_1__im0_.f1) like ?) clause. At plan time, PG doesn't know this is a "prefix" and most probably it will plan it as a seq-scan. [...]

Don't we need this to be (upper(rtrim(tt_1_1__im0_.f1)) in order to give the database a chance to match an index? At least, for dialects which compose indices using upper(rtrim(...)).

I was a bit puzzled why isn't BEGIN implemented as an UDF?
I mean that was my first reaction, to see how udf.begins(a text, b text) (for PSQL) is implemented and whether it can be improved.
I am thinking also of constructs like

find first tt where tt.f1 begins tt.f2

find first tt where tst begins tt.f2

So I assume the UDF performance has already been explored. Right?

Don't we need this to be (upper(rtrim(tt_1_1__im0_.f1)) in order to give the database a chance to match an index? At least, for dialects which compose indices using upper(rtrim(...)).

You are right. However, I tested now some SQLs in PgAdmin4 and both upper(f1) like 'ABC%' and upper(rtrim(f1)) like 'ABC%' use the scan index. upper(rtrim(f1)) like 'ABC' uses the scan index and upper(f1) like 'ABC' doesn't. I agree however that this is a conversion bug.

Interestingly is also that find first tt where tt.f1 = 'ABC' converts to new FindQuery(pt, "upper(pt.f1) = 'ABC'", null, "pt.f1 asc").first(); without rtrim. Something is not right .... Is the rtrim added at run-time?

So I assume the UDF performance has already been explored. Right?

Not yet, but I doubt the planner will resolve the UDF to an index scan. I think the UDF are quite opaque to the planner and if it simply plans where udf.begins(tt.f1, "abc"), then it will most probably say that this is a seq scan as it doesn't know the range properties of begins in regard to the b-tree. It seems it doesn't even know to resolve "like 'abc%'" for that matter :)

Alexandru Lungu wrote:

Don't we need this to be (upper(rtrim(tt_1_1__im0_.f1)) in order to give the database a chance to match an index? At least, for dialects which compose indices using upper(rtrim(...)).

You are right. However, I tested now some SQLs in PgAdmin4 and both upper(f1) like 'ABC%' and upper(rtrim(f1)) like 'ABC%' use the scan index. upper(rtrim(f1)) like 'ABC' uses the scan index and upper(f1) like 'ABC' doesn't. I agree however that this is a conversion bug.

I assume from these mixed results that you are testing this on an analyzed table with a lot of data. The PostgreSQL query planner will sometimes decide a table scan is faster for a table with few rows, or if it decides the table statistics call for that plan. It also considers the various cost settings, which can be configured in postgresql.conf, though I've never changed these from the defaults myself. That being said, I don't know the details of this algorithm.

I don't know how other database implementations come up with their query plans, but I expect there are similar considerations in their algorithms.

All this is to say that we have to test with a typical (I know that's vague) data set to be able to safely draw conclusions about the query planner's decisions. By "typical", I suppose that means a lot of rows with a good distribution of values for the columns we are using.

Interestingly is also that find first tt where tt.f1 = 'ABC' converts to new FindQuery(pt, "upper(pt.f1) = 'ABC'", null, "pt.f1 asc").first(); without rtrim. Something is not right .... Is the rtrim added at run-time?

Yes, it is injected by FQLPreprocessor if needed.

BTW, I've considered the idea of doing the same with upper, instead of emitting it during conversion, depending on whether the target field is case-insensitive or not. But, we would have to be consistent and do the same with the opposite operand, which often is a substitution parameter, but can be a more complex expression. In the end, it would have meant doing a lot of the same work at runtime we currently do during conversion. What prevented me from going down this path was a combination of inertia and a concern for hurting runtime performance.

So I assume the UDF performance has already been explored. Right?

Not yet, but I doubt the planner will resolve the UDF to an index scan. I think the UDF are quite opaque to the planner and if it simply plans where udf.begins(tt.f1, "abc"), then it will most probably say that this is a seq scan as it doesn't know the range properties of begins in regard to the b-tree. It seems it doesn't even know to resolve "like 'abc%'" for that matter :)

Whether or not the UDF would be opaque I believe depends on the language used and the complexity of the UDF implementation.

A simple UDF implemented with pure SQL (as opposed to a procedure language) has better odds of being properly analyzed by a query planner, but it depends on a database's query planner implementation.

I agree that the odds of a good query plan generally are better if the query can be expressed with simple operands and operators, instead of a UDF. If we do use a UDF, this will require a lot more testing across dialects to ensure we are getting good query plans. If we can avoid a UDF and get the correct functional behavior with native operators, I think that is the way to go.

I assume from these mixed results that you are testing this on an analyzed table with a lot of data. The PostgreSQL query planner will sometimes decide a table scan is faster for a table with few rows, or if it decides the table statistics call for that plan. It also considers the various cost settings, which can be configured in postgresql.conf, though I've never changed these from the defaults myself. That being said, I don't know the details of this algorithm.

I was running on #9690 analyzed table with 3.5k rows. I can't say this is "a lot of data", but enough to separate a table scan from an index scan.
I can agree that planning can be different according to index selectivity and other statistics analyzed.

Yes, it is injected by FQLPreprocessor if needed.

Huh, dodged a bullet here. I really though we messed up with this. Just checked today morning and indeed, SQL queries end up having rtrim injected.

After a super-fast internet search, it seems like text datatype we choose for character legacy fields uses a default operator class that is limited in terms of planning with LIKE.

According to https://www.postgresql.org/docs/current/indexes-opclass.html

• text_pattern_ops is an operator class that can be set per-field in index and so it organizes the data to satisfy LIKE queries faster. I did such attempt and indeed, LIKE 'A%' is using that index with text_pattern_ops field.

However, there is the following note:

The difference from the default operator classes is that the values are compared strictly character by character rather than according to the locale-specific collation rules.

But at the same time:

If you do use the C locale, you do not need the xxx_pattern_ops operator classes, because an index with the default operator class is usable for pattern-matching queries in the C locale.

Finally, inside https://www.postgresql.org/docs/current/locale.html

The locale settings influence the following SQL features: 
*   [...]
*   The ability to use indexes with LIKE clauses
The drawback of using locales other than C or POSIX in PostgreSQL is its performance impact. It slows character handling and prevents ordinary indexes from being used by LIKE. For this reason use locales only if you actually need them.

This is getting messy. The database I was testing with used a custom fwd_basic locale flavor (installed using the FWD guide). With such, pattern-matching queries aren't using the indexes with default operator class.
I also just tested with an UTF-8 database and guess what: the default operator indeed supports pattern-matching queries!

So I would say that begins constructs that end up as field LIKE 'A%' are going to work fast by default on databases that have C locales (like UTF-8). The workaround exists as documented:

As a workaround to allow PostgreSQL to use indexes with LIKE clauses under a non-C locale, several custom operator classes exist. These allow the creation of an index that performs a strict character-by-character comparison, ignoring locale comparison rules. Refer to Section 11.10 for more information. Another approach is to create indexes using the C collation, as discussed in Section 23.2.

But it has the obvious limitations: the comparison will not be locale sensitive and extra indexes are required (as text_pattern_ops ones do not support =, <, <=, >, >=).

Therefore, I think this task #9305 still stands, but it should be toggled so that customers with DB that use C locale can use the native support for pattern matching.

From #10165:
For temp-table (H2 database), LIKE 'prefix%' does not use an index at the moment. I suspect it is because the BEGINS is turned into something like (upper(tt_1_1__im0_.word) like 'PREFIX%') and H2 does not know how to handle upper(...) in an index.

In H2 the condition is (UPPER(TT_1_1__IM0_.WORD) LIKE CAST('PREFIX%' AS VARCHAR_IGNORECASE))

This case will be fully fixed if we remove the upper(...) call and send only (tt_1_1__im0_.word like 'PREFIX%') as it is already a VARCHAR_IGNORECASE. This way the H2 planner will use this:

    /* PUBLIC.IDX__TT1_IDX_WORD__1: _MULTIPLEX = ?1
        AND WORD >= 'PREFIX'
        AND WORD < 'PREFIY'
     */

Alexandru,
You told yesterday and in #9305-10 that the default database configuration, with en_us.UTF8 collation, the LIKE operator should work. I think the actual configuration that you tested was actually a C or pg_c_utf8 collation, which LIKE operator works by default with B-TREE indexes.
The thing is that there is a configuration on a customer, with en_us.UTF8 and the LIKE operator is slow. en_US.UTF8 is a libc collation, which the LIKE operator will use the sequential scan.

There is pg_unicode_fast, which was introduced in PSQL 18, where the range and LIKE operator will use the index.

Teodor Gorghe wrote:

You told yesterday and in #9305-10 that the default database configuration, with en_us.UTF8 collation, the LIKE operator should work. I think the actual configuration that you tested was actually a C or pg_c_utf8 collation, which LIKE operator works by default with B-TREE indexes.
The thing is that there is a configuration on a customer, with en_us.UTF8 and the LIKE operator is slow. en_US.UTF8 is a libc collation, which the LIKE operator will use the sequential scan.

Indeed with en_us.UTF8 locale on LIKE does not use index scan. I also created a separate index with text_pattern_ops operator class, and this actually helped index usage. Since the duplicating number of indices is not a viable solution, I guess we are left with the #9305-1.

The range check follows the field collation or is byte-by-byte?
If it is after collation, there are some cases like foo-a, which goes before foo. Replacing LIKE with range check will skip foo-a. This is a specific en_US.UTF8 rule, but there are lots of rules in other languages in which the prefix is NOT an interval boundary.

Please do the tests requested in #9305-25 in 4GL and PG with LIKE / < and > / with BETWEEN. We need to take a decision that is functionally sound.

This is one difference between BEGINS and range check, on BASIC collation:

DEFINE TEMP-TABLE tt1 NO-UNDO
    FIELD f1 AS CHARACTER
    INDEX idx1 IS PRIMARY f1.

CREATE tt1. tt1.f1 = "ORD".
CREATE tt1. tt1.f1 = "ORD-123".

FOR EACH tt1 WHERE tt1.f1 BEGINS "ORD ":
    DISPLAY tt1.f1 "BEGINS".
END.

FOR EACH tt1 WHERE tt1.f1 >= "ORD " AND tt1.f1 < "ORE":
    DISPLAY tt1.f1 "RANGE CHECK".
END.

4GL output:

ORD      BEGINS
ORD      RANGE CHECK
ORD-123  RANGE CHECK

FWD output:

ORD      BEGINS
ORD-123  BEGINS
ORD      RANGE CHECK
ORD-123  RANGE CHECK

Something might be wrong at conversion, BEGINS is converted into upper(tt1.f1) like 'ORD%'.
Also, it seems that when using BEGINS, 4GL takes the shorter operand in length and then it appends with spaces to match the length with the other operand. This is why the "ORD" is matched with BEGINS "ORD ".
I will find some other cases where BEGINS and range check is different.

This is another example of RANGE CHECK vs BEGINS, using UTF-8 collation on 4GL:

DEFINE TEMP-TABLE tt1 NO-UNDO
    FIELD f1 AS CHARACTER
    INDEX idx1 IS PRIMARY f1.

CREATE tt1. tt1.f1 = "luna".
CREATE tt1. tt1.f1 = CHR(322, "UTF-8", "UTF-32") + "una".
CREATE tt1. tt1.f1 = "macaw".

DISPLAY 
    "Session Collation: " SESSION:CPCOLL FORMAT "x(20)" SKIP(1)
    WITH FRAME fTop NO-BOX NO-LABELS WIDTH 60.

DISPLAY "--- WHERE f1 >= 'l' AND f1 < 'm' ---" FORMAT "x(40)" 
    WITH FRAME fRange NO-BOX NO-LABELS.

FOR EACH tt1 WHERE f1 >= "l" AND f1 < "m":
    DISPLAY tt1.f1 FORMAT "x(15)" WITH FRAME fBody1 DOWN NO-LABELS.
END.

DISPLAY "--- WHERE f1 BEGINS 'l' ---" FORMAT "x(40)" 
    WITH FRAME fBegins NO-BOX NO-LABELS.

FOR EACH tt1 WHERE f1 BEGINS "l":
    DISPLAY tt1.f1 FORMAT "x(15)" WITH FRAME fBody2 DOWN NO-LABELS.
END.

With UTF-8 basic collation:

RANGE CHECK: luna
BEGINS: luna

With UTF-8 ICU collation:

RANGE CHECK: luna, łuna
BEGINS: luna

Notes:
- if you want to execute this test on 4GL, you need to use the prowin. If you try it from Developer Studio, it will corrupt the łuna string.

I have also noticed that for Western characters, there is no difference between BASIC and ICU-UCA on RANGE CHECK/BEGINS.

I think this is due to the fact that long ago, there were no ICU-UCA implementation. Since some of Progress 4GL users are from Western Europe, they have implemented some sort of support for western characters like ß in the BASIC collation.

I have also tested the difference between LIKE and RANGE CHECK on PSQL.

When the libc collation provider is being used, there is no difference between LIKE and RANGE CHECK.

When the collation provider ICU is used, there are some differences, but it depends on the ICU rules.
I have tested with Polish rules and I see that the LIKE operator displays luna, but the range check displays both luna and łuna.
The surprise for me is that the English United States ICU rules displays the same results as when using the Polish ones.