SQL queries declaratively describe some subset of the tuples in a database, but they do not specify the method by which these tuples should be retrieved. The same SQL query can be implemented in many different ways. For example, a single-relation query can be implemented with a full table scan, with an index scan, with an index-only scan, etc. Each of these different methods of accessing tuples is called an access path, and it's the job of the query optimizer to select the most efficient access path. This paper explores how System R's query optimizer selects access paths.

#### Processing of a SQL Statement

A SQL query goes through four phases: parsing, optimization, code generation, and execution. First, the query is parsed where it is decomposed into a set of SELECT-FROM-WHERE query blocks. Then, it is optimized. The optimizer first typechecks the query against type information in the catalog. It then chooses an order to evaluate the blocks and for each block chooses an access path. Each access path is expressed in the Access Specification Language (ASL). Then, the ASL plans are compiled to machine code by a table-driven code generator that maps specific forms of joins to precompiled machine code. Subqueries are treated as subroutines. Finally, the query is ready to be executed.

#### Research Storage System

The Research Storage System (RSS) is System R's storage subsystem that is responsible for managing the physical layout and physical access of relations. Tuples are stored in 4KB pages, and pages are logically organized into segments. Tuples from different relations can share the same pages (each tuple is annotated with the id of its relation), but each relation is sequestered to a single segment. Tuples are accessed through the tuple-oriented Relation Storage Interface (RSI) which supports an OPEN/NEXT/CLOSE scan interface. The RSI supports full segment scans as well as B-tree backed index scans (including range scans). Moreover, the RSI accepts a set of search arguments or (SARGS)—a collection of predicates of the form column op value in disjunctive normal form—to filter the returned tuples. If a predicate is in the form column op value, we say it's a sargable predicate.

#### Costs for Single Relation Access Paths

System R's query optimizer tries to select an access path which minimizes cost as defined by the following formula:

```
COST = PAGE_FETCHES + w*RSI_CALLS
```

PAGE_FETCHES (the number of page fetches) is a measure of the amount of I/O a query has to perform, and RSI_CALLS (the number of calls to the RSI) is a measure of the amount of CPU a query has to perform. RSI_CALLS also approximates the number of tuples a query returns.

The System R catalog maintains the following statistics which are used by the query optimizer. They are updated periodically.

 - NCARD(T): the cardinality of relation T.
 - TCARD(T): the number of pages that hold tuples from relation T.
 - P(T): TCARD(T) divided by the number of pages in T's segment.
 - ICARD(I): The number of distinct keys in index I.
 - NINDX(I): the number of pages in index I.

The WHERE clause of a query is considered in conjunctive normal form, and each conjunct is called a boolean factor. The query optimizer estimates a selectivity factor F for each boolean factor with the following rules.

| column = value                   | F = 1 / ICARD(column index)                                                              | If there exists an index.         |
|----------------------------------|------------------------------------------------------------------------------------------|-----------------------------------|
| column = value                   | F = 1 / 10                                                                               | If there does not exist an index. |
| column1 = column2                | F = 1 / MAX(ICARD(columnn1 index), ICARD(columnn2 index))                                | If there exists two indexes.      |
| column1 = column2                | F = 1 / ICARD(columnni index)                                                            | If there exists one index.        |
| column1 = column2                | F = 1 / 10                                                                               | If there does not exist an index. |
| column > value                   | F = (high key - value) / (high key - low key)                                            | If column is arithmetic.          |
| column > value                   | F = 1/3                                                                                  | If column is not arithmetic.      |
| column BETWEEN value1 AND value2 | F = (value2 - value1) / (high key - low key)                                             | If column is not arithmetic.      |
| column BETWEEN value1 AND value2 | F = 1/4                                                                                  | If column is not arithmetic.      |
| column IN (list of values)       | F = (number of items in list) * (F for column=value)                                     | Capped at 1/2.                    |
| column IN subquery               | F = (expected cardinality of subquery result) / (product of subquery FROM cardinalities) |                                   |
| a OR b                           | F = F(a) + F(b) - F(a)*F(b)                                                              |                                   |
| a AND b                          | F = F(a)*F(b)                                                                            |                                   |
| NOT a                            | F = 1 - F(a)                                                                             |                                   |

The cardinality of query (QCARD) is the product of the sizes of the relations in the FROM clause multiplied by the selectivity factor of every boolean factor in the WHERE clause. The number of RSI calls (RSICARD) is the product of the sizes of the relations in the FROM clause multiplied by the selectivity of the sargable boolean factors.

Some access paths produce tuples in a particular order. For example, an index scan produces tuples in the order of the index key. If this order is consistent with the order of a GROUP BY or ORDER BY clause, we say it is an interesting order. The query optimizer computes the minimum cost unordered plan and the minimum cost plan for every interesting order. After taking into account the (potential) additional overhead of sorting unordered tuples for a GROUP BY or ORDER BY, the least cost plan is selected.

The following costs include the number of index pages fetched, then the number of data pages fetched, and then the number of RSI calls weighted by W.

| Unique index matching an equal predicate.                   | 1 + 1 + W                               |
|-------------------------------------------------------------|-----------------------------------------|
| Clustered index I matching one or more boolean factors.     | F(preds)*(NINDX(I) + TCARD) + W*RSICARD |
| Non-clustered index I matching one or more boolean factors. | F(preds)*(NINDX(I) + NCARD) + W*RSICARD |
| Clustered index I not matching any boolean factors          | NINDX(I) + TCARD + W*RSICARD            |
| Non-clustered index I not matching any boolean factors      | NINDX(I) + NCARD + W*RSICARD            |
| Segment scan.                                               | TCARD/P + W*RSICARD                     |

#### Access Path Selection for Joins

The System R query optimizer considers access plans with (pipelined) tuple-nested loop joins and sort-merge joins. The most critical part of choosing an access plan is choosing a join order. There are n! left-deep access plans for n relations (that's a lot). To avoid enumerating all of them, the query optimizer uses dynamic programming.

First, it determines the cheapest single-relation access path for each relation and for each interesting order. Note that interesting orders now include ordering by a GROUP BY or ORDER BY clause and any joining predicates which could take advantage of the order with a sort-merge join. Then, it determines the cheapest 2-way join with each single-relation access path as the outer relation. Then, it determines the cheapest 3-way join with the 2-way joins as the outer relation. And so on.

The query optimizer performs a couple of tricks to speed up this algorithm. First, it does not consider a cross-join if there are other more selective joins possible. Second, it computes interesting order equivalence classes to avoid computing redundant interesting orders. For example, if there are predicates E.DNO = D.DNO and D.DNO = F.DNO, then all three columns belong to the same equivalence class.

This algorithm computes at worst (2n times the number of interesting orders) intermediate access paths.

#### Nested Queries

Non-correlated subqueries are evaluated once before their parent query. Correlated subqueries are evaluated every time the parent query is evaluated. As an optimization, we can sort the parent tuples by the correlated column and compute the subquery once for every unique value of the correlated column.

## Introduction to elastic net

* Regularization and variable selection method.
* Sparse Representation
* Exihibits grouping effect.
* Prticulary useful when number of predictors (*p*) >> number of observations (*n*).
* LARS-EN algorithm to compute elastic net regularization path.

## Lasso

* Least square method with L1-penalty on regression coefficient.
* Does continuous shrinkage and automatic variable selection
 
 ### Limitations
 
 * If *p >> n*, lasso can select at most *n* variables.
 * In the case of a group of variables exhibiting high pairwise correlation, lasso doesn't care about which variable is selected.
 * If *n > p* and there is a high correlation between predictors, ridge regression outperforms lasso.

## Naive elastic net

* Least square method.
* Penalty on regression cofficients is a convex combination of lasso and ridge penalty.
* *penalty = (1−α)\*|β| + α\*|β|<sup>2</sup>* where *β* refers to the coefficient matrix.
* *α = 0* => lasso penalty
* *α = 1* => ridge penalty
* Naive elastic net can be solved by transforming to lasso on augmeneted data.
* Can be viewed as redge type shrinkage followed by lasso type thresholding.

### Limitations

* The two-stage procedure incurs double amount of shrinkage and introduces extra bias without reducing variance.

## Bridge Regression

* Generalization of lasso and ridge regression.
* Can not produce sparse solutions.

## Elastic net

* Rescaled naive elastic net coefficients to undo shrinkage.
* Retains good properties of the naive elastic net.

## Justification for scaling

* Elastic net becomes minimax optimal.
* Scaling reverses the shrinkage control introduced by ridge regression.

## LARS-EN

* Based on LARS (used to solve lasso).
* Elastic net can be transformed to lasso on augmented data so can reuse pieces of LARS algorithm.
* Use sparseness to save on computation.

## Conclusion

Elastic net performs superior to lasso.

In 1980, synchronization primitives like semaphores, monitors, and condition variables had been well studied in the literature, but there weren't any large systems implementing them. Mesa was a programming language that was being developed to write the Pilot operating system at Xerox. Due to the inherent concurrency of an operating system, Mesa was designed to ease the development of concurrent programs. The Mesa designers considered implementing a message passing interface, but deemed it too complex. They considered semaphores, but found them too undisciplined. They considered cooperative multi-threading but came upon a number of serious disadvantages:

 - Cooperative multithreading cannot take advantage of multiple cores.
 - Preemption is already required to service time-sensitive I/O devices.
 - Cooperation is at odds with modularity. Critical sections have no principled way of knowing if they are calling a function which yields control.

Eventually, Mesa settled on implementing monitors and condition variables and exposed a number of previously undiscussed issues:

 - What is the interface for dynamically spawning threads and waiting for them to terminate?
 - What is the interface for dynamically constructing monitors?
 - How are threads scheduled when waiting and notifying each other?
 - What are the semantics of wait when one monitor calls into another monitor which also calls wait?
 - How are exceptions and I/O devices handled?

Mesa allowed an arbitrary function call to be forked and run by a separate thread and eventually joined:


https://i.imgur.com/McaDktY.png

Moreover, if a forked thread was not intended to be joined, it could instead be detached via detach[p]. This fork/join style process management had a number of advantages---(i) processes were first class values, (ii) thread forking was type checked, and (iii) any procedure could be forked---but also introduced lots of opportunities for dangling references.

Monitors are objects that only allow a single thread to be executing one of its functions at any given time. They unify data, synchronization of the data, and access of the data into one lexical bundle. Mesa monitors included public entry preocedures and private internal procedures that operated with the monitor locked as well as public external procedures that operated without locking the monitor. Monitors, in conjunction with condition variables, were used to maintain an invariant about an object that was true upon entering and exiting any of the monitor's methods. Monitors also lead to potential deadlocks:

 - Two monitor methods could wait for one another.
 - Two different monitors could enter each other.
 - A monitor M could enter a monitor N, then wait on a condition that could only be enabled by another thread entering M through N.


Special care also had to be taken to avoid priority inversion.

Mesa also introduced Mesa semantics, best explained with this code snippet:

```
"""
Condition variables typically obey one of two semantics:

1. Under *Hoare semantics* [1], when a thread calls `notify` on a condition
   variable, the execution of one of the threads waiting on the condition
   variable is immediately resumed. Thus, a thread that calls `wait` can assume
   very strong invariants are held when it is awoken.
2. Under *Mesa semantics* [2], a call to `notify` is nothing more than a hint.
   Threads calling `wait` can be woken up at any time for any reason.

Understanding the distinction between Hoare and Mesa semantics can be
solidified by way of example. This program implements a concurrent queue (aka
pipe) to which data can be written and from which data can be read. It spawns a
single thread which iteratively writes data into the pipe, and it spawns
`NUM_CONSUMERS` threads that read from the pipe. The producer produces the same
number of items that the consumers consume, so if all goes well, the program
will run and terminate successfully.

Run the program; not all goes well:

    Exception in thread Thread-3:
    Traceback (most recent call last):
      File "/usr/lib/python2.7/threading.py", line 810, in __bootstrap_inner
        self.run()
      File "/usr/lib/python2.7/threading.py", line 763, in run
        self.__target(*self.__args, **self.__kwargs)
      File "hoare_mesa.py", line 66, in consume
        pipe.pop()
      File "hoare_mesa.py", line 52, in pop
        return self.xs.pop(0)
    IndexError: pop from empty list

Why? The pipe is implemented assuming Python condition variables obey Hoare
semantics. They do not. Modify the pipe's implementation assuming Mesa
semantics and re-run the program. Everything should run smoothly!

[1]: https://scholar.google.com/scholar?cluster=16665458100449755173&hl=en&as_sdt=0,5
[2]: https://scholar.google.com/scholar?cluster=492255216248422903&hl=en&as_sdt=0,5
"""

import threading

# The number of objects read from and written to the pipe.
NUM_OBJECTS = 10000

# The number of threads consuming from the pipe.
NUM_CONSUMERS = 2

# An asynchronous queue (a.k.a. pipe) that assumes (erroneously) that Python
# condition variables follow Hoare semantics.
class HoarePipe(object):
    def __init__(self):
        self.xs = []
        self.lock = threading.Lock()
        self.data_available = threading.Condition(self.lock)

    # Pop the first element from the pipe, blocking if necessary until data is
    # available.
    def pop(self):
        with self.lock:
            # This code is incorrect beacuse Python condition variables follows
            # Mesa, not Hoare, semantics. To correct the code, simply replace
            # the `if` with a `while`.
            if len(self.xs) == 0:
                self.data_available.wait()
            return self.xs.pop(0)

    # Push a value to the pipe.
    def push(self, x):
        with self.lock:
            self.xs.append(x)
            self.data_available.notify()

def produce(pipe):
    for i in range(NUM_OBJECTS):
        pipe.push(i)

def consume(pipe):
    assert NUM_OBJECTS % NUM_CONSUMERS == 0
    for i in range(NUM_OBJECTS / NUM_CONSUMERS):
        pipe.pop()

def main():
    pipe = HoarePipe()
    producer = threading.Thread(target=produce, args=(pipe,))
    consumers = [threading.Thread(target=consume, args=(pipe,))
                 for i in range(NUM_CONSUMERS)]

    producer.start()
    for consumer in consumers:
        consumer.start()

    producer.join()
    for consumer in consumers:
        consumer.join()

if __name__ == "__main__":
    main()
```

Threads waiting on a condition variable could also be awoken by a timeout, an abort, or a broadcast (e.g. notify_all).

Mesa's implementation was divided between the processor, a runtime, and the compiler. The processor was responsible for process management and scheduling. Each process was on a ready queue, monitor lock queue, condition variable queue, or fault queue. The runtime was responsible for providing the fork/join interface. The compiler performed code generation and a few static sanity checks.

Mesa was evaluated by Pilot (an OS), Violet (a distributed calendar), and Gateway (a router).

TLDR; the authors present Recurrent Memory Network. These networks use an attention mechanism (memory bank, MB) to explicitly incorporate information about preceding into the predictions at each time step. The MB is a layer that can be incorporated into any RNN, and the authors evaluate a total of 8 model variants: Optionally stacking another LSTM layer on top of the MB, optionally including a temporal matrix in the attention calcuation, and using a gating vs. linear function for the MB  output. The authors apply the model to Language Modeling tasks, achieving state of the art performance, and demonstrating that inspecting the attention weights yields intuitive insights into what the network learns: Co-occurence statistics and dependency type information. The authors also evaluate the models on a sentence completion task, achieving new state of the art.


#### Key Points

- RM: LSTM with MB as the top layer. No "horizontal" connections from MB to MB.
- RMR:  LSTM with MB and another LSTM stacked on top.
- RM with gating typically outperforms RMR.
- Memory Bank (MB): Input is current hidden state, and n preceding inputs including the current one. Attention is then calculated over the inputs based on the hidden state. The Output is a new hidden state, which can be calculated with or without gating. Optionally apply temporal bias matrix to attention calculation.
- Experiments: Hidden states and embeddings all of size 128. Memory size 15. SGD 15 epochs, halved each epoch after the forth.
- Attention Analysis (Language Model): Obviously, most attention is given to current and recent words. But long-distance dependencies are also captured, e.g. separable verbs in German. Networks also discovers dependency types.


#### Notes/Questions

- This works seems related to "Alternative structures for character-level RNNs" where the authors feed n-grams from previous words into the classification layer. The idea is to relieve the network from having to memorize these. I wonder how the approaches compare. 
- No related work section? I don't know if I like the name memory bank and the reference to Memory Networks here. I think the main idea behind Memory Networks was to reason over multiple hops. The authors here only make one hop, which is essentially just a plain attention mechanism.
- I wonder why exactly the RMR performs worse than the RM. I can't easily find an intuitive explanation for why that would be. Maybe just not enough training data?
- How did the authors arrive at their hyperparameters (128 dimensions)? 128 seems small compared to other models.

## General Framework
Really **similar to DAgger** (see [summary](https://www.shortscience.org/paper?bibtexKey=journals/corr/1011.0686&a=muntermulehitch)) but considers **cost-sensitive classification** ("some mistakes are worst than others": you should be more careful in imitating that particular action of the expert if failing in doing so incurs a large cost-to-go). By doing so they improve from DAgger's bound of $\epsilon_{class}uT$ where $u$ is the difference in cost-to-go (between the expert and one error followed by expert policy) to  $\epsilon_{class}T$ where $\epsilon_{class}$ is the error due to the lack of expressiveness of the policy class. In brief, by accounting for the effect of a mistake on the cost-to-go they remove the cost-to-go contribution to the bound (difference in the performance of the learned policy vs. expert policy) and thus have a tighter bound. In the paper they use the word "regret" for two distinct concepts which is confusing to me: one for the no-regret online learning meta-approach to IL (similar to DAgger) and another one because Aggrevate aims at minimizing the cost-to-go difference with the expert (cost-to-go difference: the sum of the cost I endured because I did not behave like the expert once = *regret*) compared to DAgger that aims at minimizing the error rate wrt. the expert.

Additionally, the paper extends the view of Imitation learning as an online learning procedure to Reinforcement Learning. 

## Assumptions
**Interactive**: you can re-query the expert and thus reach $\epsilon T$ bounds instead of $\epsilon T^2$ like with non-interactive methods (Behavioral Cloning) due to compounding error.
Additionally, one also needs a **reward/cost** that **cannot** be defined relative to the expert (no 0-1 loss wrt expert for ex.) since the cost-to-go is computed under the expert policy (would always yield 0 cost).

## Other methods
**SEARN**: does also reason about **cost-to-go but under the current policy** instead of the expert's (even if you can use the expert's in practice and thus becomes really similar to Aggrevate). SEARN uses **stochastic policies** and can be seen as an Aggrevate variant where stochastic mixing is used to solve the online learning problem instead of **Regularized-Follow-The-Leader (R-FTL)**. 

## Aggrevate - IL with cost-to-go
![](https://i.imgur.com/I1otJwV.png)

Pretty much like DAgger but one has to use a no-regret online learning algo to do **cost-sensitive** instead of regular classification. In the paper, they use the R-FTL algorithm and train the policy on all previous iterations. Indeed, using R-FTL with strongly convex loss (like the squared error) with stable batch leaner (like stochastic gradient descent) ensures the no-regret property.

In practice (to deal with infinite policy classes and knowing the cost of only a few actions per state) they reduce cost-sensitive classification to an **argmax regression problem** where they train a model to match the cost given state-action (and time if we want nonstationary policies) using the collected datapoints and the (strongly convex) squared error loss. Then, they argmin this model to know which action minimizes the cost-to-go (cost-sensitive classification). This is close to what we do for **Q-learning** (DQN or DDPG): fit a critic (Q-values) with the TD-error (instead of full rollouts cost-to-go of expert), argmax your critic to get your policy. Similarly to DQN, the way you explore the actions of which you compute the cost-to-go is important (in this paper they do uniform exploration).

**Limitations**

If the policy class is not expressive enough and cannot match the expert policy performance this algo may fail to learn a reasonable policy. Example: the task is to go for point A to point B, there exist a narrow shortcut and a safer but longer road. The expert can handle both roads so it prefers taking the shortcut. Even if the learned policy class can handle the safer road it will keep trying to use the narrow one and fail to reach the goal. This is because all the costs-to-go are computed under the expert's policy, thus ignoring the fact that they cannot be achieved by any policy of the learned policy class. 

## RL via No-Regrety Policy Iteration -- NRPI
![](https://i.imgur.com/X4ckv1u.png)

NRPI does not require an expert policy anymore but only a **state exploration distribution**. NRPI can also be preferred when no policy in the policy class can match the expert's since it allows for more exploration by considering the **cost-to-go of the current policy**. 

Here, the argmax regression equivalent problem is really similar to Q-learning (where we use sampled cost-to-go from rollouts instead of Bellman errors) but where **the cost-to-go** of the aggregate dataset corresponds to **outdated policies!** (in contrast, DQN's data is comprised of rewards instead of costs-to-go).
Yet, since R-FTL is a no-regret online learning method, the learned policy performs well under all the costs-to-go of previous iterations and the policies as well as the costs-to-go converge. 

The performance of NRPI is strongly limited to the quality of the exploration distribution. Yet if the exploration distribution is optimal, then NRPI is also optimal (the bound $T\epsilon_{regret} \rightarrow 0$ with enough online iterations). This may be a promising method for not interactive, state-only IL (if you have access to a reward).

## General limitations
Both methods are much less sample efficient than DAgger as they require costs-to-go: one full rollout for one data-point.

## Broad contribution 
Seeing iterative learning methods such as Q-learning in the light of online learning methods is insightful and yields better bounds and understanding of why some methods might work. It presents a good tool to analyze the dynamics that interleaves learning and execution (optimizing and collecting data) for the purpose of generalization. For example, the bound for NRPI can seem quite counter-intuitive to someone familiar with on-policy/off-policy distinction, indeed NRPI optimizes a policy wrt to **costs-to-go of other policies**, yet R-FTL tells us that it converges towards what we want. Additionally, it may give a practical advantage for stability as the policy is optimized with larger batches and thus as to be good across many states and many cost-to-go formulations.