XML databases lie at the conjunction of two disparate themes and have to address issues related to both. On one hand there is the traditional database field of structured data, query languages, algebras, logical and physical plans while on the other hand is the new standard of the eXtensible Markup Language (XML) for storing and disseminating semi-structured data over the web. This paper focuses on issues involved in implementing the query engine for a native XML database. The issues of data storage, indexing, and query evaluation are discussed in relation to existing XML database systems such as Lore, XSet, and QuiXote. The query engine of MMXDB, a main memory XML database system being developed by us is also described.