We provide a procedure, based on random sampling, for estimation of the size of a query result. the procedure is sequential in that sampling terminates after a random number of steps according to a stopping rule that depends upon the observations obtained so far. enough observations are obtained so that, with a prespecified probability, the estimate differs from the true size of the query result by no more than a prespecified amount, unlike previous sequential estimation procedures for queries, our procedure is asymptotically efficient and requires no ad hoc pilot sample or a priori assumptions about data characteristic. in addition-to establishing the asymptotic properties of the esestimation procedure,we provide techniques for reducing undercoverage at small sample sizes and show that the sampling cost of the procedure can be reduced through stratified sampling techniques.