剖析数字范围

Question

我正在尝试找出生成 WHERE 查询的最有效方法。我之前问过另一个类似的问题，但我会直奔主题。

给定一个数字范围的集合，即 1-1000、1500-1600，创建一个 mysql where 条件来选择这些值之间的记录非常简单。

即，您只需执行：

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

例如，如果您定义多个规则，例如...

• ALLOW BETWEEN 1 - 1000
• ALLOW BETWEEN 1500 - 1600
• ALLOW BETWEEN 1250 - 1300
• DENY BETWEEN 25 - 50

如何合并这些规则以有效生成 WHERE 条件。 我希望在 WHERE 中剖析 ALLOW BETWEEN 1 - 1000 以在其中创建间隙。这样它就会变成 1-24 和 51-1000。由于 DENY 规则是在第一个规则之后定义的，因此它“覆盖”前面的规则。

再举个例子， 假设您有

• ALLOW BETWEEN 5 - 15
• DENY BETWEEN 10 - 50
• ALLOW BETWEEN 45 - 60

然后我想生成一个 WHERE 条件，该条件允许我执行以下操作：

WHERE (lft BETWEEN 5 and 9) OR (lft BETWEEN 45 和 60）。

注释（编辑）

• 此外，允许的最大范围是 1 - 5600000。（这将是“地球”）即。允许地球上的一切。
• 数字范围实际上是嵌套集合模型中的左侧值。这些不是唯一的键。 您可以在我之前提出的问题中了解我为什么要这样做。 https://stackoverflow.com/questions/ 6020553/generating-a-mysql- Between-where-condition-based-on-access-ruleset
• 关于我的数字范围的可能重要说明我可能不应该使用该示例我所做的示例，但关于数字范围的性质的一个重要注意事项是，范围实际上应该始终完全消耗或被先前的规则消耗。比如我用上面的例子，10-50允许，拒绝45-60。这在我的数据集中实际上不会发生。实际上，允许 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组合在一起，并将“Denys”AND组合在一起）并继续前进去更重要的事情。然后，如果以后出现问题，请重新审视它。但我真的不认为这会成为一个太大的问题...

编辑 好的，这是一个非常简单的算法来做到这一点。它使用字符串作为数据存储，因此对于较小的数字（低于 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"

Answer 2

我花了一点时间试图解决这个问题（这是一个很好的问题），然后想出了这个。它不是最佳的，我也不保证它是完美的，但它可能会让您开始：

<?php

/*$cond = array(
    array('a', 5, 15),
    array('d', 9, 50),
    array('a', 45, 60)
);*/

$cond = array(
    array('a', 1, 1000),
    array('a', 1500, 1600),
    array('a', 1250, 1300),
    array('d', 25, 50)
);

$allow = array();

function merge_and_sort(&$allow)
{
    usort($allow, function($arr1, $arr2)
    {
        if ($arr1[0] > $arr2[0])
        {
            return 1;
        }
        else
        {
            return -1;
        }
    });

    $prev = false;

    for ($i = 0; $i < count($allow); $i++)
    {
        $c = $allow[$i];
        if ($i > 0 && $allow[$i][0] < $allow[$i - 1][1])
        {
            if ($allow[$i][1] <= $allow[$i - 1][1])
            {
                unset($allow[$i]);
            }
            else
            {
                $allow[$i - 1][1] = $allow[$i][1];
                unset($allow[$i]);
            }
        }
    }

    usort($allow, function($arr1, $arr2)
    {
        if ($arr1[0] > $arr2[0])
        {
            return 1;
        }
        else
        {
            return -1;
        }
    });
}

function remove_cond(&$allow, $start, $end)
{
    for ($i = 0; $i < count($allow); $i++)
    {
        if ($start > $allow[$i][0])
        {
            if ($end <= $allow[$i][1])
            {
                $temp = $allow[$i][1];
                $allow[$i][1] = $start;
                $allow []= array($end, $temp);
            }
            else
            {
                $found = false;
                for ($j = $i + 1; $j < count($allow); $j++)
                {
                    if ($end >= $allow[$j][0] && $end < $allow[$j][1])
                    {
                        $found = true;
                        $allow[$j][0] = $end;
                    }
                    else
                    {
                        unset($allow[$j]);
                    }
                }

                if (!$found)
                {
                    $allow[$i][1] = $start;
                }
            }
        }
    }
}

foreach ($cond as $c)
{
    if ($c[0] == "a")
    {
        $allow []= array($c[1], $c[2]);

        merge_and_sort($allow);
    }
    else
    {
        remove_cond($allow, $c[1], $c[2]);
        merge_and_sort($allow);
    }
}

var_dump($allow);

最后一个 var_dump 输出：

array(4) {
  [0]=>
  array(2) {
    [0]=>
    int(1)
    [1]=>
    int(25)
  }
  [1]=>
  array(2) {
    [0]=>
    int(50)
    [1]=>
    int(1000)
  }
  [2]=>
  array(2) {
    [0]=>
    int(1250)
    [1]=>
    int(1300)
  }
  [3]=>
  array(2) {
    [0]=>
    int(1500)
    [1]=>
    int(1600)
  }
}

编辑为使用第一个示例而不是第二个示例。

Answer 3

我会一次处理一个指令，创建一个应包含的数字列表。然后最后将该列表转换为 where 子句的一组范围。这是一些伪代码：

$numbers = array();
foreach (conditions as $condition) {
    if ($condition is include) {
        for ($i = $condition.start; $i <= $condition.end; $i++) {
            $numbers[$i] = true;
        }
    } else {
        for ($i = $condition.start; $i <= $condition.end; $i++) {
            unset($numbers[$i]);
        }
    }
}
ksort($numbers);

Answer 4

我在 IRC 上询问并收到了两个回复。我将把它们都发布出来，以便其他人可能受益（这样我就不会失去它们，因为我很快就会详细了解它们）。

示例 1 TML

<pre><?php

$cond = array(
    array('a', 5, 15),
    array('a', 5, 15),
    array('d', 9, 50),
    array('a', 45, 60),
    array('a', 2, 70),
    array('d', 1, 150),
);



function buildAcl($set) {
    $allow = array();
    foreach($set as $acl) {
        $range = range($acl[1], $acl[2]);
        switch($acl[0]) {
            case 'a':
                $allow = array_unique(array_merge(array_values($allow), $range));
                break;
            case 'd':
                foreach($range as $entry) {
                    unset($allow[array_search($entry, $allow)]);
                }
        }
    }
    return $allow;
}

var_dump(buildAcl($cond));
var_dump(buildAcl(array(array('a', 5, 15), array('d', 10, 50), array('a', 45, 60))));

示例 2 (matslin)

<?php
$conds = array(
    array('a', 5, 15),
    array('a', 5, 15),
    array('d', 9, 50),
    array('a', 45, 60),
    array('a', 2, 70),
    array('d', 1, 150),
);

$segments = array();

foreach($conds as $cond)
{
    print($cond[0] . ': ' . $cond[1] . ' - ' . $cond[2] . "\n");
    if ($cond[0] == 'a')
    {
        $new_segments = array();
        $inserted = false;
        $prev_segment = false;

        foreach($segments as $segment)
        {
            if ($segment['begin'] > $cond[2])
            {
                $new_segments[] = array('begin' => $cond[1], 'end' => $cond[2]);
                $new_segments[] = $segment;
                $inserted = true;
                print("begun\n");
                continue;
            }

            if ($segment['end'] < $cond[1])
            {
                print("end\n");
                $new_segments[] = $segment;
                continue;
            }

            if ($cond[1] < $segment['begin'])
            {
                $segment['begin'] = $cond[1];
            }

            if ($cond[2] > $segment['end'])
            {
                $segment['end'] = $cond[2];
            }

            $inserted = true;

            if (
                $prev_segment &&
                ($prev_segment['begin'] <= $segment['begin']) &&
                ($prev_segment['end'] >= $segment['end'])
            )
            {
                print("ignore identical\n");
                continue;
            }

            print("default\n");
            $prev_segment = $segment;
            $new_segments[] = $segment;
        }

        if (!$inserted)
        {
            print("inserted at end\n");
            $new_segments[] = array('begin' => $cond[1], 'end' => $cond[2]);
        }

        $segments = $new_segments;
        print("---\n");
    }

    if ($cond[0] == 'd')
    {
        $new_segments = array();

        foreach($segments as $segment)
        {
            # not contained in segment
            if ($segment['begin'] > $cond[2])
            {
                print("delete segment is in front\n");
                $new_segments[] = $segment;
                continue;
            }

            if ($segment['end'] < $cond[1])
            {
                print("delete segment is behind\n");
                $new_segments[] = $segment;
                continue;
            }

            # delete whole segment
            if (
                ($segment['begin'] >= $cond[1]) &&
                ($segment['end'] <= $cond[2])
            )
            {
                print("delete whole segment\n");
                continue;
            }

            # delete starts at boundary
            if ($cond[1] <= $segment['begin'])
            {
                print("delete at boundary start\n");
                $segment['begin'] = $cond[2];
                $new_segments[] = $segment;
                continue;
            }
            # delete ends at boundary
            if ($cond[2] >= $segment['end'])
            {
                print("delete at boundary end\n");
                $segment['end'] = $cond[1];
                $new_segments[] = $segment;
                continue;
            }

            # split into two segments
            print("split into two\n");
            $segment_pre = array('begin' => $segment['begin'], 'end' => $cond[1]);
            $segment_post = array('begin' => $cond[2], 'end' => $segment['end']);

            $new_segments[] = $segment_pre;
            $new_segments[] = $segment_post;
        }

        print("--\n");
        $segments = $new_segments;
    }

    print("----\n");
    var_dump($segments);
    print("----\n");
}

var_dump($segments);