0

Say I have a database with 100 tables. Scattered throughout the tables are some string columns for short things that could be considered usernames/tags/categories/hashtags/addresses/placenames/other short names. Also scattered throughout are integer columns ranging from super tiny numbers like 10-50 to super BigInts like 1050. Each of these tables is mapped to a "class". So you might have some tables like this:

Table A:
Col1 Example: foobar@domain.com
Col2 Example: 15918591859185998519818595918851959158195819581951851958
Col3 Example: hello,world

Table B:
Col1 Example: 123
Col2 Example: 1235981958
Col3 Example: foo,bar,baz
Col4 Example: Hello there
Col5 Example: 958151985195818959185893852459

Table C:
Col1 Example: ABC
Col2 Example: foo,world
...

Table D:
Col1 Example: bar,world
Col2 Example: XYZ
Col3 Example: 19519581985888872578275481951958198588887257827548195195819858888725782754819519581985888872578275481951958198588887257827548

Table N:
...

What I'm wondering is how to use a trie, or some sort of data structure, to efficiently find items matching the following types of queries....

Say you first of all just create a trie for all the possible values in one global trie. So 1235981958 maps to its binary and into a trie position, and likewise foobar@domain.com maps into the same trie. These trie nodes then point to collections of items: all the records across all the tables. This would allow for searching things like "show me all records containing foo anywhere", or "show me something that looks like an email matching the \w+@\w+ pattern", or "show me all records containing integers in the 100 - 10000000000 range".

From here, you then want to filter the result set down. So say we queried for all records with foo somewhere. Now we want only the records from tables B, C, or D. If we had this global trie concept implemented, then we would end up with a collection of records from tables A, B, and C, and would then naively just iterate through all of them to filter down those containing foo.

But if you had some sort of additional trie, then perhaps you could do another trie search and avoid the filtering explosion. Wondering if anything like this is possible, or any design patterns exxist around performing complex querying and filtering like this. Maybe this falls into the category of Decision Trees and maybe there is a way to do it like that instead of tries, I would like to know. Or maybe it is considered "Tries with multiple attributes", but I haven't found anything related to that.

  • The database experience in me is cringing at the way data is stored. By restructuring your database, you can make cross-type searches more tenable. However, with a trie you have to populate it in memory and crawl it that way. – Berin Loritsch Feb 6 at 13:34
  • At first blush, you would use a Visitor Pattern (en.wikipedia.org/wiki/Visitor_pattern) to evaluate the nodes, but use the trie traversal methods to apply the visitor and evaluate the match. You can evaluate each trie sequentially, or you can apply some parallelism since read operations don't (shouldn't) mutate the trees. – Berin Loritsch Feb 6 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.