%ex1.5

\begin{enumerate}[label=(\alph*)]
% (a)
\item\begin{verbatim}
SELECT DISTINCT displayname FROM users u
WHERE id IN (SELECT owneruserid FROM posts p WHERE p.viewcount > u.views);
\end{verbatim}

Original results
\begin{verbatim}
Planning time: 0.978 ms
Execution time: 86179.847 ms
\end{verbatim}


Optimized query:
\begin{verbatim}
SELECT DISTINCT displayname FROM posts p
    JOIN users u ON p.owneruserid = u.id
    WHERE p.viewcount > u.views;
\end{verbatim}

Improvements:\\
Converted the selection to a JOIN.\\
This improves the $n_{users} + n_{users} * n_{posts}$ Seq Scans to one JOIN and two Seq Scans.

\begin{verbatim}
 Planning time: 0.960 ms
 Execution time: 37.354 ms
\end{verbatim}



% (b)
\item\begin{verbatim}
SELECT score FROM comments WHERE lower(substring(text for 3)) = 'yes';
\end{verbatim}

Original results
\begin{verbatim}
 Planning time: 0.540 ms
 Execution time: 60.946 ms
\end{verbatim}


Attempt at optimization
\begin{verbatim}
SELECT score FROM comments WHERE text ILIKE 'yes%';
\end{verbatim}


If we are allowed to create indexes
\begin{verbatim}
CREATE INDEX ON comments (lower(text) varchar_pattern_ops)
REINDEX DATABASE u00726236; VACUUM ANALYZE;
EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
SELECT score FROM comments WHERE lower(text) like 'yes%';
\end{verbatim}

Results
\begin{verbatim}
Bitmap Heap Scan on public.comments  (cost=17.71..321.40 rows=114 width=4)
                               (actual time=0.462..5.917 rows=363 loops=1)
Planning time: 0.218 ms
Execution time: 6.069 ms
\end{verbatim}



% (c)
\item\begin{verbatim}
SELECT DISTINCT postid FROM votes v
WHERE (SELECT COUNT(*) FROM votes v2
	WHERE v2.postid = v.postid AND v2.votetypeid = 2)
	 = (SELECT COUNT(*) FROM votes v2 WHERE v2.postid = v.postid);
\end{verbatim}

Original results
\begin{verbatim}
Did not terminate.
On a different machine with SSD and no time limit it took 16 minutes.
\end{verbatim}


Optimized query:
\begin{verbatim}
SELECT DISTINCT postid FROM votes WHERE postid NOT IN (
    SELECT postid FROM votes WHERE votetypeid != 2
);
\end{verbatim}

Improvements:\\
Instead of doing about twelve million Seq Scans this is now reduced to
two Seq Scans by inverting the condition.

Optimized version:
\begin{verbatim}
 Planning time: 1.093 ms
 Execution time: 81.776 ms
\end{verbatim}



% (d)
\item\begin{verbatim}
SELECT p.*, c.*, u.* FROM posts p, comments c, users u, badges b
WHERE c.postid=p.id
AND u.id=p.owneruserid
AND u.upvotes+3 >= (SELECT AVG(upvotes)
    FROM users WHERE u.creationdate > c.creationdate)
AND EXISTS (SELECT 1 FROM postlinks l WHERE l.relatedpostid > p.id)
AND u.id = b.userid
AND (b.name SIMILAR TO 'Autobiographer' OR b.name SIMILAR TO 'Supporter');
\end{verbatim}

Original results
\begin{verbatim}
Hash Join (cost=4231.28..3049237.06 rows=1494 width=1506)
    (actual time=4259.393..4405.810 rows=10 loops=1)
Planning time: 4.560 ms
Execution time: 4406.299 ms
\end{verbatim}

Improvements:

Converted the joins via WHERE clause to proper JOINs

Attempt at optimization
\begin{verbatim}
SELECT p.*, c.*, u.* FROM posts p
JOIN comments c ON (c.postid = p.id)
JOIN users u ON (u.id = p.owneruserid)
JOIN badges b ON (u.id = b.userid)
WHERE
u.upvotes+3 >=
    (SELECT AVG(upvotes) FROM users WHERE u.creationdate > c.creationdate)
AND EXISTS (SELECT 1 FROM postlinks l WHERE l.relatedpostid > p.id)
AND b.name IN ('Autobiographer','Supporter');
\end{verbatim}

Results
\begin{verbatim}
Hash Join (cost=4777.00..3352584.37 rows=1640 width=1506)
    (actual time=4189.629..4303.507 rows=10 loops=1)
Planning time: 3.739 ms
Execution time: 4303.959 ms
\end{verbatim}


Another attempt at optimization
\begin{verbatim}

SELECT p.*, c.*, u.* FROM posts p
JOIN comments c ON (p.id = c.postid)
JOIN users u ON (p.owneruserid = u.id)
JOIN badges b ON (u.id = b.userid)
WHERE
u.upvotes+3 >=
    (SELECT AVG(upvotes) FROM users WHERE u.creationdate > c.creationdate)
AND EXISTS (SELECT 1 FROM postlinks l WHERE l.relatedpostid > p.id)
AND b.name IN ('Autobiographer','Supporter');
\end{verbatim}

Results
\begin{verbatim}
Hash Join (cost=4777.00..3421794.82 rows=28452 width=1506)
    (actual time=3212.737..3330.359 rows=10 loops=1)
Planning time: 3.295 ms
Execution time: 3330.766 ms
\end{verbatim}

And move that semijoin for each post to a simple value comparison,
because ``some $x$ exists where $f(x)$ is larger than $y$'' equals ``$y < max(f(x))$'',
\begin{verbatim}
SELECT p.*, c.*, u.* FROM posts p
JOIN comments c ON p.id = c.postid
JOIN users u ON p.owneruserid = u.id
JOIN badges b on u.id = b.userid
WHERE
b.name IN ('Autobiographer','Supporter')
AND p.id < (SELECT MAX(relatedpostid) FROM postlinks)
AND u.upvotes+3 >=
    (SELECT AVG(upvotes) FROM users WHERE u.creationdate > c.creationdate);
\end{verbatim}

Results
\begin{verbatim}
Hash Join  (cost=4274.13..3221469.71 rows=28448 width=1506)
    (actual time=261.341..369.495 rows=10 loops=1)
Planning time: 4.422 ms
Execution time: 370.932 ms
\end{verbatim}

\end{enumerate}
