1

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

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

即，你会这样做：

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-24and 51-1000。因为 DENY 规则是在第一条规则之后定义的，所以它会“覆盖”之前的规则。

另一个例子，假设你有

  • 允许在 5 - 15 之间
  • 拒绝 10 - 50 之间
  • 允许在 45 - 60 之间

然后我想生成一个允许我执行的 WHERE 条件：

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

注释（编辑）

  • 此外，允许的最大范围是 1 - 5600000。（这将是“地球”）即。允许地球上的一切。
  • 数字范围实际上是嵌套集模型中的 LEFT 值。这些不是唯一的键。您可以在我之前提出的这个问题中阅读我为什么要这样做。 https://stackoverflow.com/questions/6020553/generating-a-mysql-between-where-condition-based-on-an-access-ruleset
  • 关于我的数字范围的可能重要说明我可能不应该使用我所做的示例示例，但关于数字范围性质的一个重要说明是，范围实际上应该始终完全消耗或被先前的规则消耗。比如我用上面的例子，10-50允许，45-60拒绝。这实际上不会在我的数据集中发生。它实际上是allow 10-50，那么 DENY 必须要么完全被该范围消耗，即 34-38。或者，完全使用前面的规则。9-51. 这是因为范围实际上代表嵌套集合模型中的 lft 和 rgt 值，并且您不能像我介绍的那样有重叠。

问这个问题的时候我没有想到要提到，但是在看到下面的工作示例代码之后，我可以看到这个注释实际上很重要。

（根据下面的评论，编辑示例 mysql 以包含 OR 而不是 AND）

4

4 回答 4

8

老实说，何苦呢？只要您要查询的键被索引，只需将多个查询放在那里：

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将 Allows 和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"
于 2011-05-16T19:52:50.740 回答
1

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

<?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)
  }
}

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

于 2011-05-16T20:12:33.053 回答
0

我会一次处理一个指令，创建一个应该包含的数字列表。然后最后将该列表转换为 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);
于 2011-05-16T19:47:44.100 回答
0

我在 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);
于 2011-05-16T21:40:18.953 回答