質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.91%

レコード数の多いMySQLの順番決めに関する構造のベストプラクティス

受付中

回答 5

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 268

tesopgmh

score 106

お世話になります

レコード数の多い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するような構造は良いものとは言えないかなと思います

「順番を任意に保存できるようにしたい」「レコード数が多い」場合
みなさんはどのような構造にしているのでしょうか??

なにかアルゴリズムで対応しているのでしょうか
事例やヒントをいただけますと幸いです

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

+1

順番がやすく変更できるのがリンクリストらしいと思います。orderではなくnextを記録すればどうでしょうか?例えば:

id name order(更新前) order(更新後) next(更新前) next(更新後)
50000 そば  50000  50001 1
いちご  2 3 3
メロン  5 5 5
りんご  3 4 4
バナナ  4 2 2

行を移動する際、その行、その前後行と行先の前後行、まとめて5行だけ更新していいです。

しかし、その代わり、読み込みの際、SQL側でORDERできなくなります。


もう一つ書き方はStackOverflowからパクってきたアイディアなんですが、orderの間を大きくすれば、順番更新の際に間の中に入れば、多数のレコードを更新する必要が後押せます。デフォルトのINTEGERのidは最大値が21億であり、2億のデータでもorderの間に10を留めれば大丈夫でしょう。

id name order(更新前) order(更新後) next(更新前) next(更新後)
50000 そば  500000  50001 1
いちご  10  10 3 3
メロン  40  40 5 5
りんご  20  20 4 4
バナナ  30  30 2 2

お役に立てば幸いです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/10 21:06 編集

    ありがとうございます!

    おおおおお、前半、目から鱗でした
    次のカラムのid情報を保持するカラムでしたら
    最大5カラムの更新で済みますね
    しかも更新は何度も繰り返せます!

    後半はyambejpさまから頂いたやり方に近いですね
    例えば10おきだと11回の挿入ができなくなるので
    繰り返しソートされると破綻するかもしれません

    キャンセル

  • 2020/07/11 15:27 編集

    そうです、でも前半はデータベースがORDERできなくなり、ページ付けもできなくなります。すべての行を取得し、アプリ側でnextに沿って表示したり;試していっぱいの行を取得し、nextに沿って見つけなかったらもっと取得したりしなければなりません。つまり更新しやすいの代わりに読み込みが難しくなるのです。この取捨をしっかり考えてください。いや、考えるより、テストして本当にユーザー体験を向上できるか検証しなさい。

    後半はご意見の通りいつか破綻しますけど、行の数とユーザーの行動に合わせて調整してみれば、破綻までの時間をなるべく長くできますか、再整理を段階的に行い破綻のタイムコストを敷けてユーザー体験を維持できます。

    調整とは例えば、INT型が負数合わせて42億以上の数字を含めています。2億行なら20おきできます。BIGINTを使えば10億おきもできますが、行ごとINTより4Byte増必要なので400MB増のストレージを使ってしまいます。

    再整理を段階的にするとは例えば、おきが定数ではなく、範囲を行数で分けて決めます。そして全部を再整理ではなく、いくつかの条件で再整理の範囲を決めます。更新の際にはおきの真ん中(order_front + order_back / 2)に入れます。条件とは例えば前後3000行とか前後10万順番とかで、テストしながら調整していきなさい。

    最終的には、実行時間、ストレージ、コードの難しさ、この三つの間に取捨しなければなりません。テストと検証しながら最善の策を探りましょう。

    キャンセル

  • 2020/07/11 16:06

    読み込みの難しさは例えば、2億行すべて取得すれば、idとnextだけ取得しても800MBのメモリーが必要です。行のデータを取得すればメモリーもっと必要ですが、取得しなければ後で順番で1行1行取得になってしまいますので、実行時間が長くなりそうです。

    一回すべての行を取得しなければ、少ないほどnextを見つけないリスクが高くなって、再取得しなければならなくて実行時間が長くなります。

    そもそもスクリーンに2億行が多分すべて表示できないので、用例にとっていいところがコストに見合いかを検証してみてください。

    キャンセル

0

例えば、order 50,000位だった列をorder 1位に移動すると5万件のレコードの更新が必要になってしまうと思います

そばのorderを-1にすれば回避できます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/10 12:57

    状況がはっきりすれば、もっといいデータ構造、操作体系があるかもしれませんので、もう少し具体的にしていただけないでしょうか。

    キャンセル

  • 2020/07/10 13:41 編集

    ありがとうございます!
    質問内容は何かの要件をデフォルメしているわけではなく書いた通りの要件でございます!

    10万件のデータを
    5万位から2位 and 6万位から5位 and 2位から9万位 など任意に順位変更して
    その順位を1~10万件まで正確に出したいです

    特に特殊な要件ではないかなと思ったんですが
    これを実現したいなら、全データのorderをUPDATEするしかないのですかね

    キャンセル

  • 2020/07/10 13:42

    正確には全データではなく全対象データですね

    キャンセル

0

そもそもこのテーブルでソート用のカラムがないなら
どういうロジックで順位をきめるかわかりませんよね
一般的なランク付け処理は1データごとに処理がはいるので重くなりがちです

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/10 18:57

    中割をするのがやなら二次ソート列をつくるくらいですかね

    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

    キャンセル

  • 2020/07/10 21:21

    なるほど!!
    saziさまが同様の回答をくれていたのですが
    yambejpさまの具体例でやっと理解できました

    しかしこの方法でも
    sort1=2の次にソートした回数分
    蓄積して更新回数が増えていくのではと思います
    sort2が1~5000まで割り振ったのちにsort2:2500の場所にデータをソートした場合など

    キャンセル

  • 2020/07/10 23:22 編集

    頻繁でなければ定期的に振り直す処理が必要にはなりそうですね
    月イチくらいのメンテでいけるんじゃないですかね?

    キャンセル

0

orderとは別に枝番(sub order)を項目として追加すれば、同じorder内のデータのみの更新で済みます。
また、その枝番も追加なら100番おきにして置き、挿入に備えるようにすると、更新対象はさらに減らすことができます。

結局、並べ替えを想定して、予め隙間をどのように準備しておくかという事

追記

ソートをツリーと見立てて再帰を使用して行うなら、3件だけの更新で済みますが、性能面で現実的では無いと思います。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/10 14:04

    ありがとうございます

    すみません条件が不足しておりました
    ユーザーが順番を任意にソートして保存できる機能は
    一回限定の機能ではなく繰り返し行われます

    ソートを行うたびに枝番を増やすと
    全レコード更新とはまた別のコストがかかりそうです

    キャンセル

  • 2020/07/10 14:30

    枝番を増やすとは? 枝番とはカラムの事です。
    質問の例なら
    (order, suborder)=(50000, 0) →(1,-1)
    のように更新する事です。

    キャンセル

  • 2020/07/10 21:23

    私の理解不足でした申し訳ございません

    この方法でも
    sub orderに記録してソートした回数分
    蓄積して更新回数が増えていくのではと思います
    sub orderが1~5000まで割り振ったのちにsub order:2500の場所にデータをソートした場合など

    キャンセル

  • 2020/07/10 22:13 編集

    suborderに隙間が無い場合に振り直ししたとして、枝番の部分だけですからorderだけよりはましですね。
    実際に同じ隙間に何度も並び替えが起こることが想定できるなら、最初は1,000番単位で振るようにすれば、良いでしょう?
    (回答したように「予め隙間をどれだけ準備できるか」が更新対象を減らす事に繋がります)
    因みに、追記した部分は理解されたでしょうか。

    キャンセル

0

order 列を integer でなく float にしては?
7万位から2万位に動かす場合, 2万位 と 1万9999位の中間の値を設定する様にするのです。
order 列には index を張っておくことは必要です。
1万9999位 と 2万位のレコードは order by order offset 19998 limit 2 で得られます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/11 10:39

    割り算で誤差が生じないですかね?

    キャンセル

  • 2020/07/11 11:31

    誤差は関係ないです。大小関係さえ保たれればよいので。
    もし (a + b) /2 が a か b になったなら、 a, 挿入する値, ,b の3つを調整する必要は出てきますが。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.91%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る