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 条件を効率的に生成するために、これらのルールをマージするにはどうすればよいですか。ALLOW BETWEEN 1 - 1000そこにギャップを作るために、WHERE で を分析してほしいと思います。となるよう1-24に51-1000。DENY ルールは最初のルールの後に定義されるため、前のルールを「上書き」します。

別の例として、あなたが持っているとしましょう

  • 5 ～ 15 の間で許可
  • 10 ～ 50 の間で拒否
  • 45 ～ 60 の間を許可

次に、実行できる WHERE 条件を生成したいと思います。

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

メモ (編集)

  • また、許可される最大範囲は 1 ～ 5600000 です (これは「地球」になります)。地球上のすべてを許可します。
  • 数値範囲は、実際には NESTED SET MODEL の LEFT 値です。これらは一意のキーではありません。なぜ私がこれをやりたいのかは、以前に尋ねたこの質問で読むことができます。 https://stackoverflow.com/questions/6020553/generating-a-mysql-between-where-condition-based-on-an-access-ruleset
  • 数値範囲に関する重要な注意事項 私が行ったサンプル例を使用するべきではなかったかもしれませんが、数値範囲の性質に関する重要な注意事項の 1 つは、実際には範囲が常に完全に消費されるか、前のルールによって消費される必要があるということです。たとえば、上記の例では、10 ～ 50 が許可され、45 ～ 60 が拒否されます。これは、私のデータセットでは実際には起こりません。実際にはallow 10-50の場合、DENY はその範囲、つまり 34 ～ 38 で完全に消費される必要があります。または、前のルールを完全に消費します。9-51. これは、範囲がネストされたセット モデルの lft 値と rgt 値を実際に表しており、提示したように重複することができないためです。

私は質問をするときにそれについて言及するつもりはありませんでしたが、以下の実際のサンプル コードを見て、このメモが実際に重要であることがわかりました。

(以下のコメントに従って、AND の代わりに OR を含めるように mysql の例を編集しました)

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許可をANDまとめ、拒否をまとめて）、より重要なことに移ります。その後、問題が発生した場合は、もう一度確認してください。しかし、これが大きな問題になることはないと思います...

編集OK、これを行うための非常に単純なアルゴリズムがあります。データストアとして文字列を使用するため、数値が小さい場合（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)
  }
}

2 番目の例の代わりに最初の例を使用するように編集されました。

于 2011-05-16T20:12:33.053 に答える
0

指示を 1 つずつ処理して、含める番号のリストを作成します。最後に、そのリストを 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 で質問したところ、2 つの回答がありました。他の人が利益を得ることができるように (そして、すぐに両方について詳しく説明するので、それらを失うことのないように)、両方を投稿します。

例 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 に答える