Many modern use cases of relational databases involve multi-tenancy. To allow a tenant to only access its data, relational database systems (RDBMSs) introduced row-level security (RLS). RLS enables specifying per-row access controls, which the database enforces by rewriting tenant queries to add an RLS policy filter that filters out rows the tenant is not allowed to view. Unfortunately, while RLS blocks queries from returning unauthorized data, side-effects of query execution can form a side-channel that leaks information about such secret data. This paper investigates how RLS query execution time can leak information about rows that the querying tenant is restricted from viewing. We show that in PostgreSQL and SQL Server, an attacker can craft index-using queries to learn whether a value they are not authorized to view exists in an RLS-protected table, and in some cases, how many times such a value exists in the table. Our attack succeeds in a realistic cloud setting: we successfully attack managed PostgreSQL and SQL Server database instances on AWS from virtual machines in the same and different data centers. To block the RLS time side-channel, we design a data-oblivious query scheme for the case of unique keys. We also analyze the trade-offs created by the data-oblivious approach for non-unique keys. To facilitate the evaluation of RLS attacks and defenses, we introduce a benchmark that supports multi-tenancy and RLS, which are not supported by established benchmarks such as YCSB. We implement our solution in PostgreSQL and show that it achieves security with minimal performance impact.