0

I'm looking for advice on how to design the data model for a project I'm working on. I'm not really sure where to ask such a question. I've been using StackOverflow for years, but this problem is a bit too abstract and theoretical for that site. I hope found the right place here.

I will first try to explain what I'm trying to solve, then describe the approach I'm thinking about and what are my sticking points. I will obfuscate the domain somewhat, out of an irrational fear of getting "scooped", but the essence of what I'm trying to do should still come across. If my explanation is unclear or insufficient, please do ask follow-up questions.

In my system I have a lot of what I'll call "facts". My guesstimate is something like 30,000-40,000. These are basically "data objects", with properties and values, for example:

{
"name": "African bush elephant",
"latin_name": "Loxodonta africana"
"max_height_m": 3.96,
"max_weight_kg": 10000,
"diet": "herbivore"
}

These "facts" represent true facts about the world, they are immutable and identical for every user of the system. Each user can import an unlimited amount of text resources, let's call them "articles". These "articles" will be scanned upon import, and each time a "mention" of a "fact" is encountered, an entity is created (or updated), let's call it "flashcard". This "flashcard" will have some metadata, but the it should be fairly lightweight, it shouldn't hold all the information from the "fact".

Crucially, there will only be one "flashcard" per "fact". So if the user has a total of 50 mentions of an elephant within 20 "articles", there won't be 50 "flashcards", but one "flashcard" linked to all 50 "mentions" in 20 "articles". This is a crucial part of my system design, as I need to be able to tell the user "You've encountered the elephant 50 different times, in 20 articles, and here are those occurrences" (again, I've obfuscated things, this makes more sense in my actual domain).

Also, crucially, the "articles" are "fact-rich", so to speak, so there will be a LOT of connections between "flashcards" and "articles". Possibly hundreds of thousands per user.

Like most application developers, (I'm assuming) I have primarily worked with SQL databases, and when it comes to data models SQL is pretty much all I know. So naturally I've tried designing the system in SQL in my head, but when I imagined the constant lookups with JOINs between the Users, Flashcards and Articles tables, I quickly realized this is simply not viable due to performance issues.

Then I learned about graph databases, and realized my data model is basically a huge, ever-expanding graph. So the current plan is to implement this using a graph database. However, being new to graph databases, their limitations, best practices, and things like possible performance bottlenecks, I' like to ask for advice regarding the details of the data model.

Right now I'm mulling over 3 different approaches to representing the "facts" and their relationships to "flashcards". Here they are:

  1. The "pure graph" approach

The "facts" and all their data are simply nodes in my graph. Each "flashcard" of each user is connected to its corresponding fact. This is the most "pure" approach in the sense that it most accurately reflects the relationships between my data. However, it also introduces connections between individual users' data. The users may share a common "knowledge base" of facts, but the actual user specific data in the system is private to each user. The users don't interact with each other's data. So it seems to me it might be a good idea for the data structure to reflect this. It would also introduce a bunch more connections in an already connection-heavy graph. Also I feel like there might be a performance hit when executing queries. It seems to me like querying should be faster if each user's data is its own island as opposed to everything being connected. Or is this a non-issue, if I start from a specific user and design my query properly?

  1. The duplicate facts approach

In this approach the facts are still nodes in the graph, but a "fact" node is generated separately for each user. (or to simplify, the "flashcard" node would hold all the data from the fact). This way the individual users' graphs don't touch, but there's a LOT of duplicate data in the system.

  1. The external facts approach

In this approach the facts don't live in the graph. Instead each "flashcard" will have a simple "fact id" property, and whenever the fact data is needed (which, relatively speaking, isn't that often) it will be retrieved by the id from something like an in-memory dictionary.

I think I like approach 3 the most, because it opens doors for further optimizations. But there may be pitfalls inherent to my chosen database paradigm that I'm not even aware of.

Any suggestions, ideas, comments or questions are welcome. As for specific technologies I'm planning to use, I'll code the thing in .NET. For database I've looked at neo4j, and so far it seems like a winner, but before I commit I'll take a good look at Azure Cosmos. If you have a different suggestion, I'm all ears (eyes).

Thank you.

3
  • 2
    Did you make any performance tests with an RDBMS for your case, are are you just guessing "it could be too slow" without actually having tried it? Guesses about performance tend to be wrong.
    – Doc Brown
    Dec 16, 2023 at 7:34
  • Is there an optional moment in the future where the facts, connection etc. would be possibly shared between users? Like a feature in which teams are working together on analyzing the data, sharing connections publicly etc? Dec 16, 2023 at 8:59
  • @LucFranken no, each user's collection of flashcards the user's level of knowledge about the domain. The more the user uses the system, the more closely the state resembles the user's actual state of knowledge. This is very unique to each user and it wouldn't make sense to share it between them.
    – Shaggydog
    Dec 16, 2023 at 9:36

1 Answer 1

5

tl;dr: Use an RDBMS, as there's nothing in the problem statement to motivate neo4j or similar graph databases.

primary key

You said you have 40,000 rows in world_fact, things that are immutably and universally true.

You have a bunch of isolated tenants / users, who can take FK references to that universe of facts. Their fact table would have PK of (userid, factid). We might find it convenient to insert 40 K ('world', factid) rows into that table for consistency -- the "world" pseudo-user knows all.

The users don't interact with each other's data.

Right, the PK addresses that.

I feel like there might be a performance hit when executing queries.

I don't feel that way. Mostly because you've not demonstrated any observed performance numbers, have not articulated any 95th percentile latency targets you need to hit. A B-tree is very good at encouraging locality of data, especially if you design the factid's so they have a sensible lexical order.

querying should be faster if each user's data is its own island

Yes. That's why userid appears first in the compound key.

flashcard

You didn't draw a useful distinction between fact and flashcard, so I'm ignoring it. That is, you told us they are 1:1 with each other, and I'm just taking them to be identical. If there's some interesting aspect of their frequency distribution or the giant size of some of their attributes, then tell us about that. A relational database, implemented as a column store, is perfectly good at projecting down to a subset of fat columns in a performant way. Presumably queries will just ask for columns they actually need. Introducing the notion of a flashcard sounds like an unmotivated premature optimization at this point.

throughput

You didn't describe your workload, nor your KPIs, nor whether lots of tenants will be querying simultaneously. If low latency is the metric you care most about, a graph database may be best for you, with the caveat that most graph nodes should be memory resident, so buy enough RAM. If high throughput is what you care about, and size of data exceeds size of RAM, you will be hard pressed to find a general purpose graph database that beats a general purpose RDBMS. Even when data is smaller than RAM, I've been able to drag results out of postgres faster than with neo4j.

If flashcards about elephants is what you care about, recommend you use a database with mature support for full text indexing.


EDIT

when I imagined the constant lookups with JOINs ... I quickly realized this is simply not viable due to performance issues.

There's no such thing as a performance "issue" if you haven't clicked a stopwatch and written down your observation.

I enclose a PoC based on your requirements which creates a 6 GiB database in less than half an hour. On an ancient 8 GiB RAM laptop.

from array import array
from hashlib import sha3_224
from pathlib import Path
from random import shuffle
from typing import Any, Callable

from sqlalchemy import Column, ForeignKey, Integer, String
from sqlalchemy.orm import Session, declarative_base
from sqlalchemy.schema import PrimaryKeyConstraint
from tqdm import tqdm
import pandas as pd
import sqlalchemy as sa

Base = declarative_base()


class WorldFact(Base):
    __tablename__ = "world_fact"
    id = Column(Integer, primary_key=True)
    name = Column(String, nullable=False)
    details = Column(String)


class Fact(Base):
    __tablename__ = "fact"
    user_id = Column(Integer)
    fact_id = Column(Integer, ForeignKey("world_fact.id"))
    PrimaryKeyConstraint(user_id, fact_id)


def create_engine():
    DB_FILE = Path("/tmp/article.db")
    DB_URL = f"sqlite:///{DB_FILE}"
    engine = sa.create_engine(DB_URL)
    return engine


# It takes 1 second to INSERT 188_000 rows into world_facts.
NUM_FACTS = 40_000
NUM_USERS = 10_000


def get_fact_df():
    return pd.DataFrame(
        {
            "name": [
                sha3_224(f"Earth {i}".encode()).hexdigest() for i in range(NUM_FACTS)
            ],
            "details": [f"Loxodonta africana {i}" for i in range(NUM_FACTS)],
        }
    )


def insert_world_facts(fact_df: pd.DataFrame) -> None:
    fact_df.to_sql("world_fact", engine, index=False, if_exists="append")


def insert_user_facts(user_df: pd.DataFrame) -> None:
    user_df.to_sql("fact", engine, index=False, if_exists="append")


def main():
    fact_df = get_fact_df()
    insert_world_facts(fact_df)

    with Session(engine) as session:
        fact_ids = array("I", [row.id for row in session.query(WorldFact.id)])

    for userid in tqdm(range(NUM_USERS)):
        shuffle(fact_ids)
        user_df = pd.DataFrame({"fact_id": fact_ids[: NUM_FACTS // 2]})
        user_df["user_id"] = userid
        insert_user_facts(user_df)


if __name__ == "__main__":
    engine = create_engine()
    Base.metadata.create_all(engine)
    main()

There were certain inconsistencies in the OP + comments specification, which I resolved by giving each user a random subset (50%) of the global knowledge base.

The PoC INSERTs 200 M rows with throughput greater than 114 K row / second, using the most basic RDBMS, sqlite, and the slowest language, python. No tuning. Go substitute a more mature NoSQL or RDBMS offering by changing the connect string, and measure the speedup.

Querying a random user is performant:

def num_facts_for(user_id: int):
    select = "count(*)"  # or "sum(fact_id)"
    with Session(engine) as session:
        yield from session.query(text(select)).filter(Fact.user_id == user_id)


def main(num_queries=1_000):
    for _ in tqdm(range(num_queries)):
        user_id = randrange(NUM_USERS)
        n, = next(num_facts_for(user_id))
        assert NUM_FACTS / 2 == n

This will COUNT() or SUM() all of a random user's 20 K fact IDs in 20 msec (fifty queries per second), due to sequential I/O against the PK.

When each random user pulls in world_fact details from a JOIN it takes just a little longer, 200 msec, due to random reads from external storage. Such random I/O is a good match for several web queries executing simultaneously, each returning sub-second interactive response latencies.

If there is a "performance issue" with hosting the proposed app atop an RDBMS, we have not yet seen such an issue revealed.


I observe a python3.11 process consuming 70 MiB of memory during each transient run when reading the DB. This is on an 8 GiB laptop with browser, PyCharm, and other interactive apps sitting on more than half the RAM. When I quit some of them to free up space for OS FS caching, then summarizing records of a thousand random users proceeds at a rate of > 120 query/sec rather than 50 query/sec. Performance of a relational database degrades gracefully as memory conditions tighten. Contrast this with performance of a graph engine like neo4j, which tends to fall off a cliff if even a small fraction of nodes turn out to not be memory resident.

7
  • I'm not sure I understand what you're getting at. Let's say I have 10,000 users, and each of them has 1000 articles and 500,000 flashcards on average (that might seem like a lot, but again, each article will contain a high number of facts. The 10k users is a stretch, especially for the beginning, but I want my solution to be scalable). That would mean a Facts table with 5,000,000,000,000 records, an Articles table with 10,000,000 records, and every time an article is loaded by a user, there has to be a JOIN over these tables.
    – Shaggydog
    Dec 16, 2023 at 9:11
  • And I don't know how many users would want to do that concurrently, but it's safe to assume there would be a number of people using the system at the same time. I just can't imagine how that would have good performance. You wrote "Their fact table would have PK of (userid, factid)." Do you mean I should create a separate Facts table for each user? That would lead to having 10,000 tables in my system. Is that even possible?
    – Shaggydog
    Dec 16, 2023 at 9:15
  • 1
    @Shaggydog I don't think J_H is advocating a separate table per user, but is pointing out that your data seems to be a very good fit for a mostly relational model, especially when using composite keys. I think your question means that each Flashcard is uniquely identified by (userid, factid), and that your largest relation would be the Mentions (article–flashcard connection). 1E4 users × 1E3 articles per user × 5E2 mentions is just 5E9 entries (not 5E12!), which will probably only take about 120GB + indices. Not nothing, but also not "big data". Joins are annoying, not inherently slow.
    – amon
    Dec 16, 2023 at 10:42
  • @amon hmm. What you're saying makes sense, but I still get the sense that doing a join over tables with millions of rows every time a user requests an article won't result in a responsive application. I just want to avoid scaling issues in the future. But I guess if performance ever becomes an issue, I can just create tables Flashacrds2, Mentions2, Articles2, and move some of my users' data into those tables.
    – Shaggydog
    Dec 16, 2023 at 15:27
  • @Shaggydog a billion-row table isn't inherently problematic. As long as you have appropriate indexes, things are going to be decently fast. You probably have a read-heavy workload, and many RDBMS support read replicas to spread the load (if you really have more queries than one server can handle). Some DBs have built-in tools for table partitioning if actually needed. Doing partitioning manually by creating multiple tables will make your queries much more painful and won't really help performance. In any case, don't plan too far ahead. Validate your ideas using simple, robust technology first.
    – amon
    Dec 17, 2023 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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