正则表达式在 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

您的正则表达式导致 catastrophic backtracking .

简而言之，您的正则表达式具有可以捕获输入的同一部分的术语，但未能这样做。正则表达式引擎必须在失败之前尝试所有组合，并且由于创建了匹配树，每个额外的字符都会使匹配的方式数量增加一倍。创建和遍历这棵树会导致与 2^n 成正比的几何指数执行时间 - 您正在看到。

您可能会发现将双重表达式更改为所有格量词(即 ++ 而不是 + )会阻止这种行为，因为使用 ++一旦角色被消耗，他们就会被消耗。

顺便说一句，这个表达

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

可以改写为:

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

因为:

在字符类中(几乎)所有字符都失去了它们特殊的正则表达式含义

第一个或最后一个破折号是一个 literakl 破折号(不是范围)

\w == [a-zA-Z0-9_]