(57)【要約】方法及びシステムは、メモリシステム内のデータベースを検索するために複数の検索要求を受信するよう操作する。この検索要求は、ＦＩＦＯキューに格納され、検索は各検索要求のために続いて生成され得る。得られた複数の検索は、実質的にデータベースで並行して実行され得る。それぞれの表示は、各それぞれの検索が完了したときまたは各それぞれの検索が検索結果を生成されたときの何れかの場合に、要求側ホストに送信される。【選択図】図５
2016536694.tif 000002
【特許請求の範囲】
【請求項１】
メモリへ検索要求を発行することと、
前記検索要求に対応する検索が完了したこと、または検索結果が見つかったことの表示を前記メモリから受信することと、を含み、
前記検索結果が見つかった場合には、前記表示に応答して前記メモリから前記検索結果を取得する方法。
【請求項２】
前記検索要求は前記メモリへのライトコマンドを含む、請求項１に記載の方法。
【請求項３】
前記ライトコマンドは、検索条件と検索キーの表示を含む、請求項２に記載の方法。
【請求項４】
前記メモリから前記検索要求が受信されたという確認を受信することをさらに含む、請求項１に記載の方法。
【請求項５】
前記検索要求に応答する前記検索が完了し、または前記検索結果が見つかったという前記表示の前記メモリからの受信が、前記検索が前記メモリに格納されたデータベースの最後に到達したという表示を受信することを含む、請求項１に記載の方法。
【請求項６】
前記要求に応答する前記検索が完了したこと、または前記検索結果が見つかったことの前記表示の前記メモリからの受信が、前記メモリ内のバッファが一杯であることの表示を受信することを含む、請求項１に記載の方法。
【請求項７】
前記表示に応答して前記メモリからの前記検索結果の取得が、前記メモリに前記検索結果を返信させるよう前記メモリにリードコマンドを発行することを含む、請求項１に記載の方法。
【請求項８】
ホストが前記検索結果を受信する準備ができていることを前記メモリに示すために、リードコマンドを前記メモリに発行することをさらに含む、請求項１に記載の方法。
【請求項９】
前記メモリがソフトウェアアップデートを受信することをさらに含む、請求項１に記載の方法。
【請求項１０】
第１のコマンドをメモリシステムに送信し、前記第１のコマンドはデータベースを検索するための検索要求の表示を含み、
前記メモリシステムへの第２のコマンドを送信し、前記第２のコマンドが、ホストが検索結果を受領する準備ができているという、前記メモリシステムへの表示を含み、
前記検索結果を取得する前記メモリシステムへの第３のコマンドを送信することを含む、方法。
【請求項１１】
前記第２のコマンドを送信することと、前記第３のコマンドを送信することとの間で、前記メモリシステムから応答を受信することをさらに含み、前記メモリシステムが検索結果を有するか、または前記データベースがその全体を検索されたことの表示を含む、請求項１０に記載の方法。
【請求項１２】
前記第１のコマンドがスモールコンピュータシステムインタフェース（ＳＣＳＩ）ライトコマンドを含み、前記第２のコマンドがＳＣＳＩリードコマンドを含み、前記第３のコマンドがＳＣＳＩリードコマンドを含む、請求項１０に記載の方法。
【請求項１３】
前記検索要求の前記表示が、前記第１のコマンドと関連するバッファが検索条件と検索キーを含むことを示す前記第１のコマンドの特定のフィールドに設定されたビットを含む、請求項１０に記載の方法。
【請求項１４】
前記検索条件は１つ以上の「等しい」、「未満」、「超」、「等しくない」、「以下」、「以上」、「及び」、「または」または「ではない」を含む、請求項１３に記載の方法。
【請求項１５】
メモリ内のデータベースの検索に対応する、複数の受信された検索要求を待機すること、
複数の前記データベースの検索を生成し、前記複数の前記検索のそれぞれの１つが前記複数の受信された検索要求のそれぞれに生成され、
実質的に並行で、前記複数の前記データベースの検索を実行することと、
前記複数の検索の各それぞれの１つが、前記それぞれの検索が完了したか、または検索結果を生成したという表示を送信することと、を含む方法。
【請求項１６】
受信されたコマンドに対応して前記検索結果のそれぞれ１つをホストに送信することをさらに含む、請求項１５に記載の方法。
【請求項１７】
前記複数の検索のそれぞれが各検索キー及び各検索条件を含む、請求項１５に記載の方法。
【請求項１８】
第１のコマンドをホストから受信し、前記第１のコマンドはメモリシステム内のデータベースを検索するために検索要求の表示を含み、
前記ホストから第２のコマンドを受信し、前記第２のコマンドは、前記ホストが前記メモリシステムから検索結果を受領する準備ができているという前記メモリシステムへの表示を含み、
前記検索結果を取得するよう第３のコマンドを前記ホストから受信することと、を含む方法。
【請求項１９】
前記第３のコマンドに対応して前記ホストにバッファ内のデータを送信することをさらに含む、請求項１８に記載の方法。
【請求項２０】
前記第１、第２及び第３のコマンドをパースすることと、
検索要求のバッファで前記第１のコマンドを待機することと、
未了の要求バッファにおける前記第２と第３のコマンドのそれぞれの表示を格納することと、
応答情報バッファにおける検索結果の表示を格納することと、
応答バッファに前記検索結果を格納することと、
前記第２のコマンドの前記表示と前記検索結果の前記表示に対応して前記ホストに情報応答を送信することと、
前記第３のコマンドの前記表示と前記検索結果の前記表示に対応して前記応答バッファから前記検索結果を送信することと、をさらに含む、請求項１８に記載の方法。
【請求項２１】
前記応答バッファから前記検索結果を送信した後、応答のバッファ自由リストの表示を格納することをさらに含む、請求項２０に記載の方法。
【請求項２２】
前記検索結果を格納するためのデータ構造を作成する前記メモリシステムをさらに含む、請求項１８に記載の方法。
【請求項２３】
前記検索結果が、第１のデータ構造からのデータを含み、前記第１データ構造に対応して、第２のデータ構造からのデータをさらに含む、請求項１８に記載の方法。
【請求項２４】
前記第２のデータ構造を作成することが、前記第１と第２のデータ構造の両方に存在する特定のフィールドに基づいて前記第２のデータ構造を作成することを含む、請求項２３に記載の方法。
【請求項２５】
前記検索結果中のその他のレコードの集約関数に対応するレコードのフィールドに値を割り当てることをさらに含む、請求項１８に記載の方法。
【請求項２６】
データベースの検索を実行するメモリシステムの処理回路によって実行するための命令を格納する、非一時的コンピュータで読み取り可能な記憶媒体であって、前記検索を実行する前記操作が、
前記データベースを検索する複数の検索要求を待機し、
複数の検索を生成し、それぞれの検索が前記複数の受信された検索要求のそれぞれに生成され、
実質的に並行で、前記複数の検索を実行することと、
各それぞれの検索のために、前記それぞれの検索が全体の前記データベースを検索したか、検索結果を生成したという表示を送信する操作である記憶媒体。
【請求項２７】
前記検索を実行する前記操作が、前記検索結果を受信するホストの準備ができていることを示すコマンドの受信に対応して各それぞれの検索のために前記表示をさらに送信する、請求項２６に記載の非一時的コンピュータで読み取り可能な記憶媒体。
【請求項２８】
前記検索を実行する前記操作が、前記検索結果の読み出しを示すコマンドに対応して、前記検索結果をさらに送信する、請求項２７に記載の非一時的コンピュータで読み取り可能な記憶媒体。
【請求項２９】
前記検索を実行するための前記操作が、前記検索結果の前記読み出しを示す、前記コマンドを受信するまで前記メモリシステムにおけるバッファ内の前記検索結果をさらに格納する、請求項２８に記載の非一時的コンピュータで読み取り可能な記憶媒体。
【請求項３０】
データベースを格納するよう構成されたメモリと、
前記メモリに連結されたコントローラであって、前記コントローラが、結果要求の受信と、前記検索要求に対応して前記データベースの検索の生成と、実質的にその他の検索要求と並行する前記データベースの前記検索の実行と、前記それぞれの検索が完了したか検索結果を生成したかの何れかを示すそれぞれの検索のためのそれぞれの表示の送信と、を制御するよう構成されたコントローラを備えるメモリシステム。
【請求項３１】
前記コントローラが、
前記検索結果を要求するホストからのコマンドの受信に対応する前記ホストへ前記検索結果を備えるデータバッファの送信と、
前記データバッファが前記検索結果の送信の後に空であるという表示する設定と、を制御するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項３２】
前記データベースが非構造化データセットを備える、請求項３０に記載のメモリシステム。
【請求項３３】
前記データベースが構造化データセットを備える、請求項３０に記載のメモリシステム。
【請求項３４】
前記メモリシステムがソリッドステートドライブを備え、前記メモリが不揮発性メモリを備える、請求項３０に記載のメモリシステム。
【請求項３５】
前記データベースが、複数のメモリシステム格納されたデータセットを備え、前記コントローラがさらに、前記複数のメモリシステムにわたって前記データベースの前記検索の実行を制御するよう構成された、請求項３０に記載のメモリシステム。
【請求項３６】
前記コントローラが、前記検索結果に、エラー訂正冗長性をさらに追加するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項３７】
前記コントローラは、検索結果の複製を制御するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項３８】
前記コントローラが、前記検索結果の１つ以上のレコードのフィールド内のインデックスを作成するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項３９】
前記コントローラは前記検索結果をキャッシュするようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４０】
前記コントローラが、
前記検索結果が受信されたことを示すコマンドを受信し、
前記検索結果が受信されたことを示す前記コマンドに対応して前記検索結果に関連するメモリをクリアするようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４１】
前記コントローラが、前記検索結果に関連するメモリ位置の割り当てを解除するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４２】
前記コントローラが空の場合に前記データバッファの割り当てを解除するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４３】
前記コントローラはデータ構造形式に関する情報を格納するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４４】
前記情報がフィールドの説明、データベーススキーマ、二分木情報またはグラフ構造を備える、請求項４３に記載のメモリシステム。
【請求項４５】
前記コントローラがデータ構造の前記格納のためにスペースを割り当てるようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４６】
前記コントローラが前記データベースの状態を変更し、前記データベースを作成し、前記データベース内のテーブルを作成し、前記データベース内に第１のレコードを挿入し、前記データベース内の第２のレコードを削除し、前記データベース内のテーブルを削除し、及び／または前記データベースを削除することのうち、１つ以上を実行するようさらに構成された、請求項３０に記載のメモリシステム。
【請求項４７】
複数のメモリシステムであって、各メモリシステムが、
データベースを格納するよう構成されたメモリと、
前記メモリに連結されたコントローラであって、前記コントローラは、検索要求の受信と、前記検索要求に対応して前記データベースの検索の生成と、その他の検索要求と実質的に並行する前記データベースの前記検索の実行と、前記それぞれの検索が完了したか検索結果を生成したかの何れかを示すそれぞれの検索のためのそれぞれの表示の送信と、を制御するよう構成されたコントローラと、を備え
前記複数のメモリシステムが、第１のメモリシステムが、前記検索要求が前記第１と第２のメモリシステムの両方で実行される前記第２のメモリシステムのクライアントであるように、共に連結されていることを備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権出願
本願は、２０１３年８月１３日出願の米国特許出願第１３／９６５，７３９号の利益を主張し、その全体が参照により本明細書に組み込まれる。
【背景技術】
【０００２】
メモリ装置は通常、コンピュータまたはその他の電子装置中の内部集積回路、半導体集積回路として提供されている。ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、シンクロナスダイミックランダムアクセスメモリ（ＳＤＲＡＭ）及び不揮発性（例えば、フラッシュ）メモリを含む、多くの異なる種類のメモリがある。
【０００３】
いくつかの不揮発性メモリ装置は、コンピュータシステムで機械的に操作されたハードディスクドライブをエミュレートできる、ソリッドステートドライブ（ＳＳＤ）を作るために結合され得る。ソリッドステートドライブは、可動部分がないため、機械的なハードドライブよりも信頼性が高く、より速いアクセスを可能にする。
【０００４】
コンピュータシステムの性能を少なくとも部分的に高めるために、メモリ及びソリッドステートドライブの製造業者は、コンピュータシステムの性能向上に付いて行くように、メモリの性能を高めるために常に重圧にさらされている。メモリ製造業者にとってのメモリの性能を上げる１つの方法は、メモリの読み出し／書き込みの回数を減らすことである。しかしながら、メモリ技術における進化はその努力を妨げ得る。メモリの性能を上げる別の方法は、メモリ及びＳＳＤの検索をより効率的に行うことであり得る。
【図面の簡単な説明】
【０００５】
【図１】データベース格納システムの実施形態のブロック図を示す。
【図２】図１の実施形態によるメモリシステムの実施形態のブロック図を示す。
【図３Ａ】データベース格納形式の実施形態の図を示す。
【図３Ｂ】データベース格納形式の実施形態の図を示す。
【図４Ａ】ホストとメモリ間の通信の実施形態におけるプロトコルのフローチャートを示す。
【図４Ｂ】ホストとメモリ間の通信の実施形態におけるプロトコルのフローチャートを示す。
【図５】自律的メモリ検索のための方法の実施形態における機能ブロック図を示す。
【図６Ａ】自律的メモリ検索のための方法の実施形態におけるフローチャートを示す。
【図６Ｂ】自律的メモリ検索のための方法の実施形態におけるフローチャートを示す。
【図７】多数のメモリシステムを有するシステムのブロック図を示す。
【発明を実施するための形態】
【０００６】
以下の詳細な記述において、本明細書の一部を構成する添付の図面を参照し、特定の実施形態を実例として示す。図面においては、類似の番号は、複数の図面を通して実質的に類似の部品を示す。その他の実施形態を利用することができ、本開示の範囲から逸脱することなく、構造的、論理的及び電気的な変更を行い得る。したがって、以下の発明を実施するための形態は、限定する意味で理解すべきではない。
【０００７】
説明の目的のみにソリッドステートドライブ（ＳＳＤ）を後続で参照する。本明細書で開示されるように、自律的メモリ検索の操作は、任意の形式のメモリ装置または半導体メモリ、光メモリまたは磁気メモリを含む、メモリ装置の群で等しく機能し得る。したがって、本開示は、ＳＳＤの検索に限定されるものではない。
【０００８】
構造化照会言語（ＳＱＬ）及び「ＭｙＳＱＬ」という用語もまた、後続で参照する。ＳＱＬは、当技術分野で公知であるが、リレーショナルデータベースを管理するために設計された専用プログラミング言語を意味する。「ＭｙＳＱＬ」という用語は、いくつかのデータベースに複数のユーザのアクセスを提供するサーバとして動作する純正のリレーショナルデータベース管理システムを意味する。ＭｙＳＱＬ（登録商標）データベースシステムは、しばしば構造化データベースとして特徴づけられ得る。したがって、ＳＱＬ及びＭｙＳＱＬ（登録商標）データベースへの本明細書における参照は、説明の目的のためのみである。本明細書で開示された自律的メモリ検索方法の実施形態は、構造化データ及び非構造化データを格納する、その他の種類のデータベースにおいても等しく機能し得る。例えば、キー値を格納する任意のデータベース（例えば、ＮｏＳＱＬデータベース）は、自律的メモリ検索方法を使用し得る。
【０００９】
本発明で使用する場合、構造化データは、離散的レコード（例えば、素子）にまとめられたデータであり得る。このレコードは１つ以上のフィールドから構成され得る。構造化データの例は、名前、アドレス及び識別情報に分割されたレコードである可能性がある。
【００１０】
本発明で使用する場合、非構造化データは、離散的レコード（例えば、素子）にまとめられないデータであり得る。非構造化データの例は、文書、デジタル画像または人間の音声のデジタル表示からのテキストであり得る。
【００１１】
図１は、ホスト１３０及びメモリシステム（例えば、ＳＳＤ）１０８を含むことが可能な、データベースシステムの実施形態のブロック図を示す。ホスト１３０はコンピュータシステムまたはＣＰＵであり得る。メモリシステム（例えば、ＳＳＤ）１０８は、単一の不揮発性メモリ装置または単一の装置（例えばＳＳＤ）に結合された複数の不揮発性メモリ装置であり得る。
【００１２】
ホスト１３０は、データベースシステムにおいて異なるデータベース機能を提供可能な複数のクライアント（例えば、クライアントソフトウェア、プログラム）１００を備え得る。例えば、これらのクライアント１００は、データベースのバックアップルーチン（例えば、ｍｙｓｑｌｄｕｍｐルーチン）、テーブルメンテナンスルーチン（例えば、ｍｙｓｑｌｃｈｅｃｋルーチン）、コマンドラインインタフェースルーチン（例えば、ｍｙｓｑｌｉｍｐｏｒｔルーチン）及び／またはその他のデータベース機能を含み得る。
【００１３】
クライアント１００はサーバ１０２と通信する。サーバ１０２はｍｙｓｑｌｄ（ＭｙＳＱＬサーバ）またはいくつかのその他の種類のサーバであり得る。サーバ１０２は、クライアント１００及びホスト用（例えば、中央処理装置、コンピュータ、コントローラ）のメモリシステム１０８に格納されたデータベースへのアクセスを管理するデータベースシステム中では主プログラムであり得る。
【００１４】
ストレージエンジン１０４は、サーバ１０２とホスト１３０のオペレーティングシステム（ＯＳ）ファイルシステムプロトコル１０６との間を通信する。ストレージエンジン１０４は、ホスト１３０のＯＳファイルシステム１０６を通してメモリ１０８に条件キー及び検索キーを送信し、ホスト１３０のＯＳファイルシステム１０６を通してメモリシステム１０８から検索に対する応答を受信する。検索条件及び検索キーは後で説明される。
【００１５】
典型的な従来技術のストレージエンジンは、データベースの典型的な検索をする間、メモリ内のデータベースから大量の生データを通信し得る。例えば、テーブルの何千ものレコードを含むデータベースの典型的な従来技術においては、大半または全部のレコードはＣＰＵによって処理するためにメモリからＣＰＵのメインメモリへ読み込まれる。
【００１６】
自律的メモリ検索のための方法のためのストレージエンジン１０４は、検索条件及び検索キーをメモリシステム１０８に通信し、検索条件及び検索キーを使用してデータベースの検索結果から検索結果のみを受信し得る。よって、ストレージエンジン１０４は、大量の生データをパースする必要がなく、ＣＰＵは生データに検索条件及び検索キーの比較を実行する貴重な時間を使用する必要がない可能性がある。これは、自律的メモリ検索の方法を使用するシステムの性能の向上をもたらす。これは、また、全体的な電力の節約、費用節約をもたらし、要素の利点を形成し得る。
【００１７】
メモリシステム１０８は検索されるデータベースを格納し得る任意の種類のメモリを含み得る。図２は、メモリシステム１０８（例えば、ＳＳＤ）の実施形態のブロック図を示す。例えば、複数の不揮発性メモリ装置（例えば、フラッシュメモリ）は、メモリブロック２０３を形成するために結合され得る。メモリシステム１０８（例えば、ＳＳＤ）は、メモリシステム１０８（例えばＳＳＤ）の操作を制御するために、メモリブロック２０３に連結されたコントローラ（例えば、プロセッサ）２０１を有し得る。図４から図６に記載されたプロトコル及び方法によると、コントローラ２０１は、ストレージエンジン１０４のアクティビティを命令するモジュール２１０（例えば、ファームウェアまたはソフトウェア）を備え得る。
【００１８】
図３Ａは、データベース格納形式の実施形態の図を示す。図示された実施形態において、データベースは表形式３００に格納され得る。図示されたテーブル３００は、ヘッダ３０１及び「ｎ」レコード（例えば、レコード（０）からレコード（ｎ−１））を含む。それぞれのレコードはテーブル３００の次のレコードを指すことができ、テーブル３００が次のレコードにアップデートされる場合、以前のレコードが次のレコードを指すようにアップデートされ得る。
【００１９】
ヘッダ３０１は、テーブル３００を記述するフィールドを含み得る。例えば、ヘッダ３０１は、テーブル３００中のいくつかのレコード、各レコードの長さ、レコード単位のフィールドの数、及び各フィールドの長さを含むことができる。その他の実施形態は、ヘッダ３０１に追加の記述データを含み得る。
【００２０】
データの各レコード（例えば、レコード（０）からレコード（ｎ−１）３０３は複数のフィールド（例えばフィールド（０）からフィールド（ｍ−１）を含み得る）は、検索される。各レコード３０３もまた、次のレコードにポインタフィールド３０５を含み得る。このポインタフィールド３０５は、次のレコードを含むメモリ中の別の位置の論理アドレスであり得る。したがって、メモリ内にレコードが引き続き配置される必要はない。
【００２１】
各フィールド（例えば、フィールド（０）からフィールド（ｍ−１））は、フィールドの長さ及びフィールドデータを格納する要素３０７を備え得る。フィールドデータは、検索される実データ３０９を備え得る。
【００２２】
図３Ｂは、データベース格納形式の別の実施形態を示す。本実施形態もまた、表形式３１０内にあり得る。しかしながら、図３Ａ及び図３Ｂの形式は、説明のためのみの目的である。本実施形態はどれか１つの形式、表または別の方法に限定されない。
【００２３】
テーブル３１０は、テーブルヘッダ３１２及び「ｎ」レコード群（例えばレコード群（０）からレコード群（ｎ−１））を備える。それぞれのレコード群はテーブル３００の次のレコード群を指すことができ、テーブル３１０が次のレコード群にアップデートされる場合、以前のレコード群が次のレコード群を指すようにアップデートされ得る。
【００２４】
ヘッダ３１２は、テーブル３１０を記述するフィールドを含み得る。例えば、ヘッダ３１２は、いくつかのレコード群、レコード群の長さ、いくつかのレコード、レコード単位のいくつかのフィールド、フィールドの長さ、第１レコード群のアドレス（例えば、論理アドレス、物理アドレス）及び／またはテーブルのバージョン番号を含み得る。
【００２５】
各レコード群（例えば、レコード群（０）からレコード群（ｎ−１））３１４は、「ｍ」レコード（例えばレコード（０）からレコード（ｍ−１））を含み得る。各レコード群３１４は、レコード群３１４の次のポインタ３２０及び、レコード３１６に加えて、各レコード群３１４中のいくつかのレコード３２１のためのフィールドを含み得る。このポインタ３２０は、次のレコードを含むメモリ中の別の位置の論理アドレスであり得る。したがって、メモリ内にレコード群が引き続き配置される必要はない。
【００２６】
各レコード３１６は、データの「ｋ」フィールド３１８を備え得る（例えば、フィールド（０）からフィールド（ｋ−１））。各フィールド３１８は、検索される実データを備え得る。
【００２７】
図４Ａ及び図４Ｂは、ホストとメモリシステム間の通信の２つの実施形態におけるプロトコルのフローチャートを示す。これらの実施形態は、説明の目的のためのみであり、その他の実施形態は代替的な方法を使用し得る。
【００２８】
図１を参照して前述したように、図４Ａは、自律的メモリ検索方法を使用している間のホスト（例えばＣＰＵ、コンピュータ）１３０とメモリシステム１０８間の通信のための実施形態のプロトコルのフローチャートを示す。図示された実施形態では、検索を実行するために、３つのコマンドがストレージエンジン１０４から実行され得る。例えば、ライトコマンド（例えば、スモールコンピュータシステムインタフェース（ＳＣＳＩ）のライトコマンド）の後に、２つ以上のリードコマンドが、データベース検索の結果を取得するのと同様に、検索キー及び検索条件の両方をメモリシステム１０８に転送するために使用され得る。
【００２９】
メモリシステム１０８におけるデータベースの検索は、１つ以上の検索キー（例えばパターン）、検索条件（例えば比較条件）及び検索されるデータセット（例えばデータベース）によって定義され得る。この検索は、検索キーとデータセットとを全体として、またはデータの一連のサブセットとして比較することによって実行され得る。検索条件によって限定された検索キーの比較が、少なくともデータセットの一部に一致する場合に、一致され得る。検索結果は、一致なし、１つの一致または複数の一致であり得る。
【００３０】
検索条件は「等しい」、「未満」、「超」、「等しくない」、「以下」または「以上」のような演算子を含み得る。さらに「かつ」、「または」「ではない」のような任意の論理演算子及び任意の論理演算子の組合せが単独で、またはデータベースを検索するその他の演算子との組み合わせで使用され得る。
【００３１】
初期コマンド（例えば、ＳＣＳＩライトコマンド）４０１をメモリシステム１０８に発行され、検索はホスト１３０によって開始され得る（例えば、コマンドは、図１のストレージエンジン１０４のようなストレージエンジンによって発行され得る）。初期コマンド４０１は、検索条件及び検索キーの表示を含み得る。
【００３２】
初期コマンド（例えばＳＣＳＩライトコマンド）における検索条件及び検索キーの表示は、コマンドによって暗示され、関連付けられたバッファが検索条件及び検索キーを含んでいると示すコマンドの特定のフィールドに設定されたビットであり得る。例えば、ＳＣＳＩライトコマンドでは、入ってくる論理ブロックアドレス（ＬＢＡ）の上位ビットは、バッファ内の待機検索条件及び検索キーの表示を示すために設定され得る。
【００３３】
メモリシステム１０８は、初期コマンド４０１を受信し、バッファ内の待機検索条件及び検索キーの表示を読み取る。メモリシステム１０８は、次に確認４０２とともにホスト１３０に返答する。ホスト１３０は単に、メモリシステム１０８は初期コマンド４０１を受信したと仮定することができるため、確認は、任意として考えられ得る。
【００３４】
ホスト１３０（例えば、ストレージエンジン）は、次に、検索結果を受信する準備ができていることを示すために、第２のコマンド（例えば、ＳＣＳＩリード）４０３をメモリシステム１０８に発行し得る。メモリシステム１０８が検索を完了するか、または検索結果に割り当てられた内部バッファを一杯にするまで第２のコマンド４０３は、メモリシステム１０８からの応答がない状態で未了のままであり得る。一旦、バッファが検索結果で一杯にされるか、検索がデータベースの最後まで達した場合、メモリシステム１０８は、検索が完了したことを示す応答（例えば、センスデータ）４０５をホスト１３０に発行する。この応答（例えば、センスデータ）４０５は、検索が完了した場合またはバッファが単に一杯になってバッファを空にするために読み込む必要がある場合、検索から判明した結果があれば、いくつかの結果を示すことができる。
【００３５】
メモリシステム１０８からの応答４０５がゼロ以外の数字の検索結果を示す場合には、ホスト１３０は別のコマンド（例えば、ＳＣＳＩリード）４０７を発行し、この表示に対応し、メモリシステムバッファからの結果を取得する。メモリシステム１０８は、次に、バッファからの検索結果を含み得る、別の応答（例えば、センスデータ）４０９を発行し得る。
【００３６】
ホスト１３０からの第１のリードコマンド４０３の結果が、検索がまだ完了していないことを示した場合には、ホスト１３０はこのリードステップ４０３に戻り、メモリシステム１０８から検索が完了したと表示されるまで、工程を繰り返す。
【００３７】
図１を参照して前述したように、図４Ｂは、自律的メモリ検索方法の間のホスト（例えばＣＰＵ、コンピュータ）１３０とメモリシステム１０８間の通信のための別の実施形態のプロトコルのフローチャートを示す。図示された実施形態では、検索を実行するために、３つのコマンドがストレージエンジン１０４より発行され得る。例えば、ライトコマンド（例えば、スモールコンピュータシステムインタフェース（ＳＣＳＩ）のライトコマンド）の後に、２つ以上のリードコマンドが、データベース検索の結果を取得するのと同様に、検索キー及び検索条件の両方をメモリシステム１０８に転送するために使用され得る。
【００３８】
初期コマンド（例えば、ＳＣＳＩライトコマンド）４１０がメモリシステム１０８に発行され、検索はホスト１３０によって開始され得る（例えば、コマンドは、図１のストレージエンジン１０４のようなストレージエンジンによって発行され得る）。初期コマンド４１０は、検索条件及び検索キーの表示を含み得る。
【００３９】
初期コマンド（例えばＳＣＳＩライトコマンド）における検索条件及び検索キーの表示は、コマンドによって暗示され、関連付けられたバッファが検索条件及び検索キーを含んでいると示すコマンドの特定のフィールドに設定されたビットであり得る。例えば、ＳＣＳＩライトコマンドでは、入ってくる論理ブロックアドレス（ＬＢＡ）の上位ビットは、バッファ内の待機された検索条件及び検索キーの表示を示すために設定され得る。
【００４０】
メモリシステム１０８は、初期コマンド４１０を受信し、バッファ内の待機された検索条件及び検索キーの表示を読み取る。メモリシステム１０８は、次に確認４１２とともにホスト１３０に返答し得る。ホスト１３０は単に、メモリシステム１０８は初期コマンド４１０を受信したと仮定することができるため、確認は、任意として考えられ得る。
【００４１】
メモリシステム１０８が検索を完了するか、または検索結果に割り当てられた内部バッファを一杯にするまで初期コマンド４１０は、メモリシステム１０８からの応答がない状態で未了のままであり得る。一旦、バッファが検索結果で一杯になるか、検索がデータベースの最後まで達した場合には、メモリシステム１０８は、検索が完了したこと、または検索結果のバッファが検索要求に対応して一杯であるということを示す応答（例えば、センスデータ）４１４をホスト１３０に発行する。この応答（例えば、センスデータ）４１４は、むしろ、検索が完了した場合またはバッファが単に一杯になってバッファを空にするために読み込む必要がある場合、検索から判明した結果があれば、いくつかの結果を示すことができる。
【００４２】
メモリシステム１０８は、実際の検索結果４１６（例えば、センスデータ）で応答４１４を追跡し、検索結果がゼロ以外の数と仮定する。ホスト１３０はコマンド４１８（例えば、ＳＣＳＩリードコマンド）で検索結果の正しい受信を確認し得る。
【００４３】
メモリシステム１０８は、検索に関連したバッファを破棄することができる。これはメモリシステム１０８からの応答（例えば、センスデータ）４２０によってホスト１０８に表示され得る。
【００４４】
図４Ａ及び図４Ｂに図示されたプロトコルのフローチャートでは、メモリシステム１０８は依然として正常に操作し続けることが可能である。そのため、メモリシステム１０８は、依然としてホスト１３０からの正常なリードコマンドとライトコマンドに応答することができる。
【００４５】
図５は、自律的メモリ検索のための方法の実施形態における機能ブロック図を示す。この機能ブロック図の実行は、メモリシステム１０８のコントローラ２０１によって実行され得る。
【００４６】
コマンド（例えば、検索要求、リード）は、ホストからのメモリバス（例えば、シリアルアドバンスドテクノロジーアタッチメント（ＳＡＴＡ））から受信し得る。受信されたコマンドは、コマンドの種類を決定するためにパースブロック５０１によって調べることができる。
【００４７】
受信されたコマンドが検索要求（例えば、図４のＳＣＳＩライトコマンド４０１）である場合には、検索処理スレッド５１２によって、要求ファーストインファーストアウト（ＦＩＦＯ）バッファ５０３に使用するために待機され得る。バッファ５０３は、検索キー及び検索条件を格納し得る。受信されたコマンドがパースブロック５０１によって、２つの次のコマンド（例えば、図４のＳＣＳＩリード４０３，４０７）のうちの１つであると決定された場合、これらのコマンドの表示は２つの未了要求バッファ５０５、５０６のうち１つに格納され得る。
【００４８】
継続バッファ５０５は、メモリシステムが、一旦バッファが一杯になるか、検索が完了した場合に応答するよう要求する第２のコマンド（例えば、図４のＳＣＳＩリード４０３）の表示を格納することができる。このバッファ５０５は、送信応答情報ブロック５０７に連結され、応答情報ＦＩＦＯ５０８が、検索が終了したことを示すデータを含む場合（例えば、応答ＦＩＦＯ５１０、５１１が一杯で、全体のデータベースが検索されたとき）、送信応答情報ブロック５０７は、バッファは一杯であるか、または全体のデータベースが検索されたことを示す情報応答（例えば、図４の応答４０５）をホストへとパッケージ化することができる。
【００４９】
ゲット要求バッファ５０６は、メモリシステムから検索結果を要求する第３のコマンド（例えば、図４のＳＣＳＩリード４０７）の表示を格納することができる。第２のコマンド（例えば、図４のＳＣＳＩリード４０７）がホストから受信された場合、応答送信ブロック５０９は、応答ＦＩＦＯバッファ５１０、５１１に格納された検索結果をパッケージ化し、メモリバスを介してホストにデータを送信し得るように、このバッファ５０８は、応答送信ブロック５０９に連結される。一旦、これらのバッファ５１０、５１１が空になると、表示が、検索が依然として継続する場合には、スレッド５１２はバッファ５１０、５１１を一杯にし続けることができることを、検索処理スレッド５１２に表示するために、応答バッファ自由リスト５１３に格納され得る。
【００５０】
検索処理スレッド５１２のそれぞれは、ホストから受信されたときに、別々の検索を含む。多数の異なる検索処理スレッド５１２を使用することにより、複数の別々の検索が実質的に同時に実行され得る（例えば、実質的に並行で、部分的にまたは完全に重複する）。
【００５１】
初期コマンド（例えば、図４のＳＣＳＩライト４０１）がホストから受信されたとき、検索条件及び検索キーは、検索処理スレッド５１２の１つに転送され得る。その特定の検索処理スレッド５１２は、次にデータベースのレコードテーブル（例えば、図３）に、検索条件による検索キーを格納されたレコードと比較するためにアクセス可能である。各検索処理スレッド５１２は、異なる検索条件及び検索キーを有する別々の検索を実行し得る。
【００５２】
一旦、検索処理スレッド５１２の１つがバッファ５１０、５１１のどちらかを検索の結果または検索された全データベース（例えば、検索が完了）で一杯にすると、達成されたものの表示が応答情報ＦＩＦＯ５０８に格納され得る。この表示は、バッファ５１０、５１１が単に一杯になっているかまたは検索が完了したかの情報に加えて、表示が意味する特定の検索への参照を含み得る。この表示は、次に、前述したように、送信応答情報ブロック５０７によってパッケージ化され、ホストに送信され得る。
【００５３】
図５の機能ブロックは、メモリシステム１０８の一部であることができ、メモリシステム内のコントローラ２０１によって実行され得る。機能ブロックは、ハードウェアとソフトウェア／ファームウェアモジュールとの組み合わせであり得る。そのため、多数の検索処理スレッド５１２が複数の並行検索を可能にするだけでなく、これらの検索を達成する処理は、ホスト１３０の作業負荷を低減することができるメモリシステム１０８によって実行され得る。
【００５４】
図６Ａは、自律的メモリ検索のための方法の実施形態におけるフローチャートを示す。ホストはコマンドをメモリシステムに送信（例えば、ＳＣＳＩライトコマンド、検索要求）し、検索を開始することができる６０１。このコマンドは、検索キー及び検索条件の指示を含み得る。ホストは、検索要求が受信されたというメモリシステムからの確認を受信することができる６０３。
【００５５】
ホストは、次に、コマンド（例えば、ＳＣＳＩリードコマンド）をメモリシステムに送信し、メモリシステムにホストが検索要求からの任意の結果を受信する準備ができていることを示す６０５。応答は、検索が完了した（例えば、全データベースが検索された）または検索結果のバッファが一杯であるかの何れかを示し得るメモリシステムから受信され得る６０７。
【００５６】
ホストは、次に、それらの検索結果を取得するために、コマンド（例えば、ＳＣＳＩリードコマンド）をメモリシステムに送信し、そこへメモリシステムが検索結果に応答する６０９。メモリシステムが、検索が完了していない６１１と示した場合、この方法はホストが検索結果を受信する準備ができたことを示す箇所６０５から繰り返す。検索が完了した場合には、この方法は終了する６１５。
【００５７】
図６Ｂは、自律的メモリ検索のための方法の別の実施形態におけるフローチャートを示す。任意のステップにおいて、メモリは、検索要求の前に構成され得る。例えば、転送サイズの構成（例えば、要求元／イニシエータに返信する前の全応答のサイズ）が設定されてよく、最大／最小レコード及びページサイズ（例えば、格納されたデータ構造及びメモリページのデータ構造のサイズ）が設定されてよく、物理ページ単位のいくつかのレコードが設定されてよく、多数の領域用のドライブを分割し、いくつかは従来の読み書きを支援すること、その他はデータ構成を意識する操作を支援することが設定されてよく、圧縮の存在（例えば、アルゴリズムの使用の可能／不可能）が設定されてよく、及び／または暗号化の存在（例えば、アルゴリズムの使用の可能／不可能）が設定されてよい。
【００５８】
ホストはコマンドをメモリシステムに送信（例えば、ＳＣＳＩライトコマンド、検索要求）し、検索を開始することができる６２０。このコマンドは、検索キー及び検索条件の表示を含み得る。ホストは、検索要求が取得されたというメモリシステムからの確認を取得することができる６２２。
【００５９】
メモリシステムはホストに、検索が完了または検索応答バッファが一杯であることを示す応答を発行することができる６２４。メモリシステムはこの応答を実際の検索結果に従い追跡し得る６２６。ホストは、次に、結果及びその結果は正しく受信されたという受領を確認することができる６２８。メモリシステムは、次に、検索に関連した検索結果のバッファを破棄することができる６３０。
【００６０】
別の実施形態では、メモリシステム送信及びホスト受信のステップにおいては、検索結果が存在するという表示（例えば、６０７及び６２４）は、送信された実際の結果（例えば、６０９及び６２６）のステップと組み合わせることができる。
【００６１】
図６Ａ及び図６Ｂの実施形態がホストの観点から図示されているが、当業者はこれらの実施形態はまた、メモリシステムによって実行されるような過程を示すと知っているであろう。換言すれば、ホストがメモリシステムから応答を受信すると、当業者はメモリシステムがその応答を送信したことを理解するであろう。
【００６２】
実施形態は、図２のメモリ２０３を含む、ハードウェア、ファームウェア及び／またはソフトウェアの１つまたはそれらの組み合わせで実行され得る。実施形態もまた、コンピュータで読み取り可能な記憶装置上に格納された命令として実行されてよく、本明細書で記載された操作を行う少なくとも１つのプロセッサによって読み出し、実行され得る。コンピュータで読み取り可能な記憶装置は、機械（例えば、コンピュータ）によって読み取り可能な形式で情報を格納するために、任意の非一時的機構を含み得る。例えば、コンピュータで読み取り可能な記憶装置は、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光学的記憶媒体、フラッシュメモリ装置、及びその他の記憶装置もしくは媒体を含み得る。いくつかの実施形態では、システムは、１つ以上のプロセッサを含み、コンピュータで読み取り可能な記憶装置に格納された命令で構成され得る。
【００６３】
メモリシステム１０８のコントローラ２０１は、（例えば、図３Ａ及び図３Ｂに開示されるような）検索されたデータ構造形式を認識し得る。コントローラ２０１がデータ構造を認識するために、ソフトウェア／ファームウェア２１０は、データ構造に関連する属性を含むために書き込み及び／またはアップグレードされている。コントローラは、次に、データ構造の個別フィールドをパースでき、したがって、特定のデータ構造を含む操作を実行できる。例えば、特定のデータ構造は、以前に使用されたか、またはそのデータ構造に関する情報は、コントローラ２０１によって特定のデータ構造を実際に使用する前に実行されたソフトウェア／ファームウェアに予め格納された可能性がある。この情報はデータベーステーブル、データベーススキーマ、二分木形式、グラフ構造またはデータ構造形式のメモリシステムを通知する、いくつかのその他の方法のフィールドの記述を含み得る。この情報のすべては、コントローラ２０１が、特定のデータベース形式がメモリシステムにおいて使用される場合どうなるかを知るために、コントローラのファームウェア／ソフトウェアの一部であり（またはアップデートされ）得る。
【００６４】
コントローラ２０１がデータ構造形式を認識し得る、このような操作の例として、ユーザはメモリシステム１０８に命令してアドレス０に配置されたデータベース中のリストを検索し得る。メモリシステムのコントローラは、アドレス０を見て、リストに適切な形式を見つける。コントローラのファームウェア（またはファームウェアのアップグレードを介して送信される）は、格納されたデータ構造の形式を認識できる格納されたルーチンを備える。コントローラはそこでリストの第１要素を見つけたと仮定した場合には、そのリストの構造を今、認識し（一般データとして単に扱う代わりに）、何か有意性のあるものとして異なるデータフィールドを見て関連付ける（例えば、次のリストのノード及び格納されたデータへのポインタ）。リストが検索されると、ソフトウェア／ファームウェアはコントローラに次のリストノードへのポインタをパースし、追跡し、同じやり方で次のリストノードを処理し始めることを命令する。
【００６５】
メモリシステム１０８のコントローラ２０１は、メモリシステムによってまだ使用されたことがない新しいデータ構造の格納のためのスペースをいかに割り当てるかを理解することができる。例えば、コントローラは、メモリアレイ中の格納を管理し、入ってくるコマンドのために任意のその格納を割り当てることができる。
【００６６】
メモリシステム１０８のコントローラ２０１は、データベースの状態を変更するために、（例えば、ホスト１３０からの）コマンドを理解し受け付けることができる。換言すれば、コントローラ２０１は、データベースを作成し、データベース内のテーブルを作成し、レコードを挿入し、レコードを削除し、テーブルを削除し、またはデータベースを削除するよう構成され得る。コントローラ２０１は、また、特定のデータセット上のインデックスがホスト１３０によって要求されるデータベースの状態を変更することができる。
【００６７】
メモリシステム１０８のコントローラ２０１は、第１のメモリシステムが別のデータベース有効メモリシステムに、クライアントとして動作できるように、メモリシステム１０８を制御できる。例えば、メモリシステムがＳＳＤである場合には、データベースを備えるＳＳＤは、クライアントであってよく、データベースを備える別のＳＳＤからのコマンドに応答し得る。これは、同様の検索条件及び検索キーで、その他のメモリシステムも検索する能力を１つのメモリシステムに提供し得る。
【００６８】
図７は、こうしたシステムの一例を示す。ホスト１３０は、複数のメモリシステム（例えば、ＳＳＤ）１０８，７０１，７０２に連結され、通信することができ、メモリシステム１０８，７０１，７０２のそれぞれが実質的に類似している。メモリシステム１０８，７０１，７０２は、１つのメモリシステム７０１が別のメモリシステム１０８へのクライアントであり得るように、ホスト１３０だけでなく、それら自体の間でも同様に通信することができる。
【００６９】
メモリシステム１０８のコントローラ２０１は、コントローラによって実行されるファームウェア／ソフトウェア２１０によって決定される追加の機能をも有することができる。これらの機能は、説明の目的のためのみであり、コントローラ２０１は特定の機能のみに限定されない。
【００７０】
例えば、コントローラ２０１は、確実に受信する能力を有し、ファームウェア／ソフトウェア２１０のアップデートを制御し得る。これはコントローラ２０１の能力をアップデートするために使用され得る。コントローラ２０１は、検索結果を格納し、多数の入力データ構造（例えば、ＭｙＳＱＬ（登録商標）−結合、合併及びその他のデータ加工演算のようなスタイル操作）から得られる新しいデータ構造を作成し、データ構造中の共通フィールドの比較に基づいて新しいデータ構造を作成し（例えば、ＭｙＳＱＬ（登録商標）−多数のレコード中の特定の列中の等価データの比較に基づくスタイル結合）、その他のレコードの集約関数（例えば、ＭｙＳＱＬ（登録商標）−ｃｏｕｎｔ、ｓｕｍ、ａｖｅｒａｇｅ，標準偏差及びｓｕｍ  ｉｆのようなスタイル操作）に基づいてレコード中のフィールドに値を割り当てるための新しいデータ構造を作成することが可能である。
【００７１】
コントローラ２０１は、さらにデータベースのレコードに冗長性を加える能力を有し、エラーを検出し得る（例えば、エラー訂正コード（ＥＣＣ））。例えば、コントローラ２０１は、ＥＣＣがデータベース内に格納され、またはコントローラ２０１がホストへの送信前に検索結果にＥＣＣを加えるのを制御し得るように、データがメモリに格納されたときに、ＥＣＣの追加を制御し得る。コントローラ２０１は、また、現在のレコードでエラーが検出された場合、追加のレコードを調べられるように、レコードを複製できる。
【００７２】
コントローラ２０１は、さらに、検索効率を改善するために、データベースの１つ以上のフィールド中のインデックスを作成する能力を有し得る。例えば、次の検索が、その特定のレコードが検索キー及び検索条件に合致するかどうか決定するフラグを単に探すことができるように、コントローラ２０１は各レコードの特定のフィールドにあるフラグの格納を制御できる。
【００７３】
コントローラ２０１は、さらに、メモリシステムのキャッシュの検索結果の格納を制御する能力を有し得る。このキャッシュは、検索結果のデータバッファであるか、または、メモリシステムでその他の目的に使用された別のキャッシュであり得る。
【００７４】
コントローラ２０１は、さらに、検索結果が正しく受信されたという表示（例えば、ライトコマンド）が受信されたときに、メモリ及び／または検索結果のデータバッファのクリアを制御する能力を有し得る。コントローラ２０１は、さらに検索結果を格納するために使用されたメモリ位置（例えば、キャッシュ、データバッファ、メモリ）のデアロケーションを制御し得る。
【００７５】
装置は回路、集積回路ダイ、メモリ装置、メモリアレイまたはシステムとして定義され得る。
【００７６】
結論：
自律的メモリ検索のための装置及び方法の１つ以上の実施形態は、メモリシステム（例えば、ＳＳＤ）のデータベース中の構造化または非構造化データセットの何れかの検索を実行し得る。この検索は外部ホストからの介入なしに完全にメモリシステム内で実行され得る。１つ以上の検索要求は、メモリシステム内で待機され得る。多数の検索は実質的に並行で処理され得る。多数のメモリシステム（例えば、多数のＳＳＤ）を備えるシステムにおいては、メモリシステム毎の多数の検索が待機され得る。データセットは単一のメモリシステムに常駐するか、または多数のメモリシステムにまたがうことが可能であり、単一の検索で全体のデータセットを検索され得る。
【００７７】
特定の実施形態が本明細書にて図示及び記載されているが、類似の目的を達成するために計算された任意の配列は、示された特定の実施形態と置き換えられ得ると当業者は認識するであろう。多くの適用は当業者には明白であろう。したがって、本願は、いかなる翻案または変形をも包含することを意図したものである。
【図１】
2016536694.tif 000003
【図２】
2016536694.tif 000004
【図３Ａ】
2016536694.tif 000005
【図３Ｂ】
2016536694.tif 000006
【図４Ａ】
2016536694.tif 000007
【図４Ｂ】
2016536694.tif 000008
【図５】
2016536694.tif 000009
【図６Ａ】
2016536694.tif 000010
【図６Ｂ】
2016536694.tif 000011
【図７】
2016536694.tif 000012
【国際調査報告】
2016536694.tif 000013
2016536694.tif 000014