groonga - An open-source fulltext search engine and column store.

4.8. Prefix search with patricia trie

Groonga supports to create a table with patricia trie option. By specifying it, You can do prefix search.

And more, you can do suffix search against primary key by specifying additional option.

4.8.1. Prefix search by primary key

table_create command which uses TABLE_PAT_KEY for flags option supports prefix search by primary key.

Execution example:

table_create --name PatPrefix --flags TABLE_PAT_KEY --key_type ShortText
# [[0, 1337566253.89858, 0.000355720520019531], true]
load --table PatPrefix
[
{"_key":"James"}
{"_key":"Jason"}
{"_key":"Jennifer"},
{"_key":"Jeff"},
{"_key":"John"},
{"_key":"Joseph"},
]
# [[0, 1337566253.89858, 0.000355720520019531], 6]
select --table PatPrefix --query _key:^Je
# [
#   [
#     0,
#     1337566253.89858,
#     0.000355720520019531
#   ],
#   [
#     [
#       [
#         2
#       ],
#       [
#         [
#           "_id",
#           "UInt32"
#         ],
#         [
#           "_key",
#           "ShortText"
#         ]
#       ],
#       [
#         3,
#         "Jennifer"
#       ],
#       [
#         4,
#         "Jeff"
#       ]
#     ]
#   ]
# ]

4.8.2. 主キーによる後方一致検索

table_createコマンドのflagsオプションにTABLE_PAT_KEYとKEY_WITH_SISを指定することで、主キーによる前方一致検索・後方一致検索の両方が可能となります。

KEY_WITH_SISフラグを付与すると、データを追加する際に後方一致用のレコードも追加されてしまいます。そのため、単純に検索すると、元のレコードに加えて自動的に追加されたレコードまでヒットしてしまいます。元のレコードのみ検索するために、一工夫必要になります。

例えば、元のレコードと自動的に追加されたレコードとの区別をつけるために、元のレコードであることを示すoriginalカラムを追加して、検索時にはoriginalカラムが true も検索条件に加えます。 --query オプションでは Bool 型の値を直感的に指定することができないので --filter オプションを使っていることに注意してください。

Execution example:

table_create --name PatSuffix --flags TABLE_PAT_KEY|KEY_WITH_SIS --key_type ShortText
# [[0, 1337566253.89858, 0.000355720520019531], true]
column_create --table PatSuffix --name original --type Bool
# [[0, 1337566253.89858, 0.000355720520019531], true]
load --table PatSuffix
[
{"_key":"ひろゆき","original":true},
{"_key":"まろゆき","original":true},
{"_key":"ひろあき","original":true},
{"_key":"ゆきひろ","original":true}
]
# [[0, 1337566253.89858, 0.000355720520019531], 4]
select --table PatSuffix --query _key:$ゆき
# [
#   [
#     0,
#     1337566253.89858,
#     0.000355720520019531
#   ],
#   [
#     [
#       [
#         4
#       ],
#       [
#         [
#           "_id",
#           "UInt32"
#         ],
#         [
#           "_key",
#           "ShortText"
#         ],
#         [
#           "original",
#           "Bool"
#         ]
#       ],
#       [
#         3,
#         "ゆき",
#         false
#       ],
#       [
#         2,
#         "ろゆき",
#         false
#       ],
#       [
#         5,
#         "まろゆき",
#         true
#       ],
#       [
#         1,
#         "ひろゆき",
#         true
#       ]
#     ]
#   ]
# ]
select --table PatSuffix --filter '_key @$ "ゆき" && original == true'
# [
#   [
#     0,
#     1337566253.89858,
#     0.000355720520019531
#   ],
#   [
#     [
#       [
#         2
#       ],
#       [
#         [
#           "_id",
#           "UInt32"
#         ],
#         [
#           "_key",
#           "ShortText"
#         ],
#         [
#           "original",
#           "Bool"
#         ]
#       ],
#       [
#         5,
#         "まろゆき",
#         true
#       ],
#       [
#         1,
#         "ひろゆき",
#         true
#       ]
#     ]
#   ]
# ]