Probabilistic Many-to-Many Relationships (with Bloom Filters)(blog.zacharyvoase.com)

    CREATE INDEX ON movie_person (movie_id);
    CREATE INDEX ON movie_person (person_id);

    SELECT pg_size_pretty(pg_total_relation_size('movie_person'));
    => 45MB

    CREATE TABLE movies_people (
      movie_id INTEGER REFERENCES movie,
      person_id INTEGER REFERENCES person
    );

    EXPLAIN ANALYZE SELECT * FROM movies_for_people_junction WHERE person_id = 160;

    Hash Join  (cost=282.37..10401.08 rows=97 width=33) (actual time=7.440..64.843 rows=9 loops=1)
      Hash Cond: (movie_person.movie_id = movie.id)
      ->  Seq Scan on movie_person  (cost=0.00..10117.01 rows=97 width=8) (actual time=2.540..59.933 rows=9 loops=1)
            Filter: (person_id = 160)
      ->  Hash  (cost=233.83..233.83 rows=3883 width=29) (actual time=4.884..4.884 rows=3883 loops=1)
            Buckets: 1024  Batches: 1  Memory Usage: 233kB
            ->  Seq Scan on movie  (cost=0.00..233.83 rows=3883 width=29) (actual time=0.010..2.610 rows=3883 loops=1)
    Total runtime: 64.887 ms

    $ time sqlite3 ratings.db '
        select *
        from
          users
          natural join ratings
          natural join movies
        where user_id = 160
      ' > /dev/null

    real    0m0.006s
    user    0m0.002s
    sys     0m0.004s

    $ wget http://www.grouplens.org/system/files/ml-1m.zip
    $ unzip ml-1m.zip
    $ cd m1-1m
    $ sqlite3 ratings.db <<EOF

      CREATE TABLE movies (
          movie_id INTEGER PRIMARY KEY NOT NULL
        , title TEXT NOT NULL
        , genres TEXT NOT NULL
      );

      CREATE TABLE users (
          user_id INTEGER PRIMARY KEY NOT NULL
        , gender TEXT NOT NULL
        , age TEXT NOT NULL
        , occupation TEXT NOT NULL
        , zipcode TEXT NOT NULL
      );

      CREATE TABLE ratings (
          user_id INTEGER REFERENCES users(user_id)
        , movie_id INTEGER REFERENCES movies(movie_id)
        , rating INTEGER NOT NULL
        , timestamp INTEGER NOT NULL
        , PRIMARY KEY (user_id, movie_id)
      );

      .separator ::
      .import movies.dat movies
      .import users.dat users
      .import ratings.dat ratings

    EOF

    $ time sqlite3 ratings.db '
        select count(*)
        from
          users
          natural join ratings
          natural join movies
      ' 
    1000209

    real    0m0.953s
    user    0m0.925s
    sys     0m0.021s

    $ time sqlite3 ratings.db '
        select *
        from
          users
          natural join ratings
          natural join movies
      ' > /dev/null

    real    0m5.586s
    user    0m5.497s
    sys     0m0.059s