Q&A
割り算で誤差が生じないですかね？
お世話になります
レコード数の多いMySQLの順番決めに関する構造のベストプラクティスを
皆様にお聞きしたいです
もしかするとアルゴリズムの質問になるかもしれません
例えば以下のように、順番を管理するカラムorderを作って
任意に出力順を決めるような構造にしたとします
| id | name | order |
|---|---|---|
| 1 | いちご | 1 |
| 2 | メロン | 4 |
| 3 | りんご | 2 |
| 4 | バナナ | 3 |
SELECT `name` FROM `table` ORDER BY `order` ASC
出力結果は
いちご、りんご、バナナ、メロン
期待通りです
このような「順番用のカラム」を作ってORDERするような構造はよく使われていると思いますが
例えば、10万件ほどのデータがあり
ユーザーが順番を任意にソートして保存できるような機能を採用した場合
例えば、order 50,000位だった列をorder 1位に移動すると5万件のレコードの更新が必要になってしまうと思います
| id | name | order(更新前) | order(更新後) |
|---|---|---|---|
| 50000 | そば | 50000 | 1 |
| 1 | いちご | 1 | 2 |
| 2 | メロン | 4 | 5 |
| 3 | りんご | 2 | 3 |
| 4 | バナナ | 3 | 4 |
| 5...続く |
ユーザーが順番を任意にソートして保存できる機能ですので
7万位から2万位に動かす場合、5万位から2位 and 6万位から5位 and 2位から9万位など複数のソートがある場合があります
ユーザーが順番を任意にソートして保存できる機能は
一回限定の機能ではなく繰り返し行われます
これが100万件になったら、1億件になったら、ソートだけでとんでもない負荷になると思います
ですので、レコード数が多い場合「順番用のカラム」を作ってORDERするような構造は良いものとは言えないかなと思います
「順番を任意に保存できるようにしたい」「レコード数が多い」場合
みなさんはどのような構造にしているのでしょうか？？
なにかアルゴリズムで対応しているのでしょうか
事例やヒントをいただけますと幸いです
回答5件
0
順番がやすく変更できるのがリンクリストらしいと思います。orderではなくnextを記録すればどうでしょうか？例えば：
| id | name | order(更新前) | order(更新後) | next(更新前) | next(更新後) |
|---|---|---|---|---|---|
| 50000 | そば | 50000 | 1 | 50001 | 1 |
| 1 | いちご | 1 | 2 | 3 | 3 |
| 2 | メロン | 4 | 5 | 5 | 5 |
| 3 | りんご | 2 | 3 | 4 | 4 |
| 4 | バナナ | 3 | 4 | 2 | 2 |
行を移動する際、その行、その前後行と行先の前後行、まとめて5行だけ更新していいです。
しかし、その代わり、読み込みの際、SQL側でORDERできなくなります。
もう一つ書き方はStackOverflowからパクってきたアイディアなんですが、orderの間を大きくすれば、順番更新の際に間の中に入れば、多数のレコードを更新する必要が後押せます。デフォルトのINTEGERのidは最大値が21億であり、2億のデータでもorderの間に10を留めれば大丈夫でしょう。
| id | name | order(更新前) | order(更新後) | next(更新前) | next(更新後) |
|---|---|---|---|---|---|
| 50000 | そば | 500000 | 5 | 50001 | 1 |
| 1 | いちご | 10 | 10 | 3 | 3 |
| 2 | メロン | 40 | 40 | 5 | 5 |
| 3 | りんご | 20 | 20 | 4 | 4 |
| 4 | バナナ | 30 | 30 | 2 | 2 |
お役に立てば幸いです。
投稿2020/07/10 05:27
総合スコア464
0
order 列を integer でなく float にしては？
7万位から2万位に動かす場合, 2万位 と 1万9999位の中間の値を設定する様にするのです。
order 列には index を張っておくことは必要です。
1万9999位 と 2万位のレコードは order by order offset 19998 limit 2 で得られます。
投稿2020/07/11 01:22
総合スコア22324
誤差は関係ないです。大小関係さえ保たれればよいので。
もし (a + b) /2 が a か b になったなら、 a, 挿入する値, ,b の３つを調整する必要は出てきますが。
0
orderとは別に枝番(sub order)を項目として追加すれば、同じorder内のデータのみの更新で済みます。
また、その枝番も追加なら100番おきにして置き、挿入に備えるようにすると、更新対象はさらに減らすことができます。
結局、並べ替えを想定して、予め隙間をどのように準備しておくかという事
追記
ソートをツリーと見立てて再帰を使用して行うなら、3件だけの更新で済みますが、性能面で現実的では無いと思います。
投稿2020/07/10 04:44
編集2020/07/10 13:42総合スコア25327
ありがとうございます
すみません条件が不足しておりました
ユーザーが順番を任意にソートして保存できる機能は
一回限定の機能ではなく繰り返し行われます
ソートを行うたびに枝番を増やすと
全レコード更新とはまた別のコストがかかりそうです
枝番を増やすとは？ 枝番とはカラムの事です。
質問の例なら
(order, suborder)=(50000, 0) →(1,-1)
のように更新する事です。
私の理解不足でした申し訳ございません
この方法でも
sub orderに記録してソートした回数分
蓄積して更新回数が増えていくのではと思います
sub orderが1～5000まで割り振ったのちにsub order:2500の場所にデータをソートした場合など
suborderに隙間が無い場合に振り直ししたとして、枝番の部分だけですからorderだけよりはましですね。
実際に同じ隙間に何度も並び替えが起こることが想定できるなら、最初は1,000番単位で振るようにすれば、良いでしょう？
（回答したように「予め隙間をどれだけ準備できるか」が更新対象を減らす事に繋がります）
因みに、追記した部分は理解されたでしょうか。
0
そもそもこのテーブルでソート用のカラムがないなら
どういうロジックで順位をきめるかわかりませんよね
一般的なランク付け処理は１データごとに処理がはいるので重くなりがちです
投稿2020/07/10 03:50
総合スコア116724
>ソート用のカラムがないなら
「順番用のカラム」はorderなのですが
sort用のカラムとは具体的にどういったものでしょうか？？
>どういうロジックで順位をきめるか
「順番用のカラム」order を ORDER ASC します
順番用のカラムは前後のランクとの大小関係しかみなくていいのですね？
であれば50000を1の前に持っていきたいなら0にすることです。
intではなくdoubleか何かにしておけば、50000を2と3の間に入れるときは
2.5にすればいいです
ランク付けはorderカラム自分より小さい数をcountして1足したものです
ありがとうございます
すみません条件が不足しておりました
ユーザーが順番を任意にソートして保存できる機能は
一回限定の機能ではなく繰り返し行われます
>intではなくdoubleか何かにしておけば、50000を2と3の間に入れるときは
>2.5にすればいいです
double小数点第一位に設定した場合、2と3の間に11回以上入れると上記は破綻すると思います
intを歯抜けにした場合も同じで更新回数に制限がついてしまいます
中割をするのがやなら二次ソート列をつくるくらいですかね
create table tbl(id int primary key,name varchar(10),sort1 int,sort2 int,unique(sort1,sort2));
insert into tbl values
(1,'いちご',1,0),
(2,'メロン',4,0),
(3,'りんご',2,0),
(4,'バナナ',3,0),
(50000,'そば',50000,0);
id=50000をsort1=2の次にいれるには
update tbl set sort1=2,sort2=1 where id=50000;
select * from tbl order by sort1,sort2
なるほど！！
saziさまが同様の回答をくれていたのですが
yambejpさまの具体例でやっと理解できました
しかしこの方法でも
sort1=2の次にソートした回数分
蓄積して更新回数が増えていくのではと思います
sort2が1～5000まで割り振ったのちにsort2:2500の場所にデータをソートした場合など
頻繁でなければ定期的に振り直す処理が必要にはなりそうですね
月イチくらいのメンテでいけるんじゃないですかね？
0
例えば、order 50,000位だった列をorder 1位に移動すると5万件のレコードの更新が必要になってしまうと思います
そばのorderを-1にすれば回避できます。
投稿2020/07/10 03:49
総合スコア146018
> 「順番を任意に保存できるようにしたい」「レコード数が多い」場合
それが必要になる状況のほうが想像できません（1億件のリストを任意にソートするといっても、おそらく人間が対応しきれません）。
すみません、私の出した例が少なかったです
例の5万位から1位の例ではその通りですが
ユーザーが順番を任意にソートして保存できる機能ですので
5万位から2万位の場合、5万位から2位 and 6万位から5位 and 2位から9万位など複数のソートがあった場合
その方法では期待する結果にはならないです
ソートはどれくらいの頻度で行われるものなのでしょうか？「たまに負荷が発生する」程度であれば気にすることもないでしょう。
状況がはっきりすれば、もっといいデータ構造、操作体系があるかもしれませんので、もう少し具体的にしていただけないでしょうか。
ありがとうございます！
質問内容は何かの要件をデフォルメしているわけではなく書いた通りの要件でございます！
10万件のデータを
5万位から2位 and 6万位から5位 and 2位から9万位 など任意に順位変更して
その順位を1～10万件まで正確に出したいです
特に特殊な要件ではないかなと思ったんですが
これを実現したいなら、全データのorderをUPDATEするしかないのですかね
正確には全データではなく全対象データですね
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2020/07/10 12:26 編集
2020/07/11 06:35 編集
2020/07/11 07:06