数据加工DSL编译优化：搜索算子语义等价转换

2022-01-17 10:53:08

本次分享主要介绍面向数据加工DSL的一项编译优化：搜索算子语义等价转换。e_search()是灵活的语义丰富的搜索算子，通过简洁的DSL即可实现复杂的搜索需求。搜索过滤是日志处理的基本功能，在数据加工作业中搜索算子被极高频使用（数据加工共200+算子，搜索算子e_search()使用频度排名top 5）。搜索算子支持哪些语法？搜索算子语义等价转换是怎么实现的？有哪些实际价值？

搜索算子支持哪些语法？

# 全文
e_search("active error")     # 全文：两个子串是OR关系，进行搜索。
e_search('"active error"')   # 全文：一个子串搜索。

# 字段:字符串
e_search("status: active")         # 单词搜索。
e_search('author: "john smith"')   # 带空格子串搜索。
e_search('field: active error')   # 相当于field:active OR "error"。

# 完全匹配
e_search('author== "john smith"')  

# 通配符搜索，星号（*）匹配零个或多个字符，问号（?）匹配一个字符。
e_search("status: active*test")    # active*test中仅包含星号（*），可以不使用双引号（""）包裹。
e_search("status: active?good")    # active?good中仅包含问号（?），可以不使用双引号（""）包裹。
e_search("status== ac*tive?good")  # 完全匹配。

# 搜索值转义，星号（*）或问号（?）需要使用反斜线（\）转义。
e_search('status: "\*\?()[]:="')  # \*\?()[]:=中包含特殊字符，需要使用双引号（""）包裹，除了星号（*）、问号（?）和反斜线（\）需要转义外，其他不用转义。
e_search("status: active\*test")  # active\*test中仅包含星号（*），可以不使用双引号（""）包裹。
e_search("status: active\?test")  # active\?test中仅包含问号（?），可以不使用双引号（""）包裹。

# 字段名转义
e_search("\*\(1+1\)\?: abc")                  # 字段名不能用双引号（""）包裹，特殊字符用反斜线（\）转义。
e_search("__tag__\:__container_name__: abc")  # 用反斜线（\）转义。
e_search("中文字段: abc")                     # 直接写中文。

# 正则匹配
e_search('content~="正则表达式"')   # 正则匹配。

# 数字
e_search('count: [100, 200]')   # >=100 and <=200
e_search('count: [*, 200]')     # <=200
e_search('count: [200, *]')     # >=200
e_search('age >= 18')           # >= 18
e_search('age > 18')            # > 18

# 使用关系运算符
e_search("abc OR xyz")    # 关系运算符不区分大小写，OR和or效果一样。
e_search("abc and (xyz or zzz)")
e_search("abc and not (xyz and not zzz)")
e_search("abc && xyz")    # and
e_search("abc || xyz")    # or
e_search("abc || !xyz")   # or not

e_search使用说明：

https://help.aliyun.com/document_detail/125398.htm?spm=a2c4g.11186623.0.0.5cd145e6edi73h#title-k4j-izy-ojw

查询字符串语法：

https://help.aliyun.com/document_detail/129383.htm?spm=a2c4g.11186623.0.0.7cbc45e6c8xylM#concept-1597612

搜索算子语义等价转换是怎么实现的？

搜索算子语法支持较为丰富，原方案采用遍历AST（抽象语法树，Abstract Syntax Tree）的方式，根据当前的标识符类型执行对应操作。上述设计也就是常说的“解析执行”方案，由于每次都需要 “判断标识符类型”，执行效率较慢。“搜索算子语义等价转换”设计方案相当于在执行前提前分析AST，避免了重复“判断标识符类型”，直接搜索表达式对应操作，由此“编译执行”设计方案不仅功能上兼容了“解析执行”方案，而且执行效率较快。

搜索算子语义等价转换主要包含如下步骤：

词法语法分析

采用词法语法解析工具将数据加工作业的DSL解析并改写为语义一致且具有父子关系的AST。

AST准确表示了搜索算子的语义，并且，通过AST的节点层级关系表示了嵌套语义。

搜索算子e_search的Antlr4语法文件，如下：

/**
 * alibab sls etl dsl
 * author lanyan_wb
 * java -classpath antlr-4.7.2-complete.jar org.antlr.v4.Tool -Dlanguage=Cpp DSL.g4
*/

grammar DSL;

//
searchExpression
    :   logicalOrExpression
    ;

//
logicalOrExpression
    :   logicalAndExpression
    |   logicalOrExpression logicOr logicalAndExpression
    |   logicalOrExpression logicalAndExpression
    ;

logicOr
    :   '||'
    |   Or
    ;

//
logicalAndExpression
    :   logicalNotExpression
    |   logicalAndExpression logicAnd logicalNotExpression
    ;

logicAnd
    :   '&&'
    |   And
    ;

//
logicalNotExpression
    :   logicNot fieldSearchExpression
    |   fieldSearchExpression
    ;

logicNot
    :   '!'
    |   Not
    ;

//
fieldSearchExpression
    :   numberCompareExpression
    |   numberRangeCompareExpression
    |   singleFieldSearchExpression
    |   fullFieldSearchExpression
    ;


// field_name("field") + (COLON | EQ_FULL | EQ_REG | EQ)
singleFieldSearchExpression
    :   fieldIdentifier singleFieldSearchOperator primaryFieldSearchExpression
    ;

singleFieldSearchOperator
    :   COLON
    |   EQ_FULL
    |   EQ_REG
    |   EQ
    ;

fullFieldSearchExpression
    :   primaryFieldSearchExpression
    ;

primaryFieldSearchExpression
    :   wordExpression
    |   stringExpression
    |   LPAR searchExpression RPAR
    ;

// field_name("field") + (EG | EL | GT | LT | EQ) + number
numberCompareExpression
    :   fieldIdentifier numberCompareOpertor Number
    ;

numberCompareOpertor
    :   EG
    |   EL
    |   GT
    |   LT
    |   EQ
    ;


// field_name("field") + (COLON | EQ) + range_search
numberRangeCompareExpression
    :    fieldIdentifier numberRangeOperator LBRACK NumberRange RBRACK
    ;

numberRangeOperator
    :   COLON
    |   EQ
    ;


fieldIdentifier
    :   Or
    |   And
    |   Not
    |   To
    |   Number
    |   ValidWord
    ;

wordExpression
    :   Or
    |   And
    |   Not
    |   To
    |   Number
    |   ValidWord
    ;

stringExpression
    :   String
    ;

COLON: ':';
LBRACK: '[';
RBRACK: ']';
LBRACE: '{';
RBRACE: '}';
TILDE: '~';
CARAT: '^';

EG: '>=';
EL: '<=';
EQ_FULL: '==';
EQ_REG: '~=';
GT: '>';
LT: '<';
EQ: '=';

LPAR: '(';
RPAR: ')';

Or: [Oo][Rr];
And: [Aa][Nn][Dd];
Not: [Nn][Oo][Tt];
To: [Tt][Oo];

Number
    :   [+-]? [0-9]+ '.'? [0-9]* ([eE] [+-]? [0-9]+)?
    ;

NumberRange
    :   RangeNumber [ \t]* ',' [ \t]* RangeNumber
    ;

fragment
RangeNumber
    :   Number
    |   '*'
    ;

ValidWord
    :   ([\u0800-\u9fa5a-zA-Z0-9*?_+.,-] | '\\' ([\u0800-\u9fa5a-zA-Z0-9] | [+\-!(){}^"~*?:@#,] | '[' | ']' | '||' | '&&' ) )+
    ;

String
    :   '"' ('\\"' | ~["\n\r])* '"'
    ;

Whitespace
    :   [ \t]+ -> skip
    ;

高频场景语义转换

高频操作主要分为“全文搜索”、“否逻辑运算”、“与否逻辑运算”、“字段搜索”。其中，“全文搜索”为单目运算，“否逻辑运算”为二目运算，“与或逻辑运算”和“字段搜索”为三目运算。

判断当前处理的表达式是几目运算，并分别执行对应的操作：

如果为单目运算，则转换为“全文搜索”。

如果为二目运算，则转换为“否逻辑运算”。

如果为三目运算，则判断当前操作符是否为“And/Or”,如果是，则转换为“与或逻辑运算”，否则，判断当前操作符是否为“==/:/=/~=”,如果是，则转换为“字段搜索”。

其他情况，表示转换失败。

由于搜索算子e_search()支持嵌套语法，因此在执行上述操作时，“否逻辑运算”和“与或逻辑运算”需要执行上述转换以处理嵌套的子表达式。

有哪些实际价值？

搜索算子的语义等价转换均由后台编译器自动实现，用户无需参与。通过搜索算子的语义等价转换编译优化，“全文搜索”、“字段子串搜索”和“字段相等判断”会有5倍的性能提升，“字段正则匹配”会有2倍的性能提升。进而优化了事件吞吐率和实时性，有效降低了客户数据加工作业出现延时的概率。并且，减少了服务器使用数量，节省了运营成本。

注意：搜索算子语义等价转换只能解决一些高频优化操作，较优数据结构的转换后面会另起一篇文章详细说明。

本次分享承接“数据加工DSL编译优化：公共子表达式删除”，均隶属“数据加工性能优化”专栏。相关链接：

数据加工概述：https://help.aliyun.com/document_detail/125384.html

数据加工DSL简介：https://help.aliyun.com/document_detail/125439.html

数据加工DSL函数总览：https://help.aliyun.com/document_detail/159702.html

数据加工架构设计：https://topic.atatech.org/articles/208924

数据加工DSL编译优化：公共子表达式删除：https://ata.alibaba-inc.com/articles/214189