0

I need to perform quick searches against a combination of tags while including date ranges:

Example:

  • Users
    • who have requested notifications
    • who did not respond to a notification sent at least 3 days ago
    • and who have not been sent any other notification in the past 3 days

Data Structure

The event data structure is pretty simple:

  • Event
    • EntityId
    • EventType
    • EventName
    • Date

Normalized Database Structure Performance Concerns

  • With billions of events, doing a table scan will not work
  • The only column that would index well is Date and it will not always be included in every filter
  • EventName will not be distributed well for an index (some event names could include 1/4 of the records)
  • Doing a simple WHERE query against this normalized table would most likely require a full table scan which won't be fast enough

LIKE or Full-Text Search

Another approach is to convert these tags into a single text column one per entity.

  • EntryType_EntryName_Date_Time1, EntryType_EntryName_Date_Time2, EntryType_EntryName_Date_Time3

Then, I can do a SQL full-text search.

This would reduce the number of rows by at least 10 times, but I cannot figure out how to search by date range:

  • User
    • CONTAINS (RequestedNotifications*)
    • NOT CONTAINS (OpenNotification_ID4*) (Before 3 days ago ???)
    • NOT CONTAINS (SentNotification*) (Since 3 days ago ???)

At best, I could reduce the table and then scan a smaller partition, but I don't think it will help much.

In-Memory Solution

I have thought about creating a dedicated VM with an in-memory data structure of the entire complex data set.

Basically, I would create a dictionary for each tag type with buckets for date-time ranges and keep everything in hashtables for rapid intersections:

// Some structures like these
Dictionary<EventType, Dictionary<EventName, HashSet<int>>> nameIndex;
Dictionary<EventType, Dictionary<EventName, Dictionary<Day, HashSet<int>>>> dayIndex;
Dictionary<EventType, Dictionary<EventName, Dictionary<Day, Dictionary<Hour, HashSet<int>>>>> hourIndex;

// To search like this (kind of)
var entityIds = filters.Select(f => hourIndex[f.tagType][f.tagName][f.day][f.hour])
    .IntersectMultiple()
    .ToList();

// Note: In order to perform an operation like before 3 days
var filterResults = nameIndex[eventType][eventName].except(dayIndex[...][...][today].union(...[today-1]).union(...[today-2]));

On a dedicated server, it could handle around a billion events in-memory.

  • Each Event would require ~12 bytes (~4 bytes for each maintained index)
  • 1 Billion Events ~ 12 GB memory ~ $250/month A5 VM

This could be scaled by partioning the entities and persistence wouldn't be too difficult.

But before going that very custom route, I would like to know if there is a simpler way to do this.

Question

  • How can I structure an index so that fast searches can be performed against multiple text and date range filters as per my example?
  • What Azure solution would be the best way to solve this problem?
  • This question would most likely be a better fit at DBA.SE that Programmers.SE as it is really about query optimization. What ever you do decide to do about the queries, it will almost always be faster to use a data retrieval tool like SQL than to write your own cube and manipulation software. – Adam Zuckerman May 10 '16 at 4:43
  • Well a DB may not be the ideal solution for this. I was considering whether Azure Service Fabric or Data Lake would provide a solution. Data Lake would be ok for offline analysis but I don't think it can provide a real time solution. Service Fabric might work for partitioning the in-memory solution. However, I want to make sure the DB solution is exhausted first. – Rick Love May 11 '16 at 12:59
1

One of the methods I have used in the past to tremendously increase query performance is to pre-aggregate the data along one or more attributes (i.e., event type by day, event type by event name, etc.). This would be the equivalent of running a summation (for example) over the last month's data and storing the results in a separate table.

This will allow you to archive the transactions (each event record) into a backup table for when you need to see the actual data, but still allow for a quick-ish lookup for current data.

This technique appears to be fairly common for reporting.

You will probably want to increase period for the attribute going further into history to minimize the amount of data that you must query against for longer ranges of data. (You might only need the aggregation by monthly data beyond the last few weeks.)

  • Thanks, this has given me some ideas to think about. You are right that I don't need to segment older data as precisely, so some temporary lookup tables might help. The biggest problem is that our data has huge peaks, so we might receive 25% new data (100+ million events) in a single day. – Rick Love May 11 '16 at 13:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.