A Brief Discussion on How Halo Database Adapts to DB2 Syntax Issues

If a database is based on PostgreSQL development, to adapt to various other types of databases (such as DB2, Oracle, etc.), we will inevitably encounter lexical and syntactic issues. These include: missing adapted tokens, additions, deletions, and modifications of syntactic rules, adjustments to regular expressions for scanning identifiers, and various shift-reduce or reduce-reduce conflicts. Many people feel at a loss when facing these problems and do not know where to start.

Next, I will explain using a typical syntax issue encountered when the HALO database adapts to DB2: In DB2, the ORDER keyword can legally be used as a table name or column name. For example, the following SQL:

CREATE TABLE order ( id int,  order VARCHAR(32));
INSERT INTO order VALUES(1, 'JACK') ,(2,'LEO');
SELECT id, order FROM order;

Executes successfully in native DB2, outputting the following:

(instance:DB2INST1, database:):CREATE TABLE order ( id int,  order VARCHAR(32));@
DB20000I  The SQL command completed successfully.
(instance:DB2INST1, database:):INSERT INTO order VALUES(1, 'JACK') ,(2,'LEO');@
DB20000I  The SQL command completed successfully.
(instance:DB2INST1, database:):SELECT id, order FROM order;@
ID          ORDER                           
----------- --------------------------------
          1 JACK                            
          2 LEO                             
  2 record(s) selected.

However, executing it in PostgreSQL (or HALO) results in an error:

ERROR:  syntax error at or near "order" at character 14

This is because ORDER is a reserved keyword (RESERVED_KEYWORD) in PostgreSQL, which can only be used in specific contexts (such as the ORDER BY clause) and cannot be directly used as a regular identifier.

An intuitive solution is to use double quotes to escape in the SQL:

CREATE TABLE "order" ( id INT,  "order" VARCHAR(32));
INSERT INTO "order" VALUES(1, 'JACK') ,(2,'LEO');
SELECT id, "order" FROM "order";

However, this method has obvious drawbacks:

1. It only supports lowercase "order" and cannot be compatible with mixed case or all uppercase writing;

2. If the SQL contains ORDER BY, string replacement may incorrectly modify the keyword;

3. If the string constant contains 'order', it will be incorrectly replaced;

4. It requires multiple traversals of the SQL string, affecting execution efficiency;

5. Code readability is poor, making maintenance difficult;

6. As the context becomes complex, patch-style modifications will lead to bloated logic, high coupling, and a sharp increase in maintenance costs.

Therefore, a better solution is to resolve this issue within the query analysis module. According to the query processing flow, the earlier the processing (such as the lexical/syntactic stage), the lower the system coupling and the better the scalability.

Query Processing Flow Architecture

After the backend process receives the SQL command, it first enters the query analysis module for lexical, syntactic, and semantic analysis. Simple DDL is handled by the functional module; complex SELECT/DML constructs a query tree → query rewrite → path generation (considering access methods, join order, etc.) → plan generation → execution.

The brief description of each module is as follows:

Query Analysis Flow Framework

Query analysis is the first step of query compilation, including lexical analysis, syntactic analysis, and semantic analysis. Among them, lexical and syntactic analysis are implemented by Flex (Lex) and Bison (Yacc) tools. The SQL string input by the user is analyzed to generate a raw parse tree, and then the query tree is obtained through semantic analysis.

The entry function is exec_simple_query → pg_parse_query → raw_parser, which calls scanner and parser to generate the analysis tree list.

The core files related to PostgreSQL lexical and syntactic analysis include:

[1] kwlist.h: Declaration of the keyword list

For example:

PG_KEYWORD("order", ORDER, RESERVED_KEYWORD, AS_LABEL)

[2] kwlookup.cpp: Implementation of the ScanKeywordLookup function, which uses binary search to determine if the input is a keyword;

[3] scanup.c: Provides lexical auxiliary functions, such as downcase_truncate_identifier, scanner_isspace, etc.;

[4] scan.l: Flex lexical rule file, compiled to generate scan.c;

[5] gram.y: Bison syntax rule file, compiled to generate gram.c;

[6] check_keywords.pl: Verifies the consistency of keywords between gram.y and kwlist.h;

[7] parser.c: Provides the raw_parser entry function and the base_yylex lexical filtering logic.

The main flow of raw_parser: Initialize scanner and parser, call base_yyparse for parsing.

Brief Description of Lexical (Flex) and Syntactic (Bison) Working Principles

• Flex: Compiles the regular expression rules in the .l file into C code to identify tokens such as reserved words, identifiers, and operators;

• Bison: Generates a syntactic analyzer based on LALR(1) grammar, using a bottom-up shift-reduce strategy, and executes semantic actions by calling yylex to obtain tokens.

Solving Syntax Problems through Lexical and Syntactic Analysis

Adapting to DB2 usually requires modifying gram.y and kwlist.h. For example, adding the DB2 keyword MICROSECOND:

1. Insert in kwlist.h in ASCII order (to avoid conflicts):

PG_KEYWORD("microsecond", MICROSECOND_P, UNRESERVED_KEYWORD, AS_LABEL)

2. In gram.y:

%token <keyword> ... MICROSECOND_P ...

unreserved_keyword:
        ABORT_P
      | ABSOLUTE_P
      ...
      | MICROSECOND_P

%type <list> interval_microsecond

interval_microsecond:
      MICROSECOND_P
        { $ = list_make1(makeIntConst(INTERVAL_MASK(SECOND), @1)); };

For modifying lexical rules (such as DB2 supporting identifiers containing '#'):

SELECT * FROM USER#;

Need to modify scan.l:

ident_start    [A-Za-z\200-\377_]
ident_cont     [A-Za-z\200-\377_0-9\$\#]   /* Add # symbol */

Returning to the ORDER keyword problem: If simply changing it to UNRESERVED_KEYWORD, it will cause a large number of shift-reduce conflicts in the ORDER BY clause:

gram.y: error: shift/reduce conflicts: 18 found, 0 expected
gram.y: error: reduce/reduce conflicts: 5 found, 0 expected

Solution: Introduce a 'pseudo token' mechanism. A pseudo token is only declared in gram.y, has no actual keyword value, is not restricted by keyword classification, and is only used as a syntax placeholder.

Declare in gram.y:

%token ORDER_Q

The key is to use the base_yylex function in parser.c to implement the lookahead (look ahead one token) logic: When the current token is ORDER, pre-read the next token; if it is not BY, replace it with ORDER_Q, otherwise keep ORDER.

Modify base_yylex as follows:

base_yylex(YYSTYPE *lvalp, YYLTYPE *llocp, core_yyscan_t yyscanner)
{
  base_yy_extra_type *yyextra = base_yyget_extra(yyscanner);
  int cur_token, next_token, cur_token_length;
  YYLTYPE cur_yylloc;

  /* Get current token */
  if (yyextra->have_lookahead) {
    // ... Take from lookahead cache
  } else {
    cur_token = base_core_yylex(&(lvalp->core_yystype), llocp, yyscanner);
  }

  /* Determine if lookahead is needed */
  switch (cur_token) {
    case ORDER: cur_token_length = 5; break;
    default: return cur_token;
  }

  /* Save current position, pre-read next token */
  cur_yylloc = *llocp;
  next_token = base_core_yylex(&(yyextra->lookahead_yylval), llocp, yyscanner);
  yyextra->lookahead_token = next_token;
  yyextra->lookahead_yylloc = *llocp;
  *llocp = cur_yylloc;

  /* Restore current token string end */
  yyextra->lookahead_end = yyextra->core_yy_extra.scanbuf + (*llocp).endpos;
  yyextra->lookahead_hold_char = *(yyextra->lookahead_end);
  *(yyextra->lookahead_end) = '\0';
  yyextra->have_lookahead = true;

  /* Decide whether to replace based on lookahead */
  switch (cur_token) {
    case ORDER:
      if (next_token != BY)
        cur_token = ORDER_Q;
      break;
    // Other similar processing (e.g., NOT + BETWEEN → NOT_LA)
  }

  return cur_token;
}

Finally, add the syntax rule for ORDER_Q in gram.y, allowing it to be used as a column name or table name and return the string "order" (case insensitive):

/* Column identifier --- names that can be column, table, etc names. */
ColId:
      IDENT                  { $ = $1; }
    | unreserved_keyword     { $ = pstrdup($1); }
    | col_name_keyword       { $ = pstrdup($1); }
    | ORDER_Q                { $ = pstrdup("order"); }
    ;

After compiling and restarting, the test command executes successfully, with results consistent with DB2:

CREATE TABLE order (id int,  order VARCHAR(32));
INSERT INTO order VALUES(1, 'JACK'), (2,'LEO');
halodb2=# SELECT id, ORDER FROM ORDER;
 id | order 
----+-------
  1 | jack
  2 | LEO
(2 rows)

Summary: When adapting to multi-database dialects, customization at the lexical and syntactic layer is inevitable. The third technique mentioned above (pseudo token + lookahead) is very practical. For example, DB2 supports function-style type conversion like int(12.32), which is not natively supported in PostgreSQL; directly modifying keyword declarations often causes shift-reduce conflicts. At this time, lookahead can similarly be used to distinguish contexts (such as char(Iconst) vs char(func_arg_list_opt)), thus perfectly solving the conflict.

Thinking question: How to use this method to solve the shift-reduce conflict between char(Iconst) (type declaration) and char(func_arg_list_opt) (function call) in DB2?