解析数字范围

Question

我试图找出生成WHERE查询的最有效方法.我之前问过另一个问题,这个问题很相似,但我会在这个问题上做到正确.

给定一个数字范围的集合,即1-1000,1500-1600创建一个mysql非常简单,其中条件选择这些值之间的记录.

即,你会这样做:

WHERE (lft BETWEEN 1 and 1000) OR (lft BETWEEN 1500-1600).但是,如果您想要合并NOT BETWEEN,该怎么办？

例如,如果您定义了几个规则,例如......

• 允许在1 - 1000之间
• 允许在1500 - 1600之间
• 允许在1250 - 1300之间
• 拒绝在25-50之间

如何合并这些规则以便有效地生成WHERE条件.我希望WHERE能够剖析它ALLOW BETWEEN 1 - 1000以便在其中创造一个空白.这样它就会成为1-24和51-1000.因为DENY规则是在第一个规则之后定义的,所以它会"覆盖"以前的规则.

另一个例子,说你有

• 允许在5 - 15之间
• DENY BETWEEN 10 - 50
• 允许45-60之间

然后我想生成一个允许我这样做的WHERE条件:

WHERE (lft BETWEEN 5 and 9) OR (lft BETWEEN 45 and 60).

备注(编辑)

• 此外,允许的最大范围是1 - 5600000.(这将是'地球')即.允许地球上的一切.
• 数字范围实际上是NESTED SET MODEL中的LEFT值.这些不是唯一键.你可以在我之前提到的这个问题中解读为什么我要这样做. /sf/ask/421438741/
• 关于我的数字范围的可能重要说明我可能不应该使用我所做的示例示例,但关于数字范围的性质的一个重要注意事项是,范围实际上应该总是完全消耗或被先前规则消耗.例如,我使用上面的例子,10-50允许,并拒绝45-60.这实际上不会发生在我的数据集中.实际上allow 10-50,然后,DENY必须完全被该范围消耗,即34-38.或者,完全消耗以前的规则.9-51.这是因为范围实际上代表嵌套集模型中的lft和rgt值,并且您不能像我提出的那样重叠.

在提出问题时我没想到提到这个问题,但在看到下面的工作示例代码后,我可以看到这个说明实际上非常重要.

(编辑示例mysql包含OR而不是AND,如下面的评论)

Answer 1

老实说,为什么要这么麻烦？只要您查询的密钥被编入索引,只需将多个查询放在那里:

WHERE (foo BETWEEN 1 AND 1000 
        OR foo BETWEEN 1500 AND 1600
        OR foo BETWEEN 1250 AND 1300
    ) AND (
        foo NOT BETWEEN 25 AND 50
    )

你可以通过构建一个解剖器来扼杀一点点效率,但我会怀疑它是否值得.所有WHERE子句项都不在索引之外,因此您不会阻止任何硬操作发生(这意味着您不会通过执行完全表扫描来停止).

因此,不要花时间构建一个系统来为您完成,只需实现一个简单的解决方案(OR将允许,并将ANDDenys结合在一起)并继续进行更重要的事情.然后,如果它后来成为一个问题,那么重新访问它.但我真的不认为这会成为一个太大的问题......

编辑好了,这是一个非常简单的算法.它使用字符串作为数据存储,因此对于较小的数字(低于100万)它是合理有效的:

class Dissector {
    protected $range = '';
    public function allow($low, $high) {
        $this->replaceWith($low, $high, '1');
    }
    public function deny($low, $high) {
        $this->replaceWith($low, $high, '0');
    }
    public function findRanges() {
        $matches = array();
        preg_match_all(
            '/(?<!1)1+(?!1)/', 
            $this->range, 
            $matches, 
            PREG_OFFSET_CAPTURE
        );
        return $this->decodeRanges($matches[0]);
    }
    public function generateSql($field) {
        $ranges = $this->findRanges();
        $where = array();
        foreach ($ranges as $range) {
            $where[] = sprintf(
                '%s BETWEEN %d AND %d', 
                $field, 
                $range['from'], 
                $range['to']
            );
        }
        return implode(' OR ', $where);
    }
    protected function decodeRanges(array $matches) {
        $range = array();
        foreach ($matches as $match) {
            $range[] = array(
                'from' => $match[1] + 1, 
                'to' => ($match[1] + strlen($match[0]))
            );
        }
        return $range;
    }
    protected function normalizeLengthTo($size) {
        if (strlen($this->range) < $size) {
            $this->range = str_pad($this->range, $size, '0');
        }
    }
    protected function replaceWith($low, $high, $character) {
        $this->normalizeLengthTo($high);
        $length = $high - $low + 1;
        $stub = str_repeat($character, $length);
        $this->range = substr_replace($this->range, $stub, $low - 1, $length);
    }
}

用法:

$d = new Dissector();
$d->allow(1, 10);
$d->deny(5, 15);
$d->allow(10, 20);
var_dump($d->findRanges());
var_dump($d->generateSql('foo'));

产生:

array(2) {
  [0]=>
  array(2) {
    ["from"]=>
    int(1)
    ["to"]=>
    int(4)
  }
  [1]=>
  array(2) {
    ["from"]=>
    int(10)
    ["to"]=>
    int(20)
  }
}
string(44) "foo BETWEEN 1 AND 4 OR foo BETWEEN 10 AND 20"