正则表达式挂起在Oracle 11g中

Question

我正在使用Oracle 11g.以下语句大约需要3秒钟才能执行:

select  case when regexp_like(
    'blahblahblahblah.blah@blah-blah.blah.gov.uk', 
    '^[\-a-zA-Z0-9_''^&\+\?\:]+(\.?[\-a-zA-Z0-9_''^&\+\?\:]+)*@([a-zA-Z0-9]+\.)+[a-zA-Z]{2,3}$') 
    then 'true' else 'false' end

在电子邮件地址中添加另一个字符:

'blahblahblahblah.blahx@blah-blah.blah.gov.uk'

需要6秒.另一个角色12,然后是24,48,依此类推.所以:

'blahblahblahblah.blahxxxxx@blah-blah.blah.gov.uk'

运行大约需要96秒.

但是,删除连字符:

'blahblahblahblah.blahxxxxx@blahblah.blah.gov.uk'

它会立即运行.

谁知道这里发生了什么？

Answer 1

你的正则表达式造成了灾难性的回溯.

简单地说,你的正则表达式有条款可以既捕获输入的相同部分,但没有这样做.正则表达式引擎必须在失败之前尝试所有组合,并且由于创建了匹配树,每个额外字符使得匹配的方式数量加倍.创建和遍历此树会导致几何指数执行时间与2 ^ n成比例 - 您将看到它.

您可能会发现改变你的双重表达的占有欲量词(即++不是+)停止这种行为,因为++一旦字符被消耗掉,它们保持消耗.

顺便提一句,这个表达方式

[\-a-zA-z0-9_''^&\+\?\:]

可以改写为:

[-\w''^&+?:]

因为:

• 在一个角色类里面(几乎)所有角色都失去了特殊的正则表达式意义
• 破折号第一个或最后一个是一个文字破折号(不是一个范围)
• \w == [a-zA-Z0-9_]