How to denormalize many-to-many relation without nested select

denormalizationmany-to-manyperformancequery-performancesqlite

I have the following schema:

house has many students, student has one house
gender has many students, student has one gender
game has many students. student has many games

For instance, consider

create table sex (type text);
insert into sex values ("wizard");
insert into sex values ("witch");

create table house (nature text);
insert into house values ("Gryffindor");
insert into house values ("Hufflepuff");
insert into house values ("Ravenclaw");
insert into house values ("Slytherin");

create table students (
  sid integer primary key autoincrement, 
  name text, 
  fk_type integer, 
  fk_house integer, 
  constraint valid_sex foreign key (fk_type) references sex (ROWID), 
  constraint valid_grade foreign key (fk_house) references house (ROWID)
);
insert into students (name, fk_house, fk_type) values ("Harry", 1, 1);
insert into students (name, fk_house, fk_type) values ("Hermione", 1, 2);
insert into students (name, fk_house, fk_type) values ("Nymphadora", 2, 2);
insert into students (name, fk_house, fk_type) values ("Cedric", 2, 1);
insert into students (name, fk_house, fk_type) values ("Bridget", 2, 2);
insert into students (name, fk_house, fk_type) values ("Lupin", 2, 1);
insert into students (name, fk_house, fk_type) values ("Salazar", 4, 2);
insert into students (name, fk_house, fk_type) values ("Yurika", 4, 2);

create table games (game text);
insert into games values ("Quidditch");
insert into games values ("Aingingien");

create table likes (
  fk_student integer, 
  fk_game integer, 
  constraint strictM2M UNIQUE (fk_game, fk_student), 
  constraint valid_student foreign key (fk_student) references students (sid), 
  constraint valid_game foreign key (fk_game) references games (ROWID)
);

insert into likes values (1, 1);
insert into likes values (2, 1);
insert into likes values (2, 2);
insert into likes values (3, 1);
insert into likes values (4, 1);
insert into likes values (5, 1);
insert into likes values (5, 2);
insert into likes values (6, 1);
insert into likes values (6, 2);
insert into likes values (7, 1);
insert into likes values (8, 1);
insert into likes values (8, 2);

Now, I want to create a view that shows student roll number, name, gender, house, and games liked. I wrote a join query

select 
  s.sid, s.name, xy.type, h.nature, l.fk_game
from 
  students s 
  inner join sex xy on s.fk_type = xy.ROWID 
  inner join house h on s.fk_house = h.ROWID 
  inner join likes l on l.fk_student = s.sid 
order by 
  l.fk_game;

But I want to see game's real names not ROWIDs, of course I can replace l.fk_game by (select game from games where ROWID = l.fk_game) but is it possible to get the same result without nested select?

Best Answer

Nothing forbids you from adding another join, to games. Then you can add the games.game column in the SELECT list:

select 
  s.sid, s.name, xy.type, h.nature, g.game
from 
  students s 
  inner join sex xy on s.fk_type = xy.ROWID 
  inner join house h on s.fk_house = h.ROWID 
  inner join likes l on l.fk_student = s.sid 
  left join games g on g.ROWID = l.fk_game
order by 
  s.sid,
  l.fk_game;

Related Solutions

Postgresql – Postgres multiple joins slow query, how to store default child record

You write:

Each customer can have multiple sites, but only one should be displayed in this list.

Yet, your query retrieves all rows. That would be a point to optimize. But you also do not define which site is to be picked.

Either way, it does not matter much here. Your EXPLAIN shows only 5026 rows for the site scan (5018 for the customer scan). So hardly any customer actually has more than one site. Did you ANALYZE your tables before running EXPLAIN?

From the numbers I see in your EXPLAIN, indexes will give you nothing for this query. Sequential table scans will be the fastest possible way. Half a second is rather slow for 5000 rows, though. Maybe your database needs some general performance tuning?

Maybe the query itself is faster, but "half a second" includes network transfer? EXPLAIN ANALYZE would tell us more.

If this query is your bottleneck, I would suggest you implement a materialized view.

After you provided more information I find that my diagnosis pretty much holds.

The query itself needs 27 ms. Not much of a problem there. "Half a second" was the kind of misunderstanding I had suspected. The slow part is the network transfer (plus ssh encoding / decoding, possibly rendering). You should only retrieve 100 rows, that would solve most of it, even if it means to execute the whole query every time.

If you go the route with a materialized view like I proposed you could add a serial number without gaps to the table plus index on it - by adding a column row_number() OVER (<your sort citeria here>) AS mv_id.

Then you can query:

SELECT *
FROM   materialized_view
WHERE  mv_id >= 2700
AND    mv_id <  2800;

This will perform very fast. LIMIT / OFFSET cannot compete, that needs to compute the whole table before it can sort and pick 100 rows.

pgAdmin timing

When you execute a query from the query tool, the message pane shows something like:

Total query runtime: 62 ms.

And the status line shows the same time. I quote pgAdmin help about that:

The status line will show how long the last query took to complete. If a dataset was returned, not only the elapsed time for server execution is displayed, but also the time to retrieve the data from the server to the Data Output page.

If you want to see the time on the server you need to use SQL EXPLAIN ANALYZE or the built in Shift + F7keyboard shortcut or Query -> Explain analyze. Then, at the bottom of the explain output you get something like this:

Total runtime: 0.269 ms

Normalizing the Test Table

The problem here is the approach. Looking at table values and guessing keys is not a way to go.

Simply write down the predicate and constraints for the table, everything else follows from this.

Here is one example. If your business rules (predicate and constraints) are different then keys are going to be different too, so table may or may not have to be decomposed.

Note:

[Px]   = predicate x
[cx.y] = constraint x.y

KEY = PK or AK

PK  = PRIMARY KEY
AKn = ALTERNATE KEY (UNIQUE)
FKn = FOREIGN KEY

[P1] Test number (TEST_ID) of test type (TEST) with total score of (TOTAL_POINTS) was administered on date (DATE) by teacher (TEACHER_ID).

[c1.1] Test is identified by test number.

[c1.2] Each test is of exactly one test type; for each test type it is possible that more than one test is of that test type.

[c1.3] Each test has exactly one total score, for each total score it is possible that more than one test has that total score.

[c1.4] Each test was administered on exactly one date; for each date it is possible that more than one test was administered on that date.

[c1.5] Each test was administered by exactly one teacher; for each teacher it is possible that more than one test was administered by that teacher.

test {TEST_ID, TEST, TOTAL_POINTS, DATE, TEACHER_ID}
 KEY {TEST_ID}

As far as the TEST column is concerned, it simply contains valid values from the domain of this attribute. You may for example add a predicate.

[P2] Test type (TEST) exists.

test_type {TEST}
      KEY {TEST}

and populate with valid domain values

test_type (TEST)
{
  ('Pronoun Quiz')
, ('Solids Quiz')
, ('China Test')
, ('Grammar Test')
}

Use this to constrain values in the test table, so it would look like this:

test {TEST_ID, TEST, TOTAL_POINTS, DATE, TEACHER_ID}
  PK {TEST_ID}
 FK1 {TEST} REFERENCES test_type {TEST}

When considering physical design, you may want to use an integer for this foreign key -- so this may look like:

test_type {TEST_TYP_ID, TEST}
       PK {TEST_TYP_ID}
       AK {TEST}


test {TEST_ID, TEST_TYP_ID, TOTAL_POINTS, DATE, TEACHER_ID}
  PK {TEST_ID}
 FK1 {TEST} REFERENCES test_type {TEST_TYP_ID}

And so on; however, without explicitly defining business rules -- in form of predicates and constraints -- everything is open to misinterpretation and endless arguing.

Best Answer

Related Solutions

Postgresql – Postgres multiple joins slow query, how to store default child record

pgAdmin timing

Normalizing the Test Table

Related Question