The base of foundations of Venice are not masonry, but rather wooden pilings.

Pilings were driven into the clay and then limestone masonry built on top near the waterline. Wood in salt water is surprising durable. The anaerobic environment does not allow organisms that cause rot to survive.

Boston's Back Bay neighborhood is similar. It was built on the former tidal flats and the groundwater levels are carefully controlled because if the wood is allowed to dry out, then fungus can take hold and the piling must be replaced.

You ask specifically about the Venetians, but you also ask more generally about underwater masonry. You might be interested in the Roman architect Vitruvius, particularly Book V, Chapter 12, in which he discusses underwater construction. The Romans had quite good underwater concrete. Vitruvius knows how to mix it with particular volcanic powder so that it will work underwater.