]> git.somenet.org - pub/jan/adbs.git/blob - ex1/main_5.tex
GITOLITE.txt
[pub/jan/adbs.git] / ex1 / main_5.tex
1 %ex1.5
2
3 \begin{enumerate}[label=(\alph*)]
4 % (a)
5 \item\begin{verbatim}
6 SELECT DISTINCT displayname FROM users u
7 WHERE id IN (SELECT owneruserid FROM posts p WHERE p.viewcount > u.views);
8 \end{verbatim}
9
10 Original results
11 \begin{verbatim}
12 Planning time: 0.978 ms
13 Execution time: 86179.847 ms
14 \end{verbatim}
15
16
17 Optimized query:
18 \begin{verbatim}
19 SELECT DISTINCT displayname FROM posts p
20     JOIN users u ON p.owneruserid = u.id
21     WHERE p.viewcount > u.views;
22 \end{verbatim}
23
24 Improvements:\\
25 Converted the selection to a JOIN.\\
26 This improves the $n_{users} + n_{users} * n_{posts}$ Seq Scans to one JOIN and two Seq Scans.
27
28 \begin{verbatim}
29  Planning time: 0.960 ms
30  Execution time: 37.354 ms
31 \end{verbatim}
32
33
34
35 % (b)
36 \item\begin{verbatim}
37 SELECT score FROM comments WHERE lower(substring(text for 3)) = 'yes';
38 \end{verbatim}
39
40 Original results
41 \begin{verbatim}
42  Planning time: 0.540 ms
43  Execution time: 60.946 ms
44 \end{verbatim}
45
46
47 Attempt at optimization
48 \begin{verbatim}
49 SELECT score FROM comments WHERE text ILIKE 'yes%';
50 \end{verbatim}
51
52
53 If we are allowed to create indexes
54 \begin{verbatim}
55 CREATE INDEX ON comments (lower(text) varchar_pattern_ops)
56 REINDEX DATABASE u00726236; VACUUM ANALYZE;
57 EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
58 SELECT score FROM comments WHERE lower(text) like 'yes%';
59 \end{verbatim}
60
61 Results
62 \begin{verbatim}
63 Bitmap Heap Scan on public.comments  (cost=17.71..321.40 rows=114 width=4)
64                                (actual time=0.462..5.917 rows=363 loops=1)
65 Planning time: 0.218 ms
66 Execution time: 6.069 ms
67 \end{verbatim}
68
69
70
71 % (c)
72 \item\begin{verbatim}
73 SELECT DISTINCT postid FROM votes v
74 WHERE (SELECT COUNT(*) FROM votes v2
75         WHERE v2.postid = v.postid AND v2.votetypeid = 2)
76          = (SELECT COUNT(*) FROM votes v2 WHERE v2.postid = v.postid);
77 \end{verbatim}
78
79 Original results
80 \begin{verbatim}
81 Did not terminate.
82 On a different machine with SSD and no time limit it took 16 minutes.
83 \end{verbatim}
84
85
86 Optimized query:
87 \begin{verbatim}
88 SELECT DISTINCT postid FROM votes WHERE postid NOT IN (
89     SELECT postid FROM votes WHERE votetypeid != 2
90 );
91 \end{verbatim}
92
93 Improvements:\\
94 Instead of doing about twelve million Seq Scans this is now reduced to
95 two Seq Scans by inverting the condition.
96
97 Optimized version:
98 \begin{verbatim}
99  Planning time: 1.093 ms
100  Execution time: 81.776 ms
101 \end{verbatim}
102
103
104
105 % (d)
106 \item\begin{verbatim}
107 SELECT p.*, c.*, u.* FROM posts p, comments c, users u, badges b
108 WHERE c.postid=p.id
109 AND u.id=p.owneruserid
110 AND u.upvotes+3 >= (SELECT AVG(upvotes)
111     FROM users WHERE u.creationdate > c.creationdate)
112 AND EXISTS (SELECT 1 FROM postlinks l WHERE l.relatedpostid > p.id)
113 AND u.id = b.userid
114 AND (b.name SIMILAR TO 'Autobiographer' OR b.name SIMILAR TO 'Supporter');
115 \end{verbatim}
116
117 Original results
118 \begin{verbatim}
119 Hash Join (cost=4231.28..3049237.06 rows=1494 width=1506)
120     (actual time=4259.393..4405.810 rows=10 loops=1)
121 Planning time: 4.560 ms
122 Execution time: 4406.299 ms
123 \end{verbatim}
124
125 Improvements:
126
127 Converted the joins via WHERE clause to proper JOINs
128
129 Attempt at optimization
130 \begin{verbatim}
131 SELECT p.*, c.*, u.* FROM posts p
132 JOIN comments c ON (c.postid = p.id)
133 JOIN users u ON (u.id = p.owneruserid)
134 JOIN badges b ON (u.id = b.userid)
135 WHERE
136 u.upvotes+3 >=
137     (SELECT AVG(upvotes) FROM users WHERE u.creationdate > c.creationdate)
138 AND EXISTS (SELECT 1 FROM postlinks l WHERE l.relatedpostid > p.id)
139 AND b.name IN ('Autobiographer','Supporter');
140 \end{verbatim}
141
142 Results
143 \begin{verbatim}
144 Hash Join (cost=4777.00..3352584.37 rows=1640 width=1506)
145     (actual time=4189.629..4303.507 rows=10 loops=1)
146 Planning time: 3.739 ms
147 Execution time: 4303.959 ms
148 \end{verbatim}
149
150
151 Another attempt at optimization
152 \begin{verbatim}
153
154 SELECT p.*, c.*, u.* FROM posts p
155 JOIN comments c ON (p.id = c.postid)
156 JOIN users u ON (p.owneruserid = u.id)
157 JOIN badges b ON (u.id = b.userid)
158 WHERE
159 u.upvotes+3 >=
160     (SELECT AVG(upvotes) FROM users WHERE u.creationdate > c.creationdate)
161 AND EXISTS (SELECT 1 FROM postlinks l WHERE l.relatedpostid > p.id)
162 AND b.name IN ('Autobiographer','Supporter');
163 \end{verbatim}
164
165 Results
166 \begin{verbatim}
167 Hash Join (cost=4777.00..3421794.82 rows=28452 width=1506)
168     (actual time=3212.737..3330.359 rows=10 loops=1)
169 Planning time: 3.295 ms
170 Execution time: 3330.766 ms
171 \end{verbatim}
172
173 And move that semijoin for each post to a simple value comparison,
174 because ``some $x$ exists where $f(x)$ is larger than $y$'' equals ``$y < max(f(x))$'',
175 \begin{verbatim}
176 SELECT p.*, c.*, u.* FROM posts p
177 JOIN comments c ON p.id = c.postid
178 JOIN users u ON p.owneruserid = u.id
179 JOIN badges b on u.id = b.userid
180 WHERE
181 b.name IN ('Autobiographer','Supporter')
182 AND p.id < (SELECT MAX(relatedpostid) FROM postlinks)
183 AND u.upvotes+3 >=
184     (SELECT AVG(upvotes) FROM users WHERE u.creationdate > c.creationdate);
185 \end{verbatim}
186
187 Results
188 \begin{verbatim}
189 Hash Join  (cost=4274.13..3221469.71 rows=28448 width=1506)
190     (actual time=261.341..369.495 rows=10 loops=1)
191 Planning time: 4.422 ms
192 Execution time: 370.932 ms
193 \end{verbatim}
194
195 \end{enumerate}