メモリに乗りきらないcsvの重複レコード有無を判別する方法

Question

環境

CentOS
Python3

やりたいこと

メモリに乗りきらない大容量csvの重複レコード有無を判別したい。

補足

CentOS上で数十GBのcsvの集計を実施するタスクがある。
メモリに全レコード乗らないので、pandasでchunksizeを指定してTextFileReaderをループして集計する方針を立てた。

大部分の集計はこれで問題ないと思われたが、レコードを分割してしまうと全レコードに対して重複するレコードがないか確認する手段がないと気付いた。

概ね全カラム必要となるのでusecolでカラムを絞るのは不可。
csvの最大サイズが保証されないので、dtype明示してある程度メモリを節約してもオーバーフローする可能性あり。

試したこと

各カラムの値の組み合わせ毎に一意な識別子を生成する。
生成された識別子をリストに格納して重複判定する。
もしくはデリミタを設けて文字列型辺りでスタックして文字列検索して重複判定する。

例

A	B	C
1	2	3
4	5	6
7	8	9

上記テーブルの場合、
[123,456,789]に重複がないので重複レコードなし。
もしくは string型のstr = '/123/456/'と順番にスタックして、789が文字列内に含まれないので重複レコードなし。
以降は str = '/123/456/789/'として同様に後続の判定。

問題点

いずれの場合も数十GBのテーブルのすべてのレコードに対して識別子を生成する処理が必要となり、非常に処理時間が長くなってしまう。

かつ、レコードが非常に多い場合、リストでも文字列でもメモリに乗りきらない可能性がある。

結局知りたいこと

メモリは有限だが、csvの最大サイズは保証されない。
つまり、それらに依存せず、任意のメモリ内で分割して重複判定ができる方法があれば知りたい。

個人的には、少なくとも何らかの形でメモリに乗せきる必要はあると思う。

ただ、以前別件で鶴の一声があって、考えてみればそりゃそうだと思う様な手法で解決した実績があるので取り敢えず質問した次第です。

根幹的解決に至らずとも、少しでもメモリ効率を上げる手法がございましたらご提案いただけますと幸甚です。

Comments

[meg_]

> メモリに乗りきらない大容量csvの重複レコード有無を判別したい。
どのようなデータか不明ですが、重複するようなデータなのですか？

[ka-you]

いいえ。本来重複しないはずのデータです。
間違いなく重複がないか検品をする必要があります。

[meg_]

awkを使ってもメモリ不足になりますか？

[68user]

DBに突っ込んで重複行確認。
あるいは適当な行数でファイル分割してそれぞれをソートし、さらにマージソートで1ファイルに結合。上から順に見ていって同じ値が連続していたら重複 (全部をメモリ上に持たなくてもよい方法)

[fourteenlength]

> レコードが非常に多い場合、リストでも文字列でもメモリに乗りきらない可能性
カラムのボリュームによりますが、
1. レコード毎にSHA1(SHA2)ハッシュを生成
2. ハッシュを（リスト型よりコンパクトで済む）文字列型として結合
3. 連結したハッシュ文字列に対して一致ありなしを確認
ではいかがでしょうか？
質問の例のようにカラムの内容がSHA1ハッシュより短いとかえってかさばりますが、カラムの内容がSHA1ハッシュより長いならSHA1ハッシュ化すれば情報をいくらか集約できます。
「ハッシュでも長すぎる」であれば、ハッシュを前半後半に分割して、簡易的には前半のハッシュだけで検索してもし前半のハッシュが一致するなら別に取っておいてある後半のハッシュも検索－－とすれば、一度に検索するデータ量は（前半が一致するまでは）半分まで減らせます。

[fourteenlength]

stackoverflowを見るとmeg_さんのコメントにあるようにawkを使う方法がどれもトップに来ていました。たぶんPythonを使う時点で「メモリを食う」「処理が遅い」のダブルパンチになるのだと思います。

[TakaiY]

「同一装置の同一時刻のデータ」など重複しているレコードの判断基準は無いのでしょう。これまでいろいろデータを扱ってきましたが、「全カラム同一なら重複」というデータを見たことがありません。

[ka-you]

meg_様
awkでも乗り切りません。
swapは完全に使い潰しませんが、全体の8割程度のメモリを喰った後にstat:Dで処理が止まります。

68user様
DBの内部処理は明るくないので恐縮ですが、重複行の確認にレコード分のメモリ必要ないのでしょうか。
ただ、いずれにしても新規システムの導入は不可ですのでDBの利用はできません。

こちらもそこまで明るくありませんが、マージソートはIn-place等除いて要素数分メモリ必要な認識です。
分割した各ファイルはソート可能と思いますが、最終的に1ファイルに結合する際に全件分のメモリ必要ではないでしょうか。

fourteenlength様
ハッシュは私も考えました。
本文の例では単に結合しただけですが、文中の一意な識別子というのがそれです。

ご指摘の通り、Pythonで扱う時点で処理が遅い事案は発生してしまう様です。
awkを使ってもメモリに乗り切りませんでした。

TakaiY様
>...データを見たことがありません。
とのことですが、事実ベースそうなっています。

というか、既に不要なカラムを排除している状態です。
必要なカラムのみを抽出した結果、メモリに乗りきらないサイズのデータになっています。

[68user]

> DBの内部処理は明るくないので恐縮ですが、重複行の確認にレコード分のメモリ必要ないのでしょうか。
メモリに乗らない分は一時領域であるHDD/SSDなどのストレージを使うのが一般的かと思います。もちろん遅いし、一時領域不足ならエラーになります。

> 分割した各ファイルはソート可能と思いますが、最終的に1ファイルに結合する際に全件分のメモリ必要ではないでしょうか。
試してませんが sort -m *.splitted-and-sorted | uniq -d で重複行出てこないでしょうか。sort -m は各ファイルがソートされている前提なのでファイル全体を溜め込まない。uniq は同じ行が連続していたら出力するだけ。

そもそも GNU sort であればメモリで足りない分は一時ファイルを使ってくれるので、微妙に足りない程度なら -S オプションを適切に使えば分割せずにいけるのかもしれません。

[68user]

なおメモリはないけどストレージはそこそこあるという前提で書いてます。

[ka-you]

68user様
sort -m *.splitted-and-sorted | uniq -d　についてです。

まだ試せていませんが、調べた所 sort -m はソートせずにマージのみ行うと認識しました。
マージというのはマージソートの事でしょうか。

そうでない場合、分割された各ファイルがソートされていたとしても、それぞれを連結しただけでは uniq -d では重複検出できないと思います。異なるファイル間で重複レコードが発生した場合など。
またマージソートの場合はやはりメモリに乗りきらないかと思います。

月曜日までにご返信いただければラッキー程度です。
月曜日には自分で検証できますので。

ちなみにストレージはそこそこあると思います。

[otn]

マージというのは、あらかじめソートされた複数ファイルから、全体としてソートされた1つのファイルを作ると言うことなので、出力ファイルはソート済みで、uniq コマンドが使えます。
データ用のメモリーは、「最大行長 * ファイル数」だけです。

例で言い換えると、
学校の各クラスの生徒が、身長順にクラス毎に一列になっているとして（5クラスの場合は5列に並ぶ）、
「各列の先頭の人の中で一番身長の低い人を出力列に移動する」
という操作を誰もいなくなるまで繰り返せば、出力列には全生徒が身長順に並んでいます。
これがマージです。
比較するのは先頭の5人だけで、先頭の人が移動するまで、次の人のデータは読まないので、
データを読み込むメモリーは5人の分だけあれば良いです。

[ka-you]

otn様
ありがとうございます。納得できました。

stackoverflow等確認した所、想定しない一時ファイルが作成される、一度に処理可能なファイル数に上限がある、などの情報があり、他オプションも適切に利用する必要があるものと思いました。

Answer 1

結局、以下の点などから後述の変更前のやり方は止めました。
・適切なカラム選定が困難
・カラム構成によって都度カスタマイズ必要
・値毎のレコード数によっては複数カラム必要

ハッシュ生成も考慮しましたが、非常に膨大なレコードの場合に必ずしもメモリに乗りきると断言できないので今回は不採用としました。

最終的に、sort が一時ファイルを利用してマージソートを行うことで、メモリに乗りきらないサイズのファイルでもソートできることを知り、以下の様にしました。

sort 対象csv > 出力ファイル
uniq -d 出力ファイル

ご提案いただいたやり方からファイルが分割されている前提を排除した形です。

そういえばパイプのバッファに乗るかは試してません。
さっと調べた感じ、やはりメモリに乗りきらないと駄目っぽいので一旦ストレージに出力するのが妥当かと思います。

ご助力いただきましてありがとうございました。

変更前：
1．処理可能なサイズに分割します。
2．適度なグルーピングが可能なカラムを指定します。
3．分割した各ファイル内で指定のカラムの値（以降、指定キーと記載）毎に更に分割します。分割後のファイル名等で指定キーが特定できる様にします。
4．指定キー毎にファイルをマージします。
5、指定キーが異なるレコードは絶対に重複しないので、項番4で作成したファイル毎に重複判定をします。

Comments

[TakaiY]

指定キーのカラムの取り得る値があらかじめ判っているのであれば、ファイルを読み投がら、そのキー値ごとのファイルに順次書き出していけばいいと思います。
フォイルは開いたからといって、全ての内容を読み込む必要はありませんから。

[ka-you]

誤字が奇跡的なことになっていて感嘆しております。

私も事前に取り得る値が判明している場合は、その値毎にファイルを用意する方が容量が良いと思います。
本件では前述の通り最大ファイルサイズが保証されませんので、都度カラムの選定が必要になることを想定して一先ず回答本文の様に記載しました。

一応複数カラムの選定も考慮しています。

ただ、
>フォイルは開いたからといって、全ての内容を読み込む必要はありませんから。
の部分について、詳しくお聞きしたいです。

[TakaiY]

> 部分について、詳しくお聞きしたい
openして 1行ずつ読む場合、過去の分はメモリに残しておく必要がないので、いくらでも大きなファイルを開いて扱うことができるということです。
ですので、やっぱり、ファイルを分割する必要は無いと思います。

カラムの内容がわからないからということであれば、開いて対象カラムの内容を読んで自動なり手動なりで分割し、最初から1レコードずつ見ていって適切なファイルに書き出せばよいのではないでしょうか。

[ka-you]

内容把握できました。
他集計時にchunksize利用して取得したDataframe毎にカラムの値で捌こうと思っておりました。
1行ずつ読んでファイル分割するならchunksize不要なので、諸々検討してみます。

Answer 2

重複したときどうするか、がないのでとりあえず検出するだけ。
rubyには OpenSSL::Digest::SHA256 というハッシュ化する lib があります。 Python3 は経験がないのでわかりませんが、きっと有るのでは？
rubyでは 33千行、180MBの各行処理で0.1秒でした。

これを用いて、１行 処理する毎にハッシュを配列に入れておき比較する という方法はどうでしょう。
配列サイズがどのくらいになるか、ですが、その探索にも高速化の工夫が必要でしょう。
配列ではなく(ruby語の)Hash を使うと早いかも。

なおこの方法の欠点は「CSVとしては同じ内容だが、文字列としては異なる」場合に重複検出ミスります。例えば 文字データが " でくくられてるか ' でくくられてるか とか。

どの方法をとるにしても 重複確認が必要なので「その探索にも高速化の工夫」は必要ですが、提案の方法の良いところは 32Byte整数なので、文字列での比較よりはずっと高速です。

追記
ハッシュの提案はあったのですね。失礼

Answer 3

パッと思いついたアルゴリズム。 時間はかかりそうです。

・最初のn件のデータを読込み、重複を確認する。
・n+1 件以降のデータを順によみこみ、n件のデータとの重複を確認する。
・n+1件目を最初のデータとして、上記を繰替えす。

Comments

[ka-you]

内容把握できました。
元のコメント見ておられましたら、そちらへの返答は不要です。

内容について少々検討します。

[ka-you]

他集計に選定したchunksizeの利用と併せて処理が可能な自己回答の方が適切と思い、一旦こちらの検討はストップします。

n + 1 件目以降最終行までのすべてのレコードを n 件のレコードと照合する工程が複数回必要であり、本文に記載の通り時間がかかってしまうと思いました。

ご提案ありがとうございました。