I have 100M users and 10M items. A database (mysql) stores which items a user has clicked. On average, a user has clicked 15 items. Each user/item has an unique id which is a long number.
This is my problem:
- Given some items, i.e: a,b,c. And logic operators between them,i.e :
a AND b NOT c
(it means: the user clicked a AND b BUT did NOT click item c)
- Return how many users satisfied.
Response time must be in a few seconds.
The result does not need 100% accurate, but with a reasonable error.
What did I try:
Use Java HashMap to store the whole data on memory, and use some Java 8 stream APIs to count. It's really fast but needs synchronize with database. And it uses a lot of memory.
So, is there any in-memory database can do this counting above? I know Redis is an in-memory database but don't know how to store my data for this counting job.
And, the result does not need to be 100% accurate, is there any data structure which fasts and does not use a lot of memory?
EDIT:
As comments suggest I should use mysql database for queries.
This is my "small" table which has ~178M rows. A very simple query that count how many users clicked on item 1 takes 7.85 seconds. It is not too slow. But it seems not easy (for me) to build a very complicated logic query like
1 AND (2 OR (3 OR 4))
mysql> DESCRIBE user_item; +---------+------------+------+-----+---------+-------+ | Field | Type | Null | Key | Default | Extra | +---------+------------+------+-----+---------+-------+ | user_id | bigint(20) | NO | PRI | NULL | | | item_id | int(11) | NO | PRI | NULL | | +---------+------------+------+-----+---------+-------+ 2 rows in set (0.00 sec) mysql> select TABLE_ROWS from information_schema.TABLES where table_name = 'user_item'; +------------+ | TABLE_ROWS | +------------+ | 178611337 | +------------+ 1 row in set (0.00 sec) mysql> SELECT COUNT(1) FROM `user_item` WHERE `item_id`=1; +----------+ | COUNT(1) | +----------+ | 33923046 | +----------+ 1 row in set (7.85 sec)