5 Linguistic Sorting and String Searching

Monolingual Linguistic Sorts

Oracle Database compares character strings in two steps for monolingual sorts. The first step compares the major value of the entire string from a table of major values. Usually, letters with the same appearance have the same major value. The second step compares the minor value from a table of minor values. The major and minor values are defined by Oracle Database. Oracle Database defines letters with diacritic and case differences as having the same major value but different minor values.

Each major table entry contains the Unicode code point and major value for a character. The Unicode code point is a 16-bit binary value that represents a character.

Table 5-1 illustrates sample values for sorting a, A, ä, Ä, and b.

Multilingual Linguistic Sorts

Oracle Database provides multilingual linguistic sorts so that you can sort data in more than one language in one sort. This is useful for regions or languages that have complex sorting rules and for multilingual databases. As of Oracle Database 11g, Oracle Database supports all of the sort orders defined by previous releases.

For Asian language data or multilingual data, Oracle Database provides a sorting mechanism based on the ISO 14651 standard and the Unicode 5.0 standard. Chinese characters are ordered by the number of strokes, PinYin, or radicals.

In addition, multilingual sorts can handle canonical equivalence and supplementary characters. Canonical equivalence is a basic equivalence between characters or sequences of characters. For example, ç is equivalent to the combination of c and ,. Supplementary characters are user-defined characters or predefined characters in Unicode that require two code points within a specific code range. You can define up to 1.1 million code points in one multilingual sort.

For example, Oracle Database supports a monolingual French sort (FRENCH), but you can specify a multilingual French sort (FRENCH_M). _M represents the ISO 14651 standard for multilingual sorting. The sorting order is based on the GENERIC_M sorting order and can sort diacritical marks from right to left. Oracle recommends using a multilingual linguistic sort if the tables contain multilingual data. If the tables contain only French, then a monolingual French sort may have better performance because it uses less memory. It uses less memory because fewer characters are defined in a monolingual French sort than in a multilingual French sort. There is a tradeoff between the scope and the performance of a sort.

Multilingual Sorting Levels

Oracle Database evaluates multilingual sorts at three levels of precision:

• Primary Level Sorts

• Secondary Level Sorts

• Tertiary Level Sorts

Bat
bat
BAT
BET
Bet
bet

resume
résumé
Résumé
Resumes
resumes
résumés

resume
Resume
résumé
Résumé
resumes
Resumes
résumés
Résumés

Base Letters

Base letters are defined in a base letter table, which maps each letter to its base letter. For example, a, A, ä, and Ä all map to a, which is the base letter. This concept is particularly relevant for working with Oracle Text.

Ignorable Characters

Some characters can be ignored in a linguistic sort. These characters are called ignorable characters. There are two kinds of ignorable characters: diacritics and punctuation.

Examples of ignorable diacritics are:

• ^, so that rôle is treated the same as role

• The umlaut, so that naïve is treated the same as naive

An example of an ignorable punctuation character is the dash character -. If it is ignored, then multi-lingual can be treated that same as multilingual and e-mail can be treated the same as email.

Contracting Characters

Sorting elements usually consist of a single character, but in some locales, two or more characters in a character string must be considered as a single sorting element during sorting. For example, in traditional Spanish, the string ch is composed of two characters. These characters are called contracting characters in multilingual linguistic sorting and special combination letters in monolingual linguistic sorting.

Do not confuse a composed character with a contracting character. A composed character like á can be decomposed into a and ', each with their own encoding. The difference between a composed character and a contracting character is that a composed character can be displayed as a single character on a terminal, while a contracting character is used only for sorting, and its component characters must be rendered separately.

Expanding Characters

In some locales, certain characters must be sorted as if they were character strings. An example is the German character ß (sharp s). It is sorted exactly the same as the string SS. Another example is that ö sorts as if it were oe, after od and before of. These characters are known as expanding characters in multilingual linguistic sorting and special letters in monolingual linguistic sorting. Just as with contracting characters, the replacement string for an expanding character is meaningful only for sorting.

Context-Sensitive Characters

In Japanese, a prolonged sound mark that resembles an em dash — represents a length mark that lengthens the vowel of the preceding character. The sort order depends on the vowel that precedes the length mark. This is called context-sensitive sorting. For example, after the character ka, the — length mark indicates a long a and is treated the same as a, while after the character ki, the — length mark indicates a long i and is treated the same as i. Transliterating this to Latin characters, a sort might look like this:

kaa   
ka—   -- kaa and ka— are the same
kai   -- kai follows ka- because i is after a
kia   -- kia follows kai because i is after a
kii   -- kii follows kia because i is after a
ki—   -- kii and ki— are the same

Canonical Equivalence

Canonical equivalence is an attribute of a multilingual sort and describes how equivalent code point sequences are sorted. If canonical equivalence is applied in a particular linguistic sort, then canonically equivalent strings are treated as equal.

One Unicode code point can be equivalent to a sequence of base letter code points plus diacritic code points. This is called the Unicode canonical equivalence. For example, ä equals its base letter a and an umlaut. A linguistic flag, CANONICAL_EQUIVALENCE = TRUE, indicates that all canonical equivalence rules defined in Unicode need to be applied in a specific linguistic sort. Oracle Database-defined linguistic sorts include the appropriate setting for the canonical equivalence flag. You can set the flag to FALSE to speed up the comparison and ordering functions if all the data is in its composed form.

For example, consider the following strings:

• äa (a umlaut followed by a)

• a¨b (a followed by umlaut followed by b)

• äc (a umlaut followed by c)

If CANONICAL_EQUIVALENCE=FALSE, then the sort order of the strings is:

a¨b
äa
äc

This occurs because a comes before ä if canonical equivalence is not applied.

If CANONICAL_EQUIVALENCE=TRUE, then the sort order of the strings is:

äa
a¨b
äc

This occurs because ä and a¨ are treated as canonically equivalent.

You can use Oracle Locale Builder to view the setting of the canonical equivalence flag in existing multilingual sorts. When you create a customized multilingual sort with Oracle Locale Builder, you can set the canonical equivalence flag as desired.

Reverse Secondary Sorting

In French, sorting strings of characters with diacritics first compares base letters from left to right, but compares characters with diacritics from right to left. For example, by default, a character with a diacritic is placed after its unmarked variant. Thus Èdit comes before Edít in a French sort. They are equal on the primary level, and the secondary order is determined by examining characters with diacritics from right to left. Individual locales can request that the characters with diacritics be sorted with the right-to-left rule. Set the REVERSE_SECONDARY linguistic flag to TRUE to enable reverse secondary sorting.

Character Rearrangement for Thai and Laotian Characters

In Thai and Lao, some characters must first change places with the following character before sorting. Normally, these types of characters are symbols representing vowel sounds, and the next character is a consonant. Consonants and vowels must change places before sorting. Set the SWAP_WITH_NEXT linguistic flag for all characters that must change places before sorting.

Special Letters

Special letters is a term used in monolingual sorts. They are called expanding characters in multilingual sorts.

Special Combination Letters

Special combination letters is the term used in monolingual sorts. They are called contracting letters in multilingual sorts.

Special Uppercase Letters

One lowercase letter may map to multiple uppercase letters. For example, in traditional German, the uppercase letters for ß are SS.

These case conversions are handled by the NLS_UPPER, NLS_LOWER, and NLS_INITCAP SQL functions, according to the conventions established by the linguistic sort sequence. The UPPER, LOWER, and INITCAP SQL functions cannot handle these special characters, because their casing operation is based on binary mapping defined for the underlying character set, which is not linguistic sensitive.

The NLS_UPPER SQL function returns all uppercase characters from the same character set as the lowercase string. The following example shows the result of the NLS_UPPER function when NLS_SORT is set to XGERMAN:

SELECT NLS_UPPER ('große') "Uppercase" FROM DUAL;

Upper
-----
GROSSE

Special Lowercase Letters

Oracle Database supports special lowercase letters. One uppercase letter may map to multiple lowercase letters. An example is the Turkish uppercase I becoming a small, dotless i.

Examples of Case-Insensitive and Accent-Insensitive Sorts

The following examples show:

• A sort that uses information about base letters, diacritics, punctuation, and case

• A case-insensitive sort

• An accent-insensitive sort

blackbird
black bird
black-bird
Blackbird
Black-bird
blackbîrd
bläckbird

black bird
black-bird
Black-bird
blackbird
Blackbird
blackbîrd
bläckbird

blackbird
bläckbird
blackbîrd
Blackbird
BlackBird
Black-bird
Black bird

Specifying a Case-Insensitive or Accent-Insensitive Sort

Use the NLS_SORT session parameter to specify a case-insensitive or accent-insensitive sort:

• Append _CI to an Oracle Database sort name for a case-insensitive sort.

• Append _AI to an Oracle Database sort name for an accent-insensitive and case-insensitive sort.

For example, you can set NLS_SORT to the following types of values:

FRENCH_M_AI
XGERMAN_CI

Binary sorts can also be case-insensitive or accent-insensitive. When you specify BINARY_CI as a value for NLS_SORT, it designates a sort that is accent-sensitive and case-insensitive. BINARY_AI designates an accent-insensitive and case-insensitive binary sort. You may want to use a binary sort if the binary sort order of the character set is appropriate for the character set you are using.

For example, with the NLS_LANG environment variable set to AMERICAN_AMERICA.WE8ISO8859P1, create a table called test2 and populate it as follows:

SQL> CREATE TABLE test2 (letter VARCHAR2(10));
SQL> INSERT INTO test2 VALUES('ä');
SQL> INSERT INTO test2 VALUES('a');
SQL> INSERT INTO test2 VALUES('A');
SQL> INSERT INTO test2 VALUES('Z');
SQL> SELECT * FROM test2;

LETTER
-----------
ä 
a
A
Z

The default value of NLS_SORT is BINARY. Use the following statement to do a binary sort of the characters in table test2:

SELECT * FROM test2 ORDER BY letter;

To change the value of NLS_SORT, enter a statement similar to the following:

ALTER SESSION SET NLS_SORT=BINARY_CI;

The following table shows the sort orders that result from setting NLS_SORT to BINARY, BINARY_CI, and BINARY_AI.

When NLS_SORT=BINARY, uppercase letters come before lowercase letters. Letters with diacritics appear last.

When the sort considers diacritics but ignores case (BINARY_CI), the letters with diacritics appear last.

When both case and diacritics are ignored (BINARY_AI), ä is sorted with the other characters whose base letter is a. All the characters whose base letter is a occur before z.

You can use binary sorts for better performance when the character set is US7ASCII or another character set that has the same sort order as the binary sorts.

The following table shows the sort orders that result from German sorts for the table.

A German sort places lowercase letters before uppercase letters, and ä occurs before Z. When the sort ignores both case and diacritics (GERMAN_AI), ä appears with the other characters whose base letter is a.

Linguistic Sort Examples

The examples in this section demonstrate a binary sort, a monolingual sort, and a multilingual sort. To prepare for the examples, create and populate a table called test3. Enter the following statements:

SQL> CREATE TABLE test3 (name VARCHAR2(20));
SQL> INSERT INTO test3 VALUES('Diet');
SQL> INSERT INTO test3 VALUES('À voir');
SQL> INSERT INTO test3 VALUES('Freizeit');

SQL> SELECT * FROM test3 ORDER BY name;

Diet
Freizeit
À voir

SQL> SELECT * FROM test3 ORDER BY NLSSORT(name, 'NLS_SORT=german');

À voir
Diet
Freizeit

Figure 5-1 Character String

Description of "Figure 5-1 Character String"

Perform a monolingual German sort by using the NLSSORT function with the NLS_SORT parameter set to german.

SQL> SELECT * FROM test2 ORDER BY NLSSORT(name, 'NLS_SORT=german');

The output from the German sort shows the new character string last in the list of entries because the characters are not recognized in a German sort.

Perform a multilingual sort by entering the following statement:

SQL> SELECT * FROM test2 ORDER BY NLSSORT(name, 'NLS_SORT=generic_m');

The output shows the new character string after Diet, following ISO sorting rules.

Collation Keys

When the comparison conditions =, !=, >, <, >=, <=, BETWEEN, NOT BETWEEN, IN, NOT IN, the query clauses ORDER BY or GROUP BY, or the aggregate function COUNT(DISTINCT) are evaluated according to linguistic rules specified by NLS_SORT, the compared argument values are first transformed to binary values called collation keys and then compared byte by byte, like RAW values. If a monolingual sort is applied, collation keys contain major values for characters of the source value concatenated with minor values for those characters. If a multilingual sort is applied, collation keys contain concatenated primary, secondary, and tertiary values.

The collation keys are the same values that are returned by the NLSSORT function. That is, activating the linguistic behavior of these SQL operations is equivalent to including their arguments into calls to the NLSSORT function.

Restricted Precision of Linguistic Comparison

As collation keys are values of the data type RAW and the maximum length of a RAW value is 2000 bytes, the maximum length of a collation key is restricted to 2000 bytes. If a full source character value yields a collation key longer than 2000 bytes, the collation key generated for this value is calculated for a maximum prefix (initial substring) of the value for which the calculated result does not exceed 2000 bytes. For monolingual sorts, the prefix length is typically 1000 characters. For multilingual sorts, the prefix is typically 500 characters. The exact length may be higher or lower and depends on the particular collation and the particular characters contained in the source value.

The implication of this method of collation key generation is that SQL operations using the collation keys to implement the linguistic behavior will return results that may ignore trailing parts of long arguments. For example, two character values starting with the same 1000 characters but differing somewhere after the 1000th character will be grouped together by the GROUP BY clause.

Linguistic Comparison Examples

The following examples illustrate behavior with different NLS_COMP settings.

SQL> ALTER SESSION SET NLS_COMP=BINARY;
SQL> ALTER SESSION SET NLS_SORT=BINARY;
SQL> SELECT ename FROM emp1;

ENAME
----------------------
Mc Calla
MCAfee
McCoye
Mccathye
McCafeé

5 rows selected

SQL> SELECT ename FROM emp1 WHERE ename LIKE 'McC%e';

ENAME
----------------------
McCoye

1 row selected

SQL> ALTER SESSION SET NLS_COMP=LINGUISTIC;
SQL> ALTER SESSION SET NLS_SORT=BINARY_CI;
SQL> SELECT ename FROM emp1 WHERE ename LIKE 'McC%e';

ENAME
----------------------
McCoye
Mccathye

2 rows selected

SQL> ALTER SESSION SET NLS_COMP=LINGUISTIC;
SQL> ALTER SESSION SET NLS_SORT=BINARY_AI;
SQL> SELECT ename FROM emp1 WHERE ename LIKE 'McC%e';

ENAME
----------------------
McCoye
Mccathye
McCafeé

3 rows selected

SQL> ALTER SESSION SET NLS_COMP=BINARY;
SQL> ALTER SESSION SET NLS_SORT=BINARY;
SQL> SELECT DISTINCT ename FROM emp2;

ENAME
----------------------
McAfee
Mcafee
McCoy

3 rows selected

However, with a case-insensitive setting, McAfee and Mcafee are the same:

SQL> ALTER SESSION SET NLS_COMP=LINGUISTIC;
SQL> ALTER SESSION SET NLS_SORT=BINARY_CI;
SQL> SELECT DISTINCT ename FROM emp2;

ENAME
----------------------
McAfee
McCoy

2 rows selected

In this example, either McAfee or Mcafee could be returned from the DISTINCT operation. There is no guarantee exactly which one will be picked.

SQL> ALTER SESSION SET NLS_COMP=BINARY;
SQL> ALTER SESSION SET NLS_SORT=BINARY;
SQL> SELECT ename FROM emp3 WHERE ename LIKE 'C%';

ENAME
----------------------
Cindy
Chad
Clara

3 rows selected

In a database session with the linguistic rule set to traditional Spanish, XSPANISH, ch is treated as one character. So the letter c in Chad is different than the letter C in Cindy and Clara:

SQL> ALTER SESSION SET NLS_COMP=LINGUISTIC;
SQL> ALTER SESSION SET NLS_SORT=XSPANISH;
SQL> SELECT ename FROM emp3 WHERE ename LIKE 'C%';

ENAME
----------------------
Cindy
Clara

2 rows selected

And the letter c in combination ch is different than the c standing by itself:

SQL> SELECT REPLACE ('character', 'c', 't') "Changes" FROM DUAL;

Changes
---------------------
charatter

Supported SQL Operations and Functions for Linguistic Indexes

Linguistic index support is available for the following collation-sensitive SQL operations and SQL functions:

• Comparison conditions =, !=, >, <, >=, <=

• Range conditions BETWEEN | NOT BETWEEN

• IN | NOT IN

• ORDER BY

• GROUP BY

• LIKE (LIKE, LIKE2, LIKE4, LIKEC)

• DISTINCT

• UNIQUE

• UNION

• INTERSECT

• MINUS

The SQL functions in the following list cannot utilize linguistic index:

• INSTR (INSTR, INSTRB, INSTR2, INSTR4, INSTRC)

• MAX

• MIN

• REPLACE

• TRIM

• LTRIM

• RTRIM

• TRANSLATE

Linguistic Indexes for Multiple Languages

There are three ways to build linguistic indexes for data in multiple languages:

• Build a linguistic index for each language that the application supports. This approach offers simplicity but requires more disk space. For each index, the rows in the language other than the one on which the index is built are collated together at the end of the sequence. The following example builds linguistic indexes for French and German.

  CREATE INDEX french_index ON employees (NLSSORT(employee_id, 'NLS_SORT=FRENCH'));
  CREATE INDEX german_index ON employees (NLSSORT(employee_id, 'NLS_SORT=GERMAN'));
  

  Oracle Database chooses the index based on the NLS_SORT session parameter or the arguments of the NLSSORT function specified in the ORDER BY clause. For example, if the NLS_SORT session parameter is set to FRENCH, then Oracle Database uses french_index. When it is set to GERMAN, Oracle Database uses german_index.

• Build a single linguistic index for all languages. This requires a language column (LANG_COL in "Example: Setting Up a French Linguistic Index") to be used as a parameter of the NLSSORT function. The language column contains NLS_LANGUAGE values for the data in the column on which the index is built. The following example builds a single linguistic index for multiple languages. With this index, the rows with the same values for NLS_LANGUAGE are sorted together.

  CREATE INDEX i ON t (NLSSORT(col, 'NLS_SORT=' || LANG_COL));
  

  Queries choose an index based on the argument of the NLSSORT function specified in the ORDER BY clause.

• Build a single linguistic index for all languages using one of the multilingual linguistic sorts such as GENERIC_M or FRENCH_M. These indexes sort characters according to the rules defined in ISO 14651. For example:

  CREATE INDEX i on t (NLSSORT(col, 'NLS_SORT=GENERIC_M');
  

  See Also:

  "Multilingual Linguistic Sorts" for more information about Unicode sorts

Requirements for Using Linguistic Indexes

The following are requirements for using linguistic indexes:

• Set NLS_SORT Appropriately

• Specify NOT NULL in a WHERE Clause If the Column Was Not Declared NOT NULL

This section also includes:

• Example: Setting Up a French Linguistic Index

WHERE NLSSORT(column_name) IS NOT NULL

ALTER SESSION SET NLS_SORT='FRENCH';
CREATE INDEX test_idx ON test4(NLSSORT(name, 'NLS_SORT=FRENCH'));
SELECT * FROM test4 ORDER BY col;
ALTER SESSION SET NLS_COMP=LINGUISTIC;
SELECT * FROM test4 WHERE name > 'Henri';

Character Range '[x-y]' in Regular Expressions

According to the POSIX standard, a range in a regular expression includes all collation elements between the start point and the end point of the range in the linguistic definition of the current locale. Therefore, ranges in regular expressions are meant to be linguistic ranges, not byte value ranges, because byte value ranges depend on the platform, and the end user should not be expected to know the ordering of the byte values of the characters. The semantics of the range expression must be independent of the character set. This implies that a range such as [a-d] includes all the letters between a and d plus all of those letters with diacritics, plus any special case collation element such as ch in Traditional Spanish that is sorted as one character.

Oracle Database interprets range expressions as specified by the NLS_SORT parameter to determine the collation elements covered by a given range. For example:

Expression:     [a-d]e
NLS_SORT:       BINARY
Does not match: cheremoya
NLS_SORT:       XSPANISH
Matches:        >>che<<remoya

Collation Element Delimiter '[. .]' in Regular Expressions

This construct is introduced by the POSIX standard to separate collating elements. A collating element is a unit of collation and is equal to one character in most cases. However, the collation sequence in some languages may define two or more characters as a collating element. The historical regular expression syntax does not allow the user to define ranges involving multicharacter collation elements. For example, there was no way to define a range from a to ch because ch was interpreted as two separate characters.

By using the collating element delimiter [. .], you can separate a multicharacter collation element from other elements. For example, the range from a to ch can be written as [a-[.ch.]]. It can also be used to separate single-character collating elements. If you use [. .] to enclose a multicharacter sequence that is not a defined collating element, then it is considered as a semantic error in the regular expression. For example, [.ab.] is considered invalid if ab is not a defined multicharacter collating element.

Character Class '[: :]' in Regular Expressions

In English regular expressions, the range expression can be used to indicate a character class. For example, [a-z] can be used to indicate any lowercase letter. However, in non-English regular expressions, this approach is not accurate unless a is the first lowercase letter and z is the last lowercase letter in the collation sequence of the language.

The POSIX standard introduces a new syntactical element to enable specifying explicit character classes in a portable way. The [: :] syntax denotes the set of characters belonging to a certain character class. The character class definition is based on the character set classification data.

Equivalence Class '[= =]' in Regular Expressions

Oracle Database also supports equivalence classes through the [= =] syntax as recommended by the POSIX standard. A base letter and all of the accented versions of the base constitute an equivalence class. For example, the equivalence class [=a=] matches ä as well as â. The current implementation does not support matching of Unicode composed and decomposed forms for performance reasons. For example, ä (a umlaut) does not match 'a followed by umlaut'.

Examples: Regular Expressions

The following examples show regular expression matches.

Expression: catalog(ue)?
NLS_SORT: GENERIC_M_CI
Matches: 

>>Catalog<<
>>catalogue<<
>>CATALOG<<

SQL> ALTER SESSION SET NLS_SORT='GENERIC_M_CI';
SQL> SELECT col FROM test WHERE REGEXP_LIKE(col,'catalog(ue)?');

Expression: catalog(ue)?
NLS_SORT: GENERIC_M_CI
Match option: 'c'
Matches:

>>catalogue<<

Does not match: 

Catalog
CATALOG

SQL> ALTER SESSION SET NLS_SORT='GENERIC_M_CI';
SQL> SELECT col FROM test WHERE REGEXP_LIKE(col,'catalog(ue)?','c');

Expression: [^-a-[.ch.]]+  /*with NLS_SORT set to xspanish*/
Matches: 

>>driver<<

Does not match:

cab

SQL> SELECT col FROM test WHERE REGEXP_LIKE(col,'[^-a-[.ch.]]+');

Expression: [[:lower:]]{6}
Database character set: WE8ISO8859P1
Matches:

>>maître<<
>>mòbile<<
>>pájaro<<
>>zurück<<

SQL> SELECT col FROM test WHERE REGEXP_LIKE(col,'[[:lower:]]{6}');

Expression: r[[=e=]]sum[[=e=]]
Matches:

>>resume<<
>>résumé<<
>>résume<<
>>resumé<<

SQL> SELECT col FROM test WHERE REGEXP_LIKE(col,'r[[=e=]]sum[[=e=]]');