4

我正在使用 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'

它立即运行。

有人知道这里发生了什么吗？

4

1 回答 1

6

您的正则表达式正在导致灾难性的回溯。

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

您可能会发现将对偶表达式更改为所有格量词（即++，而不是+）会阻止这种行为，因为++一旦字符被消耗，它们就会保持消耗。

顺便说一句，这个表达式

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

可以改写为：

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

因为：

  • 在一个字符类中（几乎）所有字符都失去了它们特殊的正则表达式含义
  • 第一个或最后一个破折号是 literakl 破折号（不是范围）
  • \w==[a-zA-Z0-9_]
于 2013-06-26T15:30:50.170 回答