uwescience/myria — pull request #609 by dhalperi (2014-08-29 06:08:19+00:00)
Title: Histogram query: be more efficient

Equivalent, but much more efficient, algorithm.

The old query (for fragment 1 of query 32305) [link: https://demo.myria.cs.washington.edu/profile?queryId=32305]. Plus explanation, on dbserver03, myria2.
```sql
myria2=> explain analyze
myria2-> SELECT p.opid, s.t AS nanotime
myria2-> FROM generate_series(0, 219642389978, 311549489) AS s(t),
myria2-> "public logs Profiling" AS p
myria2-> WHERE p.queryid=32305 AND p.fragmentid=1 AND s.t BETWEEN p.starttime AND p.endtime;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=6666.27..2091067.51 rows=13153889 width=12) (actual time=286.916..32587.185 rows=1241 loops=1)
Join Filter: ((s.t >= p.starttime) AND (s.t <= p.endtime))
-> Function Scan on generate_series s (cost=0.00..10.00 rows=1000 width=8) (actual time=0.099..0.888 rows=706 loops=1)
-> Materialize (cost=6666.27..19615.97 rows=118385 width=20) (actual time=0.044..13.720 rows=210706 loops=706)
-> Bitmap Heap Scan on "public logs Profiling" p (cost=6666.27..19024.05 rows=118385 width=20) (actual time=30.994..75.858 rows=210706 loops=1)
Recheck Cond: ((queryid = 32305) AND (fragmentid = 1))
-> Bitmap Index Scan on "public logs__myria_indexes Profiling_0_1_3_4" (cost=0.00..6636.67 rows=118385 width=0) (actual time=30.701..30.701 rows=210706 loops=1)
Index Cond: ((queryid = 32305) AND (fragmentid = 1))
Total runtime: 32591.992 ms
```

The new query

```sql
myria2=> explain analyze
myria2-> select opid, 0::bigint+311549489::bigint*s.bin as nanotime
myria2-> from
myria2-> (
myria2(> select p.opid, greatest((p.starttime-1-0::bigint)/311549489, 0) as startbin, least((p.endtime+1-0::bigint)/311549489, 705) as endbin
myria2(> from "public logs Profiling" p
myria2(> where p.queryid = 32305 and p.fragmentid = 1
myria2(> and greatest((p.starttime-0::bigint)/311549489, 0) < least((p.endtime-0::bigint)/311549489, 705) and p.starttime < (0::bigint+311549489::bigint*705) and p.endtime >= 0::bigint
myria2(> ) times,
myria2-> generate_series(0, 705) as s(bin)
myria2-> where s.bin > times.startbin and s.bin <= times.endbin;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=7234.29..1325945.54 rows=4383778 width=8) (actual time=115.714..275.708 rows=1241 loops=1)
Join Filter: ((s.bin > GREATEST((((p.starttime - 1) - 0::bigint) / 311549489), 0::bigint)) AND (s.bin <= LEAST((((p.endtime + 1) - 0::bigint) / 311549489), 705::bigint)))
-> Function Scan on generate_series s (cost=0.00..10.00 rows=1000 width=4) (actual time=0.081..0.151 rows=706 loops=1)
-> Materialize (cost=7234.28..21860.29 rows=39454 width=20) (actual time=0.051..0.186 rows=400 loops=706)
-> Bitmap Heap Scan on "public logs Profiling" p (cost=7234.28..21663.02 rows=39454 width=20) (actual time=35.856..114.967 rows=400 loops=1)
Recheck Cond: ((queryid = 32305) AND (fragmentid = 1) AND (starttime < 219642389745::bigint) AND (endtime >= 0::bigint))
Filter: (GREATEST(((starttime - 0::bigint) / 311549489), 0::bigint) < LEAST(((endtime - 0::bigint) / 311549489), 705::bigint))
-> Bitmap Index Scan on "public logs__myria_indexes Profiling_0_1_3_4" (cost=0.00..7224.42 rows=118361 width=0) (actual time=33.480..33.480 rows=210706 loops=1)
Index Cond: ((queryid = 32305) AND (fragmentid = 1) AND (starttime < 219642389745::bigint) AND (endtime >= 0::bigint))
Total runtime: 276.014 ms
```

The second query gets the exact same answer, but is about 100x faster. When deployed on Myria, the "cold" run of variant 1 takes 28s and a "hot" run takes 21s ; the "cold" run of variant 2 takes 1.4s and the "hot" run takes 0.43.

@domoritz look reasonable?